"Build a Chess Board" by Steve Ramsey |
The Game of Chess
(2007-07-01) Endgames and Nalimov Tables
Tabulating all positions is an efficient way to solve an endgame perfectly.
If the total number of game positions is small enough,
then each of them can be alloted a small computer record in an explicit table.
The entire game can then be solved efficiently by analyzing that
(first completing the records corresponding to final positions, like checkmates).
For the game of chess, this is practical only in endgame situations,
when only very few pieces remain on the board.
A database is a set of stored key/value pairs, where only
a small portions of the possible keys exist (for example, not all possible
surnames exist in a database of people whose names are used as "keys").
By contrast, a tablebase includes (almost) all
keys. The key itself need not be stored in a tablebase; it's merely used
to compute the unique numerical address where the information corresponding to
that key is located.
In game tablebases, the game position is the "key" used to access the
value recorded in the tablebase.
By contrast, in a data base, only a tentative address can be computed,
based on a so-called hash-code which a key
may share with many other possible keys.
The location computed from
the key's hash-code is merely a starting point where a whole list of keys can be
found (with their associated recorded values). When a database is queried
for a key, the query key must be compared with the stored keys.
The size of a database containing n different keys is thus more than
n lg n bits. (A tablebase which associates a single bit
to each of n possible keys has a size of only n bits.)
Perfect play is defined as achieving victory as fast as
possible, or delaying defeat as much as possible. A full analysis of the
game is normally possible only by recording the length of a perfect game for
each tabulated position (the position is a first-player win when that length
is odd, it's a first-player loss otherwise
(the issue of ties is discussed below).
A computer database which gives the number of half-moves to the end of a
perfectly played game is called a Nalimov table.
It's easy to play perfectly by looking up such a table:
Play into the smallest even position if you can, otherwise play into the largest
odd position. A special label must be assigned to ties which is
adequately defined as an odd number larger than any other...
(for example 255, if Nalimov records consist of a single byte).
There is no notion of "perfect play" for a game which ends in a tie.
Such a game is merely considered equivalent to a game which goes on forever
because neither player can force a victory.
Yet, it's possible to refine Nalimov values to distinguish between
a tie "by the book" (which tells that an undecided game is over)
having the highest odd value and other ties which have odd values just below
that (but above any other odd values corresponding to true
Error-free play (as opposed to perfect play)
can be defined as what happens when neither player gives up victory
when it's available to them.
It is not required of the winner to force a quick conclusion.
A practical "tie" may even result if victory is postponed indefinitely
(a win may thus be transformed into a tie by the actual rules of
chess which limit the number of capture-free moves).
Compact bit-wide tablebases, known as bitbases, are sometimes used
in actual chess-playing programs as "oracles" which help make error-free decisions
in the endgame.
A single bit is assigned to each position whose value is
zero (0) if and only if it is a first-player loss.
The value "1" corresponds to a first player win if and
only if it has at least one option labeled "0" (otherwise,
the "1" indicates a tie).
A bitbase (for mere error-free play) is normally obtained by
extracting the relevant information from a complete Nalimov table.
Eugene Nalimov was born in Novosibirsk in 1965.
He is a programmer who joined Microsoft in 1997.
In 1998, he started writing tablebases generators for chess endgames
and was honored for that work at the
Example: The Knight and Bishop Endgame
The basic table base (TB) only needs to consider the positions where the bishop
is on one of the 16 topmost white squares. Ignoring obvious illegal
positions (e.g., several pieces on the same square or adjacent kings) the other
pieces can be on one of 64 squares and it can be the turn of either
Black or White. All told, the size of the TB,
at one byte per position, is fairly small:
2 . 16 . 64 . 64 . 64 = 8 MB
(2010-01-28) Static Evaluation Function
Evaluating quiescent positions is an art form.
(2010-01-28) Minimax Search
Minimize your opponent's gain, maximize your own.
(2010-01-28) Alpha-Beta Pruning
In a minimax search, some alternatives need not be explored at all.
(2010-01-28) Hash Tables
How to avoid exploring the same position more than once.
(2010-01-27) Short Games
Checkmates in the opening moves.
There are 8 variations which result in a position similar to
the one depicted at right, where White is checkmated.
They differ by the order White moves his two pawns and also by two
possible choices for moving the central pawns of each player
(one square or two squares).
The locution fool's mate is sometimes used as a generic term
to denote any very early checkmate, especially the following one:
This mate is often attempted among newcomers.
The French call it le coup du berger which translates
literally as Shepherd's mate, as do the names of that checkmate
in several other languages, including
The fool's mate and scholar's mate
are certainly as old as chess itself but they were apparently not mentioned in print before
the seventeenth century,
as they found their rightful place in the early classification
proposed by one Arthur Saul
in "Famous Games of Chesse-play" (1614)
Counting the number of 4-move games ending in a scholar's mate
can be an interesting exercise:
The game may end with Qf3xf7++
(e.g., after the infamous
opening) or Qh5xf7++ (as above).
In either case, White can play in 4 different ways
(opening with either e3 or e4, then moving either the bishop or the queen).
Each sequence makes different "compatible" moves available to Black.
If the black queen moves, she must move back.
To allow the mating move,
the white queen's path must be clear and f7 must be unprotected...
(2010-01-29) Sam Loyd's Chess Puzzles
Toying with chess positions which can't arise in actual games.
The American columnist
Sam Loyd (1841-1911)
devised many clever puzzles based on the rules
of chess which have little or no relevance to actual play.
Lone black king on h4
(against 16 white pieces). Mate in 3 moves.
The same prblem for other positions for the black king is less easy to analyze.
Tabulated below are the number of moves needed to mate, according to
In this context, e4 is almost always the strongest move;
often the only strongest move,
as indicated by the exclamation mark (!)... d4 is second best.
Full White Starting Lineup against Lone Black King