SEE

[micron]

Here is the excellent pseudocode for iterative SEE, from CPW.

Code: Select all

int Board::see ( enumSquare toSq, enumPiece target, enumSquare frSq, enumPiece aPiece)
{
   int gain[32], d = 0;
   U64 mayXray = pawns | bishops | rooks | queen;
   U64 fromSet = 1ULL << frSq;
   U64 occ     = occupiedBB;
   U64 attadef = attacksTo( occ, toSq );
   gain[d]     = value[target];
   do {
      d++; // next depth and side
      gain[d]  = value[aPiece] - gain[d-1]; // speculative store, if defended
      attadef ^= fromSet; // reset bit in set to traverse
      occ     ^= fromSet; // reset bit in temporary occupancy (for x-Rays)
      if ( fromSet & mayXray )
         attadef |= considerXrays(occ, ..);
      fromSet  = getLeastValuablePiece (attadef, d & 1, aPiece);
   } while (fromSet);
   while (--d)
      gain[d-1]= -max (-gain[d-1], gain[d])
   return gain[0];
}

How should this be changed to use alpha/beta?
Robert P.

[bob]

Here is the excellent pseudocode for iterative SEE, from CPW.

Code: Select all

int Board::see ( enumSquare toSq, enumPiece target, enumSquare frSq, enumPiece aPiece)
{
   int gain[32], d = 0;
   U64 mayXray = pawns | bishops | rooks | queen;
   U64 fromSet = 1ULL << frSq;
   U64 occ     = occupiedBB;
   U64 attadef = attacksTo( occ, toSq );
   gain[d]     = value[target];
   do {
      d++; // next depth and side
      gain[d]  = value[aPiece] - gain[d-1]; // speculative store, if defended
      attadef ^= fromSet; // reset bit in set to traverse
      occ     ^= fromSet; // reset bit in temporary occupancy (for x-Rays)
      if ( fromSet & mayXray )
         attadef |= considerXrays(occ, ..);
      fromSet  = getLeastValuablePiece (attadef, d & 1, aPiece);
   } while (fromSet);
   while (--d)
      gain[d-1]= -max (-gain[d-1], gain[d])
   return gain[0];
}

How should this be changed to use alpha/beta?
Robert P.

This is not particularly practical since abstract functions do much of the work, but the idea is that at the bottom of the main loop ends at "} while (fromSet)"

You do something like this:

if (gain[d] - piece you just used to make a capture > 0) break;

The idea is that you just captured something and the current material state is in "gain[d]". If that value, less the value of the piece you just used to make this capture is still > 0, your opponent can't improve things for himself, and when he re-captures that piece, you will have the option to stand pat (since you will still be ahead in material) or make a capture that might win even more...

It simply terminates that main loop as soon as one side can't make a capture that swings the material balance back to zero or better...

[cms271828]

Thanks for the code, I just got round to going through it and it makes sense now.

The code will always search to the very end of the capture sequence, I'm thinking P x (not P) will always be good, but then you wouldn't know if the pawn is lost, so its harder to value, so perhaps searching to the end is better.

I haven't thought entirely about kings, the kings can't be captured so they must be the very last attacker in the sequence, so calling see(white_king) would look for least black attacker, of which there is none, and 0 is returned.

Do you think this will give a decent speed up considering that I currently order moves by:

Hash Move
Captures (MVVLVA sorted)
Non-Captures

So clearly with this ordering I'm searching bad captures before non-captures, so I guess this see algorithm must give an improvement.

Thanks

[cms271828]

I just thought about a potential problem...

What if pieces in the attackLists are pinned, and also making captures on the TO square causes checks, preventing a recapture.

I guess we either ignore it and get a false representation of the captures order which will only occur when pinned pieces / checks are involved, or we could be more thorough and test for pinned attackers, and which moves give check.

The check problem is more complex as I think about it now. If we make a capture on the TO square that causes a direct check(and no discovery check), then this check will be eradicated by just continuing the captures on that square. But if there is a discovery check (as well as, or instead of the direct check) then I think that most likely stops any more captures on the TO square.

Any suggestions? Thanks

[bob]

I just thought about a potential problem...

What if pieces in the attackLists are pinned, and also making captures on the TO square causes checks, preventing a recapture.

I guess we either ignore it and get a false representation of the captures order which will only occur when pinned pieces / checks are involved, or we could be more thorough and test for pinned attackers, and which moves give check.

The check problem is more complex as I think about it now. If we make a capture on the TO square that causes a direct check(and no discovery check), then this check will be eradicated by just continuing the captures on that square. But if there is a discovery check (as well as, or instead of the direct check) then I think that most likely stops any more captures on the TO square.

Any suggestions? Thanks

Ignore those conditions. This is not an exact science, it is just about ordering moves. This code is executed so many times it can't be slow or the search speed will drop drastically.