Computer Chess Club Archives


Search

Terms

Messages

Subject: 3-3 tablebase (with pawns) suggestion

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.35 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.