On-demand tablebase generation

[Evert]

Leonidas has a special heuristic evaluation function for mating a lone king, which encourages driving the king to the edge of the board (and to a corner of the bishop colour in KBNK) and bringing the attacking king as close as possible to the defending king (but also closer to the centre).

This works well for endings with orthodox chess pieces: combined with the search this is sufficient to deliver mate in KBNK, KBBK, KQK and KRK (with a bit more difficulty). However, it had more of an issue with the KKW ending in Spartan Chess. The Spartan Warlord (W) is a N+B compound, alternatively called an Archbishop or a Hawk (in Seirawan chess). This piece is exceptional in the sense that it can deliver mate on its own (without help from the king).

The issue was that at very short time controls the search would fail to efficiently drive the defending king to the edge of the board, which is more difficult than with a piece that can move as a rook where you can always use a combination of cutting off a rank, bringing the king closer and zugzwang. I got fed up with watching the program struggle and sometimes bungle the ending by not finding the mate before the 50 move rule kicked in. I tried tweaking some of the weights in the heuristic, but with very little success. So I decided that it'd be easier to just use a tablebase for this particular ending.

There aren't a whole lot of existing solutions for chess variants with fairy pieces, so I ended up writing my own generator for it, which seemed like a good exercise anyway. The algorithm is fairly stupid, just keep iterating over all positions and update the score based on what is known about its descendants and stop when you no longer update anything, but I can always make it better later. At the moment it also exploits all symmetries of the board to restrict the defending king to the A1-D1-D4 triangle (so no pawns) and it only handles 3-piece endings. It works though, and that was the point.

Generating the tablebase takes a fraction of a second, much less than it takes to solve it by a forward search, so this got me thinking: has anyone ever thought of generating a tablebase on-demand and as-needed? Clearly there comes a point where it would be too expensive and clearly it's not worth doing for all endings, but for some it could be a better use of that ponder time than doing a forward search. Of course, if you have the files on disk you could always use those instead, so in that situation it may be a non-question.

[syzygy]

HGM has been interested in generating tablebases on the fly, see e.g. this post.

[Bloodbane]

Glaurung 2.2 used to generate a KPK bitbase every time it started itself. Not sure how quick the algorithm is though so I don't know if it is suitable for on the fly generation. Maybe you could generate all three-piece bitbases when starting up the program, and then construct additional tablebases on the fly with the 3-man bitbases?

[Evert]

HGM has been interested in generating tablebases on the fly, see e.g. this post.

Interesting how you seem to encounter the same usual suspects again and again.

Seems like a while ago, so I'm guessing nothing came of it...

[Evert]

Glaurung 2.2 used to generate a KPK bitbase every time it started itself. Not sure how quick the algorithm is though so I don't know if it is suitable for on the fly generation. Maybe you could generate all three-piece bitbases when starting up the program, and then construct additional tablebases on the fly with the 3-man bitbases?

I think the bitbase is based on complete heuristics rather than retrograde analysis, but I could be wrong…

Generating all bitbases (other than 3 men) at startup will be too slow for sure, but they'd definitely get used to accelerate generation of other bases.

[michiguel]

Leonidas has a special heuristic evaluation function for mating a lone king, which encourages driving the king to the edge of the board (and to a corner of the bishop colour in KBNK) and bringing the attacking king as close as possible to the defending king (but also closer to the centre).

This works well for endings with orthodox chess pieces: combined with the search this is sufficient to deliver mate in KBNK, KBBK, KQK and KRK (with a bit more difficulty). However, it had more of an issue with the KKW ending in Spartan Chess. The Spartan Warlord (W) is a N+B compound, alternatively called an Archbishop or a Hawk (in Seirawan chess). This piece is exceptional in the sense that it can deliver mate on its own (without help from the king).

The issue was that at very short time controls the search would fail to efficiently drive the defending king to the edge of the board, which is more difficult than with a piece that can move as a rook where you can always use a combination of cutting off a rank, bringing the king closer and zugzwang. I got fed up with watching the program struggle and sometimes bungle the ending by not finding the mate before the 50 move rule kicked in. I tried tweaking some of the weights in the heuristic, but with very little success. So I decided that it'd be easier to just use a tablebase for this particular ending.

There aren't a whole lot of existing solutions for chess variants with fairy pieces, so I ended up writing my own generator for it, which seemed like a good exercise anyway. The algorithm is fairly stupid, just keep iterating over all positions and update the score based on what is known about its descendants and stop when you no longer update anything, but I can always make it better later. At the moment it also exploits all symmetries of the board to restrict the defending king to the A1-D1-D4 triangle (so no pawns) and it only handles 3-piece endings. It works though, and that was the point.

Generating the tablebase takes a fraction of a second, much less than it takes to solve it by a forward search, so this got me thinking: has anyone ever thought of generating a tablebase on-demand and as-needed? Clearly there comes a point where it would be too expensive and clearly it's not worth doing for all endings, but for some it could be a better use of that ponder time than doing a forward search. Of course, if you have the files on disk you could always use those instead, so in that situation it may be a non-question.

Of course, that is the way to go, but it will be done when someone spends time on it. The obvious and simple way is to dedicate on core to build this while the engine keeps playing with the rest. It is in my todo list, but with lower priority than for instance, generating 6-pieces first . Most people are interested in other stuff.

Miguel

[Evert]

Well, I've expanded my generator to four pieces and gave KBNK a go. It's not bug free (it failed to deliver mate and opted for a repetition instead) but I don't generally expect fresh code to be bug-free.

The issue, however, is the speed: it takes about 10 seconds to generate KBNK, which I think would be too long to make it worthwhile. Guess I got bitten by the exponential nature of the game...

[michiguel]

Glaurung 2.2 used to generate a KPK bitbase every time it started itself. Not sure how quick the algorithm is though so I don't know if it is suitable for on the fly generation. Maybe you could generate all three-piece bitbases when starting up the program, and then construct additional tablebases on the fly with the 3-man bitbases?

I think the bitbase is based on complete heuristics rather than retrograde analysis, but I could be wrong…

Generating all bitbases (other than 3 men) at startup will be too slow for sure, but they'd definitely get used to accelerate generation of other bases.

It was discussed before, and it is retrograde. Gaviota uses a lot of heuristics to speed up the generation and complete as much as possible in the first pass, but it is pretty much overkill for nothing. A simple retrograde is so fast that nothing else is needed.

Miguel

[syzygy]

The issue, however, is the speed: it takes about 10 seconds to generate KBNK, which I think would be too long to make it worthwhile. Guess I got bitten by the exponential nature of the game...

Just a small fraction of a second with my generator

[Evert]

The issue, however, is the speed: it takes about 10 seconds to generate KBNK, which I think would be too long to make it worthwhile. Guess I got bitten by the exponential nature of the game...

Just a small fraction of a second with my generator

Nice!
I should study it a bit more. Do you have any idea where the speed comes from? Apart from multiple cores.

I suspect mine is probably slowed down by whatever bug causes the tablebase to not work correctly. Or the algorithm is just too simple and stupid. Or both.