How your chess program humbles you every time

I found the source of this article a long time ago somewhere. I can’t find it any more, but I have made a chapter in my chess book about it (not sure if this is the original or modified, so the credits may go to the original author).
I assume that you are not a computer geek, or you would probably already know how your computer chess program works and would therefore not be reading this.  Since you are not a geek, I will write this so anyone can understand it without specialized geek training. Under the assumption that it is wise to understand your enemy, this post will explain, if not all the nuances, at least the fundamentals of how your computer program regularly defeats you in a game of chess. Let us refer to our common digital enemy as ‘Chessifer’.

It is an oversimplification, but not totally inaccurate to say that Chessifer considers each move on the board, thinks of all your likeliest replies, then his replies again, and so on as far into the future as time and processing power permits.  At the end of this process he evaluates the resulting positions, decides which is the best and then makes the move that gets him closer to that outcome.

If you think that is not unlike how you play chess, you would be correct, only Chessifer does it much faster and much further into the future than you possibly can.  If you have read Kotov’s book “Think Like a Grandmaster”, you are aware that he advocates imagining a ‘tree’ of possibilities as you think ahead.  That is, the current position is regarded as the root of the tree.  Your potential moves are branches that emanate out from this root, and your opponent’s replies to your moves branch outward from each of those.  The leaves of the tree represent the farthest positions that you can imagine with your necessarily limited brain power.

This kind of a chess game tree is precisely how computers represent the game. The top square or ‘root’ of this tree represents the initial position before any moves have been made.  All of the possible moves by white are shown as branches from this root that lead to the next board position from which Black plays.  The label on each square, or node, of the tree indicates the move that was played to reach it.  But the node itself actually represents the entire board position after that move is played.  We follow the convention in computer science where trees grow downward, but don’t let this confuse you.

TreeAs I said above, Chessifer builds as much of this tree as he can, and when he reaches a leaf node (any node that does not have branches to any lower nodes), he uses a program referred to as the ‘evaluation function’, but which we will refer to as ‘Eval’, and assigns a numeric score to that position. The higher the score, the more valuable that position is deemed to be for Chessifer. Eval is the part of the program that encodes actual chess knowledge.  Thus it will award points to a position based on material, mobility of pieces, pawn structure, and so forth. Programmers work with chess masters, and if a chess master can explain in concrete terms why a given position is better for one side or the other, then this knowledge can be encoded into Eval.

But when the two of you run out of book moves to play, or (more likely) when you depart from the book because you don’t know it as well, then Chessifer reverts to the basic process noted above.  He computes as much of the chess tree as he can, starting with the current position as the root, evaluates the leaf nodes (which are just board positions, remember), and selects the move that maximizes his chances of reaching the best such leaf node.

In the Middle is Minimax

But exactly how does Chessifer maximize his chances of reaching that desirable position he lusts after?  In your own studies with chess books you have probably read that you should always assume that your opponent will choose the best move available to him or her, and make your own move accordingly.  Once again this is what Chessifer does using a procedure called ‘Minimax’, which we can explain using the partial game tree:

Minimax
It is Chessifer’s turn to move, and we will refer to the current position as Position A. There are only two legal moves that lead to Position B or Position C. If is your move from each of those.  Let us suppose that you have two legal moves from each of those, and it will again be Chessifer’s move.  From Position D he would have three moves, from Position E only one, from Position F he would have four,  and from Position G there are none. This could simply be the case because Chessifer ran out of time to compute more branches, or it might be a stalemate. I have not labeled the actual moves on this tree since that is irrelevant.  We are only interested in how values are assigned. After the above tree is created, Chessifer uses Eval to assign values only to the 9 leaf nodes, namely Positions G through O.  The numbers on these leaf nodes represent the values assigned by the Eval function.

The values for the non-leaf nodes, Positions A through F, are actually selected from the previously-computed leaf nodes according to the following rules.

Max:  From nodes where it is Chessifer’s turn to move, that node receives the same score as the maximum value of the nodes at the next level down.

Min:  From nodes where it is your turn to move, that node receives the same score as the minimum value of the nodes at the next level down.

There are a few points to recognize here.  First, since non-leaf nodes get their values from the nodes directly below them, this forces the process to assign values starting from the bottom of the tree, working upwards toward the root.  Second, the Max rule is nothing more than the rule that says to choose your best move.  Third, the Min rule is equivalent to the assumption that your opponent will choose his or her best move.

At Position D it is Chessifer’s turn to move, so he uses the Max rule and finds the highest value at the next level down, assigning that value (47) to Position D.  In other words, Chessifer would move to best position for him if he first reaches Position D.  Since there is only one move from Position E, he has to assign 27 to E, and then Position F again receives the value from the largest value below it, or 59.

We are now ready to assign values to Positions B and C, from which it is your move.  Remember that the numbers from Eval are according to Chessifer’s point of view.  So larger numbers are worse for you.  Thus, you would play the move to the smallest value position, so for your nodes, the numbers assigned are the minimum of the ones below.  For Position B that means 27 is assigned, and for Position C it is 42.

Finally, Chessifer can now decide which of his two moves from Position A would be best for him, which again would be the maximum of the two choices he has.  So the ultimate answer to the question currently facing Chessifer is, interestingly enough, 42. Chessifer would play the move that gets him to Position C.

Chessifer would like to compute as far ahead as possible, but he does not want to waste time following branches of the tree that are stupid, wasting his time. Fortunately for Chessifer (not you), there is a way to identify parts of the game tree that are useless to explore, allowing Chessifer to spend his time in more promising parts of the tree.

Healthy Trees Must be Pruned

There is a procedure called alpha-beta pruning that can determine when exploring certain portions of the game tree is not useful.
PruningHere one can ask an interesting question:  should Chessifer continue expanding the game tree at Position G?  Notice that Eval has already given a value of 18 to Position F.  What will happen when Minimax is ready to give a value to Position C?  Since C is a Min Position its value will be 18 or less.  And since that cannot be larger than the value 27 at Position B, the value at A can be assigned right now from B, and Position G can be ignored altogether.  If there are a large number of positions under G, this could result in a significant savings of processing time. The example is an instance of “alpha” pruning.  The next figure shows the related “beta” pruning:BetaConsider when it is your move at Position B.  Obviously, you would avoid moving to E since Chessifer could then go to Position F with a value of 62.  You would be better off moving instead to D, which has a value to Chessifer of only 47.  Thus, 47 can be immediately assigned to Position B, and there is no need at all to expand the tree from Position G or perform any evaluations on those positions.  Once again there could be a great many positions that are avoided, saving a tremendous amount of processing.

In the End is the Beginning

I explained how Chessifer uses a very large table to play the opening, rather than performing tree search.  The same basic idea is used to play the end game, although the end game can be played even better than the opening.  That is, the opening is based on current chess theory, as it is called, which is simply the collective wisdom of chess masters around the globe and which is collected into large reference works such as ECO, MCO-14, and others.  But just as medical wisdom changes over time, so does chess wisdom, which is why these works are periodically updated.

But endgame databases are different in that, within bounds, they encode perfect play.  By perfect play, I mean just that.  If there is a win, the end game database can tell Chessifer how to get it.  If the best that he can do is draw, then Chessifer will draw.

Endgame databases are created by what is called retrograde analysis.  An ending position, either a win or a draw, is investigated backwards by finding all moves that can result in that end position, and then all moves that lead to those pre-final positions are found, and so forth.  Such perfect end game databases have been constructed for all endings with 6 or fewer pieces and pawns.  You can even download some end game databases from the web, if you search on “endgame tablebase”. Here you can use all the 6 man tablebases.

Conclusions

There is much more than Minimax and Alpha-Beta pruning that goes into a full-featured chess engine, but these are the essentials of what your computer is doing when it humbles you repeatedly.  Other procedures and issues for the computer include such things as iterative deepening, the horizon effect, node ordering and critical nodes, the killer heuristic and more.

This entry was posted in Chess and tagged , , , , , , , , , , , , . Bookmark the permalink.

1 Response to How your chess program humbles you every time

  1. Pingback: Strategy And Tactics For Chess

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s