11. Transposition Tables

Transposition tables (often referred to as hash tables) are used for storing chess positions during the search to avoid re-searching positions that can be reached via several different move sequences. This can speed up the search dramatically, particularly in the endgame.

The famous Lasker position shown below is one of the more extreme examples:

White to move and win! [Lasker]

White wins by the obscure move Ka1-b1!! rather than the more intuitive Ka1-b2 which merely leads to a draw. The reason for this is far from obvious and requires a search depth of at least 20 ply. Without transposition tables, finding this move would take many hours or even days for a chess program, but with transposition tables Sigma Chess finds the solution in less than a second! The reason for this dramatic speedup of the search is that there are very few different positions reachable from the initial position, because all the pawns are locked.

Sigma Chess stores 10 bytes per position, and actually maintains four separate transposition tables; two for each side. The larger the transposition tables, the more positions can be stored. However, even small tables (e.g. 320 Kb) give significant speed improvements. Very large transposition tables (e.g. 80 Mb or more) are not recommended on slow machines or during blitz games, because the tables have to be reset before starting the search and this can become quite time consuming. Additionally, large transposition tables actually decrease the number of moves per second, because Sigma Chess then won't be able to use the processor cache properly. 10 Mb transposition tables is actually a good setting except in the endgame.

The minimal transposition table size supported by Sigma Chess is 80 Kb (about 8.000 positions); the remaining sizes are achieved through "successive doubling" - i.e. 160 KB, 320 KB, 640 KB, 1.25 MB etc. - up to a maximum of 320 MB.

Under Classic Mac OS you can reserve some memory for general use (for game windows, libraries, game collections etc.) in the Memory "sheet" in Sigma Chess's Preferences dialog. The remaining memory is assigned to the transposition tables. Under OS X, which has a better application memory handling system, this is handled automatically and thus the Memory sheet is not needed.

Since Sigma Chess supports multiple engine "instances" running at the same time, so the transposition table memory has to be divided between each engine. This is done in the Transposition Tables "sheet" in the Preferences dialog, where you can specify the maximum transposition table size for each engine. If you rarely run more than one engine at a time, you might want to assign most of the available memory to the "first" engine.

Using transposition tables has one minor drawback: They are not 100 % fool proof. To be of any use, it must be possible to look up positions quickly and efficiently. This is achieved through so-called hash keys, which serve as indices in the transposition tables. But these keys are not unique and thus two different positions may “hash” into the same table entry. However, for the hash keys to be unique they would have to be very large and therefore useless, and consequently there is a theoretical possibility that the program will sometimes retrieve incorrect information from the tables. In practical play, however, the probabililty is very low and the risk therefore worth taking because of the huge reductions in search time.

Sigma Chess will normally use transposition tables when solving mate problems. In case the program should fail finding a mate, you should turn off the transposition tables and try again. If this still has no effect, then there are no solutions!

Sigma Chess 6.2.1 User's Manual - Copyright (C) 2011, Ole K. Christensen

Previous page | Next page | Back to index