Chess Tablebase: Rook + Pawn vs. Rook + Pawn: For loops?

[GothicChessInventor]

I am just wondering, since Rook + Pawn vs. Rook + Pawn is one of those symmetrical endings, technically speaking, you only have to solve it for white to move. To lookup a black to move result, swap the colors, and place every piece on 9 - its current rank, and that white to move result = the equivalent move for black to move.

Now, for symmetry, I think you only have to let the white pawn roam over half of the squares. Say, the rectangle formed by a7:d7:d2:a2. If the white pawn is elsewhere, flip the board horizontally, and lookup that result, and it should be the same.

I think that's all the symmetry reduction possible, thanks to the lousy en passant rule you have to check for.

So, my question is, is the size of the Rook + Pawn vs. Rook + Pawn database basically:

24 x 47 x 62 x 61 x 60 x 59 = 15,101,979,840 positions? I know this is a simplification since I did not enumerate the en passant entries that are needed.

24 = white pawn within rectangle a7:d7:d2:a2
47 = black pawn within rectangle a7:d7:d2:a2 - 1 square for white pawn
62 = white rook squares - 2 for the 2 pawns already on the board
61 = black rook squares - 3 for the other pieces on the board, etc.

I know the solving order is very important also, placing the pawns near the crowning ranks initially in order to be able to lookup precomputed promotions.

What I want to do is generate a 6-piece database that is not a tablebase, but a bitbase of pre-searched scores to a fixed depth to put into a permanent hash table. So, I'll need to solve it in a very specific order.

I am wondering, does anyone know the solving order/symmetry used for doing the 6-piece tablebase of R + P vs. R + P?

[Edmund]

Your first point is being applied in current state of the art tablebases. If both sides have the same pieces only wtm is generated and for btm wtm is used.

Your second point, reducing the pawns to a rectangle is being used as well.
The general procedere is. For games with pawns always flip the bord, so that the black king in in the e1-h8 rectangle. Only for games without pawns more is possible, where the game is fliped and mirrored, so that the black king is in the triangle e1-e4-h1

Finally, Tablebases are computed retrograd. First you find all positions, where the black king is mated, or white can promote into a won endgame, or white can capture into a won endgame. From this position you will then work your way backward.
So I dont understand, what you mean by "a bitbase of pre-searched scores to a fixed depth", 1) scores can nevery be saved in a bitbase, 2) Tablebases are all about saving all possible positions, to enable perfect play. Not just to a fixed depth.

I am currently working on some Bitbase as well, so if you have any more questions, I could provide you with some code.

[hgm]

Making use of symmetry in the generation of end-game tablebases with Pawns is very counter-productive. Pawny EGTBs are most efficiently built by treating the indvidual P-slices entirely wthout symmetry. The symmetry advantage can be fully reaped by deciding which subset of P-slices to build.

[Tony]

I am just wondering, since Rook + Pawn vs. Rook + Pawn is one of those symmetrical endings, technically speaking, you only have to solve it for white to move. To lookup a black to move result, swap the colors, and place every piece on 9 - its current rank, and that white to move result = the equivalent move for black to move.

Now, for symmetry, I think you only have to let the white pawn roam over half of the squares. Say, the rectangle formed by a7:d7:d2:a2. If the white pawn is elsewhere, flip the board horizontally, and lookup that result, and it should be the same.

I think that's all the symmetry reduction possible, thanks to the lousy en passant rule you have to check for.

So, my question is, is the size of the Rook + Pawn vs. Rook + Pawn database basically:

24 x 47 x 62 x 61 x 60 x 59 = 15,101,979,840 positions? I know this is a simplification since I did not enumerate the en passant entries that are needed.

24 = white pawn within rectangle a7:d7:d2:a2
47 = black pawn within rectangle a7:d7:d2:a2 - 1 square for white pawn
62 = white rook squares - 2 for the 2 pawns already on the board
61 = black rook squares - 3 for the other pieces on the board, etc.

I know the solving order is very important also, placing the pawns near the crowning ranks initially in order to be able to lookup precomputed promotions.

What I want to do is generate a 6-piece database that is not a tablebase, but a bitbase of pre-searched scores to a fixed depth to put into a permanent hash table. So, I'll need to solve it in a very specific order.

I am wondering, does anyone know the solving order/symmetry used for doing the 6-piece tablebase of R + P vs. R + P?

Your calculation is unusual but close to correct.

It should be about 1806*(62*61)*(48*47)=15.409.138.752

2kings*(Rook1*Rook2)*(pawn1*pawn2)

Ep can be handled by not lowering the pawn squares count (and use the squares with 2 pawns on it ) raising the total positions to: 15.736.992.768

Tony

[GothicChessInventor]

Your first point is being applied in current state of the art tablebases. If both sides have the same pieces only wtm is generated and for btm wtm is used.

Your second point, reducing the pawns to a rectangle is being used as well.
The general procedere is. For games with pawns always flip the bord, so that the black king in in the e1-h8 rectangle. Only for games without pawns more is possible, where the game is fliped and mirrored, so that the black king is in the triangle e1-e4-h1

Finally, Tablebases are computed retrograd. First you find all positions, where the black king is mated, or white can promote into a won endgame, or white can capture into a won endgame. From this position you will then work your way backward.
So I dont understand, what you mean by "a bitbase of pre-searched scores to a fixed depth", 1) scores can nevery be saved in a bitbase, 2) Tablebases are all about saving all possible positions, to enable perfect play. Not just to a fixed depth.

I am currently working on some Bitbase as well, so if you have any more questions, I could provide you with some code.

Hello,

Thanks for your remarks. I am doing things a little bit differently than pure tablebase generation. First off I would like to state that I've generated large endgame databases for the games of checkers, chess, and Gothic Chess already... I just wanted to double check my "estimate" for the size of the 8x8 chess endgame for R+P vs. R+P.

And now, I would like to solve R+P vs. R+P for the game of Gothic Chess on an 80 square board. I would like to do this without having to precompute all of the other piece combinations first, otherwise this would take about a century.

So, in a way, the end result will be a bitbase because I will compress the results to only win, loss, draw, or unknown. My approach would be:

1. Solve all of the mates in 1 that could be solved (imperfect information is present with some promotions not leading to immediate mates although they could win material or gain significant material.)

2. Iterate and find mated-and-mate positions until no more can be resolved (much quicker since there is imperfect information and the iterations won't persist as long.)

3. Recurse over the database examining only promotions, but switch from retrograde analysis to forward searches. (This will allow me to do 3-ply searches to find promotion mates, 4 ply searches for mated-in-2 positions, 5 ply searches for mates in 3, etc.)

At some point there would be a cutoff factor, maybe around ply 13 or 15, where the search time x number of unsolved positions really starts to balloon. If the scores are within the absolute value of some number, I set them to "unknown", outside of this, I code them as ad hoc wins or losses.

I then compress this data for run-time probing. If the position is encountered during the search as a leaf node, and the positon is being searched LESS THAN the depth I have done for the calcuation, I use my precomputed information. If the depth is deeper, I use the evaluation score and send it back down the tree.

[hgm]

I am not sure this could ever be competative. Aren't you a bit over-pessimistic about the time it would take to generate daughter EGTBs? Seems to me you need only KQRKRP, KCRKRP and perhaps KQRKQR. The other's don't count, really, being 80 times smaller.

[GothicChessInventor]

I am not sure this could ever be competative. Aren't you a bit over-pessimistic about the time it would take to generate daughter EGTBs? Seems to me you need only KQRKRP, KCRKRP and perhaps KQRKQR. The other's don't count, really, being 80 times smaller.

Well H.G., I'm going to give it a shot without computing any of the "required" predecessors first, and see what happens. Of course, I will have the capture conversions solved with perfect information in isntances where 1 pawn can be won, or the pair of pawns can be unavoidably traded. This seeds good information. The forced mates that occur are good information. Immediate mates via pawn promotion will be good information.

As I perform the forward search, I have the ability to probe this data in RAM. Of course, I will begin with white to move and a pawn on the 7th rank, the white rook behind the passed pawn, and the black rook and king as distant from both as possible. The for-loops can be constructed in any fashion, as long as all positions are visited with each database iteration. The earlier a position is resolved with perfect information, the sooner it can be made available for other searches and assist with computing losses for the other side to move. Of course, you only iterate over unsolved positons, so the more you solve, the quicker the rest of it goes, until you can't resolve any more.

There is always the chance that a vast majority of the interesting positions will not be able to be resolved, but I can live with that. I was just surprised how often this 6-piece slice is encountered during the search, and anything is better than making a guess with a leaf node evaluation.

[hgm]

I am a bit afraid that the cost of the forward searches will get out of hand pretty quickly. The branching ratio in these end-games (after promotion) is enormous. Doing a 5-ply alpha-beta search from each promoted position might very well be more demanding than calculating the full EGTB by retrograde analysis.

The demands on memory is very low, though, as you can do the computation P-slice by P-slice. So it an be done entirely in RAM, and if you nest the for loops for scanning the TB cleverly, you can even make sure that all the probes will go to entries that were cached anyway in the process of the sequential scan.

I am not contesting the usefulness of this particular EGTB. My approach (for Joker), however, will be to generate the EGTB on the fly, as soon a the search starts probing it. It should be possible to do this very fast, as by that time you know which P-slices you need, the vast bulk of them remaining forever unreachable from the position you have at the root.