Author: Shane Hudson
Date: 14:00:14 12/23/01
Hi all, I have a few ideas regarding practical generation and use of 3-vs-3 endgame tablebases. The following discussion is fairly technical so it probably only interests those with some knowledge of tablebase indexing methods. Currently, for 3-3 Nalimov TBs, only pawnless ones where (at least) one side as two like pieces have been generated, and others seem infeasible for now. Most existing 3-3 TBs are probably not that useful (how often will a search reach KQR-KNN?) but 3-3 TBs with one pawn per side would be extremely useful to humans who like endgame study (such as myself) and chess engines alike. Of course, it would be great to have complete unrestricted TBs for these one-Pawn-per-side endings, but since they are not yet feasible, why not generate and use a practical subset in the meantime? The main idea is to generate a TB for 3-3 endings where each side has one pawn and a promotion before the next capture is impossible -- namely, where the pawns oppose each other on the same file. So this includes wPe2 vs bPe7 but not wPe6 vs bPe4. There are ten such endgame classes: KQP-KQP, KQP-KRP, KQP-KBP, KQP-KNP, KRP-KRP, KRP-KBP, KRP-KNP, KBP-KBP, KBP-KNP, and KNP-KNP. This amounts to 16 wtm/btm files since 4 of them are symmetrical. Of these, all except perhaps the Q-B and Q-N cases are of very high practical importance. I'll distinguish two categories, one a subset of the other: (a) Rammed pawns (where there are no ranks between them), e.g. wPe4 bPe5. (b) Opposing pawns (where there may be ranks between them) eg wPe4 bPe7. So rammed pawn (I'll call them "m" since r denotes rook) positions are a subset of opposing pawn ("o") positions. Since first thinking about generating TBs for these cases, I noticed that Ernst Heinz (in a 1999 ICCA Journal article) noted the potential for 6-man TBs for the rammed pawns case, but I have not yet seen any mention of the case for an opposing-pawns tablebase - but I don't subscribe to the journal. First, consider generating the 10 EGTBs "KxP-KyPm" where x and y are (non-pawn) pieces and the m denotes rammed pawns. These could be indexed exactly as for the 5-man equivalent KxP-Ky, since the stm pawn location specifies where both pawns are. Actually, the index could be smaller since ram formations with the stm pawn on its 7th rank are impossible, but it would be easier to just allow this redundancy and use the equivalent 5-man indexing. The changes required to Nalimov's code to generate and use such rammed pawn 3-3 TBs would be rather easy, and they would require far less time and space to generate than any other 6-man TB done so far. Of course, it would be even better to generate TBs for the larger set of opposing pawn positions: "KxP-KyPo" where x,y are non-pawns. A few quick database searches indicated about 1 in 6 of all KxP-KyP positions reached have opposing pawns, so these would be a huge benefit compared to only generating rammed-pawn TBs. How much effort would these require? They would be about 2.5 times the size of their KxP-Ky counterparts (since there are 120 opposing pawn formations [a2-a3, a2-a4, ... h5-h6, h5-h7, h6-h7] compared to 48 single pawn formations). Compressed, the factor may be lower than 2.5 since I'd expect both broken and drawn positions to be more common for the 3-3 opposing pawn TBs than for the 5-men TBs. This would require more work to do than rammed-pawn TBs, since an indexing scheme for the opposing pawn formations needs to be devised. But is not very difficult: I'd favour treating the two pawns as a pair, just as two like pieces of the same color are in current TBs. For example, the index subrange for KRP-KRPm for wKa1 and bKc1 would be 59 (wR) * 120 (pawns) * 62 (bR), compared to 59 * 48 * 62 for KRP-KR. Pawn-TBs have 1806 king formations, so 1806 * 59 * 120 * 62 is around the order of 800 million positions. This is much lower than the approximately 3 billion positions for some existing pawnless 3-3 TBs, so opposing pawn TBs should require far less RAM and CPU time to generate. Would these opposing-pawn TBs be more useful than the current 6-men TBs? I believe so. While database stats are not a perfect indiactor of engine tablebase use, a quick 500,000-game search I did found the most common existing 3-3 TB ending was only reached in about 20 games while KRP-KR was reached in 4500 games and over 700 of these had opposing pawns. To conclude, it seems clear that compared to the latest generated pawnless 3-3 tablebases, there are alternatives (3-3 with 1 pawn per side and opposing pawns) that are probably a lot more interesting and useful, would take a lot less disk space, could be generated much faster, and with fewer resources. The amount of additional coding is not very large or difficult. So why hasn't anyone done this already? I must be missing something. :-) Cheers, Shane
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.