Effect of symmetry on tablebase size

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

Effect of symmetry on tablebase size

Postby QuakePhil » Thu Oct 20, 2011 6:10 pm

So now that I have my very first endgame generator working in the most primitive way possible (for a turkish checkers variant) I would like to learn how to reduce the size.

For example, my current 3-piece egtb weighs in at around 200MB (5mb compressed) which, comparing to chess egtb, is on the order of 6 magnitudes too big! I would like to get it into the kilobyte range.

In order to do this, I need to understand how symmetry applies to tablespaces. I understand that you can place a rook (for example) on a 1/8 slice of the 8x8 board, and that is sufficient to express all the other 7/8 slices by doing some kind of symmetry or rotation. So you only need an index function 1/8 the size of the board. What I don't understand is, how does this work for more than one rook?

P.S. The turkish chess variant consists of two pieces - kings (which move and capture identically like rooks, with the only difference being that when they capture, they can continue capturing if there's more to capture) - and pawns (which move one square left/forward/right (not back) and capture adjacent pieces in the same three directions)
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Effect of symmetry on tablebase size

Postby Arpad Rusz » Fri Oct 21, 2011 1:27 am

If there is a pawn in a position you have only left-right symmetry. It is enough to save positions with the pawn on the left side of the board.(With more pawns you place the first pawn on the left side.)
The pawnless positions have 8-fold symmetry so you always place one of the white kings on a1, b1, b2, c1, c2, c3, d1, d2, d3, or d4.

But the problem you have is probably not related to symmetries: the tablebase sizes are too big. The question is what data you save about a position and what structure has your tablebase? You should have only the depths in a tablebase (and not even the positions)!
Arpad Rusz
 
Posts: 93
Joined: Mon Mar 27, 2006 5:33 pm
Location: Romania/Hungary

Re: Effect of symmetry on tablebase size

Postby QuakePhil » Fri Oct 21, 2011 4:39 pm

Currently my tablebase is indexed using the side-to-move information which is probably not required? And also the last piece moved square - information necessary for move generator because if this last piece can be captured, then it must be captured.

The size is calculated like this (the 65 factor is the last piece move square, including -1 if it doesn't exist, which now that I think about it, should never be, so actually this factor whoult be 64 at most...)

2*65*product(64,piece count)
So for two pieces its 2*65*64*64 bytes - half a MB :(
For three pieces its ~32 MB

Now for two pieces my dumb generator requires WW and BB tables, so its:
WB + WW + BB = 1.5 MB

Then for three pieces its WWB + WBB + WBb + Wbb + WwB + wwB = 195 MB :(:(
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Effect of symmetry on tablebase size

Postby QuakePhil » Fri Oct 21, 2011 4:46 pm

Actually just thinking about it the 65 factor should be reduced to n where n is the number of enemy pieces...

So I think I can already reduce the size to 6 MB, and to 3 MB if I only need one side... And that's without symmetry. (And for 4 pieces it looks like it'll be ~878MB...)

I still don't understand how, even without pawns, how more than one piece works in symmetry... Does the indexing function store a factor 1..8 which is how many times to rotate the piece?
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Effect of symmetry on tablebase size

Postby Arpad Rusz » Fri Oct 21, 2011 5:53 pm

In a pawnless tablebase the (first) White King always goes to the following squares:

8/8/8/8/3K4/2KK4/1KKK4/KKKK4 b - - 0 1
8/8/8/8/3K4/2KK4/1KKK4/KKKK4 b - - 0 1

So you will have a factor of 10 for that piece instead of 64.

But what if during generation the wK moves out of the triangle? Then you should rotate/flip the position in a way that the White King is back again in the triangle so you can probe the position.
Arpad Rusz
 
Posts: 93
Joined: Mon Mar 27, 2006 5:33 pm
Location: Romania/Hungary

Re: Effect of symmetry on tablebase size

Postby QuakePhil » Fri Oct 21, 2011 7:00 pm

Yes the 1 piece scenario is clear for me, as I mentioned before.

What's not clear for me is how it works with a 2nd piece. For example, how do you introduce the black king while having the space saving from symmetry?
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Effect of symmetry on tablebase size

Postby QuakePhil » Fri Oct 21, 2011 7:06 pm

For example, when I have this position:
7k/8/8/8/8/8/8/K7 b - - 0 1
7k/8/8/8/8/8/8/K7 b - - 0 1
I have a factor of 10 for the white king, but I still have a factor of 64-1 for the black king, correct?
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Effect of symmetry on tablebase size

Postby Arpad Rusz » Fri Oct 21, 2011 9:13 pm

If the wK is on b1, c1, c2, d1, d2, or d3, then yes, you have 63 squares for the bK.
If the wK is on the long diagonal, you may choose to place the bK only above the a1-h8 diagonal, to reduce that number to 35.

kkkkkkkk/kkkkkkk1/kkkkkk2/kkkkk3/kkkk4/kkk5/kk6/K7 w - - 0 1
kkkkkkkk/kkkkkkk1/kkkkkk2/kkkkk3/kkkk4/kkk5/kk6/K7 w - - 0 1
Arpad Rusz
 
Posts: 93
Joined: Mon Mar 27, 2006 5:33 pm
Location: Romania/Hungary

Re: Effect of symmetry on tablebase size

Postby syzygy » Sat Oct 22, 2011 11:39 am

QuakePhil wrote:Currently my tablebase is indexed using the side-to-move information which is probably not required? And also the last piece moved square - information necessary for move generator because if this last piece can be captured, then it must be captured.

I'm not familiar with the rules of Turkish checkers, so I looked it up here. It seems familiar to international draughts (except that draugts is played on the black squares of a 10x10 board and pieces move diagonally).

In these games, a piece can make multiple captures in one ply.

What you are trying to do, is encode positions after each capture, i.e. after "sub-plies". As a result, you need to encode the piece-that-is-moving. This is very very suboptimal.

What you should do, is encode only positions after a full ply. That way you only need to encode the positions of the pieces and the side to move.

For three pieces, this will give 2 x 64 x 64 x 64 = 524288 values, or less if you optimise further.

For further optimisation, let's say white has two pieces and black has one piece. You can always mirror the black piece to the left side of the board, which gives 32 possibilities for black. Since pieces are identical, you can also interchange the two white pieces so that the square index of the first white piece is lower than the square index of the second white piece, leaving 64*63/2 possibilities. Since the black piece was already placed on the board, this can be further optimised to 63*62/2. In total, this results in 2 x 32 x 63*62/2 = 124992 values to be stored.

Hmmm, I guess this is still not complete: regular pieces cannot occupy the first rank, nor the last rank. So you can further reduce to 2 x 24 x 47x46/2 = 51888 values. (Of course you need separate tables for white regular pieces plus king versus a black regular piece and for the other possibilities.)

For generation I would advise to use a simple 2 x 32 x 64 x 64 indexing scheme. This is much faster and easier to program with. Then when storing to disk you re-index to a more optimised scheme (and possibly add compression).
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: Effect of symmetry on tablebase size

Postby syzygy » Sat Oct 22, 2011 12:15 pm

QuakePhil wrote:Then for three pieces its WWB + WBB + WBb + Wbb + WwB + wwB = 195 MB :(:(

If you have WWB, you don't need WBB since you can simply change the color of all pieces and the side-to-move.

Assuming W stands for white king, w stands for white pawn, I get:

wwb: 2 x 24 x 47x46/2 (place b first, then ww)
wwB: 2 x 32 x 48x47/2 (place B first, then ww)
Wwb: 2 x 24 x 47 x 62 (place B first, then w, then W)
WwB: 2 x 24 x 63 x 62 (place w first, then W, then B)
WWb: 2 x 24 x 63x62/2 (place b first, then WW)
WWB: 2 x 32 x 63x62/2 (place B first, then WW)
For a total of 670176 values, if I didn't miss anything.

Take some time to see how I arrive at those numbers.
In general, placing two identical pieces on N available squares can be done in Nx(N-1)/2 ways. For wwB, I placed the B first on one of the 32 squares of the left side of the board. I then have either 47 of 48 squares available for ww, depending on the rank I placed the B on. To keep it "simple", I take 48 squares. To get a slight further optimisation, I could consider these cases separately and get 2 x 8 x 48*47/2 + 2 x 24 x 47*46/2 = 69936 instead of 2 x 32 x 48x47/2 = 72192.

In general, removing each and every broken position (with two pieces on 1 square) is not terribly important, since compression will take care of those anyway. Removing as much symmetry as possible is important though, since compression will not be able to recognise symmetry.
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: Effect of symmetry on tablebase size

Postby QuakePhil » Mon Oct 24, 2011 4:58 pm

syzygy wrote:What you are trying to do, is encode positions after each capture, i.e. after "sub-plies". As a result, you need to encode the piece-that-is-moving. This is very very suboptimal.


Not quite.

While it's true that in my engine I've broken down single-ply captures that involve multiple captures into sub-plies, in other words a1xa3xa5 is actually represented as 2 plys worth of moves: move a1xa3 (with same side to move) and then move a3xa5 (with next side to move). However, the tactical square information is still required - whether you are doing multiple ply captures or single ply captures. It is part of the rule (of this particular variant, not of turkish checkers in general) that if you are able to take the piece which moved last, then you are required to take (and any other moves are illegal) This rule applies after any kind of capture or quiet move.

Also I still need the "sub-plies" positions because these can be valid single-ply captures also. In other words, while it may save space to encode a1xa3xa5 as a1x...xa5, you won't actually save any space because you will still need to encode this position for the capture a3xa5, etc.

W stands for white rook (the kings move like rooks and capture like rooks) and w stands for pawn (the pawns move like the pawns in turkish checkers - 1 space forward or to the sides, and capture by hopping over a single adjacent piece forward or to the sides, with multiple captures possible)

The tip about WBB vs WWB is very good, I will use that! It sheds light on the "only one side computation is required". As you say, this is applicable in general, so WwB can become BbW, etc. This should effectively halve the size of tablebases. Thanks!

The pawns cannot occupy the 1st and last rank, correct, so there's no reason to ever place them there, I've already figured this out myself (but have not implemented) - this is actually the case for both white and black pawns, since all pawns start on their 2nd and 3rd rank, and can never move back.

For starters I will implement these simple improvements (and the removal of the full 65 tactical square factor) which should dramatically improve size. Thanks again!
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Effect of symmetry on tablebase size

Postby syzygy » Mon Oct 24, 2011 9:17 pm

QuakePhil wrote:While it's true that in my engine I've broken down single-ply captures that involve multiple captures into sub-plies, in other words a1xa3xa5 is actually represented as 2 plys worth of moves: move a1xa3 (with same side to move) and then move a3xa5 (with next side to move). However, the tactical square information is still required - whether you are doing multiple ply captures or single ply captures. It is part of the rule (of this particular variant, not of turkish checkers in general) that if you are able to take the piece which moved last, then you are required to take (and any other moves are illegal) This rule applies after any kind of capture or quiet move.

So if black can capture the piece that white moved last, black must capture that white piece?

In that case, what you should do is only store information for positions (or rather "game states") for which the piece that moved last cannot be captured by the side to move. For those positions, your probing code should just play out the forced capture (or forced captures) and probe the table for the resulting quiet position. The quiet positions are defined by the board position plus side-to-move and don't need a last-piece-that-moved.

This way you get the reductions I proposed.

The tip about WBB vs WWB is very good, I will use that! It sheds light on the "only one side computation is required". As you say, this is applicable in general, so WwB can become BbW, etc. This should effectively halve the size of tablebases. Thanks!

And in symmetric cases such as WWBB, WwBb, wwbb you only need to store positions with white-to-move.
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: Effect of symmetry on tablebase size

Postby h.g.muller » Tue Oct 25, 2011 10:19 am

I am not familiar with building tablebases for checkers (or in general games with mandatory capture). At first glance it seems the 'last piece moved' is part of the game state (like e.p. rights in chess). But you don't need to remember the square, just the piece. So in a 3+3 men tablebase, that would multiply the number of game states only by 3, not 65. In fact you can combine that with side-to-move, so that eve with 4+2 you would only need 6 times the number of board positions, rather than 2 times, as the last-piece-moved identifies the side to move.

But I wonder if this info is always relevant (again, like e.p. rights). If the board position is such that you can make no captures, it is not relevant what the opponent's last moved piece was. If capture is still mandatory even if it is not of the last-moved piece, then in positions with only a single capture the info would also not be relevant.

I wonder how retrograde methods work with mandatory capture. If you unmove from a position where a capture is possible, only uncaptures would be legal. But playing those you can very easily get into positions where you have several captures, which would be unreachable by forward play. Can those be recognized and filtered out? The reason I ask is that I could imagine you don't need toincludelast-moved-piece in the game state at all, by surging ahead (well, backward, actually) by several moves. I.e. adopt the convetion that you only store positions in the tablebase where this game-state indicator is a don't care. If I only store positions without e.p. rights, positions with a 6th-rank Pawn can e.p. uncapture, bringingmeout of the tablebase, but this position then has a mandatory 'double-unpush' reaching back into the tablebase. It seems you have something similarwith mandatory capture: if you play an uncapture, it could bring you to a position where the uncaptured piece was the last-moved one, outside the tablebase if there is now capture choice, but because you now know that this piece is the last-moved one, you can only play unmoves with that (and only to positions where no other captures are possiblefor that side), and keep doing so until you reach back into the tablebase.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Effect of symmetry on tablebase size

Postby QuakePhil » Tue Oct 25, 2011 5:37 pm

I see what you mean now with regards to reducing size -- any positions which are "forcing" need not be stored/indexed. If I'm understanding that correctly, but then it smells to me like complicated bug prone code for unknown amount of space saving... Definitely something to try but at a later stage.

Regarding retrograde methods with mandatory capture, this is actually a part where I got a bit stuck myself. But I see your point. When a piece uncaptures backwards, it doesn't really matter wether that capture would have been forced or not. But I haven't marinated on this long enough to understand it yet. To be sure, the forced captures are critical to convert a win, for example in WBB, first black sets white up so that white is forced to capture one of black's pieces, with black re-capturing on the next move and winning with one king to zero pieces.

I did not yet do true retrograde analysis :) My code is using the forward move generator (and is therefore probably a lot slower than it should be?) and it looks something like this:

Code: Select all

function build(wpawns,bpawns,wkings,bkings)
   {
   n/a_count = n/a_count_last_pass = 0;
   do
      {
      n/a_count = build2(...);
      if (n/a_count == 0)
         return 0; // everything has been calculated
      
      if (n/a_count > 0 && n/a_count == n/a_count_last_pass)
         return 1; // nothing new being calculated
      
      n/a_count_last_pass = n/a_count;
      }
   while (n/a_count > 0);
   return 0;
   }

function build2(wpawns,bpawns,wkings,bkings)
   {
   for (each position in this pawns + kings setup)
      {
      if (dtm[position]) != n/a) continue;
      decode(position);
      generate_moves(position);
      sofar = n/a;
      all_moves_known = 1;
      if (no moves)
         {
         evaluate(); // this should be a basic "decision()" with no positional calculations, just basic q: does each side have material?
         if (player which just moved has won)
            sofar = lose in 0; // reversed because this is only ever probed from one move up
         else if (player which just moved has lost)
            sofar = win in 0;
         else
            sofar = draw;
         }
      else for(each move)
         {
         do_move();
         probe = encode_and_test();
         if (probe != n/a)
            {
            if (same side to move)
               sofar = MAX(-next_dtm[probe], sofar); // -next_dtm will transform "win in 1" to "win in 2", "win in 2" to "win in 3", etc
            else
               sofar = MAX(next_dtm[probe], sofar); // next_dtm will transform "win in 1" to "lose in 2", "lose in 2" to "win in 3", etc
            }
         if (probe == n/a)
            {
            if (K-K)
               {
               evaluate();
               if (player which just moved has won)
                  sofar = MAX(win in 1, sofar); // MAX(win in 1, win in 0) will return win in 0
               else
                  sofar = MAX(draw, sofar);
               }
            else
               all_moves_known = 0;
            }
         undo_move();
         }

      if (all_moves_known == 0) // here comes the really bonehead part
         {
         if (sofar > 0) // if "win in x"
            { // preserve known wins for side to move (losses don't work)
            ; // this way subsequent passes will calculate longer winning variations
            } // until there is no more to calculate
         else
            sofar = n/a;
         }

      dtm[position] = sofar; // store dtm
      }
   return number_of_n/a_stored_this_pass;
   }

dtm[200MB] = {n/a,n/a, ... , n/a}; // lol, this will be 2MB with the space savings discussed in this thread
build(0,0,1,1); // K-K
build(0,0,2,0); // KK- // for positions rechable from KK-K
build(0,0,0,2); // -KK // e.g. W - B W - - - - ; white to move
do {
  loops = 0
  loops += build(0,0,2,1); // KK-K
  loops += build(0,0,1,2); // K-KK
  loops += build(0,1,1,1); // K-Km
 // etc...
  if (loops > 0 && loops == oldloops)
     break;// infinite loop break // can occur because not all dtm are reached
   // because of stupid stuff like pawns on 8th rank, etc... // ideally this should never happen

  oldloops = loops;
} while (loops > 0);
QuakePhil
 
Posts: 14
Joined: Fri Sep 23, 2011 7:31 pm

Re: Effect of symmetry on tablebase size

Postby h.g.muller » Tue Oct 25, 2011 8:35 pm

OK, doing only forward moves would indeed avoid many of the problems that troubled me. And it would already greatly speed up the process if you could limit the generation of forward moves to positions that at least have a chance to become decided, because they are conceivably a predecessor of some position that was decided on the previous iteration. It does not hurt if accidentally you identify too many positions as possible predecessor, because those that on closer inspection would not be predecessors, will simply not find a legal move to the position that was decided. So you might generate forward moves in vain there, which you might have been able to prevent by being smarter in recognizing valid unmoves, but it will never lead to an error, and will always be better than treating every position.

So as soon as a position becomes decided, you could generously generate unmoves and uncaptures from it, without worrying if they would really be possible, and use those to somehow mark to be visited in the next iteration (if they were not already decided). It just means you need to set apart 2 DTM (or whatever metric you use) codes to label undecided positions: those to be skipped, and those to try forward generation. If forward generation would only lead to decided positions (losing side) or to at least one decided position (winning side) with a DTM smaller than the one you are now assigning, it hets decided, (and you start marking its undecided predecessors as undecided-visit), and otherwise you reset the code to undecided-skip.

The reason I am thinking about problems like this is that I want to build EGTs for Xiangqi. There I have a problem similar to your last-moved-piece, but much worse: it is forbidden to perpetually there, so basically the whole game history becomes potentially part of the game state, because whether in a given board position a certain check will be allowed depends on the previous move(s). Which in retrograde analysis you of course don't know... But the number of possible histories is way too big to include it in the index. So I have no choice other than to ignore it, and assume all positions stored in the tablebase are 'virgin', without any forbidden moves. That means that during generation of forward moves you jump out of the tablebase as soon as you do a checking move, meaning you have to search deeper with minimax, until you do a non-checking move, (and can probe the tablebase again), or reach a repeat (in which case the game ends with a known result).

Deeper forward searches are of course very expensive, and only feasible because you only have to try the checking moves (for the losing side) as a last resort, after all non-checking moves have proved losing. (The winning side will never create repeats, and can be treated normally). And in the search tree the branching ratio is rather small, as one side can only play checks, the other only evasions.

In comparison, your problem is much simpler: when the tablebase only contains non-forcing positions, any forward move that creates a forcing situation needs to be searched deeper before you can probe the tablebase for a result, but the number of replies to the forcing moves will be very small (he will have to capture, and can usually do it in only one way), and if that capture does not create a recapture possibility, you are already back in the tablebase. And in fact you would only have to do this for positions with capture choice,
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Effect of symmetry on tablebase size

Postby syzygy » Wed Oct 26, 2011 12:03 am

QuakePhil wrote:I see what you mean now with regards to reducing size -- any positions which are "forcing" need not be stored/indexed. If I'm understanding that correctly, but then it smells to me like complicated bug prone code for unknown amount of space saving... Definitely something to try but at a later stage.

Well, while probing the tables (after generation) I really don't see a problem. In fact, performing the mandatory capture lands you in smaller tables which are much easier to cache in RAM. And of course the space saving is huge: a factor 65 compared to your current method and a factor n+1 compared to your planned optimisation.

Also during generation I don't see many problems. Positions with mandatory capture can be resolved immediately by probing smaller tables that have already been generated.

If you use the out-counts method, you only have to calculate the results for each of these positions once. So not saving these does not lose anything.

If you use a slow algorithm, then speed is apparently not (yet) an issue, so a few more recalculations won't harm either.

Trying to undo captures seems a bad idea and not necessary, especially since the positions you would arrive at aren't stored anyway (with my method). One can just loop through the index space once to identify all positions with a forced capture and undo those one ply (when using the out-counting method).

It's possible that I'm overlooking something, but as far as I can see it is really manageable.

h.g.muller wrote:If you unmove from a position where a capture is possible, only uncaptures would be legal.

This sentence I don't understand, at least not when I take it literally. Uncapturing lands you in a table with n+1 pieces. There is no need to consider such positions when generating a table with n pieces.

With e.p. this is different if you generate the whole table as a single slice. Using pawn slices you get into the same situation of never having to undo an e.p., so handling e.p. becomes actually very very easy (compared to generating the whole table as a single slice, in which case handling e.p. is only easy).
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: Effect of symmetry on tablebase size

Postby h.g.muller » Wed Oct 26, 2011 6:53 am

I usually build a table together with all possible successor tables, (stored in the broken positions), as my generator is purely RAM based, and doesn't do any disk acces at all. So it has to start from scratch every time.

But even when you build table by table, the problem I sketched would occur when 'seeding' the (n+1)-men table from the n-men table. You have to undo e.p. capture from every position in the successor with a 6th-rank Pawn to get to the table with one more Pawn, and you would get to a position with e.p. rights then. Which is O.K. if you do P-slices, because you can simply duplicate P-slices with neighboring enemy 5th-rank Pawns into one with and one without e.p. rights.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Effect of symmetry on tablebase size

Postby syzygy » Wed Oct 26, 2011 5:07 pm

h.g.muller wrote:I usually build a table together with all possible successor tables, (stored in the broken positions), as my generator is purely RAM based, and doesn't do any disk acces at all. So it has to start from scratch every time.

Do you generate everything as one big table, or do you generate the smaller tables before the larger tables? If the latter, there is not much difference.

But even when you build table by table, the problem I sketched would occur when 'seeding' the (n+1)-men table from the n-men table. You have to undo e.p. capture from every position in the successor with a 6th-rank Pawn to get to the table with one more Pawn, and you would get to a position with e.p. rights then.

It is not necessay to retrograde from an already generated table or (pawn) slice to the table or slice being generated. You can simply loop once through the table or slice being generated and perform the forward moves into the earlier table or slice. You then retrograde from the positions that were solved in this loop.

For regular chess I do in fact retrograde from (non-pawn-)captures in pawnless tables and within pawn slices, but I don't retrograde from pawn moves and pawn captures (instead I perform forward moves).

Retrograding from captures is a good thing, since it is easy enough to implement and it is more efficient as well (given that there will usually be many "capture" positions that result in the same "captured" position). Retrograding from pawn moves is not important from an efficiency point of view: pawn moves and captures are 1-1 or 2-1. An n-piece position with a pawn on c5 can only come from an n-piece position with a pawn on c4. An n-piece position with a pawn on c4 can only come from an n-piece position with a pawn on c2 or c3. For pawn captures it is similar.

In atomic chess (in which a capture also captures the surrounding pieces) retrograding from captures is a terrible nuisance, so I resolve captures by forward moves. Not as efficient, but there is not really a practical alternative.

In Turkish checkers, it seems that forward moves are the practical way to go for resolving captures.
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm

Re: Effect of symmetry on tablebase size

Postby h.g.muller » Wed Oct 26, 2011 8:19 pm

syzygy wrote:Do you generate everything as one big table, or do you generate the smaller tables before the larger tables? If the latter, there is not much difference.

I generate one big table. The original generator just iterated by DTM, first all mates (with any number of pieces), then all mat-in-1 by unmoving from them, etc. Incomplete positions do occur in the indexing scheme, by giving the captured pieces the same coordinates as the white King. I now kludged together a DTC generator from that by initially checking for every decided position if all pieces are present, and if they are, assign it DTM=125, so they are not used to propagate back the DTM=n to DTM=n+1. Then, when I run out of incomplete positions to decide, I change all DTM below 125 to 9, and all DTM=125 to 10, so that 10 now stands for DTC=0, and then continue from there.

It is not necessay to retrograde from an already generated table or (pawn) slice to the table or slice being generated. You can simply loop once through the table or slice being generated and perform the forward moves into the earlier table or slice. You then retrograde from the positions that were solved in this loop.

Indeed, you can do that on every iteration. But it is less efficient.

For regular chess I do in fact retrograde from (non-pawn-)captures in pawnless tables and within pawn slices, but I don't retrograde from pawn moves and pawn captures (instead I perform forward moves).


Well, my current generator doesn't do Pawns at all, because of symmetry. (End-games with Pawns are not really interesting to me; the result almost always depends on what Pawns you have.) The first generator I ever wrote did treat Pawns, though (assuming some default promotion rule). It was not really based on piece slices, but the indexing scheme did use a table of accessible Pawn structures (which were then generated all at the same time). In that generator I had separate elements in the table for pawn structures with e.p. rights. And I treated them by two-ply unmoving.

Retrograding from captures is a good thing, since it is easy enough to implement and it is more efficient as well (given that there will usually be many "capture" positions that result in the same "captured" position). Retrograding from pawn moves is not important from an efficiency point of view: pawn moves and captures are 1-1 or 2-1. An n-piece position with a pawn on c5 can only come from an n-piece position with a pawn on c4. An n-piece position with a pawn on c4 can only come from an n-piece position with a pawn on c2 or c3. For pawn captures it is similar.

In atomic chess (in which a capture also captures the surrounding pieces) retrograding from captures is a terrible nuisance, so I resolve captures by forward moves. Not as efficient, but there is not really a practical alternative.

In Turkish checkers, it seems that forward moves are the practical way to go for resolving captures.

I agree; forward moving is a much more robust method, and quite easy to implement. Unfortunately it is also quite slow. Interesting you did atomic. Did you publish any statistics for 3-5-men endings for that? It should not be that hard to uncapture in atomic, though. Just generate an unmove from every empty square of every position with at least two missing pieces of opposite side, and put the other pieces in all possible maners around the capture square, leaving the square on the unmove trajectory vacant. I agree that is a lot of pre-decessors for every single position, but as the new pieces must all cluster around the capture square, I guess it is still only a very small fraction of the positions in the predecessor table (which you would have to treat all if you were doing this by forward moving). The number of predecessors is mainly so large because you jump directly in tables with n+2, n+3, ... men, which are hugely larger.
h.g.muller
 
Posts: 216
Joined: Mon Feb 19, 2007 8:24 am
Location: Amsterdam

Re: Effect of symmetry on tablebase size

Postby syzygy » Sun Mar 11, 2012 9:19 pm

h.g.muller wrote:Interesting you did atomic. Did you publish any statistics for 3-5-men endings for that?

It seems I never quite finished converting my old generator for pawnful endings to atomic. I've now implemented a new generator and have just generated the statistics for atomic 3-5 endings. Here they are.

The metric used is DTZ50+: a win or loss in x>100 plies is drawn by the 50-move rule. Either it takes x plies to a winning or losing zeroing move, or it takes x-100 plies to a zeroing move that leads to a position drawn by the 50-move rule.

It took 80 minutes to generate all endings and extract the statistics on my new laptop (i7-2670QM, 2.2ghz, 4 cores / 8 threads). Compressing and saving the results would have taken quite a bit longer, but I already did that before I implemented saving the statistics to disk. Compressed they are currently 501MB in WDL50+ and 2291MB in DTZ50+ (for regular chess I get 460MB and 1952MB).

The DTZ50+-files don't store the information that is already present in the WDL-files, which gives a nice space reduction. I will probably further reduce the DTZ50+-files by keeping only information for 1 side to move and setting all values <= 10 or so to the same value.
Attachments
atomic345_stats.txt
(262.51 KiB) Downloaded 156 times
syzygy
 
Posts: 162
Joined: Sun Aug 03, 2008 4:02 pm


Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 1 guest