6/27/2013

Solving chess - facts and fiction

Because it is summer, I decided to take a vacation and spend some time with topics not directly related to my GPU chess project. One of the interesting topics I have been thinking is solving chess. I know it is not realistic with the current level of technology, but with future technologies, it might be possible. At least we can speculate what it would take to do that.

FICTION 1:Solving chess requires an evaluation function. It does not. Many people familiar with computer chess programs know that the computer uses a rough estimation of the value of the positions in its calculations, such as "white is up 0.11 pawns". This evaluation is not always accurate and one may thus suspect the accuracy of the solution if a computer is to solve chess. But the point is that, conceptually, every variation is calculated to the very end, meaning either a checkmate or a draw by one of the rules. Thus, there are only three evaluations: win for white, draw, or win for black. None of these involve any heuristics. They are the true values of the position. Another way to think about this is imagining a checkmate search that begins from the initial positions and tries to find a checkmate for white in any number of moves. It would take a very long time, but eventually, it would announce that there is a forced checkmate in X moves or that there is none. No evaluation required here.

FACT 1: Chess is solvable. Currently, this is merely a theoretical concept, because we lack computing power and memory. But it is fairly easy to show that there is a finite number of chess games, which ultimately can be enumerated and the best play for both sides can be found. First, there is a strict upper bound for moves that a game can last. The 50-move rule dictates that every 50th move, one side has to either move a pawn or make a capture. These are irreversible moves. This implies that, if the game does not end in another way, eventually the pawns cannot move or they promote to pieces, and all the pieces will be captured. Then there is no way to avoid a draw by the 50-move rule. Second, there is a finite number of moves in each position. There are only so many pieces that can move to so many squares. These two facts prove that there is a limited number of games. In his seminal paper "Programming a Computer for Playing Chess", Claude E. Shannon estimated the number of all games to be around 10120 (Philosophical Magazine, Ser. 7, Vol. 41, No. 314, March 1950).

In fact, the number of legal chess positions is much smaller. Shannon estimated this to be around 1043. This estimate was rough and ignored promotions. Currently, the best proven upper bound is around 1046.7. It seems that better than enumerating all the games is listing all the positions and finding if they are winning or not. This can be done by a technique called retrograde analysis which is widely used for generating endgame tablebases. Given the types of pieces on the board, it is possible to list all the checkmates. Then working the moves backwards, all the positions from which the checkmate positions can be achieved with one move are listed and marked as wins in 1 ply for the checkmating side. Then all the positions (where it is the defender's turn) from which one can reach only positions previously listed as wins in 1 ply are marked as wins in 2 plies. And the process is repeated until all the positions have be examined. This is a simplified explanation of the process, but you probably get the idea. This has been done for all the material combinations with 7 pieces or less (see e.g. Lomonosov Endgame Tablebases).

FICTION 2: Chess can be solved with current hardware. There have been hoaxes that claim that they have nearly solved chess. They are either good natured, such as the April Fool's joke by ChessBase, or exploit people's good faith to collect money, such as the infamous Nikola Chess. It is very common to be confused with big numbers that are given with the exponent notation. For example, 1047 and 1053 seem to be quite close to each other. But their ratio is 1 to 1 000 000. Not exactly close. While modern GPU's can perform as much as 1012-1013 operations per second, this is lightyears away from what is required. Imagine we had money to buy a million GPU's with 1013 flops capacity. That yields 1019 flops in total. Assume we had an extremely powerful algorithm for retrograde analysis, taking only 10 operations per position. This means, we can handle 1018 positions per second. Assume we had enough memory for all the position we need. How long it would take to go through all the chess positions? About 1 600 000 000 000 000 000 000 years. The universe estimated to be about 13 000 000 000 years old. Can you count the zeros?

FACT 2: It is difficult to solve chess even in the near future. For years, the so-called Moore's law was true: the computing power doubles every 18 months. Currently, as the fastest CPUs are running at 4 GHz, we seem to have hit the ceiling. While I was studying physics at a university in the beginning of the millennium, a professor said that he expected the upper limit to be around 10 Ghz. Above that, the transistors must be so small that the quantum phenomena begin to interfere with the computing. In nanometer scale, tunneling of the electrons happens with high enough probablity to make the processing unreliable. Speed of light is another issue. Information cannot travel faster than light, so the devices must be small to make them fast. Light propagates a meter in about 3.3 nanoseconds. This will become an issue if we need lots of memory, that cannot be located on the same chip as the processor. Clever computer architecture might alleviate this, but not too much. And the real problem that seems to limit the performance is the heat. Processors produce a lot of it. The more there are transistors, the more heat is emitted and the better cooling is required.

However, let us assume for a moment that Moore's law still worked. With increasing trend towards more parallel machines, we might have some overtime. Or perhaps a quantum computer is invented. One never knows. Currently, world's most powerful supercomputers achieve 1016 flops. Let us assume here the more realistic 100 operations per position. This means 1014 positions per second. Let us assume we could run the retrograde algorithm on the supercomputer for four months, i.e. 10 million seconds. Then, we can examine 1021 positions. Now, increase the computing power by using the Moore's law. When do we reach the 1046.7 positions? Simple math reveals: after 85 of the 18 months periods or 127.5 years or around year 2141. Not in our life time.

IN CONCLUSION: Heuristic approaches to chess will rule for years to come. Developing chess algorithms that use heuristic evaluation functions is still meaningful. Future chess engines will have deeper searches, more accurate evaluation, and perhaps we will see the rise of GPU chess. I want to be part of that.

6/17/2013

Hashing schemes

Eventually, I will have to implement a transposition table for the chess engine. That requires accessing global memory during the search. This, however, should not be a problem if I do not use the transposition table at the leaf nodes or in the queiscence search. Transpositions occur most often at the deepest branches. However, the subtrees are smallest near the leaf nodes. Most benefit comes from nodes that are roots of larger subtrees. And fortunately, testing the transposition entries is always cheaper than move generation which involves global memory writes.

I have been thinking about the best way to implement hashing. Many chess engines use Zobrist keys for hashing. They require serializing the bitboards and using a table of random values for each piece and position. Although simple and effective, I do not like this approach, because it requires lookup tables (about 6 kb), which I have tried to eliminate. I would like to find an alternative hashing scheme. It does not matter if the hashing function is more complicated as far as it does not consume the precious memory.

The good thing about Zobrist keys is that each square and each piece has an equal contribution to the final hash value and positions are spread uniformly in the hash table. I would like to achieve similar results with less random numbers which could be hard coded as constants in the hashing function. I could interleave the hash key calculation with the global memory writes, so I would get the keys for free.