How Chess Algorithm Works?
Chess is a two-player strategy board game played on checkered board with 64 squares arranged in an 8x8 grid. For your information, chess is considered as abstract strategy game which required strategy and tactics to win the game. It is pretty common game that I believe most of us already played it when we were child. Nowadays, we can play chess with bot as long as we have platform that is sufficient to do so such as PC and smartphone.
Have you guys ever wondered how chess bot works?
Of course, all of us know that chess bot works because math. It is pretty obvious, but what I want to explain here is how chess algorithm works in mathematics side. Actually, chess bot works like any other computer works, which is by reducing the problem to a bunch of dumb calculations. No worries! the essence of chess algorithms are simple, although, the modern chess algorithms itself kind of complicated. But i am here to explain the essence!
STEP 1 : Constructing “tree”
When we start the game, each player have 16 pieces. Assume now is computer turn. The computer can make 1 of 20 possible moves (2 each for the 8 pawn, plus 2 each for the knights). After that, the opponent can also make 20 possible moves. That make it we have 20*20 possible scenarios which means 400 scenarios only in two turns. Next, the computer can make another 20 possible moves to each of these 400 scenarios.
As long the game still continues, the tree will keeps growing. In theory, the perfect computer would be able to get to the very bottom of this tree, and look at all possible configurations of the board, approximately 10¹²⁰. Then, it would see which are the paths down this tree that will lead to the victory, and choose the best one for the bot.
STEP 2 : Evaluating the outcomes
Pretty sure that all of us know the problem, 10¹²⁰ is very huge number. For your information, the total estimated atoms in the universe are 10⁷⁵, in other words, the bot might still calculating its move while universe already reached its end.
The real and sufficient computers will build up this tree to the best of their hardware capabilites, like 5, or 10, or 20 or whatever moves into the future. Once they have this limited tree, they evaluate each position using an evaluation function.
The pretty simple example is an evaluation function could be the number of pieces the computer has minus number of pieces opponent has. For example, the computer has 12 pieces left on the board, while the opponent only has 8. Then the computer would evaluate such a board to 12-8 = 4.
Of course, that is not a very good evaluation function, but that is the idea. This can be made more and more complicated, taking into account of many values such as individual pieces, board position, control of the center, vulnerability of the king to check, vulnerability of the opponent’s queen, and tons of other parameters. Function can be whatever as long as it works, as it allows a computer to compare board positions, to see which are the desirable outcomes.
STEP 3 : Making a move
After doing the analysis, now it is time to make the decision, this is the example of simplified tree.
The computer that plays as the white, has to decide it’s move. It construct the tree like above and applies Minimax Algorithm. Minimax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. When dealing with gains, it is referred to as “maximin” to maximize the minimum gain. Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making and to general decision-making in the presence of uncertainty. It is also used in other two player turn-based games such as Tic-Tac-Toe, Backgammon, and Mancala.
Probably some of you guys wondered what is this things in pseudocode, so here it is. The pseudocode for the depth limited minimax algorithm is given below.
Now, let’s begin the fun part.First, it starts from the most bottom level, let’s call it first level. The computer will chooses the one with maximum score. Consider the right-most square team at the first level. It has two possible outcomes 2 and 5. Since it will be the computer’s turn at that stage, it chooses the best outcome, the one with MAX score, which is 5, and so it assigns 5 to that node. Same things for other square in the same level.
Now, we are done with first level, now let’s go for the next level which is second level (the one with blue color square), the outcome is decided by the opponent, since at that time, it will be black’s turn. The computer assumes that black will make the move which is best for black, which means the worst for white, hence it chooses the setups with MIN score. For example, the blue square team at the left have 3 possibilities (or maybe actually 2) which is 8, 8, and 7. The computer assumes black will take the one that leaves the computer weakest, and that is 7. So the nodes on that level are all given values.
Finally, we are done with first and second level, next we have third level (back to red square again) which means computer’s turn again, so it makes the choice with MAX score, which is 7. Thus the computer climbs the tree, alternatively choosing minimum and maximum scores (That’s the reason why the name is MINIMAX), and makes the choice that leaves it best off in the end. The better the hardware, the deeper the depth of the tree it can analyse, and so the better its chances of winning. Which is why old computers couldn’t usually beat humans (back in 1950–1960), but nowadays, not gonna lie, it can be pretty hard.
References :
ScienceHook Youtube channel : https://www.youtube.com/watch?v=CFkhUajb8c8
Quora post : https://www.quora.com/How-exactly-does-a-chess-computer-work
Wikipedia : https://en.wikipedia.org/wiki/Minimax and https://en.wikipedia.org/wiki/Chess
