Author: José de Jesús García Ruvalcaba
Date: 04:54:39 06/08/03
Go up one level in this thread
On June 08, 2003 at 04:53:02, Geoff wrote: >Hi > >I haven't so far come across a proper explanation of how EGTB's work in >principle. Can anyone explain it in a sentence or two please ? > It is not that simple that it can be explained in few words. >I will have a stab at how I think it might work. > >Typically, for 5 or less pieces each position is stored in the table with just >the board position and a mate in x moves figure. The program can then just read >these figures for each possible move and navigate its way to a shortest mate. >But there are some more detailed questions such as > >1) What format is each position stored in ? Positions are NOT stored. >Does it just store position for say white and infer info for black ? > It can be done either way. >2) Does it store the whole position or use some symmetry tricks ? > Of course! To save some storaging space. >3) How were the tables created in the first place, quite a tricky algoritm I >would imagine !! > There are several ways to do it, but the most sophisticated are really tricky. >Without sitting down and trying to do the maths I had naively assumed that the >tables would all fit in 10 Megs or so. It is surprising, well to me at least >that the tables are so big > > regards Geoff I will try to explain the basic ideas with a simple example. For example, king and queen versus king. For simplicity I will assume that white is the side with the queen. The explanation will be divided in two parts: 1. What is stored in the endgame tables. 2. How to obtain the info for part one. 1. What is stored in the tables. The info required to describe the position is: -position of the white king. -position of the white queen. -position of the black king. -side to move. To identify the side to move, we will use two files (one for white to move and the other one for black to move), each one will contain an array of theoretical values of the corresponding positions. The position of each piece can be easily given by a number from 0 to 63 (assign of number to each square of the board). So the position of the three pieces can be given by a number from 0 to 64*64*64-1 (it is a very big number). The theoretical value of some position will be found in the corresponding entry of the table with that side to move. Of course that is very primitive and wastes lots of space. A huge amount is to be saved by considering the symmetries, that is, finding a way to assign the same number to positions which differ only by a rotation of the board or a mirroring (for endgames with pawns, we can only consider left-right mirroring as symmetry). That reduces the size of the arrays. Another way, more subtle, to save space is to avoid the illegal positions (for example, the side not to move can not be in check). It is quite complex, but some intelligent and hard working people have found ways to do it. 2. How to obtain the info for part one. The first step is to recognize the "end positions". In our example (KQ vs K), the positions with the side not to move in check are simply illegal and the corresponding entry will be marked so. Checkmates are also easy to identify and in the corresponding entry a "checkmated" will be stored. Stalemates and positions in which black can capture immediately the white queen are "draws", and in the corresponding entry that value will be stored. There are still plenty of positions which are not "end positions". Each one will be considered to see if it can be conveniently transformed by the side to move in another position whose value is already known. For example, if white can deliver mate in the next move, then it has a move which leads to a position with black to move in which black is "checkmated". Such a position is a "mate in one" and we store that value in the corresponding entry. (In this simple example there is no way black can force white to stalemate him or the give up the queen, but in more complex endings there can be forced draws). We are still not done. In the next step some positions with black to move will be found for which ALL the moves lead to positions (with white to move of course) which are "mate in one". Those are "checkmated in one". We continue until no more theoretical values can be found. Again, in this simple case, we will be done after "checkmated in nine" or something like that. But in endings with more pieces, it can happen that value of some positions can not be determined by this kind of "retrograde analysis". Those positions are "draws". Also, in some tables the "distance to mate" is not stored, but the "distance to conversion". Other metrics can be used. In some cases, it is only stored "won", "draw" or "lost". And even "won" and "not won" can be used. Hope this is somewhat helpful. José.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.