My main intent here is to pool from the collective experience you have in creating endgame solvers. I would like to understand the most simplest yet powerful ideas behind endgame solving, and I realise there are different ways to approach and do it.
I've never done endgame solving before (but I created an engine to play the game in question, if you're interested I can post links to it. but of course even a basic endgame lookup is the final piece for the engine to play strongly - actually I implemented some endgame heuristics, but humbly speaking my understanding of the game's endgame is not good enough to do it this way
)So just thinking out loud about it, here is the pseudocode I came up with (and am implementing right now)
Code: Select all
// the game has 4 types of pieces: white pawn, black pawn, white king, black king.
// first I create king-king database
// then I create king-2king, 2king-king, king-kingpawn, etc, because these require king-king as well
bitbase[0 ... max_index] = {-128,-128,...,-128} // no data
// calculate "dtm reduce" function = (|dtm| - 1) * (|dtm|/-dtm)
// this just means if you know pos x is "win in 1" and you retro-move to position y from position x, then position y may be "lose in 2"
// so next_dtm[win in 1] = lose in 2, etc
next_dtm[127] = -126
next_dtm[126] = -125
...
next_dtm[-127] = 126 // calculate in a loop (of course next_dtm is stored [0...255] in real life, but ignore that for now)
// finally, this loop is run for each database to create, e.g. once for K-K, once for K-KK, etc (is this correct?)
for index = 0 to number_of_positions // (inefficient) index includes which side to move, as well as position of pieces K-K or K-KK, etc
{
decode(index)
best_scenario = -128 // no data
generate moves
foreach move
{
domove
this_index = encode
// do we ever care if the move was a capture or not?
lookup = bitbase[this_index];
// all lookups to bitbase[] should be simplified to be part of evaluate() calls?)
if (lookup != -128)
best_scenario = max(next_dtm[bitbase[this_index]], best_scenario)
else
{
evaluate() // calculate black_wins, white_wins, etc
if (black_wins && black_just_moved) || (white_wins && white_just_moved)
best_scenario = 127; // win in 1 -- this is max already
else
best_scenario = max(best_scenario, 0); // draw
// we do not seek for a lose in 1 (-127) because the mechanics of the game are such
// that when we have a K-K position, there will always be at least a drawing move
}
undomove
}
bitbase[index] = best_scenario;
}
Am I thinking too hard? Am I missing something important? Am I Doing It Wrong? Thanks!
Also, I'm wondering, has anyone thought about making an endgame solver (or perhaps a complete engine) for a generic variable size board game, given a rule file which can incorporate any kind of rules, from chess to checkers to fairy chess to this game? Of course it would not be as powerful or as fast, since the type of game gives you all kinds of shortcuts you can take...
Phil
edit: Adjusted code - draw should be = max(0, best_scenario) not = 0
