Author: Simon Finn
Date: 04:42:16 10/08/01
Go up one level in this thread
On October 07, 2001 at 22:51:33, Bob Green wrote:
>On October 07, 2001 at 19:30:46, Bruce Moreland wrote:
>
>>On October 07, 2001 at 17:34:46, Bob Green wrote:
>>
>>>I am working on a non-chess game.
><snip/>
>>>I am asking for some tips and tricks in construction of tablebases.
><snip/>
>
>>Endgame database construction is pretty simple, but there are some gotchas that
>>might not be the same for your game as for chess.
>>
>>The first pass you identify conversion cases (cases where the are exactly two
>>pieces mapped to exactly one square) and resolve them.
>
>Ok, I don't get this. Example? Are you talking checks for symetry? If so, I
>have that covered.
For chess, each endgame databases usually contains all the positions for a
particular piece configuration. A capture or pawn promotion will produce a
position that's in a different endgame database. In the jargon, this is referred
to as "conversion" (we convert the problem of winning KQPKQ into the problem of
winning KQQKQ, for example). It's important that the databases form a (partial)
order with respect to conversion so that the set of databases can be computed
bottom-up.
>>You also identify cases
>>where one side has won due to what in chess is checkmate.
>>
>
>I read this as:
>
> 1. Find all positions where the king is checkmated
> or
> 2. Find all postitions where the king is stalemated
>
>These are the starting points. Do halfboard/diagonal rotates to remove
>symetrical cases.
>
>Right?
Reflections as well as rotations. In the absence of pawns, there are only 10
distinct ways to place a single king on a chessboard, for example.
>
>>You then proceed to move backwards from there.
>
>I read this as follows:
>
> 3.a move one of your pieces from the checkmate position
> 3.b for each possible opponent piece, move it
> 4. reapeat 3a/3b for all your pieces legal to move
>
>Right?
>
>>Can one side achieve a position
>>that is known to be won? If so, this position is resolved. Next, can one side
>>not avoid a position that is lost? If so, this position is resolved.
>
>Have to admit I'm a little less clear here as to why this would happen.
>Probably some problem w/ 3a/3b.
Suppose the side to move has moves that lead to the following results
(from the point of view of the other side):
Loss in 5; Win in 3; Win in 7; Unresolved
then we can mark this position as "Win in 6"
If the options were:
Win in 3; Win in 7; Win in 9
then we can mark this position as "Loss in 9"
While if they were:
Win in 3; Win in 7; Unresolved
we can't resolve this position until we know the value of the third option.
>
>>You keep
>>going until there aren't any new positions resolved, at which point you are
>>done.
>>
>>If you are making a DTM chess database
>
>WTF is a DTM database, BTW?
DTM and DTC are the two widely used metrics for chess endgame databases.
DTM = distance to mate
DTC = distance to conversion
DTC databases are slightly easier to generate but can produce rather odd play -
such as unnecessarily sacrificing pieces, just to produce an earlier conversion.
>>, there are problems because you can't
>>simply mark a position as won if you can attain a won case. If you can convert
>>to a mate in 19, you can't say that this is mate in 20, because there might be a
>>mate in less than 20 case out there if you are still working on the "natural"
>>mates in less than 20.
Nalimov's implementation does mark the position as "mate in 20", but continues
to look for better solutions and is prepared to improve the score to "mate in
19" (or whatever).
>I'm actually not that keen for the "best mate." Any mate would be ok.
>>
>>Also, you might not make progress on a particular pass, but you still have to
>>continue, because conversions cause some gaps.
>
>The above sentance is not clear.
>
This is a feature of Bruce's implementation of the DTM algorithm, I think.
My guess is that he always finds "mate in n" on the n'th iteration of his
algorithm. That means that he can't stop on the 91'st iteration just because
there's no mate in 91 in the database - there might be a mate in 100 whose first
move converts to mate in 99 in a different database.
Nalimov's implementation works differently and *can* stop as soon as no new
mates are generated.
>>In some endings, there are no
>>mates in 90, but there are mates in 100, because of conversions to very
>>difficult won cases.
>>
>>I'm not sure what else you are looking for, but since I'm one of the few people
>>that has done this, I figured that I should say something.
>>
>>bruce
>
>As always, I appreciate your guidance Mr. Moreland.
>
>Best regards,
>
>Bob Green
Simon
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.