Related Links (Outside this Site)

---

(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 table  top-down  (first completing the records corresonding 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 could 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.)

The size of the record assigned to each position should be minimal.  In some cases, it might be enough to use a single bit which tells whether the position is a first-player loss (0) or a first player win (1).nbsp; Such bit-wide tables are known as  bitbases  are sometimes used in actual chess-playing programs as "oracles" which help make error-free decisions in the endgame.  A bitbase is not constructed directly but is obtained by extracting the least significant bit of each entry in a wider table which fully determines  perfect play...

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).  If we settle for something less than perfect-play analysis (like merely determining the win-loss status of each position) we may obtain implicitely a "result" which might no allow the winner to force a quick end  (or even result in a practical "tie" by postponing victory indefinitely).

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.  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 values just below that...

Eugene Nalimov was born in Novosibirsk in 1965.  He is a programmer who joined Microsoft in 1997.  In 1998, he started writing tablebases generators chess endgames and was honored for that work at the 2002 ChessBase convention.

Example: The Knight and Bishop Endgame

The basic table base (TB) need only 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.

1.  Fool's mate  (2-move mate) :

This is the shortest of all chessgames.

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:

2.  Scholar's mate (Queen raid) At age 9, Tal, lost to his brother thusly: 1. e4 e5 3. Qh5 Na6 2. Bc4 Bc5 4. Qxf7++ 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 Spanish, German, Dutch and Portuguese.

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)

How to beat the four move checkmate  by  ChessVision.net

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 Napoléon 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...

Short Chess Games by Serguei Vorojtsov:   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

---

(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  Fritz 8.  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.

The Excelsior Problem  (1861).  Mating with the least likely piece.

---

(2010-01-28)   Opening Traps
Well-known deadly traps in the opening game.

Ruy Lopez, Berlin defense; The "fishing pole" black trap  (v1, v2, v3)

Trap in the Trompowsky attack