How is SEE used?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
mathmoi
Posts: 265
Joined: Mon Mar 13, 2006 4:23 pm
Location: Québec
Contact:

How is SEE used?

Post by mathmoi » Mon Oct 13, 2008 5:11 pm

Hi,

I just implemented, for the first time, a very simple SEE function. It's been manually tested on a couple of positions and returns the right value. The first thing I wanted to test is replace my MVV/LVA ordering with an ordering based on the SEE value. When I do this the results are disastrous. SEE slow down the nps by a factor of 3! This is not counter-balanced by the slightly smaller tree searched.

Is SEE not supposed to be used for captures orderings? Is my SEE implementations flawed (see pseudocode)?

Code: Select all

   inline int See(attackers[2], sideOnMove, pieceValue)
   {
      int value = 0;
      int seeValue = 0;
      
      if (There is no attackers)
         return 0;

      attacker = attackers[sideOnMove].GetSmallestAttacker();
      seeVAlue = -See(attackers, reverseColor(sideOnMove), piecesValues[attacker]);
      if (seeValue >= 0)
         value = pieceValue + seeValue;

      return value;
   }

   int EvaluateCapture(move, board)
   {
      sq = move.targetSq;
      Lists attackers[2];
      GetAttackers(attackers, board, sq);
      attackers[sideOnMove].RemoveAttacker(move.piece);

      int value = piecesValues[move.piece];

      value -= See(attackers, reverseColor(sideOnMove), piecesValues[move.piece]);

      return value;
   }

bob
Posts: 20357
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: How is SEE used?

Post by bob » Mon Oct 13, 2008 5:51 pm

mathmoi wrote:Hi,

I just implemented, for the first time, a very simple SEE function. It's been manually tested on a couple of positions and returns the right value. The first thing I wanted to test is replace my MVV/LVA ordering with an ordering based on the SEE value. When I do this the results are disastrous. SEE slow down the nps by a factor of 3! This is not counter-balanced by the slightly smaller tree searched.

Is SEE not supposed to be used for captures orderings? Is my SEE implementations flawed (see pseudocode)?

Code: Select all

   inline int See(attackers[2], sideOnMove, pieceValue)
   {
      int value = 0;
      int seeValue = 0;
      
      if (There is no attackers)
         return 0;

      attacker = attackers[sideOnMove].GetSmallestAttacker();
      seeVAlue = -See(attackers, reverseColor(sideOnMove), piecesValues[attacker]);
      if (seeValue >= 0)
         value = pieceValue + seeValue;

      return value;
   }

   int EvaluateCapture(move, board)
   {
      sq = move.targetSq;
      Lists attackers[2];
      GetAttackers(attackers, board, sq);
      attackers[sideOnMove].RemoveAttacker(move.piece);

      int value = piecesValues[move.piece];

      value -= See(attackers, reverseColor(sideOnMove), piecesValues[move.piece]);

      return value;
   }
This is a trade-off. SEE is more expensive than MVV/LVA. But you can get more from it.

First, a trick for move ordering. after you generate captures, for all captures of type M x N where M is more valuable than N, use SEE to get the score. If M is equal to or less valuable than N, just use val(N) - val(M) (assume your piece will be recaptured) for the value. This saves a lot of calls to SEE.

Second, SEE will typically reduce the size of the tree about 10% over MVV/LVA, so if your SEE costs you more than that, it will be a net loss. But there is another use. In the q-search, if SEE returns a negative score, don't even search that capture as it loses material most likely. Doing this will reduce the size of the tree by about 50%, and I doubt you can make your SEE slow enough that 50% won't be faster overall...

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: How is SEE used?

Post by hgm » Mon Oct 13, 2008 6:31 pm

How can one inline a recursive routine?

You implemented SEE as a minimax search considering ony one move, but you did not implement alha-beta. That, plus the recursive implementation, makes SEE unnecessarily expensive.

e.g., if you have a Queen + 2 other pieces attacking a Pawn, and 3 pieces defending it, when you caculate the SEE of the QxP for the purpose of ordering it, you would always perform the exchange 6 ply deep (3 captures, 3 recaptures). While after QxP, NxP (2 ply) you could already stop, as you are now at -8, and wheter you capture the Knight or not, you can never get even.

Post Reply