Wu / Beal retrograde analisys algorithm

[Alvaro Jose Povoa Cardoso]

Hi everyone,
I would like to implement this memory-efficient retrograde analisys algorithm witch uses one bit in ram for every position.
Does anyone have or knows source code for this one?

Can someone explain the ProveSucessor() function in the pseudo code below?

best regards,
Alvaro

Code: Select all

DATABASE W, B; // full databases (i.e. depth to win/loss for each position),
// W for White-to-move positions, B for Black-to-move,
// sequential access only
SBITS S; // sequential access only bitmap
RBITS R; // random access bitmap
void TopLevel
{
   DoInitialize();
   n = 0; // depth to mate or conversion
   while (!DoneWhite() && !DoneBlack())
   {
      if (!DoneWhite()) // last pass added new positions
      {
         S = Load(W, WIN_IN_N(n)); // S = WTM win_in_n
         R = Predecessor(S); // R = BTM predecessors of S
         S = Load(B, UNKNOWN); // S = BTM unknown
         S = S & R; // S = BTM maylose_in_n
         R = Load(W, WIN_<=_N(n)); // R = WTM win_in_n or less
         S = ProveSuccessor(S, R); // S = BTM lose_in_n
         B = Add(S, LOSE_IN_N(n)); // B += S
         if (dtm) // distance_to_mate?
            S = Load(B, LOSE_IN_N(n)); // S = BTM lose_in_n
         R = Predecessor(S); // R = WTM maybe win_in_n+1
         S = Load(W, UNKNOWN); // S = WTM unknown
         S = S & R; // S = WTM win_in_n+1
         W = Add(S, WIN_IN_N(n+1)); // W += S
      }
      if (!DoneBlack()) // done for BTM?
      {
         S = Load(B, WIN_IN_N(n)); // S = BTM win_in_n
         R = Predecessor(S); // R = WTM predecessors of S
         S = Load(W, UNKNOWN); // S = WTM unknown
         S = S & R; // S = WTM maylose_in_n
         R = Load(B, WIN_<=_N(n)); // R = BTM win_in_n or less
         S = ProveSuccessor(S, R); // S = WTM lose_in_n
         W = Add(S, LOSE_IN_N(n)); // W += S
         if (dtm) // distance_to_mate?
            S = Load(W, LOSE_IN_N(n)); // S = WTM lose_in_n
         R = Predecessor(S); // R = BTM maybe win_in_n+1
         S = Load(B, UNKNOWN); // S = BTM unknown
         S = S & R; // S = BTM win_in_n+1
         B = Add(S, WIN_IN_N(n+1)); // B += S
      }
      n = n + 1;
  }
}


[H.G.Muller]

I am not sure how this algorithm could ever compete with the straightforward

Code: Select all

do
  cnt=0;
  for all positions X
    if label[X] == n
      for all white (retro-)moves X->X´
        if mark[X´] == 0
          mark[X´] = 1;
          for all black (retro-)moves X´->X"
            LABEL_GRANDMOTHER
while cnt != 0

LABEL_GRANDMOTHER:
  if label[X"] == UNDECIDED
    label[X"] = n+1; cnt++;
    for all black moves X"->Y
      if mark[Y] == 0
        label[X"] = UNDECIDED; cnt--;
        break;


With the TB organized such that the black pieces scan fastest, all accesses after black moves will typically be cache hits. If some of the moves of the white pieces would be so far away in the TB that they would result in cache misses, You could trivially split the retrograde tree at the root, treating the moves of those white pieces in a TB scan with the X loop scanning those pieces with reversed nesting.

By packing label[] and mark[] in a single byte (i.e. label[X] is TB[X]>>1 and mark[X] is TB[X]&1) this uses only a single byte per position. This means that 5-men TB easily fit in memory. (And some 6-men TB as well, on bigger computers). In that case you can even speed it up more by doing pre-counting of the black escape moves, so that the screening of the potentially lost in n+1 states can be done very quickly:

Code: Select all

LABEL_GRANDMOTHER:
  if label[X"] > n+1
    label[X"]++;
    if label[X"]==0
      label[X"]=n+1; cnt++;


This would require the pre-counting

Code: Select all

for all positions X
  for all black moves X->X´
    if mark[X´]==0
      label[X]--;


(For storing on disk this is probably not recommended, as it makes the data difficult to compress.)

[H.G.Muller]

Can someone explain the ProveSucessor() function in the pseudo code below?

To answer your question, btw, the routine ProveSuccessor(S, R) scans for set bits in S (corresponding to the 'may lose' positions, that are a predecessor of a position that was just resolved as won for the opponent, and were not yet resolved themselves), and tries all moves of the STM from that position. For the positions these moves lead to, it then checks (in the bit set R) if they all lead to positions that are won for the opponent in n or less.

If it is, the bit in S remains set. If there is a single move that leads to a position that is not (yet) won for the opponent (the corresponding bit in R is clear), then it resets the bit in S. So you can stop generating moves after the first 'escape' for the STM that you find.

[Alvaro Jose Povoa Cardoso]

Thanks for your answer,
Alvaro