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;

}

}