Author: Bruce Moreland
Date: 09:35:22 06/17/00
Go up one level in this thread
On June 17, 2000 at 04:39:16, Steve Maughan wrote: >I am thinking about trying to create a tablebase for a checkers program I am >developing. While I realise that the 6 pieces Chinook database is available it >doesn't contain 'distance to win' information, only win/loss/draw. > >Is there any literature on the basics of creating a tablebase from scratch? Can >anyone explain the basic algorithms in a nutshell? > >All help appreciated! > >Steve Maughan You start by assigning each possible unique position a number, which is called a Godel number. You'll make two big arrays, with one element for each Godel number. You have one array for white to move and the other for black to move. You look at each position in sequence, and see if the position is illegal, and if so you mark it as illegal. In chess this means cases where there are two pieces of the same color on a square. In chess you can also go through and figure out whether there are two pieces of opposite color on a square, or a pawn on the 8th. You can assume that a capture has taken place on the preceding move, and it was done by the side not to move now. These are conversions to simpler endings, and you can look them up in smaller tables. I don't know how you'd do captures in checkers, since piece on same square is not a good way to detect them. Anyway, you then make another pass and see if, for a given position, the game is over. In chess this means that one side is checkmated, if you do it like that (I do it differently but it's too complicated to explain in this post). In checkers it could be cases where the side to move has no moves, etc. You mark these positions with "lost in 0". You make another pass and see if you can reach a "lost in zero" position (or a won conversion position) with one move. Any you find you mark as "won in 1". You make another pass and see if you can't avoid reaching a "won in 1" for the other side, these are "lost in 1". You make another pass and see if you can reach a "lost in 1", if so these are "won in 2". You do this until you make no changes. The existence of conversion cases makes this more difficult, depending upon how you handle this. There are lots of little tricks and traps, and everyone finds a bug after building all their tables, and they have to build them again. Anyway, that's it. bruce
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.