How to represent the entire game of chess (without really trying).

0 - Instant gratification.

You can get to every legal game of chess from here.
And you can watch random games autoplay here.

The programmer's documentation is here. This includes links to the heavily optimized Java source code with detailed comments.

This document is a very brief introduction to the ideas that this code represents -- please contact me if you have any questions. As of today (9/21/00) I have written up the most important of the ideas that are being proposed but there are numerous details that are clear in my mind but have not been explicated, and worse, there are probably all sorts of mistakes and logical errors, so please feel free to drop your criticisms on me!

1 - A thousand-year dream.

Since the dawn of chess, every dedicated player has dreamed of playing an unbeatable game. But the number of legal games of chess isn't merely very large, but Vast (as Daniel Dennett has it), Vast in the sense that it is impossible for human beings (or human constructs like computer programs) to examine even a small fraction of these games.

This Vastness has led many observers to give up on the goal of actually finding a "solution" to the game of chess, as it seems to be impossible to "prove" that any definitive strategy exists for the game due to the very large size of the problem.

Luckily, all may not be as bleak as it seems. "Nearly all" of the legal games are in some sense "stupid" -- they contain moves that are clearly inferior or even irrational. What we are really interested in is the space of "best play" as human beings have defined it -- that much smaller set of games that contain "only correct moves", at least as far as human beings can see.

2 - A strategy to "beat" the game of chess.

2.1 - An overall strategy.

Create a unique name for every game.
Let players attach a value to each game.
Use "natural selection" to identify "best play".

2.2 - Create a unique name for every game.

Before we can start evaluating games of chess, we need to have some way to name them!

A system has already been created which assigns a unique URL to each legal game of chess: here are some examples, like the Ruy Lopez, the Queen's Gambit Declined, and the "Evergreen" game. The naming system is very simple: we make an ordered list of all legal moves for each position in a legal game in and identify each move with its index or position in the list.

2.3 - Let players attach a value to each game.

A "value" or an "evaluation" for a board position is simply a measure of which player is most likely to win. Since chess is a game of complete information, there are only three possible values for each board position: either it is a forced win for White (which we call +), a forced win for Black (which we call -) or a forced draw (which we logically enough call 0).

Board positions where a player has been mated are automatically assigned a value of + or - and games that are drawn due to stalemate, repetition or the 50-move rule are assigned the value of 0. This lets us evaluate all "terminal" positions, positions where the game is over: to evaluate non-terminal positions, we use a procedure called "minimaxing".

Minimaxing lets us assign a value for a position as follows. If White has the next move and if there is any move for White that leads to a value of + then this position has a value of +. Or, if there is any move for White that leads to a value of 0 then we give this position a value of 0. Otherwise, all next positions must have a value of - and this means that this position must have a value of -. A complementary statement holds if Black has the next move.

In theory, we should be able to perform this operation for any board position and find out which player has the advantage. In practice, "nearly all" the board positions won't be able to be evaluated this way!

The problem, and the beauty of the game, is that there are just too many positions to evaluate to get a complete look at all games that could follow from a given board position. In this case, we will allow the first player who reaches that position to evaluate it as +, -, or 0. Now, we have no guarantees on the competency of this player to correctly evaluate the worth of a given board position but as the next section will indicate, it is not so important that this value be initially correct as subsequent play and minimaxing will allow a "better" evaluation to occur.

For the purposes of this system, we'll call the value that we get from minimaxing from only terminal positions the true value of the position because that's what it is (an enforceable value that you can prove is correct). Any other real-world approximations to this value we'll call "estimated" values.

2.4 - Use "natural selection" to identify "best play".

The previous tactic will give us an initial evaluation for any board position that people visit and care to evaluate. However, in the real world many of these "estimated" values will not be the same as the true value of the position, due to human inadequacies. Luckily for this success of this strategy, use of the minimaxing algorithm on the estimated values, together with a population of competent and contentious users, will let us improve these estimated values until, we hope, the estimated values are almost certainly the same as the true values for all the board positions that we have visited.

The simple idea is that we use minimaxing on the estimated values that are attached to positions that occur after the given evaluated position. Thus, it doesn't matter if the position is in truth mis-evaluated, because that estimation will be overridden by evaluations of positions after the position in question. If players evaluate "all" moves and board positions until quiescence, in other words, until play reaches a position that "obviously" has no further play and has a specific value, then we should be fairly sure that the "estimated" values are the same as the "true" values. If in fact it becomes possible to actually prove that these quiescent positions have a specific value then we can actually "beat" the game of chess!

There is a lot of meat here that I'm skipping over, so let's wave our hands a little more and go to an example. Let's suppose that Joe reaches a given chess position P and mistakenly evaluates it as "+", a win for White, when it is in fact really a win for Black ("-"). Karen sees this and immediately finds the move for Black that refutes the position, the winning move for Black. She evaluates this position as "-" and thus, with the minimaxing procedure, position P is now given a value of "-". Joe doesn't believe that this is a refutation and plays a move against Karen's "killer" move, marking that position as "+" again. Karen however has a refutation for Joe's killer move, she makes it, and marks it with a "-". Joe believes this evaluation as correct and tries some other refutations for Karen's killer move, but in each case, Karen is able to come up with a refutation that Joe is unable to refute in his turn. This procedure could go on indefinitely, with different players working their way down the tree with their possible "killer moves", but eventually the tree should reach only moves that all players agree are quiescent (ie, have no possibilities for non-obvious moves) and thus are correctly evaluated.

Last update: 9/21/00