Author: h.g.muller
Date: 11:50:01 02/11/06
If my engine encounters, sy, a KrpppKrpp end-game, e.g. [D]8/1k5r/6R1/1pP5/pP1K4/P7/8/8 w it would really love to consult a TableBase for this. Of course 9-men table-bases are rather large, but the relevant fragment of it when I am in the situation of the diagram is only a tiny tiny fraction. In particular, the full TB has 48^5 Pawn structures, and only 3 of those can be reached from the given position. Each Pawn structure has 16M positions associated with it, and this is also true after we convert to end-games with a smaller number of Pawns. The total number of Pawn structures reachable without losing the Rooks is about 400. That still makes 6G positions, and making a TB for those positions only during the match (after you know you need these positions, and no others) is currently still out of reach. But it seems an easy task compared to precomputing and storing all 9-men TBs! Somehow I have the feeling that even computing the TB fragment of accessible positions is an enormously wasteful enterprise. If I would do it the usual way, building all TBs to which a certain TB can convert before it, (only the reachable parts, of course) I also build a KrKrpp TB with Pawn structure [D]8/8/8/8/8/8/pp6/8 w and fully analyze the KrKqqr end-game. My intuition as a chess-player tells me that this should be totally irrelevant: if I am trying to determine if the one-pawn advantage I have is enough to win me the game, I don't spend a minute on worrying what would happen if I sacrifice all my own Pawns, and let his Pans march all the way to 7th rank, and how I could still save the day after letting all that happen. So this brings me to the point of this posting: in a tree search I would use something like alpha-beta pruning that tells me that the situation is so bad that it is not worth looking at. A TB is build working your way back from all possible game ends (winning conversions or checkmates) without taking into account if it would be possible to steer away from this end. For KqpKp it would start putting KKq mates on the board and be supprised that the retrograde tree of wins for black that originates there would die out long before any of its branches reaches KqpKp. Wouldn't there be a way to prune generation of TBs? If my goal is not to build a TB that lists the DTM of any position, but just the DTM of ONE given position (and along the path from it towards the predicted mate), this might save enormously. Even within the subset of the TB of positions that could be theoretically reached, one could start growing retrograde trees from final positions that seem a reasonable goal for the strong side to strive for. This might be enough to mark the given state as won, and retrograde trees grown from unrealistically good or bad final goals might not have any effect even on the DTM. [D]8/4k3/8/5K2/3pP3/3P3p/7P/8 w For instance, a KpppKpp end-game where white can force queening of his passer while the black pawns are blocked can end in a KqqqK mate. But most likely it is quicker to not hunt for pawns and extra queenings, and use the first queen you have for a quick mate. Even if you would treat any conversion out of KqppKpp as a loss for white, white still easily secures a win. There is no need to leave the KqppKpp TB, retrograde trees grown from the checkmates within this ending extend to the current situation. In particular there is no need to worry about what would happen if black queens. The example is so simpe that a normal search with hash would probably also solve it (effectively building the required TB fragment in its hash table), ut a forard search is a very inefficient way to make a TB. So for examples at the edge of the feasible the retrograde approach might be very superior. Note that a TB does not have to be filled strting with ALL checkmates, followed by all mate-in-ones, then all mate-in-twos, etc. That's just the most eficient way if you want to find al those mates-in-N anyway. But it is perfectly sound to start from a subset of the checkmates, forget about others, and work back from there. This gives you an upper limit to the DTM. If you are not happy with the upper limit the position of interst has so far, you can then add a few checkmates (or other winning conversions) that you did not consider before. This lowers the DTM along the retrograde trees that grow from there, and those trees might die out before you reach the position of interest (in which case your hunch that you could ignore them proves true), or the extend to it (in which case the threat of the added mates lowers the DTM of your current position, or even bring it down from infinity to below 50). all the states that get an altered DTM you would revisit, and this represent extra work. But if you did a good job in selecting the mates that you started with, the poitions that you never visit can be much more numerous. KpKqq is not a small TB compared to the fragment of KpppKpp that is reachable! I am just thinking aloud, and would love to hear any comments on my ravings... ;-)
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.