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)?
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)?
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...
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.
