Boardgame endgame tablebase

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

Boardgame endgame tablebase

Postby QuakePhil » Fri Sep 23, 2011 8:21 pm

I emailed Kirill about an endgame question concerning a game which is not chess, but a boardgame nontheless. Actually, it is a variant of turkish checkers. Anyway, he suggest I post here, so here I am :)

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 :mrgreen: )

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;
   }


Does this kind of code make sense? Currently it calculates a seemingly sane K-K endgame, but I'm having issues with K-KK (for example, it finds only win in 1, and no win in 2, etc, in K-KK, and there's lots of win in 2+...)

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
Last edited by QuakePhil on Mon Sep 26, 2011 12:49 pm, edited 2 times in total.
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Boardgame endgame tablebase

Postby Kirill Kryukov » Mon Sep 26, 2011 6:33 am

QuakePhil wrote: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...

Yes I thought about it, but the amount of work necessary makes it impractical for me at the current moment. Perhaps I'll give it another thought after solving (or failing to solve) 4x4 chess.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: Boardgame endgame tablebase

Postby QuakePhil » Mon Sep 26, 2011 8:34 pm

Another question I have is, in general, what is endgame tablebase verification? What does it mean to verify or not to verify a tablebase? How does automatic verification work, in a perfect world?

I'm guessing it is some kind of "checksum" tes... If so, what's the sum? Or perhaps independent verification of some sort... If so, how does the first endgame generator verify itself? Or maybe verification is something else entirely... If so, what?

I'm guessing if the endgame generator is working "backwards", then the verifier would work "forwards", and for each endgame position determined to have a result (win in X, draw, etc) it would evaluate all moves and see if the calcualted result matches with the determined result? The only difficulty with understanding it this way, is I don't see much a difference in implementing the code (at least if you look at the pseudocode above) so maybe the real question here is, given the above pseudocode, how would you implement automatic verification?

Thanks :)
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Boardgame endgame tablebase

Postby Kirill Kryukov » Mon Sep 26, 2011 11:44 pm

QuakePhil wrote:Another question I have is, in general, what is endgame tablebase verification? What does it mean to verify or not to verify a tablebase? How does automatic verification work, in a perfect world?

I'm guessing it is some kind of "checksum" tes... If so, what's the sum? Or perhaps independent verification of some sort... If so, how does the first endgame generator verify itself? Or maybe verification is something else entirely... If so, what?

I'm guessing if the endgame generator is working "backwards", then the verifier would work "forwards", and for each endgame position determined to have a result (win in X, draw, etc) it would evaluate all moves and see if the calcualted result matches with the determined result? The only difficulty with understanding it this way, is I don't see much a difference in implementing the code (at least if you look at the pseudocode above) so maybe the real question here is, given the above pseudocode, how would you implement automatic verification?

Thanks :)

Yes, in fact your pseudocode resembles verification more than normal solving. If you do solving this way, then you don't need (or at least don't benefit from) verification, since they are the same thing in your case.

What we normally do for solving is working backwards. First you mark all "checkmate" positions. Then you iterate through them, and for each take one move back (in all possible ways) and mark all resulting positions as "win in 1". Next you iterate through "win in 1" positions, take one move back, and get potential "loss in 1". To know if it's really loss in 1 you do forward search one ply ahead and check if all positions are already marked as wins. And so on.

This is called retrograde analysis, and it's usually much faster than solving by forward search.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: Boardgame endgame tablebase

Postby QuakePhil » Tue Sep 27, 2011 12:18 am

I see; the problem with my case is that it is difficult (well, non-trivial) to generate reverse moves. So while I am generating the moves forwards, I am doing the big picture backwards, because first I'm calculating the simplest positions (K-K) and then the positions backwards from that (such as K-KK, KK-K, Kk-K, K-Kk, etc) -- but at least that answers my question about verification :)
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Boardgame endgame tablebase

Postby Kirill Kryukov » Tue Sep 27, 2011 6:24 am

Actually I was wrong to say that you don't benefit from verification in your scenario. Although verification won't help you with solving bugs, it may still catch some other bugs (IO, compression, hardware, etc). So I guess it's still a good idea to implement verification, even if your solver only makes forward moves.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: Boardgame endgame tablebase

Postby byakuugan » Thu Sep 29, 2011 9:14 am

QuakePhil wrote: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



I've had the idea of an "infinite tablebase" where there is no set board size, and it only calculates forward moves. I don't have enough programming experience to say what kinds of programs I would need, but it sounds like it would be pretty simple. There doesn't have to be a board or pieces, the program would just need to keep track of some numbered coordinates (however many pieces there are), rules for how the coordinates change (the x,y notation of a piece's move), and special rules for what is not allowed (such as pieces simultaneously occupying the same square, etc.). Let's say there is an origin in boundless space defined as 0,0, and then the rest of the pieces are defined based on their distance from 0,0. The program will brute force turn-based possibilities by adding/subtracting a possible coordinate choice from a possible piece, but will start with moves in which the coordinate is as close to 0,0 as possible, its logic would be something like: Disregard moves where absolute value of piece's coordinate > 1,1 distance from origin....... When moves run out, go back and only disregard moves where absolute value of piece's coordinate > 2,2 distance from origin, etc. until the moves stop running out and you know a draw can be held, or until a mathematical consistency is discovered so that you know the moves will always run out. This kind of program would probably be optimal for finding theorems between the interplay between just 2 pieces, because there wouldn't be any special rules to implement besides capturing, but it can work for 3-piece endgames, I would like to find patterns for King + Rook vs. King endgames involving a rook that does not move infinitely. (An infinite rook can mate on any size board, but with a rook that can only move a certain number of squares, it is never certain what the largest chessboard is, where mate can be forced from any position.
byakuugan
 
Posts: 40
Joined: Tue May 18, 2010 4:36 am

Re: Boardgame endgame tablebase

Postby QuakePhil » Wed Oct 12, 2011 5:34 pm

I got most of this done now (the endgame without backwards moves) mostly by trial and error :)

I've also written a pretty cool interface to it (inspired by the k4it nalimov browser)

Thank's for the insights here!

My code is pretty gross and slow. If anyone wants, I can clean it up and post it here.

For reference, what is the typical spectrum of endgame calculation times for chess solvers for 3 pieces without symmetry?

RE: The infinite board endgame: I think this would be cool. Understanding chess at the level of piece interactions and "local chunks" is how grandmasters do it, apparently, so if we could take that human strength and somehow apply it with the brute force of rigorous calculation that computers have, perhaps chess can be solved after all!...? :)
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Boardgame endgame tablebase

Postby QuakePhil » Wed Oct 12, 2011 5:45 pm

Of course next step would be to make sure the database makes full sense, and then (or at the same time) to find the longest wins, and funky positions, and that sort of stuff, in order to study the game itself!

:D

If anybody is interested, you can play the game here: http://qw.quakephil.com/giventake/

It is an old build of the engine from a year or so ago, when I put this project on hold until recently restarting it with the endgame stuff. But it works :)
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm


Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 2 guests