How endgame tablebases work

[Russell Reagan]

I was trying to figure out how the endgame tablebases are generated. I
would assume it's some form of retrograde analysis, but I couldn't really
work out all of the details of how one would generate them on my own. The
best I could come up with was, generate all legal combinations of winning
positions and draws (wins for one side would be losses for the other
obviously), and just do a backwards search from there. But when I get to
thinking about this, it seems like this search would take just as long as
searching forward from a K+R vs. K position. The only thing I can think of
that would make it work is if instead of doing a forward search and
producing only one small piece of the entire endgame, you produce the entire
endgame from any position, because you did it backwards. If someone
wouldn't mind explaining how this works, I would really appreciate it.

Thanks,
Russell

[Joost de Heer]

"Russell Reagan" <rre...@mail.utexas.edu> writes:

Tablebase generation code can be found at
ftp://ftp.cis.uab.edu/pub/hyatt/TB/tbgen.zip.

Sketch of how the code works (excluding some finetuning, like deleting obvious
illegal positions):

- Mark all positions as 'draw', except the positions in which the side to move
is in check, and can't escape that check. Mark those positions as 'lost in
0'.

While there are still changes made in the tablebase array:

- Increase the iteration number.
- Now loop over all positions. If the position has as evaluation 'draw', loop
over all the possible moves. There are a few possibilities now:
- All moves lead to a position marked 'draw'. Don't do a thing now.
- At least one move leads to a position which has evaluation 'loss in x'.
Mark this position in 'win in y+1', where y is the minimum of the x'es
previously found.
- All positions lead to 'win in x'. Mark the position as 'loss in y+1', where
y is the maximum of the x'es previously found.

The disadvantage: You have to loop over all positions every iteration.
The advantage: Once you've created the complete database, you don't have to
search anymore when this database is reached.

So the initial effort may be bigger, but after having probed the tablebase a
few times, the time you win by not having to calculate anymore is bigger than
the time you lost creating the tablebase.

Joost
--
Shredded inside there's one place left to turn
A long-term problem, a temporary remedy [Judgement ]
But fuck it all anyway [- Anathema]
You can pretend to be happy

[CCCage]

http://www.chesskit.com/aarontay/Winboard/egtb.html

"Russell Reagan" <rre...@mail.utexas.edu> wrote in message
news:9is0tr$4t5$1...@oprah.cc.utexas.edu...

[Aaron]

On Sun, 15 Jul 2001 16:52:29 GMT, "CCCage"
<chessboa[nospam]@anonymous.to> wrote:

>http://www.chesskit.com/aarontay/Winboard/egtb.html
>

No . My site addresses only the practical aspects of setting up
tablebases. There is little if not nothing at all about the theory of
how endgame tablebases work.

Want to learn how to use Winboard and the 100+ free Winboard
Chess engines?Visit http://www.chesskit.com/aarontay/Winboard/Winboard.html

[Paul Rubin]

Thompson's article from ICCJ describes TB generation methods very nicely.
I think it may be online somewhere.

[Russell Reagan]

> Thompson's article from ICCJ describes TB generation methods very nicely.
> I think it may be online somewhere.

Thanks, but what's ICCJ? Some of the results I got are:

International Council of Christians and Jews
Italian Chamber of Commerce Japan

[Paul Rubin]

"Russell Reagan" <rre...@mail.utexas.edu> writes:
> > Thompson's article from ICCJ describes TB generation methods very nicely.
> > I think it may be online somewhere.
>
> Thanks, but what's ICCJ? Some of the results I got are:

International Computer Chess Journal.

[Bruce Moreland]

There are a couple of ways to do it. I'll describe the one that is *not*
the way Ken Thompson does it. I don't know if it's how Eugene Nalimov does
it.

The idea is that you make an array that contains an element for every
conceivable position, legal or otherwise. You find the illegal ones and
mark them as illegal. You find the ones where a king is in take and mark
those.

You then make a series of passes over the data. In each pass you look at
each element. On the first pass, for each element you see if all of the
moves you can make lead to a position where your king is in take. If so,
you mark positions where your king is in take now as "mated" and positions
where your king is not in take marked as "draw".

Next pass you look at it from the opponent's point of view. You see if
there are any moves that can lead to a "mated" position. If there are, you
mark this position as "mate in 1". If not, you leave it alone.

Next pass you are back to the other side, and you check to see if every move
you make leads to "mate in 1" or worse, and if so you mark this as "mated in
1".

Next pass you try to find if it's possible to achieve a "mated in 1"
position, and if so you mark it as "mate in 2".

You continue doing this until you don't find any mates or mated's. At that
point, everything else is marked as a draw.

The above is grossly over-simplified, but you get the idea.

bruce

Russell Reagan <rre...@mail.utexas.edu> wrote in message
news:9is0tr$4t5$1...@oprah.cc.utexas.edu...