Educational project chess and artificial intelligence. Towards Deep Blue: A Step-by-Step Guide to Creating a Simple AI for Playing Chess

The match is lost: the computer against the person.

Creative thinking, logic, experience are the qualities that allowed a person to lead in the “man-machine” fight. It seemed that these advantages will always be the secret weapon of man, and the computer will play the role of "catching up".

But it took quite a bit of time for artificial intelligence to catch up and forever surpass humans in many areas, including in the field of intellectual entertainment.

Artificial intelligence beat man: where and how

Rubik's Cube
This puzzle is known all over the world. Millions of people are trying to complete the task and collect the cube correctly, and some even compete in the speed of assembly. The human record was set by 14-year-old Lucas Etter from the United States, who solves the puzzle in 4.904 seconds. Incredible, isn't it? But this result was surpassed by the robot, which was created by two enthusiasts Jay Flatland and Paul Rose: the result of the robot is 1.047 seconds.

Thanks to the built-in cameras, and there are four of them, the computer evaluates the position and selects the best algorithm of actions. The system is based on the Kotzebue formula (assembly in 20 moves). Hardly any of the people will be able to solve the Rubik's cube faster than 1 second.
0:1 in favor of artificial intelligence.

"Othello"
The peak of popularity of this game falls on the beginning of the 70s of the last century. The essence of the game is to place chips on the playing field (8 × 8 cells): you need to block the rows of opponent's chips on both sides with chips of your color, then the chips change color and go to the opponent. Victory goes to the one who occupies the largest area.

In 1980, Hiroshi Inouye was the Othello World Champion and easily defeated the Moor program 5-1.
Later, the programs learned to calculate the opponent's moves (by about 25 moves), and when the reigning world champion Takeshi Murakami met in a rematch with the Logistello system in 1997, the score was a crushing 0:6 in favor of the software.

Backgammon
Artificial intelligence owes its advantage in backgammon over humans to the world correspondence chess champion (and there are such) Hans Berliner, who wrote the BKG 9.8 program. And in 1979, the program turned out to be stronger than the world backgammon champion Luigi Villa.

It is believed that in that game the computer was lucky (good dice fell out several times), but no one else wanted to fight in a repeated rematch, especially since the software has been repeatedly improved since that time.

Chess
Chess systems began to develop in the middle of the twentieth century, the development belonged to IBM. But due to the fact that the program required serious and lengthy calculations, this venture had to be postponed for 30 years. In 1996, Garry Kasparov was put up against the "chess brain" - the Deep Blue computer.

The match ended in favor of the man: 3 wins, 2 draws, 1 loss. A year later, the match was repeated, and this time Deep Blue was more prepared. Still, the system evaluated 200 million positions per second. And although Harry wanted to recoup later, IBM refused, considering it pointless.

Checkers (a kind of checkers)
Marion Tinsley was the Checkers Champion throughout his career. And when in 1992 he met with a system developed at the University of Alberta (Canada), the victory was his. Out of 39 games - 4 wins, 2 losses and 33 draws.

After 2 years, a revenge took place, but Tinsley withdrew from the competition due to health problems (at the time of the refusal there were 6 draw games), and the victory went to the system. Since that moment, artificial intelligence has become much stronger: in 2007, the Canadians announced the creation of an ideal system, and no one from people is trying to surpass it in checkers.

Scrabble
The triumph of the computer in this game was easy even in the very first round: the world champion David Boyce was beaten in 2006 by the robo-rival Quackle.

By the way, this program is available on the Web, and you can measure your strength with it, and maybe you will bring victory to the "Man" team.

Go
This game appeared in ancient China more than two thousand years ago, but despite such a long experience in the game, people still lost. On the court (19 × 19) two players place their stones (black / white), whoever scores more points (chips are counted in a line) wins. On the one hand, everything is simple, but the interest lies in the variety of possible options and moves.

It was also interesting for the developers of AlphaGo (created under the auspices of Google) to create a system that can calculate thousands of options. At first, artificial intelligence tried its hand with other software, and when out of 500 games 499 were for AlphaGo, it took on the three-time European champion Fan Hui. The champion had no chance: 5:0.

TV
Do you like answering questions on quiz shows? The developers of the Watson robot from IBM also could not resist, and in 2011 Watson acted as a participant in the Jeopardy! Despite the fact that his opponents were the record holders of the show - Brad Rutter and Ken Jennings - he won, and the million dollars won were donated to charity.

And although the computer has already shown its intellectual and logical superiority over humans, it continues to develop. So Alibaba Group and Microsoft (developments were carried out in parallel) introduced artificial intelligence, which turned out to be stronger than a person in understanding the information read.
The Stanford University test is more than 100,000 questions based on five hundred articles from the Wikipedia library.

The best indicator for a person is 82.304 points, the result of Alibaba is 82.44, the Microsoft neural network is 82.605. the results indicate that artificial intelligence is able to answer any questions with high accuracy, which means that technologies can be used to serve customers, patients, museum visitors, etc.

Computer games were also subdued by the program. The program won the program: who would have thought that this future is so close? The popular game Quake III, where the players are gladiators, is very popular in eSports. But the best here were not people, but the DeepMind bot team, created by a division of Google. And although the battle was held in a truncated version, according to calculations, with a 73% variance, the bot would win in any competition.

Is such superiority of artificial intelligence dangerous or not? Nobody can answer for sure. And in the end, this answer will not be the key, because the main thing is not the fact that a person is inferior to a computer, but whether we can use this potential for our own benefit. As we can see, artificial intelligence beats a person and leaves no chance of winning.

The history of the development of automation and computer technology is strangely connected with chess. In the XVIII century. "thinking" chess automata were used for tricks and hoaxes. The first apparatus with real artificial intelligence, created in Spain at the beginning of the 20th century, was able to checkmate a chess player with a king and a rook. Apparently, it is no coincidence that one of the first truly intelligent tasks assigned to programmers at the dawn of computing was the game of chess. One of those who created the first chess programs, Doctor of Technical Sciences, Professor Vladimir Lvovich Arlazarov, talks about chess programs and the connection of this ancient game with the development of artificial intelligence technologies.

– Vladimir Lvovich, how did you come to the idea that a computer can solve intellectual problems?

- When it was found out that computers can not only calculate, as it was invented from the very beginning, that behind arithmetic operations there is a logical operation that not only performs auxiliary functions in the activities of computing programs, but also with the help of which it is possible to solve independent problems, it became clear: it is worth trying to put intellectual tasks on the computer. Somewhere from the end of the 40s to the end of the 50s, this was actively discussed, moreover, semi-philosophical questions were posed: maybe computers will be smarter than people? And then what? And all in all seriousness. Now such questions are not raised, after all, 40 years have passed. Then, at the dawn of computing, we only realized what machines could do in principle. We realized that the human brain is a device similar to a computer, and a thousand, a million times more powerful, but it is fundamentally a little different. It became clear that at least most of the rational problems that a person solves can be put before a machine. Therefore, you can try to write programs that solve these problems. One, two, a thousand ... after all, a person also solves not an infinite number of problems. And it is possible, so to speak, to program all the intellectual activity of a person.

– And why did you decide to turn to the game?

“As I said, there has been a lot of discussion about whether a machine can think. However, it is quite clear that if we are talking about programmers, about people who do not deal with philosophy, but with a real computer, then the question is not whether a machine can fundamentally do something, but in the search for examples of where machines decide intellectual tasks, and those that are accessible to a person in his intellectual activity. The line here, of course, is not clear. But it is clear that if a person multiplies 20-digit numbers, then he does not deal with a deeply intellectual task, since it is very easy to find a trivial algorithm for its implementation, which is known to every schoolchild. But those tasks where it is absolutely clear that a person does not have any a priori algorithm, but he nevertheless solves them well, we will call intellectual. The first contenders for the role of such tasks are games, for the simple reason that at least the rules are clearly formulated. The task is extremely difficult, and the rules of the game are easy to formulate, and thus it is easy to determine the functions of the machine. On the other hand, chess is a difficult task for a person, which somehow has never been discussed and is not being discussed now.

- And why did you choose chess from the games? Maybe a tradition?

Why only chess? We also tried cross movies and other games. But chess has many advantages over other games. If in simple games a machine beats a person, then this does not surprise anyone. Chess is a difficult game, and the victory of the computer is significant here. Then in chess, unlike a number of other games, there are many differentiable quality criteria, that is, one can determine: the machine plays well, the machine plays better, better, better. In many other games, such gradations are very difficult to establish. In some of them, the machine is either taught to play absolutely accurately, and thus all interest in the game is immediately lost, or it plays very badly. And in chess, not abstract, but, so to speak, mastered, there are so many levels that with their help it is possible to determine the class of the machine's game.

– So, it is clear why chess was one of the first and most important tasks of artificial intelligence. What methods were used to solve it?

– From the very beginning, the technique of solving the problem of a chess game was gradually mastered. In principle, chess is a finite game, and with mathematical rigor it can be proved that in any position there is an abstract best move for each of the opponents, and hence some result. Therefore, it is necessary to describe an algorithm in which this game can be calculated to the end. The only disadvantage of this algorithm is that it takes a long time. And we have not come close to those orders of time that are needed to calculate, say, chess to the end from the initial position. Over the past fifty years, the task in terms of time has remained infinitely complex. Well, infinity minus ten is still infinity. But if you need time, say, 10 to the 100th power of years, and you speed up the car, say, 100 times, and get 10 to the 98th power of years, then this is unlikely to make you feel better. Therefore, the main algorithm is exhaustive, trivial: if I go this way, then the enemy has so many possibilities. The options grow exponentially and form chains. But the number of positions is generally finite, and there are not so many of them on each chain. Chains are combined into trees, which again are not infinite. True, they grow exponentially, and the number of chains increases. So, an important question arises: do we need a complete, to the very end, enumeration - to all mats, stalemates, triple repetitions and other endings of the game according to chess rules? After all, if the algorithm leads to positions that are not required on this tree, then perhaps this entire tree does not need to be considered. Notice to yourself that in a disposition where White checkmates in one move, you can build the same infinite tree, but you don’t need to consider it, but it’s enough to find this one and only move. Maybe the situation is the same in chess in general? In general, the algorithm of enumeration, enumeration of options is related to so many tasks solved by a person that if we could organize it in some very original way, then it would, in a sense, be like the invention of a wheel for humanity - one of fundamental discoveries. So, enumeration could be, and maybe it is, the wheel of artificial intelligence.

- In one of the articles about artificial intelligence, I read that intelligence is the ability to understand and choose. Naturally, it is very difficult to teach a computer to choose from a variety of options. But surely some solutions specific to chess are possible?

- Yes Yes. This problem had to be solved quickly and efficiently, and in chess they quickly came to the following theoretical formulation of the question: let's look not at an infinite number of moves, but only a few moves ahead. Let's say we look 5 moves ahead. This is a lot. If you love chess and 5 moves seems not enough for you, then let's take 10. And then the machine for 10 moves, 20 half-moves ahead will not make mistakes in anything and guarantees that after 10 moves you will have no fewer pieces. It is clear that we are dealing with a strong playing machine. So the game tree will have to be reduced and the problem solved in a much more limited space. Another question is that they try to consider this tree not completely, with the help of mathematical pruning methods. I already talked about one of them: if there is a checkmate in one move, there is no need to look at other options. Other algorithms are heuristic, not exact. On average, they work correctly, many are absolutely accurate, but they can be wrong. For example, we can go through not all the moves, but only the capture, and calculate them much ahead, because there are few captures. The overall depth of the moves is small: you can't eat more than thirty-two pieces. Therefore, the lengths of the chains are small and there are few branches. Of course, it is clear that one cannot build a game on captures alone, there must be some positional considerations. The combination of forcing (capture, check) and positional considerations, as well as a certain depth of enumeration, is the basis of all existing algorithms, and it does not change much. Another question: how to select those moves that I will consider further? Is it based only on simple formal criteria (capture, check) or is it to link these moves, as chess players like to say, with a plan, to come up with some kind of chains that have some kind of common property? In any case, a lot of serious works with practical application have been written about this. It is not for nothing that rather reputable companies are engaged in the creation of chess programs.

– And when did the first chess programs appear?

- Real chess programs first appeared somewhere in the late 50s in America, and then somewhere in the early 60s - in our country. The programs were very weak, because then there were both extremely primitive machines and our thinking, which was not yet accustomed to novelty. We got involved in this business around 1963. Then on our domestic cars there were some matches. In my opinion, in 1967 there was the first match between the USSR and the USA. It was called that, although, of course, it took place between two teams, and not countries. It was a match between our program, developed at the Institute of Theoretical and Experimental Physics, and the program of John McCarthy, a very famous person in the computer world, one of the creators of programming languages, who was then fond of chess programs. The moves were transmitted by telegraph, because then there were no networks.

- And who won?

– We then won 3:1. Played 4 games. A move was made a day, because the Americans had more powerful and deep programs that thought for a long time, and we played on different versions of programs that thought both quickly and slowly. Our win was our first achievement. This direction began to develop gradually and became especially active in the 70s. Around 1974, the first World Chess Championship was held in Stockholm. About eight programs participated, including ours. And then we also won and became the first world champions. Since then, World Championships have been held regularly, every 3 years. We participated in them 2 more times - in 1977 and in 1980. We did not win Lavrov then, because in 1977 we shared the 2nd and 3rd places (many chess programs participated, there were even regional selections), and in 1980 - 4th and 5th place. In general, they slowly rolled back. The fact is that by this time there was already a huge progress in computing, and we were still playing on computers that were rather outdated. And by 1980, it became clear to us that competing on the machines on which we work had lost all meaning, and in general, work in the field of chess programs began to come to naught in Russia. Although there were quite a lot of interesting theoretical works. A little later, they created the first, perhaps, program that went around the world, she knew how to absolutely accurately play a complex endgame, that is, a queen and a pawn against a queen, or a rook and a pawn against a rook. The program simply considered such endgames to the end, i.e. in any position it gave an ideally correct move. The algorithm was built on principles slightly different from simple enumeration, on a complete inspection of the entire set of positions. Well, and then some works of this nature were made in chess. And then we said goodbye to the practical game, because the differences in speeds were already hundreds of times. But the championships continued, and the development of chess programs moved to a whole new level, as soon as everything moved to the PC. As a result of widespread commercialization, huge amounts of money began to be invested in chess programs, everything was immediately classified. And earlier they belonged to scientists who, if not forced on purpose, do not hide their achievements, but, on the contrary, propagate them. In 1980, we felt for the first time that it was time for commercial programming. This world is, of course, unique. Firstly, because money is invested in it, and secondly, because money is extracted from it. Although there are magazines on chess programs, but in the last 15 - 17 years, the real exchange of ideas has greatly diminished, because on the PC they have become a huge business.

– But commerce stimulates the development of the chess software market, doesn't it?

- Previously, computer competitions were timed to coincide with computer technology forums. There is such an organization - IFI (International Federation for Informatics) and, usually, world championships were timed to coincide with its congress. Now they have become absolutely independent events, quite prestigious. There are hundreds and hundreds of such programs. The very level of programming and the level of our knowledge is already such that it is not the slightest difficulty to make a simple chess program. This is normal student work. I just entrust it to some student. Beating a chess program has become, so to speak, a commonplace.

– But, as always, the lower level becomes simpler, while the higher one becomes more complicated?

- That's it. Therefore, the latest programs, those that are now winning, in particular, the program that defeated Kasparov, have become much stronger. The search depth has grown significantly and, of course, this is the result of our mathematical advances, and partly just the progress of computer technology. After all, if earlier consideration of 1000 positions per second was considered a lot, now in those trees that we have already talked about, more than a million positions are considered. And an extra million is several levels of moves with the right selection. And each level of search depth greatly enhances the program. Each level one move forward is approximately a rank, and, say, a search depth of four moves is the third rank, and five moves is already the second rank. When we reach the level of 11–13 moves, this is a master level and it is quite difficult to play with the machine further. Of course, the Americans are now leading, because they know how to invest big money in such things.

– Any artificial intelligence program for decision-making needs not only heuristic mechanisms, but also some kind of knowledge base. What is the relationship between the knowledge base and algorithms that generate positions in chess programs?

- No one can say for sure, because this is a subject of speculation. There were programs strong enough with just minimal knowledge, deliberately minimal, specifically to see what could be squeezed out of pure mathematics. At some point, this was due to commercialization, and especially to the fact that they began to make the most powerful programs - it doesn’t matter at the expense of what. But partly due to the fact that working with embedded knowledge is an independent task, there are a lot of them. First of all, a huge directory was created. Now directories are hundreds of thousands of positions. Then a lot of chess intelligence is always invested in evaluating positions. It comes down, of course, to game material, which is trivial, and to some positional factors. So, positional factors are purely chess intelligence, which, of course, is programmed, but here a lot of it is laid down and it is constantly being improved. And the more factors are invested there, the stronger the program. In a sense, the ability to evaluate the position and the depth of enumeration are interchangeable things. If we were able to evaluate the position ingeniously, then it would be enough for us to try all the first moves. This is like an extreme example. It is clear that a better position estimate has a correspondingly greater effect on the search depth. This is the second, fundamental method. There are quite a few programs where chess intellect is embedded in the choice of the options under consideration, that is, some purely chess considerations, some plans. There are quite a few such considerations, which limits the range of enumeration. The scope of their action is not very wide, and intellectual-chess-specific data slows down enumeration. By the way, it was precisely for intellectual things that Botvinnik once advocated very strongly. He was a great enthusiast of machine chess and contributed some ideas to it. Although he never managed to create a working program, nevertheless, his authority was then very high. So, he was very upset that, in general, the direction was not as "intellectual" as he would like, and a very limited amount of purely chess knowledge was invested in the programs.

– What about specialized chess computers? They, apparently, act precisely by the method of generation?

- Of course of course. First, in the sense of generation, enumeration is schematic. Secondly, any tables of positions are no less important, because in chess the repetition of positions is very high. You go E4E6D4 or D4E6E4 - the position will be the same, and it's only 3 half-moves. And when we start to go deeper, the repeatability of positions is very high. Thirdly, the technical area. In fact, at one time we built theories about for which positions local changes fundamentally cannot lead to a change in forced options, how to create some kind of templates. The templates of such options fit well into various purely technical schemes of a computer. Of course, reference diagrams are very important.

– Are there any means to create a universal mental apparatus in which one could put a knowledge base - no matter chess positions or anything else, the rules by which one must work with this knowledge - and get adequate results from it?

- It is clear that in terms of constructiveness, such a task cannot be solved today, it is not relevant. Although many intellectual tasks are now being solved, such as, for example, text recognition. You can put a sheet of text into the scanner and get it on the screen in Word. He will read himself, each letter is recognized. In fact, we have advanced in many intellectual tasks. Some of them have already been solved, others are being solved. In some ways it turns out relatively better than with the participation of a person, in some ways it is even worse. Many practical examples can be given. As for the universal artificial thinking mechanism, this is more of a philosophical problem than a practical one. After all, even for such a simple game as chess, it took us 30 - 40 years to actually achieve something. Every philosophy is based on opinions. Everyone thinks that he is right, and maybe everyone is right in his own way. For example, all my life I have dealt with artificial intelligence and I believe that the human brain is nothing more than a large computer, therefore, it cannot be said that it is fundamentally impossible to create an analogous one. The question is in its power, speed characteristics, in filling it with knowledge. There is nothing incomprehensible here. This is my personal point of view. But there are other opinions as well. Of course, if we recognize the divine nature of man, then we already have to choose one of two epistemological options. Or yes, we have a divine nature, but it is knowable. In this case, we will not be able to truly reproduce what the Lord God was able to do, but at least we will be able to at least partially recreate His creations. Or we stand on the position of agnosticism, and then it is unknowable, and the question is completely removed. It turns out that the human brain solves some problems - and here no one has any doubts. But we cannot catch up with the brain, because, on the one hand, it was created by God, and on the other hand, we are not able to know it. All three positions are associated with faith, since in reality it is not necessary to know all the functions of the brain. If we make a machine as powerful as the brain, then it does not need to think like the brain. She will work differently.

– In psychology, as far as I know, the intellectual development of a person is determined by three criteria: the ability to abstract, create an intellectual range, and something else... To what extent are these possibilities realized in artificial intelligence and are they realized at all?

- There are a lot of programs that are specifically aimed at creating concepts that abstract from the existing factual material. Such programs work well. Another question is that a person is able to create these concepts, as it were, according to his own laws, which he invents for himself. All our attempts to translate these laws of his into the language of the algebra of logic turn out to be futile. A person has a much more powerful thinking mechanism that we simply do not know. We can't do anything "at all". We create the formulations we need, but we cannot "express" them in exact machine problems. Everything is reduced to mechanical problems with difficulty, and even if it is reduced, then slowly. Probably, we do not yet know more direct ways to achieve the goal. Anything can be put into a computer. The question is that a person is able to manipulate this knowledge all the time, but he still does not know how to make a machine do the same due to the limited volume and speed of data.

“But maybe it doesn’t make any sense to force the machine to manipulate knowledge?”

– Both immoral and constructive aspects are touched upon here. We are still far from the rebellious machines. For my age, and for yours, too, there will be enough calmness for sure. Even in limited areas, we have not yet learned how to make the machine manipulate problems, even those that it can solve. We set a task, and she thinks only on command.

– Vladimir Lvovich, tell me, if it were the dawn of computer technology again, would it be worth doing chess programs? Were they really that conducive to progress?

– After all, chess expands our horizons. In chess programs, tasks are set, the result is visible, we evaluate it. Still, there must be many solved, interesting problems, which contributes to progress in computer technology.

Send your good work in the knowledge base is simple. Use the form below

Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.

Posted on http://www.allbest.ru/

Developmentsoftwaremoduleartificialintellectforgamesinchess

chess computer intelligence algorithm

• Introduction

The concept of "computer chess" is the same age as the science of cybernetics and its section "artificial intelligence". Chess is an ideal model for investigating complex problems, especially those that require iterating over options. The development of a chess program is referred to the problem of developing artificial intelligence for the following reasons:

* there is a general belief that the problem is related to the problem of artificial intelligence, since chess is considered the most intellectual game

* there is an objective criterion for the work done - the strength of the chess program

* greater differentiation of this criterion represents the possibility of gradual improvement of the program.

One of the founders of cybernetics and information theory, Claude Shannon, back in the 1950s, was the first to formulate the rules for choosing a move on a chessboard. In the analyzed position, all possible options are sorted out to a certain depth, and a numerical assessment is assigned to the final positions using objective functions. Then the minimax procedure rolls back to the initial position, evaluates it, and indicates the best move, in the opinion of the machine.

The role of a person is to set the target functions as accurately as possible while evaluating the position. These functions have two components - material and positional. Everything is clear with the first one - a material advantage (in pieces and pawns) is, as a rule, a very serious argument for evaluating a position as the best. In addition, the less material on the board on both sides, the more accurate the assessment.

But with the positional component, everything is much more complicated: many factors are taken into account here, for example, the peculiarities of the arrangement of individual pieces and pawns, space on the board, time for regrouping forces, etc. The ability to correctly assess the role of all factors in a certain position has always been considered one of the signs of chess mastery -of people.

The weakness of the game of computers was precisely in the abuse of material and the inability to carry out an "absolute enumeration" of options. In the chess books of the 1970s and 1980s, one can find a considerable number of exemplary examples of the game of people with machines, when a master or grandmaster won a game with the help of beautiful sacrifices of pieces and pawns. The secret is already clear: for the human intellect, in contrast to the artificial one, the dominance of positional factors over material ones was obvious precisely at those moments when material sacrifices were made.

Years passed, with the increase in the speed of the computer, the depth of calculation increased, and at the same time algorithms were improved that improved the compilation of functions for evaluating positions. And in the second half of the 1990s, computers began to successfully compete with extra-class grandmasters. An epoch-making event for "chess cybernetics" took place in May 1997. Created by IBM, the Deep Blue computer defeated Garry Kasparov himself in a 6-game match. The computer was equipped with a special chess chip, and the machine scanned about 200 million positions per second. IBM Corporation attracted many grandmasters for its project, the latest achievements of chess theory were used to create the most perfect algorithms. And so, as already noted, in the 90s, chess programs for desktop PCs began to crowd out specialized computers.

Every month the power of chess programs and the power of computers is inexorably increasing, outstripping even the most daring assumptions of optimists. Even 12-15 years ago, discussions on the topic “When can a machine beat a grandmaster?” basically boiled down to the question “Is she capable of doing this in principle?”. And if the answer "Can" still managed to get, then the time was estimated in the range of 15-25 years.

The reality has refuted these predictions. Everything happened much faster! Already in the mid-1990s, it was discovered that the "game program + computer" synthesis was able to compete with a grandmaster.

The aim of the work is to develop and implement an artificial intelligence software module for playing chess, which includes:

1. study of existing game algorithms applicable to the game of chess

2. development of an algorithm for the behavior of a computer opponent

3. Determining the parameters of the algorithm behavior of the computer opponent

4. software implementation, which includes the implementation of the game algorithm and the development of a graphical interface

5. comparison of the developed software with existing analogues.

1 . Storydevelopmentchessprograms

In 1951, Alan Turing wrote an algorithm that would allow a machine to play chess. Only at that time the inventor himself acted as a machine. Also in 1951, mathematician Claude Shannon wrote his first paper on chess programming. He described two strategies for finding the best move, both based on a heuristic endpoint evaluation function:

* type A - enumeration of all possible moves to a fixed depth, with a call at the end of the evaluation function (because it is impossible to enumerate to the end)

* type B - performs only selective expansion of certain lines, using accumulated chess knowledge to prune uninteresting branches

The first computer was designed by von Neumann to carry out complex calculations in the creation of nuclear weapons. In 1950, the first sample appeared, capable of performing 10,000 operations per second. One of the first experiments with the apparatus was writing a chess program, however, chess was non-standard - on a 6 * 6 board without elephants.

A few years later, this computer ("MANIAC") played with people: a strong chess player won a landslide victory, and a beginner lost in 23 moves.

In 1957, on the IBM704 (42 kHz, 7 KB memory), type B programs were implemented on a full board, with the participation of all the pieces. The machine counted 4 half-strokes in 8 minutes. The level of the game is amateur.

In 1962, Newell, Simon, and Shaw discover an algorithm called alpha-beta that produces no worse results than exhaustive search without examining all options. It did not require any special chess knowledge, and it could be used to solve any enumeration problem. The essence of the algorithm is that in each line of the game, for White and Black, their maximum results are tracked, and if at some point Black has already received a result that is equal to White's maximum reached before, then there is no point in tearing further. When the search returns to the point where the white maximum was reached, the result will still be rejected. All modern chess programs are based on one of the improved versions of this algorithm.

Until about 1973, all chess programs were type B. They were mainly based on generators of plausible displacements, cutting off improbable ones with static evaluation. With the advent of more powerful processors, programmers began to switch to type A. The first were Teach and Chess4, these were "brute force" programs, once they reached a depth of 5 half-moves of the middle stage of the game, they began to win competitions with type B programs.

In 1975, Robert Hyat starts developing CrayBlitz, which for a long time was the fastest chess program and in the period from 1983 to 1989. - world champions among chess programs. He searched for about 40-50 thousand positions per second (in 1983), which was a great achievement for his time.

In 1977, Thompson and Condon at Bell Labs create the first dedicated chess computer. The main idea was to implement some parts of the chess program (move generator, position evaluation function, check detector, etc.) at the hardware level, which eliminated software delays in each position without waiting for an increase in processor power. The best computers of the time could explore up to 5,000 positions per second, and Ken Thompson's machine, called Belle, processed 180,000 lines per second. Belle could think through positions 8-9 half-moves ahead, which put him at the level of a master. He won many computer chess tournaments. But despite the fact that specialized hardware is an order of magnitude faster than a conventional machine, the CrayBlitz program played better on a cutting-edge machine then.

In the 1990s, Richard Lang, who writes exclusively in assembler, made a very powerful Genius selective search program. Until now, this program has consistently held 5th-6th place in the world computer chess championships. Also in the 90s, chess algorithms began to develop strongly, the null move heuristic (NullMove), selective pruning of the boundary branches of the enumeration tree, appeared.

Separately, it is worth considering the most famous chess program, the chess super computer - Deep Blue. In 1987, Deep Blue started as a student development - it was interesting for a group of capable students to try their hand, and the topic for the diploma is excellent. The progress of technology made it possible to make the very first version of processors (called ChipTest) very fast. The next, improved version, called Deep Thought, followed. At that moment, the group was noticed by the marketing department of IBM and turned to them with an offer that could not be refused. The result was Deep Blue and Deep Blue II. Thus, Deep Blue II is the result of over 10 years of work by a very capable group, which included both programmers/hardware and strong grandmasters. All the work was financed by IBM, so the group had resources that academic organizations could not even dream of. Deep Blue II is based on the powerful IBM RS/6000 server. The server has 31 conventional processors; one is declared chief, 30 others are subordinate to him. 16 specialized chess processors are connected to each "working" processor, so there are 480 chess processors in total. The entire complex processed more than a billion positions per second.

On May 11, 1997, Deep Blue II defeated world chess champion Garry Kasparov in a 6-game match. After a match with the champion, Deep Blue was dismantled.

As you can see, starting from the very first and ending with the most modern programs, chess programs were built on the basis of enumeration of possible moves, but there were also attempts to build more "intelligent" algorithms, different from enumeration. Many well-known chess players tried to develop such algorithms, but the results did not meet the requirements. For example, M. M. Botvinnik, being a world champion and the author of numerous works on chess theory, has been creating a chess program for more than 20 years, but the program has never started to play.

All enumeration algorithms for finding the best move build a game tree and look for the best move based on it.

2. Generalconceptstheoriesgames

2.1 Woodpossiblepositions

Let a finite oriented tree G be given, the set B of its vertices is composed of two disjoint subsets B0 and B1 , and any vertex p B that is not the beginning of any link in this tree is assigned a real number Oe(p) . This defines the game of two opponents with perfect information. The vertices of the directed tree G that belong to the subset B0 are called positions with white to move, and those that belong to the subset B1 are called positions with black to move; the links of this tree are called white or black moves, depending on which of the subsets B0 or ​​B1 their beginning belongs to. If a position p B is assigned a number Oe(p) , it is called final, and Oe(p) is called the static evaluation of this position.

A directed tree G is called a game tree.

According to the definition, for any position p B there is a unique path L(p0 > p1, p1 > p2 , ..., pk > p ) starting at the root p0 of the oriented tree Г and ending at the position in question, such a path is called a game leading to the position p .

The root p0 of the game tree G is the highlighted position. This is the position offered to the program, and the task is to find the best move in it. To do this, it suffices to define Oep0 and Oepi for all positions that are obtained from p0 in one move. The estimation of the initial position p0 is performed by the exhaustive search scheme, and in game theory this algorithm is called the negamax algorithm.

The complexity of the game tree is calculated by the formula: w^d, where w is the average number of possible moves, and d is the depth of the tree.

Figure 1 - Tree of possible positions

2.2 Principleminimax

This algorithm is carried out using depth-first search. That is, for each vertex that has not been passed, it is necessary to find all adjacent vertices that have not been passed and repeat the search for them. We roll back to the top of the last depth and calculate the scoring points relative to the first player. Then, from its parent node, we go to the next child node (if any) and calculate the winning points there. If the number of child nodes is over, then we look for a minimum of winning points (if the level of the parent node is odd) or a maximum (if even). The parent node has the received win point. We do a similar search, but considering that the parent node is already a child.

In the leaves of the tree, the points are calculated relative to the first player, i.e. it is assumed that the first player seeks to maximize his payoff, and the second player - to minimize the payoff of the first player. The first player wins if the number of points at the top of the level tree is greater than zero.

Figure 2 - Search in the tree using the minimax algorithm

As a result, the process used by the program corresponds to the alternation of decisions (computer / human), on each move the computer chooses the maximum score. The solution returning to the root of the tree is clearly the best choice, assuming that the opponent also makes the strongest moves in each case. Static evaluation is performed only at the nodes of the last level (leaves of the tree) for the position of the computer.

This algorithm performs a complete enumeration of all options. The number of considered positions will be evaluated as W to the power of D, where W is the approximate number of moves in one position, D is the calculation depth. For chess, W is approximately equal to 40, which means that, counting to a depth of 4, we have to go through 40^4 = 2560 thousand positions, and for a depth of 5 - 10240 thousand positions.

The search tree grows exponentially. To date, on the most powerful processors with the most optimal code, it is possible to count to a depth of 6 in a realistically estimated period of time. This is the main problem in the development of algorithms for the game of chess, and all developments are aimed at reducing the considered combinations.

Figure 3 shows a block diagram of the minimax algorithm for choosing the best move, the presented algorithm returns the best move according to the estimate obtained from a deeper analysis. The block diagram of the algorithm for searching for an estimate in depth is shown in Figure 4.

Figure 3 - Flowchart for choosing the best move

Figure 4 - Flowchart for searching for an estimate in depth

When calling the algorithm for searching for an estimate in depth with a very large required depth, we obtain an estimate with a complete enumeration of all possible moves.

2.3 Methodnegativemaximum(NegaMax)

In this algorithm, the static estimate of the position for one of the parties is equal to the static estimate of the other side with the opposite sign.

Figure 5 - Negative maximum method

2.4 staticgradepositionsandmainrequirementstoappraisalfunctions

Static assessment of a position is a way of objective, quantitative expression of the subjective feeling that a person has when looking at a position, without analyzing possible ways of developing the game. In game programming, a static position estimate is called a position quality function.

If finding the best move using the game tree can be applied with equal success to all games, then static position evaluation is a part specialized for a specific game. Its specialization determines the playing style of the artificial player, the factors embedded in the evaluation function determine the goal of the enumeration.

Matching the number with the position makes it possible for the machine to distinguish between bad and good combinations. The ability to distinguish good combinations from bad ones determines the strength of a virtual player. In two-person games, the evaluation is made by one of the players. If the evaluation function returns a good score for one player, it must return a bad score for his opponent. This rule is a criterion for the applicability of any evaluation function in algorithms that implement artificial intelligence.

The main requirement for the evaluation function is its symmetry with respect to the players, i.e. the condition must be met - what is good for one player is bad for another. A good evaluation function should take into account the basic principles of the game strategy and meet the following characteristics:

* material - calculated directly as the difference in the number of players' figures, it is possible to add weight coefficients for each specific figure

* positional - shows the quality of the location of the player's pieces

* the development of the position - shows the number of possible moves of the player. The better the position is developed, the more possible strategies the player has. For this reason, it is necessary to control and reduce its condition from the enemy.

* keeping track of the end of the game - in cases of winning (taking the opponent's king), should give the maximum score, usually + infinity, in cases of loss (loss of the king), should return the minimum score, usually - infinity

To play chess, one must take into account the change in the assessment of the position, depending on the stage of the game.

The classical evaluation function is a function of some of the above characteristics of the playing position, that is, the evaluation function is the total result of the evaluation of the position from different points of view.

The evaluation function for all games is different, as it reflects the specifics of the game. The characteristics of the evaluation function are chosen experimentally.

The importance of the selected characteristic is essential. Importance is determined by multiplying the selected characteristic by the appropriate coefficient. This coefficient must have a statistical justification.

Therefore, the evaluation function can be represented as follows:

F(p) - evaluation function for position p,

The coefficient of importance for the i-th characteristic,

I-th characteristic of position p.

2.5 stagingtasks

In the course of the thesis, it is necessary to investigate the existing methods and algorithms for the computer implementation of the game of chess, to determine their main advantages and disadvantages in order, based on the knowledge gained, to choose an algorithm that ensures the best operation of this system.

At the end of the thesis, you must:

to implement the studied algorithms in the C# programming language

to implement their various modifications using additional modules

to conduct numerical experiments to evaluate the quality of the developed models, compare the implemented modifications, in order to select the best

to develop a user-friendly and intuitive interface

3. Researchedalgorithmsandadditions

3.1 alpha betaclipping

Alpha-beta pruning is a search algorithm that seeks to reduce the number of nodes evaluated in a search tree by the minimax algorithm. The main idea is this: if your opponent has an unfavorable answer for you on one of your moves, then it is pointless to analyze his other possible answers to this move of yours, because even if there are more favorable ones among them, the opponent will not choose them. Alpha-beta pruning is an optimization, since the results of the optimized algorithm do not change.

Figure 6 - Algorithm for alpha-beta pruning

The advantage of alpha-beta pruning is, in fact, that some of the sublevel branches of the search tree can be excluded after at least one of the level branches has been fully examined. Since clipping occurs at every level of nesting (except the last one), the effect can be quite significant. The efficiency of the method is significantly affected by the preliminary sorting of variants (without or with a search to a lesser depth) - when sorting, the more “good” options are considered at the beginning, the more “bad” branches can be cut off without an exhaustive analysis. minimax search is depth-first, so it suffices to consider nodes along a single path in the tree at any given time.

The key idea behind alpha-beta pruning is to find a move that is not necessarily the best, but "good enough" to make the right decision.

The parameters alpha and beta are given as input to this algorithm, they are called the search window. These parameters are responsible for the clipping boundaries at the first level, as you go deeper into the game tree, these parameters change. The alpha-beta algorithm with parameters alpha = + infinity and beta = - infinity (brute force with a full window) gives the same result as the negamax algorithm, i.e. exhaustive search. Figure 7 shows a block diagram of the alpha-beta algorithm for calculating the depth position estimate.

Figure 7 - Alpha-beta flowchart for depth-first search

3.1.1 Examplestandardclipping

Figure 8 - Standard clipping example

Let's look at an example of a standard alpha-beta clipping. In position A, we choose the move, therefore we will choose the largest value from positions B and C. The value of B has already been calculated - this is 10. When calculating position C, it turned out that one of the nodes has a value of 5. In position C, our opponent will make the move, which means will choose the smallest value. It follows from this that the value of position C will be from 5 and below, therefore we will always choose the B-option. Therefore, we do not calculate the remaining nodes C.

3 .1.2 Examplein-depthclipping

Figure 9 - Deep Cut Example

Consider an example of deep clipping. In position A, we will choose between moves in position B and C. The value of B=15. We start calculating C. In position E, one of the nodes gave a value of 5. In position E, the choice of move belongs to the opponent, which means that the final value of E will be from 5 and below. If the value of C turns out to be equal to E, then we will choose option B, since it is more attractive. Therefore, we do not need to know the exact value of the position E, so all other branches coming out of it are cut off.

3 .2 iterativedive(Iterateddeepening)

The meaning of the search fan or iterative deepening is to repeatedly call the iteration procedure to a fixed depth with increasing depth until the set time limit is exceeded or the maximum search depth is reached. The advantage of this method is that you do not have to choose the search depth in advance; other than that, you can always use the result of the last completed search. The values ​​returned from each search can be used to adjust the aspiration window of the next search.

In general, alpha-beta pruning is called from the top of the tree at the interval (-?;+?). However, using iterative immersion, we can change it.

Suppose that X is the value of the optimal move found in the previous iteration, and Epsilon is the estimated difference in results between searching to depth D-1 and depth D. Next, we simply call alpha-beta pruning from the top of the tree with the expected interval: alphabeta(D, x-epsilon, x+epsilon).

1. The value will return in the interval (x-epsilon, x+epsilon) - this is the correct value, we can use it.

2. The value will return outside the interval (x-epsilon, x+epsilon), you must repeat the calculation with a changed interval.

Even assuming that the alpha-beta cutoff method yields no gain, the overall increase in analysis time is actually relatively small. Indeed, if we assume that the average number of options at each level is D, and the number of analyzed levels is p, then iterative search to the first level, then to the second, etc. to level p, is equivalent (without alpha-beta cutoffs) to looking at D + + ...+ positions.

This sum is equal, while the number of positions viewed in the normal analysis is equal. The ratio between these two numbers for large p is approximately equal to and therefore close to 1 in cases where D is large enough

Also, when using iterative search, time control can be introduced, which will allow the computer to offer a satisfactory solution at any time. Thus, if the time for reflection is limited to 5 seconds, it will consider all positions up to level 2, for example, in 0.001 seconds, up to level 3 - in 0.01 seconds, up to level 4 - in 1 second, and then, after starting the analysis at level 5 will be forced to stop due to lack of time. However, in this case, the computer will already have a fairly good solution found at level 4.

As a result, the computer is able to give an answer in the specified time (for example, make 50 moves in 2 hours). It is also obvious that a program that supports this method will play with different strengths on different computers.

Although some branches of the tree will have to be checked several times, this method gives a sufficient number of cuts.

3.3 Sortingmoves

The results of alpha-beta pruning are very much affected by the order in which the moves are checked. Let's look at this with examples:

In the first case, we will carry out the calculation by sorting the moves "from worst to best"

Figure 10 - Alpha-beta clipping with moves "from worst to best"

As you can see from the example, not a single tree branch was cut.

Now let's sort the moves "from best to worst"

Figure 11 - alpha-beta clipping with best-to-worst moves

Under optimal circumstances, iterating with alpha-beta clipping should scan W^((D+1)/2) + W^(D/2) - 1 position. This is much less than minimax.

To increase the effectiveness of alpha-beta clipping, you need to think about which moves to explore first. For these purposes, the so-called killer heuristic is used.

The idea is that if the move was good in one part of the tree, then if it is possible, it is worth trying to check it in others (at the same depth). To do this, an array is entered where several best moves for each depth are entered, if there are moves from this table in the position for the current depth, they are checked first.

For other moves, the algorithm prefers moves with checks and captures.

3 .4 Nega Scout(NegaScout)

NegaScout is an add-on for alpha beta. This is a directed search algorithm for computing the minimax value of a node.

NegaScout is the most popular brute force algorithm today. It is extremely simple and gives some (up to 50%) acceleration without introducing any additional error into the calculation. It goes very well with the modern attributes of chess programs - hash tables.

This algorithm has the advantage that it will never explore nodes that can be truncated by alpha-beta, however some branches may be considered multiple times.

The NegaScout algorithm checks the first node with a full window (Alpha,Beta), considering this option to be the best. It tries to cut off the following nodes by enumeration with a zero window, i.e. window (Alpha , Alpha+1). If the result of the count improves alpha, then this means that 1 node was not the best, and this node needs to be checked with a full window, however, instead of Alpha, we can take the resulting value (Value,Beta). The code for this method is given below:

public int NegaScout(Cell[,] CopyBoard, int Depth, int FinalDepth, int Alpha, int Beta, int PossibleMoves, bool IsMy)

int Value = 0, MaxValue = -1000, height = 0;

Cell[,] Board = new Cell;

Point[,] Moves = new Point;

Point Move = new Point;

FindMoves(Moves, ref height, Board, true, true);

PossibleMoves = height;

FindMoves(Moves, ref height, Board, false, true);

PossibleMoves += height;

if ((Depth == FinalDepth) || GameIsOver(Board, IsMy))

return Eval(Board, PossibleMoves);

return -1 * Eval(Board, PossibleMoves);

FindMoves(Moves, ref level, Board, HaveRequiredMove(Board, IsMy), IsMy);

int a = Alpha, b = Beta;

for (int i = 0; i< leight; i++)

CopyMove(Move, Moves, i);

DoMove(Board, Move);

Value = -1 * NegaScout(Board, Depth + 1, FinalDepth, -1*b, -1 * a, PossibleMoves, !IsMy);

if (Value>a && Value 0 && (Depth

a = -1 * NegaScout(Board, Depth + 1, FinalDepth, -1 * Beta, -1 * Value, PossibleMoves, !IsMy);

if (Value > a)

CopyPosition(Board, CopyBoard);

As you can see from the description above, for the Nega Scout, iterating over moves is an important function. If you arrange all the moves “from worst to best”, then enumeration can take even more time than minimax.

3 .5 Hash tables

3 .5 .1 Theory

In chess, during the enumeration, not a game tree is obtained, but a graph - very often, after rearranging the moves, we get the same position. The technique of using hash tables is to store an estimate of already reviewed positions. For each position, you need to store its estimate (more precisely, the estimate of the subtree under this position), the search depth, and the best move. Now, having begun to analyze the position, we need to look - but have we already met her? If you haven't met, then we do as before. If we met, then we look to what depth we dismantled it before. If it is the same as we need now, or deeper, then you can use the old estimate and save time. If it is less, then we can still use part of the information, namely the best move.

The best move for depth N may also be the best move for depth N+1. That is, in addition to its original purpose, the hash table is also useful for ordering moves. Here, iterative deepening unexpectedly helps - when we start the next iteration, the hash table is filled with information from the previous one, and up to some point (up to depth 1) all positions are simply there, with the best move to depth N-1.

A program that uses iterative deepening and hash tables often runs through all iterations from 1 to N several times faster than if it started iteration N right away, because with a probability of 75%, she always chooses the best move first, and with a probability of ~90%, the best move is among the first three considered.

3 . 5 .2 Implementation

Hashing is one of the most powerful ways to improve computer performance. The use of hash tables is the main tool in programming chess games.

Hash table - is a large indexed table, the cells of which store the following information:

2 hash indexes

depth of rendering for this move

Evaluation of this move

The choice of algorithm for calculating the hash index of the move is the most important moment when using hashing algorithms. When choosing an algorithm for calculating the hash index, there are 2 important points to consider:

The index should reflect the most unique information about the course in order to minimize the number of collisions

Hash index should be easy to count

A complex algorithm gives the best indicators of the number of collisions, but they are difficult to calculate, and therefore take a lot of CPU time. It is necessary to construct an algorithm that is easy to calculate but has the minimum number of collisions.

To calculate the index, an operation with some randomly generated masks was chosen.

Initially, the mask hash is filled with random numbers. For each position, 2 hash indexes are calculated, the first one is used to look up the position in the hash table, the second one is used to check for collisions.

Before any use of information from the hash table, the coincidence of the second hash indexes is checked, if they do not match, then a collision has occurred, and the information is ignored.

Updating information about the position should be carried out only if the current rendering depth is greater than what is already stored in the hash table.

Information from the hash can only be trusted if the depth in the hash is greater than the current calculation depth.

3.6 Usagelibrariesdebuts

The algorithm for using libraries of openings is to use pre-calculated databases with openings of games, since at the beginning of the game there is the largest number of possible moves with the same scores.

3 .7 Gradepositions

When developing an algorithm for static position estimation (quality function), there is an uncertainty in the choice between quality and speed. Qualitative evaluation functions based on a statistical base work slowly, but give very accurate estimates, some even without the use of enumeration, show the makings of intelligence.

Simple functions that take into account the simplest principles of the game work much faster, they do not give an accurate estimate, but they allow you to conduct a deep search. Thus, an accurate but slow estimate may give way to a stupid but fast one.

The quality of the assessment is determined by the amount of knowledge about the game, on the basis of which the number is compared to the position. The quality factor of the assessment is directly proportional to the speed of work and the amount of knowledge. As the 40-year practice of creating programs with artificial intelligence shows, the amount of knowledge of the evaluation function is inversely proportional to its speed.

Graphically, this dependence is shown in the figure as a family of hyperbolas.

Figure 12 - Deep Cut Example

When developing an evaluation function for chess, it should be taken into account that in chess the evaluation of all parameters depends on the stage of the game.

Chess is usually divided into stages: the opening is the opening of the game, the middlegame is the middle of the game, the endgame is the final stage. For the algorithm, it was decided to divide the games into 3 stages according to the number of pieces left on the board by the computer player. Initially, the players have 16 pieces on the board. The table shows the dependence of the stage of the game on the number of remaining pieces:

Table 1 - Stages of the game

3 . 7 .1 Materialgrade

The material superiority of one of the players is considered the most important parameter in chess theory, therefore, the material assessment makes the greatest impact on the overall assessment of the position. The material score is calculated as the sum of the weights of all pieces on the board. The king is not included in the material value, because if the king is lost, the player automatically loses. Estimating the weights of figures is the main task in constructing the evaluation function. To determine the weights of the figures, it was decided to use a self-learning algorithm based on the genetic algorithm. The weights of the pieces do not depend on the stage of the game. A genetic algorithm is a heuristic search algorithm used to solve optimization and modeling problems by randomly selecting, combining and varying the desired parameters using mechanisms reminiscent of biological evolution, first proposed by Holland (1975).

3 . 7 . 2 Descriptionworkgeneticalgorithm

The original problem is encoded in such a way that its solution can be represented as a vector ("chromosome"). A number of initial vectors (the “initial population”) are randomly generated. They are evaluated using a "fitness function" whereby each vector is assigned a value ("fitness") that determines the survival probability of the organism represented by that vector.

After that, using the obtained fitness values, the vectors (selection) allowed for "crossing" are selected. "Genetic operators" (usually "crossover" and "mutation") are applied to these vectors, thus creating the next "generation". Individuals of the next generation are also evaluated, then selection is made, genetic operators are applied, etc.

This is how an “evolutionary process” is modeled, which continues for several life cycles (generations) until the criterion for stopping the algorithm is met. This criterion could be:

Finding the optimal solution;

Exhaustion of the number of generations released for evolution;

Exhaustion of time allotted for evolution.

Genetic algorithms serve mainly to search for solutions in very large, complex search spaces.

Thus, the operation of the genetic algorithm can be represented in the following diagram:

Figure 13 - Deep Cut Example

3 . 7 . 3 Stagesworkgeneticalgorithm

Creation of an initial population - an initial population is randomly created; even if it turns out to be completely uncompetitive, the genetic algorithm will still quickly transfer it into a viable population. Thus, at the first step, one can not especially try to make individuals too adapted, it is enough that they correspond to the format of the individuals of the population.

Selection (selection) - a certain proportion is selected from the entire population, which will remain "alive" at this stage of evolution. Crossbreeding (reproduction) - in order to produce a descendant, several parents are needed; usually, of course, exactly two are needed. Replication in different algorithms is defined differently - it, of course, depends on the representation of the data. The main requirement for reproduction is that the offspring or offspring should be able to inherit the traits of both parents, "mixing" them in some reasonably reasonable way.

Mutations are a stochastic change in a part of individuals (chromosomes).

3 . 7 . 4 DefinitionscalesfiguresWithhelpgeneticalgorithm

The chromosome of the genetic algorithm includes the weights of chess pieces, with the exception of the king.

To set the initial population, the values ​​of chromosomes are set randomly in the interval , except for the weights of the pawn and the queen, the values ​​of their weights are fixed, the pawn is 100, the queen is 1000.

Tournament selection is used for selection. Random 2 chromosomes play among themselves, up to four wins, go first in turn. The winner of the duel remains, the loser is removed from the population.

When crossing, the method of single-point crossing is used.

2 parents are randomly taken, a random number is chosen by which the chromosome will be divided, the scheme is shown in Figure No. 14. As a result, each child will have traits from both the first and second parent.

Figure 14 - Deep Cut Example

Mutations are performed as follows: chromosomes are selected with some probability, and for them, each "gene" is changed to a random number in the range [-50; 50], except for the value of the static evaluations of the queen and pawn.

For the final values, the resulting weights are divided by 100.

3 . 7 . 5 Totalgrade

When evaluating a position, attention is paid to 8 components:

1. The material strength of rivals

2. Number of fields under battle

3. Occupation of key fields

4. Passed pawns

5. Double pawns

6. Castling

7. Pawn advance

8. Pawn chains [*1]

The number of fields under attack is calculated at a tree depth of 2, due to high performance costs. For each square that the computer piece hits, 1 point is added to the position score, for the fields that are beaten by the player's pieces, a point is removed. The resulting value is passed to the bottom of the tree as a parameter. Also at depth 2, points are calculated for pawn chains, passed and doubled pawns. For the presence of adjoining pawns to the left or right, the side receives 1 point. A pawn is considered a passed pawn if there are no opponent's pawns on its file, as well as on its neighbors, that can prevent it from reaching the end. Double pawns - 2 pawns of the same color standing on the same file. For the presence of doubled pawns from the side, 4 points are deducted, for the presence of each passed pawn, 5 points are added. There are key fields in chess:

Figure 15 - Key fields

For the occupation of each of them, an additional 4 points are given.

Because after castling, the king is in a very stable position, for a perfect castling, the side receives 3 points.

The closer a pawn is to its last rank, the closer it is to promotion. For each cell moved forward, 1 is added to the value of the pawn.

After calculating the number of points for both sides, the final assessment of the position is obtained by subtracting the player's points from the computer opponent's points.

4 . Developmentprogramss

4 .1 Requirementstochessalgorithm

When developing a model of a software module for playing chess, the following parameters should be taken into account:

* chess algorithms are very demanding on performance, and the power of the game of the program directly depends on the performance of the program

* software modules should be easy to develop and test

* user interface should be lightweight, easily customizable and scalable

4 .2 Kindschessalgorithms

Most modern programs can be divided into 3 categories:

* The first category of Fast searchers - the idea is that by simplifying the evaluation function to the limit, and carefully optimizing the entire program as a whole (which is usually achieved by writing a program in assembler), you can increase the number of positions considered by the program (nps - nodes per second) to an astronomical number, like 150-200k nps at P/200. That is, the program spends about one to two thousand machine instructions for each position. This number includes making a move from the previous position to this one, evaluating the position, generating moves from this position, control logic, etc. Only crumbs remain for the actual evaluation function - about a hundred teams. Programs are insanely fast and perform excellently in complex tactical positions, and also perfectly solve combinational problems, but have a weak positional game.

* The second category is knowledge-based programs. Here all the forces are thrown into writing a complex evaluation function. The interaction of the pieces with each other, and the cover of the king, and the control of positions, and almost the phase of the moon are taken into account. In terms of nps, the program is 10-100 times slower than fast searches, but plays good positional chess. More precisely, these chess are good only when there are no deep tactics on the board, or the time control is such that the program has enough time to calculate these tactics.

4 .3 Controltimeinchessalgorithms

The most important parameter in building an artificial intelligence algorithm for a chess opponent is the control of the move time. The strength of the game of a chess program depends on time control. Before the computer "thinks" a move, the time available to the computer must be calculated.

When calculating the time available for a move, two parameters must be taken into account:

* The algorithm for finding the best move is based on enumeration of all possible moves to a certain depth, and, therefore, directly depends on the time spent on enumeration. The more time we use, the harder the computer plays

* waiting time for a computer opponent's response should not be too long. As a basis, you can take the international rules of chess, in which there are several types of games: blitz - 15 minutes per game, fast - 60 minutes per game, classical - more than 60 minutes per game.

Based on the required parameters, it was decided to calculate the time available for moves before the start of each computer move using the following formula: where: time - time for a move; full_game_time - total game time; avg_moves - average number of player moves in a game; collect_time - additional accumulated time; D - a slight reduction in the time required for additional calculations. The parameters of the total time of the game and the average number of moves of the player in the game are two main external parameters, by changing which you can change the strength of the game. According to the statistics of the chess portal TheChess.ru, the average number of player moves per game is 30, so it was decided to take the average number of player moves per game equal to 30. Thus, the total time of the game is set from the outside. When developing an algorithm for the behavior of a computer opponent (artificial intelligence), the following algorithms were used:

* iterative search algorithm, with time control

* alpha-beta clipping algorithm and Nega-Scout

* debut libraries

* hash tables

* Killer and history heuristics were used to sort moves.

4 .4 Developedprogram

All of the above algorithms and additions were implemented in the program in the C# programming language.

Screenshots of the program are given below:

Figure 16 - Color selection

Figure 17 - Screenshot of the program

Figure 18 - Screenshot of the program

When you hover the mouse over a shape of its color, it is highlighted in white. When a piece is selected for a move, the color of its field turns orange and all the cells that the piece can move to are highlighted in white. When you hover the mouse over such a cell, its color also turns orange.

During the game, the perfect moves are displayed in the table on the left, the player can also save the history to a separate file.

4 .5 Basecyclesearchthe bestmove

The main task of the basic cycle of finding the best move is to find and execute the best move of the computer opponent. The cycle uses the opening libraries and iterative search with time control. Figure 12 shows the process of finding the best move:

Figure 19 - Basic search loop for the best move

4 .6 Searchthe bestmovefirstlevel

The main task of the algorithm for finding the best move of the first level (opponent's response) is to find the best move of the opponent at the first level. The algorithm is based on the NegaScout algorithm, which uses depth estimation to determine the score of the current move. Figure 13 shows the process of the algorithm:

Figure 20 - Finding the best move of the first level

4 .7 Findingdeepestimatesmove

The main task of finding a deep estimate is to find the estimate of the current move using the NegaScout algorithm, zero move heuristics, data from the hash table and a static position estimate. Figure 14 shows the process of calculating the depth estimate:

Figure 21 - Finding a deep estimate of the move

4.8 Othermodelsanddiagrams

The mathematical model of the program looks like this:

Figure 22 - Mathematical model

From the abstract class Figure, 7 classes of heirs are created that describe the actions and properties of the figures. There is also an Empty class, which means that the cell is empty. The board is an array of 64 Figure elements, each of which can become any of the derived classes. The move in the computer is represented as 4 digits - coordinates (from 1 to 8) of the start point of the move and the coordinates of the end point of the move. Below is the state diagram for the program:

Figure 23 - State Diagram

5 . experimentalgradequalityRanalyzesdataalgorithms

The implemented algorithms were subjected to a comparative analysis in order to identify the configuration that was optimal in terms of speed and quality of making a move. During the experiment, a number of tournaments were held between each pair of different implementations.

5 .1 GradeworkAlpha Betaclipping

With the help of this experiment, it was necessary to find out whether it was possible to achieve a decrease in the branching factor, and as a result, improve the speed of the algorithm without losing the quality of decision-making about the move being made.

To assess the quality of the final algorithm, this search algorithm was experimentally compared with a search based on the minimax principle.

The tables show the coefficients showing the ratio of the number of searched positions for the algorithms, as well as the ratio of the time allotted for the completion of this scan.

Table 1 - Comparison of the performance of the alpha-beta clipping algorithm with the minimax algorithm.

Experimental results show that alpha-beta clipping is much better than a simple minimax search.

5 .2 Gradeworkiterativedivingandsortingmoves

To evaluate the quality of the algorithm, this search algorithm was experimentally compared with Alpha-Beta pruning and just Alpha-Beta pruning.

Similar Documents

Description of the rules of the game "sea battle". Features of modern computers and artificial intelligence. Creation of a general block diagram of the program, its appearance. Required variables, procedures and functions. A characteristic of the objects used in the application.

term paper, added 11/05/2012


Development on the basis of the game "Points" of an approach to programming "artificial intelligence" in positional games and the possibility of using this approach to solve problems in the field of economics, management and other fields of science. game situation model.

thesis, added 07/21/2013


Structural diagram of a software module. Development of the scheme of the software module and user interface. Implementation of the program module: program code; description of the used operators and functions. View of the user form with the filled matrix.

term paper, added 09/01/2010


A study of the general rules of the game of checkers, user and programmer instructions. Description of the main algorithms that perform tasks of the Life Widget class. Evaluation of computer and human moves. Building a search tree for the best move based on the evaluation of functions.

test, added 12/20/2012


Main stages of development, principles of testing and debugging of the program module "VFS". Design features in the UML language. Brute force methods and their application in program debugging. Harmful factors present in the workplace of a programmer.

thesis, added 03/07/2012


Analysis of models and methods for the implementation of intellectual games in the human-robot system. Choreograph development environment. Algorithms of the recognition module, data processing, game module functions. Testing of the software package, correction and editing of errors.

thesis, added 08/12/2017


The essence and problems of defining artificial intelligence, its main tasks and functions. Philosophical problems of creating artificial intelligence and ensuring human safety when working with a robot. The choice of the way to create artificial intelligence.

control work, added 12/07/2009


Game program "checkers" for a game between a person and a computer. Development of algorithms, the historical line of development of problems. Different approaches to building systems. Abbreviated listing of the program and description of the algorithm. Components of artificial intelligence.

term paper, added 03/26/2009


Construction and analysis of the mathematical model of the game. Determining the probability of detecting ships with all possible locations and various search systems. Development of algorithms for the operation of artificial intelligence. Structure of the program and its components.

term paper, added 12/22/2012


The concept of artificial intelligence as the properties of automatic systems to take on individual functions of human intelligence. Expert systems in the field of medicine. Different approaches to building artificial intelligence systems. Creation of neural networks.

Unfortunately, there are no better algorithms for chess yet than the enumeration of very many positions. True, the enumeration is in order (and not one) optimized, but still it is a big enumeration. To search for a response move, a tree is built with the original move at the root, edges - moves-answers and nodes - new positions.

It is easy to explain how the next move is chosen in elementary algorithms. On your turn, you choose a move (in your opinion) that will bring the greatest benefit (maximizes your benefit), and the opponent, on his next move, tries to choose a move that will bring him the most benefit (maximizes his benefit and minimizes yours). An algorithm with this principle is called minimax. At each stage, you assign a position estimate to each node in the tree (more on that later) and maximize it on your own move, and minimize it on your opponent's move. The algorithm during operation must go through all the nodes of the tree (that is, through all possible game positions in the game), that is, it is completely unsuitable in terms of time.
Its next improvement is alpha-beta clipping (branch and border method).

From the name it follows that the algorithm cuts off by some two parameters - alpha and beta. The main idea of ​​clipping is that now we will keep the clipping interval (lower and upper bounds - alpha and beta, respectively - your K.O.) and we will not consider estimates of all nodes that do not fall into the interval from below (since they are not affect the result - these are just worse moves than the one already found), and the interval itself will be narrowed as the best moves are found. Although the alpha-beta clipping is much better than the minimix, its running time is also very long. If we assume that in the middle of the game there are approximately 40 different moves on one side, then the time of the algorithm can be estimated as O(40^P), where P is the depth of the move tree. Of course, with minimax there can be such a sequence of considering moves when we do not make any cuts, then the alpha-beta cut will simply turn into a minimax. At best, alpha-beta pruning can avoid checking the root of all moves in minimax. In order to avoid a long running time (with such an O-large complexity of the algorithm), the search in the tree is done by some fixed value and the node is evaluated there. This estimate is a very great approximation to the real estimate of the node (that is, iterating to the end of the tree, and there the result is “win, lose, draw”). As for evaluating a node, there are just a bunch of different methods (you can read it in the links at the end of the article). In short - then, of course, I count the player's material (according to one system - with integers pawn - 100, knight and bishop - 300, rook - 500, queen - 900; according to another system - real in parts from one) + position on the board of this player. As for the position, this is where one of the nightmares of writing chess begins, since the speed of the program will mainly depend on the evaluation function and, more precisely, on the evaluation of the position. There is already someone in that much. For paired tours, the player +, for covering the king with his own pawns +, for a pawn near the other end of the board +, etc., and the hanging pieces, the open king, etc. minus the position. etc. - You can write a bunch of factors. Here, to assess the position in the game, an assessment of the position of the player is built, which makes a move, and the assessment of the corresponding position of the opponent is subtracted from it. As they say, one photo is sometimes better than a thousand words, and maybe a piece of pseudo C# code would also be better than explanations:

Enum CurrentPlayer(Me, Opponent); public int AlphaBetaPruning (int alpha, int beta, int depth, CurrentPlayer currentPlayer) ( // value of current node int value; // count current node ++nodesSearched; // get opposite to currentPlayer CurrentPlayer opponentPlayer = GetOppositePlayerTo(currentPlayer); / / generates all moves for player, which turn is to make move / /moves, generated by this method, are free of moves // after making which current player would be in check List moves = GenerateAllMovesForPlayer(currentPlayer); // loop through the moves foreach move in moves ( MakeMove(move); ++ply; // If depth is still, continue to search deeper if (depth > 1) value = -AlphaBetaPruning (-beta, -alpha, depth - 1, opponentPlayer); else // If no depth left (leaf node), evalute that position value = EvaluatePlayerPosition(currentPlayer) - EvaluatePlayerPosition(opponentPlayer); RollBackLastMove(); --ply; if (value > alpha) ( // This move is so good that caused a cutoff of the rest tree if (value >= beta) return beta; alpha = value; ) ) if (moves.Count == 0) ( // if no moves, than position is checkmate or if ( IsInCheck(currentPlayer)) return (-MateValue + ply); else return 0; ) return alpha; )

I think some explanations about the code will not be superfluous:

• GetOppositePlayerTo() simply changes CurrentPlayer.Me to CurrentPlayer.Opponent and vice versa
• MakeMove() makes the next move from the list of moves
• ply - a global variable (part of the class) that holds the number of half-passes made at a given depth

An example of using the method:

( ply = 0; nodesSearched = 0; int score = AlphaBetaPruning(-MateValue, MateValue, max_depth, CurrentPlayer.Me); )
where MateValue is a large enough number.
The max_depth parameter is the maximum depth to which the algorithm will descend in the tree. It should be kept in mind that the pseudo-code is purely demonstrative, but quite working.

Instead of coming up with a new algorithm, the people promoting alpha-beta pruning have come up with many different heuristics. The heuristic is just a little hack that sometimes makes a very big speed gain. There are a lot of heuristics for chess, you can't count them all. I will give only the main ones, the rest can be found in the links at the end of the article.

First, a very well-known heuristic is applied "zero move". In a calm position, the opponent is allowed to make two moves instead of one, and after that, the tree is examined to a depth (depth-2), and not (depth-1). If, after evaluating such a subtree, it turns out that the current player still has an advantage, then there is no point in considering the subtree further, since after his next move the player will only make his position better. Since the search is polynomial, the speed gain is noticeable. Sometimes it happens that the enemy evens out his advantage, then you need to consider the entire subtree to the end. An empty move does not always have to be made (for example, when one of the kings is in check, in zugzwang or in an endgame).

Further, the idea is used to first make a move, in which there will be a capture of the opponent's piece, which made the last move. Since almost all moves during the enumeration are stupid and not very reasonable, such an idea will greatly narrow the search window at the beginning, thereby cutting off many unnecessary moves.

Also known history heuristics or best moves service. During enumeration, the best moves at a given level of the tree are saved, and when considering a position, you can first try to make such a move for a given depth (based on the idea that at equal depths in the tree, the same best moves are very often made).
It is known that such a kind of caching of moves improved the performance of the Soviet program Caissa by 10 times.

There are also some ideas about the generation of moves. First, winning captures are considered, that is, such captures when a piece with a lower score beats a figure with a higher score. Then promotions are considered (when the pawn at the other end of the board can be replaced by a stronger piece), then equal captures, and then moves from the history heuristic cache. The rest of the moves can be sorted by board control or some other criterion.

Everything would be fine if alpha-beta pruning was guaranteed to give the best answer. Even considering the long time to bust. But it was not there. The problem is that after the enumeration by a fixed value, the position is evaluated and that's it, but, as it turned out, in some game positions it is impossible to stop the enumeration. After many attempts, it turned out that the enumeration can be stopped only in calm positions. Therefore, in the main enumeration, an additional enumeration was added, in which only captures, promotions and checks are considered (called forced enumeration). We also noticed that some positions with an exchange in the middle also need to be considered deeper. So there were ideas about extensions і reductions, that is, recesses and shortenings of the enumeration tree. For deepening, the most suitable positions are like endgames with pawns, avoiding check, exchanging a piece in the middle of a bust, etc. For shortening, “absolutely calm” positions are suitable. In the Soviet Caissa program, forced enumeration was a bit special - there, after a capture during enumeration, forced enumeration immediately began and its depth was not limited (because it will exhaust itself in a calm position after some time).

As Anthony Hoare said: Premature optimization is the root of all evil in programming." (note: for those who believe that this quote is from Knuth, there are interesting discussions

1997, New York. World chess champion Garry Kasparov loses to the IBM Deep Blue computer, and this battle becomes the greatest chess game of all time. This game will be referred to as "the last battle of the human mind", many will compare it to the first flight of the Wright brothers and the landing of astronauts on the moon.

July 20 - International Chess Day - we will tell you about what happened next. And also about what artificial intelligence is inferior to human, and where Alan Turing has to do with it. A word to Garry Kasparov, world chess champion and author of the book.

Paradoxically, during a simultaneous session with the best professional chess players, the robot would have the most difficulty moving between tables and rearranging chess pieces, rather than calculating moves. Although science fiction writers have been inventing automata that look and move like humans for centuries, and robots today are successfully doing manual labor, it must be admitted that our machines reproduce human thinking much better than human movements.

In chess, as in many other areas of activity, machines are strong in what people are weak, and vice versa.

This well-known principle in the field of artificial intelligence and robotics was formulated in the year by Hans Moravek, who noted that “it is relatively easy to get computers to perform an intelligence test or play checkers at the level of an adult, but it is difficult or impossible to instill in them the skills of a one-year-old child in as far as perception or mobility is concerned.

At that time I was not aware of these theories; besides, Moravec was talking about checkers, not chess, but ten years later it became obvious that this principle also applies to my field of activity. Grandmasters excelled at position assessment and strategic planning, weak points of chess computers, but they could calculate tactical consequences in seconds, which would take even the best human minds many days to complete.

This gave me an idea. After my matches with Deep Blue got so much attention, I wanted to continue experimenting with chess even though IBM had abandoned it.

My plan, simply put, was this: if you can't beat them, then join them.

I thought: what if man and machine are not adversaries, but partners? The idea was embodied in the year in the Spanish Leon, where the first match in advanced chess (advanced chess) took place. Both partners had a personal computer at hand and could use any program of their choice during the game. The goal was to reach a new, highest level of the game - thanks to the synthesis of the strongest sides of human and machine intelligence. Although, as we shall see later, not everything went as planned, the astounding results of these “battles of the centaurs” convinced me that chess still has a lot to offer in the area of ​​interaction between the human mind and artificial intelligence.

I was not the first to come to this conviction. Chess machines were the holy grail long before people could build them. And now science finally got access to this bowl - and I turned out to be the person who holds it in my hands. I had a choice: reject the call or accept it. How could I resist? It was a chance to further raise the popularity of chess and expand the audience it had won after the famous match between Bobby Fischer and Boris Spassky during the Cold War and after my fights for the world crown with Anatoly Karpov. This would attract an army of generous sponsors to the world of chess, especially from high-tech companies. For example, in the mid-1990s, Intel sponsored a whole series of rapid and classical chess tournaments and the full cycle of the World Championship, including my title match with Viswanathan Anand, which took place on the top floor of the World Trade Center. In addition, I was driven by an irresistible curiosity. Can machines really learn to play chess as well as a world champion? Are they really capable of thinking?

It's interesting that
The first chess program appeared before the first computer.

It was developed by the brilliant British mathematician Alan Turing, who cracked the code of the Nazi Enigma cipher machine. In 1952, he wrote on paper an algorithm by which a machine could play chess, only the mathematician himself acted as the central processor. Turing's paper machine turned out to be quite a competent player. The reason for its construction went beyond Turing's personal interest in chess. The ability to play chess has long been considered part of human intelligence, and the creation of a device capable of defeating a person in this game should have marked the emergence of a truly intelligent machine.

The name of Alan Turing is also forever associated with the name of the thought experiment he proposed, later carried out in reality and called the “Turing test”. Its essence is to determine whether the computer can deceive a person in such a way that he thinks that he is dealing with a person, and if he can, the test is considered passed. Even before my first match with Deep Blue, computers had begun to pass what might be called the Turing Chess Test. They still played pretty badly and often made obviously inhuman moves, but sometimes they managed to play games that would look quite appropriate in a decent human tournament. Every year the machines got stronger and stronger, but in the process of their evolution we learned more about chess itself than about artificial intelligence (AI).

It cannot be argued that the culmination of 45 years of research, which has become an event on a worldwide scale, turned into a disappointment, but it clearly showed that constructing a chess supercomputer is not at all the same as creating an artificial intelligence that can compare with the human mind, which was dreamed of. Turing and others.

In fact, the “mind” of Deep Blue was no different from the “mind” of a programmable alarm clock.

The thought of this only exacerbated the bitterness of defeat for me - to lose to a programmable alarm clock, even if it costs $10 million?!

The so-called AI community certainly rejoiced at the result and the attention it attracted, but at the same time, scientists were clearly discouraged by the fact that Deep Blue did not at all resemble the artificial intelligence that their predecessors dreamed of. Instead of playing chess like a man, demonstrating human intuition and creative thinking outside the box, he plays chess like a machine: he estimates up to 200 million possible moves per second and wins thanks to brute computational power. Of course, this does not detract from the achievement itself. After all, Deep Blue is a creation of the human mind, and the loss of a person to the machine he created at the same time means his victory.

After the unbelievable tension of that match, exacerbated by IBM's suspicious behavior and my tendency to doubt, I wasn't ready to admit defeat easily. To be honest, I've never been good at losing. I believe that a person who easily accepts defeat will never become a real champion, and this principle, of course, is true in my case. But I believe in a fair fight. At the time, I thought that IBM had deceived me - as well as the whole world, which was closely following our match.

I must admit that re-analyzing every aspect of that infamous duel with Deep Blue was no easy feat.

Over the years, I have deliberately avoided any discussion on this subject, touching only on what was already known to the general public.

There are a lot of publications on Deep Blue, but this book is the first and only one where all the facts are collected and the whole story is told as I see it. Despite the pain of the memory, it was an enlightening and rewarding experience. My great teacher Mikhail Botvinnik, the sixth world chess champion, taught me to look for the truth in every position. And I tried to fulfill his testament and look for the truth in the very essence of Deep Blue.

Illustration: Shutterstock