Endgame bitbase / tablebase compromise?

[clgd]

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]

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.

[michiguel]

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

[Bill Rogers]

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]

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.

[hgm]

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]

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]

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.

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]

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.

[sje]

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.