On-demand tablebase generation
Posted: Sun Jan 19, 2014 10:58 am
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.
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.
. Most people are interested in other stuff.