How Your Chess Program Defeats You, Part 1

Introduction:  Trees and Master Forest Rangers

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.

The history of computer chess is long and fascinating, and it has had a profound influence on the field of Artificial Intelligence, though I will not go into that history here.  There is an outstanding online lecture on that topic that I referenced in an earlier blog post, if you would like to know more.

Under the assumption that it is wise to understand your enemy, this blog 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 the satanic ‘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.  Figure 1 is an abstract visualization of a tiny fraction of this tree.  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. 

Figure 1:  Partial Chess Tree 

As 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. 

In the Beginning is the Opening

Our first exception to the above oversimplification comes immediately in the opening.  Chessifer doesn’t have to think ahead in the opening.  He barely has to think at all because he has a prodigious memory.  In another blog I noted that Modern Chess Openings, vol 14 contains approximately 30,000 tempos and Chessifer has committed all of them (and likely more) to memory.  When you make a typical ‘book move’ in the opening, he yawns and retrieves his response effortlessly from memory.  If there is more than one possible response on his part, he may choose one or the other at random or with probabilistically weighted chances, according to how he prefers the alternatives.   Chessifer is evil, and likes to maximize your frustration.

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 in Figure 2.

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.

The process just described is the Minimax function that game computers use to select moves.  Once you understand it, you can see how logical it is.

In my next blog I will discuss how Chessifer handles the most difficult problem he faces:  the size of the game tree.

Here is a link to Part 2. http://blog.chess.com/kurtgodden/how-your-chess-program-defeats-you-part-2