Endgame bitbase / tablebase compromise?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
clgd

Endgame bitbase / tablebase compromise?

Post by clgd » Mon Jul 13, 2009 6:03 pm

I have been wondering about the seemingly stark choice between memory-consuming Nalimov tablebases and smaller bitbases (which do not contain enough information to enable perfect play), and wondered about an alternative. I would appreciate thoughts, since I am not very experienced in these subjects.

For illustration, consider the KNN KN database, where white has two knights. Positions are sorted by a hash table: first by the position of the black knight, the two white knights, and then the white king. Last, for any position of the black king that results in a win or loss, there is stored the position of the black king, whether the position wins or loses, and the ideal next move (not the number of moves to mate). There are at most 16 positions for the black king, assuming we restrict it to a predetermined quadrant, and here no position permits more than 40 possible moves (and only rare setups will allow more than 64), so the terminating node of this hash table has only 11 bits of data.

Based on a past discussion in this forum, there are ~40,000 win/loss positions with this piece set. So, the terminating-leaf data in this table requires ~440,000 bits = 55KB. There is some overhead memory requirement from the hash table, but I think this can be made small (and I suspect that most of the hash tables can be eliminated simply because they are empty). The equivalent Nalimov tablebase requires ~160KB. The sacrifice is that you don’t know how many moves the mate will require, but when it is desired, it is quick to follow moves through the subsequent databases and see how many moves yield checkmate – so that all of the information of a Nalimov tablebase can quickly be gleaned from this smaller file.

How does this strike you all as a middle-ground between bitbases and tablebases?

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Endgame bitbase / tablebase compromise?

Post by wgarvin » Mon Jul 13, 2009 7:51 pm

I vote for bitbases in memory, plus tablebases on disk.

Only the win/loss/draw info contained in the bitbases, is required to guide the search into a won position. Once you reach a position on the board that is actually in the bitbases or tablebases, then the bitbases contain enough information to make sure that you never blunder away to a lesser GTV (win/loss/draw).

The only thing you need tablebases for, is to make progress towards the win when you've achieved a won position already. For which you could load the necessary info from tablebases on disk.

...Or, you could use heuristics combined with the bitbases (like DarkThought team did) to try and make progress. You could also generate a proof database to discover whether your heuristic for a particular ending is good enough to win all winnable positions without falling foul of the 50-move rule (and/or to augment it with extra info to make it good enough; that is starting to sound like a complicated project, though!)

I'm sure this is all doable, but I've had the goal of doing it as a hobby project for about 10 years now and I'm no closer now then I was back then... If you want to be 100% accurate, you need bitbases generated from tablebases that correctly handled en-passant and the 50-move rule, which I don't think any of the current ones do. So the first part of the project would be to generate 100% accurate tablebases using a metric like DTZ50. Anyway, it seems like a lot of work.

User avatar
michiguel
Posts: 6371
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Endgame bitbase / tablebase compromise?

Post by michiguel » Mon Jul 13, 2009 10:44 pm

wgarvin wrote:I vote for bitbases in memory, plus tablebases on disk.

Only the win/loss/draw info contained in the bitbases, is required to guide the search into a won position. Once you reach a position on the board that is actually in the bitbases or tablebases, then the bitbases contain enough information to make sure that you never blunder away to a lesser GTV (win/loss/draw).

The only thing you need tablebases for, is to make progress towards the win when you've achieved a won position already. For which you could load the necessary info from tablebases on disk.

...Or, you could use heuristics combined with the bitbases (like DarkThought team did) to try and make progress. You could also generate a proof database to discover whether your heuristic for a particular ending is good enough to win all winnable positions without falling foul of the 50-move rule (and/or to augment it with extra info to make it good enough; that is starting to sound like a complicated project, though!)

I'm sure this is all doable, but I've had the goal of doing it as a hobby project for about 10 years now and I'm no closer now then I was back then... If you want to be 100% accurate, you need bitbases generated from tablebases that correctly handled en-passant and the 50-move rule, which I don't think any of the current ones do. So the first part of the project would be to generate 100% accurate tablebases using a metric like DTZ50. Anyway, it seems like a lot of work.
Nalimov's don't handle en passant? Are you sure? That would lead to serious blunders. Wouldn't it?

Miguel

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: Endgame bitbase / tablebase compromise?

Post by Bill Rogers » Tue Jul 14, 2009 12:53 am

Miguel
I thought that Nalimov's only had 4 or 5 piece end game positions and in that case enpassant most likely would not exist as a possibility.
I could be wrong but that would be hard to imagine.
Bill :?:

MattieShoes
Posts: 718
Joined: Fri Mar 20, 2009 7:59 pm

Re: Endgame bitbase / tablebase compromise?

Post by MattieShoes » Tue Jul 14, 2009 1:34 am

Bill Rogers wrote:Miguel
I thought that Nalimov's only had 4 or 5 piece end game positions and in that case enpassant most likely would not exist as a possibility.
I could be wrong but that would be hard to imagine.
Bill :?:
3, 4, 5, 6, and perhaps some 7 piece TB's. ep becomes an issue by 4 piece TB's though. I don't recall if ep is supposed to be handled by the engine or the TB though.

User avatar
hgm
Posts: 22896
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Endgame bitbase / tablebase compromise?

Post by hgm » Tue Jul 14, 2009 10:20 am

clgd wrote:How does this strike you all as a middle-ground between bitbases and tablebases?
I don't think storing the best move offers any advantage over storing the DTM. In general there are fewer DTMs than there are possible moves.

Basically you try to take advantage of the fact that the tablebase is very sparse, and are looking for a way to compress it without making access unduly slow. A hash table cod be one way of doing that.

bob
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Endgame bitbase / tablebase compromise?

Post by bob » Tue Jul 14, 2009 12:36 pm

MattieShoes wrote:
Bill Rogers wrote:Miguel
I thought that Nalimov's only had 4 or 5 piece end game positions and in that case enpassant most likely would not exist as a possibility.
I could be wrong but that would be hard to imagine.
Bill :?:
3, 4, 5, 6, and perhaps some 7 piece TB's. ep becomes an issue by 4 piece TB's though. I don't recall if ep is supposed to be handled by the engine or the TB though.
Nalimov handles EP situations correctly. The only thing it does not handle is castling. It assumes that castling is not legal and is broken for positions where castling is possible.

EP is fine, however.

The older Edwards format did not work correctly and you had to avoid probing if an EP capture was possible.

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Endgame bitbase / tablebase compromise?

Post by wgarvin » Tue Jul 14, 2009 5:43 pm

hgm wrote:
clgd wrote:How does this strike you all as a middle-ground between bitbases and tablebases?
I don't think storing the best move offers any advantage over storing the DTM. In general there are fewer DTMs than there are possible moves.

Basically you try to take advantage of the fact that the tablebase is very sparse, and are looking for a way to compress it without making access unduly slow. A hash table cod be one way of doing that.
Storing best move might be better if a heuristic can predict which move is best most of the time, so you only need to store the differences from the heuristic prediction, which should be very compressible.

I'm more interested in that sort of prediction + compression of differences with regards to bitbases, though. The DarkThought team showed that for 4-man bitbases, heuristics were good enough to win pretty much all winnable positions without hitting a 50-move draw. I sort of expect the same to hold true for 5-man ones.
bob wrote:Nalimov handles EP situations correctly. The only thing it does not handle is castling. It assumes that castling is not legal and is broken for positions where castling is possible.

EP is fine, however.

The older Edwards format did not work correctly and you had to avoid probing if an EP capture was possible.
I forgot that Nalimov handles the EP properly, but anyway they are DTM, and the main reason I wanted to do my own was to make DTZ50 ones. I wouldn't want to make bitbases directly from DTM because they could contain "wins" in some positions that can't actually be won, because of the 50-move rule. Maybe only for 6-man endings, but still.

Dirt
Posts: 2851
Joined: Wed Mar 08, 2006 9:01 pm
Location: Irvine, CA, USA

Re: Endgame bitbase / tablebase compromise?

Post by Dirt » Tue Jul 14, 2009 6:33 pm

hgm wrote:
clgd wrote:How does this strike you all as a middle-ground between bitbases and tablebases?
I don't think storing the best move offers any advantage over storing the DTM. In general there are fewer DTMs than there are possible moves.

Basically you try to take advantage of the fact that the tablebase is very sparse, and are looking for a way to compress it without making access unduly slow. A hash table cod be one way of doing that.
I wonder how much space you could save by storing, say, one eighth the distance to mate (truncated). You would have to do a short search to find the best move.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

The new Edwards tablebase format

Post by sje » Wed Jul 15, 2009 12:35 am

bob wrote:The older Edwards format did not work correctly and you had to avoid probing if an EP capture was possible.
The lack of en passant support was noted back in the 1990s in the first publicly released ANSI C generator source. In fact, I seem to recall that one had to explicitly modify the source to bypass the KPKP/KXPKP block.

As part of the Banjo project, I have been designing a replacement tablebase format that would have advantages over the Namilov format, just as the Namilov format handled en passant and my first format did not. One idea here is to have a Banjo server support an endgame adjudication service that included tablebases.

As with my first tablebase format, the revised format will include an open source generator (this time in C++) and accessing routines.

Post Reply