Static Exchange Evaluation Methods

[Pradu]

I?ve done some tests with Static Exchange Evaluation and found out through many tests that a good SEE greatly increases playing strength epically when the engine is set to a particular depth.

My first try was using the MVV/LVA method. This didn?t work out too well because it had many problems with it like a move where the pawn would be hanging to be taken by a queen. This move would not even be considered.

Then I tried something that checks whether the piece would be taken with the capture

Code: Select all

int score=PieceVal[board.piece[square]];
   if(isAttacked(square,attackingpiecesq))
      score-=PieceVal[attackingpiece];
   return score;


This doesn?t work well either because of problems like the following position:

Witz_a17 ? Witz_a16

[diag]Q1bk2r1/p3pp1p/3p4/1P6/1P1P4/Pq3NP1/3K1P1P/R6R[/diag]
Q1bk2r1/p3pp1p/3p4/1P6/1P1P4/Pq3NP1/3K1P1P/R6R w - - 1 21

Witz a17 set at depth 5 search played a8c8 and went on to lose the game.
Here was its PV line in the position:
a8c8 d8c8 a1c1 c8b7 c1c3
[diag]6r1/pk2pp1p/3p4/1P6/1P1P4/PqR2NP1/3K1P1P/7R[/diag]

Here the previous SEE thought that the black queen takes the pawn and nothing is attacking it. But of course the Rook attacks it after that, and the quiescence search sees this and the program thinks that queens will be traded. (I?ve tried extending the attacking line which worked for this position but had problems in other positions)

So even this didn?t work and I went off into another round of thinking and came up with this.

Say you had a position like the following:
[diag]3r4/3r4/2n1n3/8/3p4/2PR4/1B1Q4/3R4[/diag]
White?s turn.

I came up with a very complex SEE for solving this.

Keep two arrays, one with black pieces attacking the square in question and one with white pieces attacking the square in question and keep them ordered from lowest piece score to highest piece score.

So the initial arrays would be:
White[ P , R ]
Black[ N , N , R ]

Since its whites move White plays the lowest piece that takes the piece and then generates the first piece along the diagonal starting from the position of the pawn

Score=P

White[ B, R ]
Black[ N, N, R]


Black Plays N

Score=P-P

White [B, R]
Black [N, R]

And so on to get a score. But one side is not compelled to play a capture. So if a later score is less than an earlier score for a certain side, the earlier score is returned.

Implementing this would have a lot of overhead compared to simple (but bad) algorithms like the MVV/LVA algorithms. My question is does anyone have a good SEE algorithm that is as accurate as my last one but not as slow as it?

[Pallav Nawani]

Implementing this would have a lot of overhead compared to simple (but
bad) algorithms like the MVV/LVA algorithms. My question is does anyone
have a good SEE algorithm that is as accurate as my last one but not as
slow as it?

I don't think a SEE improves playing strength that much. My experience is
that SEE is highly useful only if you are searching depth > 10. Below these
depths, the benefit of SEE is small, but its enough to make up for the loss of
speed.

When people talk about SEE, they usually mean the last method you
described, everybody seems to do it that way. There are other things you
may add, for example:

Pawn Promotions
Checks

These would make the SEE more accurate, but still slower. Adding SEE will
slow you down anywhere from 5% to 10%. So you have to counterbalance
the speed loss with the move ordering and pruning that you can do with SEE.

Best Regards,
Pallav

[Pradu]

But is there a better SEE algoritm that does the same thing mine does but faster (since its used everywhere from move generation to evaluvation fucntions)?

[Rémi Coulom]

Implementing this would have a lot of overhead compared to simple (but bad) algorithms like the MVV/LVA algorithms. My question is does anyone have a good SEE algorithm that is as accurate as my last one but not as slow as it?

Hi,

Here is how I do it in the crazy bishop:

I do not use SEE for move ordering. I use faster heuristics. I tried to replace those simple heuristics by SEE, and found that it was bad (searched more nodes with SEE than with my simple heuristics). Those simple heuristics are based on the MVV/LVA heuristics + bonus for re-capture + bonus for killer captures + bonus for moving the threatened piece away (as detected by the null move).

So, I use SEE for pruning only, one move at a time, which is less time-consuming than applying it to all moves to order them. My SEE function is based on the same principle as yours, but is faster thanks to some early exits. Since I do not use it to evaluate moves, its only objective is to determine whether a capture is a losing capture. Here is the code:

Code: Select all

////////////////////////////////////////////////////////////////////////////
// Test whether a capture is losing
////////////////////////////////////////////////////////////////////////////
static int LosingCapture(tcbMove move, const tcbMove *pmoveList, int Moves)
{
 //
 // Special moves are too complicated, evaluate them dynamically
 //
 if (move.IsSpecial())
  return 0;

 //
 // If capturing a piece of higher value, then it is not losing
 //
 int pieceMoved = tpieceBoard[move.GetFrom()];
 int evalMoved = tevalPiece[pieceMoved];
 int evalCaptured = tevalPiece[move.GetCaptured()];
 if (evalMoved <= evalCaptured)
  return 0;

 //
 // If smallest defender + captured < capturing, then it is losing
 //
 int evalDefender = SmallestDefender(move.GetTo(), 0x1000);
 if (evalDefender + evalCaptured < evalMoved)
  return 1;

 //
 // If no defender, then it is winning
 //
 if (evalDefender & 0x1000)
  return 0;

 //
 // If other pieces attack the destination square, then it has to be searched
 //
 for (int i = Moves; --i >= 0;)
  if (pmoveList[i].GetTo() == move.GetTo() &&
      pmoveList[i].GetFrom() != move.GetFrom())
   return 0;

 //
 // X-ray attacks if it is a sliding piece
 //
 if (pieceMoved & (tcbPiece::Rook | tcbPiece::Bishop))
 {
  int Direction = tDirection[119 + move.GetFrom() - move.GetTo()];
  int sq = move.GetFrom();
  int pieceBehind;
  while(!(pieceBehind = tpieceBoard[sq -= Direction]));
  if ((pieceBehind & pieceMoved & tcbPiece::Color) &&
      (tAttacks[tcbPlayer::White][119 + move.GetTo() - sq] & pieceBehind))
   return 0;
 }

 //
 // The piece is defended, and there is no other attack, so the capture is losing
 //
 return 1;
}


It is not completely equivalent to the usual SEE, but it makes very little difference (I have tried both). It will sometime tell that captures are not losing, while in fact, they are. But this is rare and not a big problem.

R?mi

[Dan Honeycutt]

Implementing this would have a lot of overhead compared to simple (but bad) algorithms like the MVV/LVA algorithms. My question is does anyone have a good SEE algorithm that is as accurate as my last one but not as slow as it?

Have you tested your first routine against the second? I've tried a flock of SEE routines, from a simple one like your first one that only looks to see if the captured piece is defended to a SEE like your second one that looks at all exchanges to one that includes x-ray attacks to one that is pin aware. They get progressively more accurate and progressively slower. For me they all worked about the same.

Best
Dan H.

[Pallav Nawani]

...
bonus for moving the threatened piece away (as detected by the null move).

So, I use SEE for pruning only, one move at a time, which is less time-consuming than applying it to all moves to order them.
...
R?mi

Hi,
How do you detect that a piece is threatened by using the Null move?

Pallav

[Rémi Coulom]

Hi,
How do you detect that a piece is threatened by using the Null move?

Pallav

If the static evaluation is >= beta, the null move fails low, and the refutation of the null move is a capture, this means that the captured piece is in danger. So it is a good idea to move it away.

This cannot be done in the QSearch, of course.

R?mi

[Pradu]

Have you tested your first routine against the second? I've tried a flock of SEE routines, from a simple one like your first one that only looks to see if the captured piece is defended to a SEE like your second one that looks at all exchanges to one that includes x-ray attacks to one that is pin aware. They get progressively more accurate and progressively slower. For me they all worked about the same.

Best
Dan H.

Yes I have tested it and it has conciderably less errors when you do heavy pruning to the quiescence search (don't concider moves that have less benifit than the value of a Pawn). Of course these errors can only be reasonably seen clearly in low-ply fixed depth searches.

[Dan Honeycutt]

[Of course these errors can only be reasonably seen clearly in low-ply fixed depth searches.

With a low ply, fixed depth search then a "good" SEE should be a definite plus. But what I've seen with a normal search is that a better (and slower) SEE does about the same as a simpler, faster SEE.

Dan H.

[Anonymous]

Hello R?mi,

First, I owe you an apology, because I wasn't so cool when I said something related to a pic of you one day. Am sorry.

Now, about the implementation you give below, if you do it in qsearch, I'm wondering how you don't do double work if you do this only just for seeing if the capture is losing, and then you don't have more info to apply the futility margin at the loop wich is searching the captures.

By the way I also do this (just a little more), but more inside the loop so I can apply there futility margin, so that's why i was wondering. But if you still are doing well somehow fine.

Please, be very well, you seem to be a fine person, good luck and my best wishes.

Implementing this would have a lot of overhead compared to simple (but bad) algorithms like the MVV/LVA algorithms. My question is does anyone have a good SEE algorithm that is as accurate as my last one but not as slow as it?

Hi,

Here is how I do it in the crazy bishop:

I do not use SEE for move ordering. I use faster heuristics. I tried to replace those simple heuristics by SEE, and found that it was bad (searched more nodes with SEE than with my simple heuristics). Those simple heuristics are based on the MVV/LVA heuristics + bonus for re-capture + bonus for killer captures + bonus for moving the threatened piece away (as detected by the null move).

So, I use SEE for pruning only, one move at a time, which is less time-consuming than applying it to all moves to order them. My SEE function is based on the same principle as yours, but is faster thanks to some early exits. Since I do not use it to evaluate moves, its only objective is to determine whether a capture is a losing capture. Here is the code:

Code: Select all

////////////////////////////////////////////////////////////////////////////
snipped


It is not completely equivalent to the usual SEE, but it makes very little difference (I have tried both). It will sometime tell that captures are not losing, while in fact, they are. But this is rare and not a big problem.

R?mi

[Rémi Coulom]

Now, about the implementation you give below, if you do it in qsearch, I'm wondering how you don't do double work if you do this only just for seeing if the capture is losing, and then you don't have more info to apply the futility margin at the loop wich is searching the captures.

By the way I also do this (just a little more), but more inside the loop so I can apply there futility margin, so that's why i was wondering. But if you still are doing well somehow fine.

I do futility pruning in the quiescence search, but it is based on the value of the captured piece only, not SEE.

If you wish to replace the "IsLosing" function that I provided by a "IsFutile" function, it is only a matter of adding an offset to the value of the captured piece.

I have the feeling that pruning futile captures based on SEE is a lot more dangerous than pruning losing captures only. I do not remember whether I ran experiments to compare, but I probably did. I use the "IsLosing" function inside the loop.

R?mi

[Anonymous]

I do futility pruning in the quiescence search, but it is based on the value of the captured piece only, not SEE.

If you wish to replace the "IsLosing" function that I provided by a "IsFutile" function, it is only a matter of adding an offset to the value of the captured piece.

I have the feeling that pruning futile captures based on SEE is a lot more dangerous than pruning losing captures only. I do not remember whether I ran experiments to compare, but I probably did. I use the "IsLosing" function inside the loop.

R?mi

Hi again.
"I have the feeling that pruning futile captures based on SEE is a lot more dangerous than pruning losing captures only."

good, now I have the excuse that even R?mi Coulom also does some things fundamenting them with just feeelings...

still, I have the feeling that in your example a move like BxB PxB NxP, wich wins a pawn only and that is something you are already seeing should be ok. Altough in my slighty slower implementation i also see if at the third ply another capture would be to other square defended by the first captured bishop so it is not the same, but never tested if that really is worth. Actually never really tested very very well this, but I know if it is making things worse, it is by a margin unnoticeable.

[Pradu]

It is a lot more dangerous to prune futile captures, mabe thats why nobody is seeing a difference when testing SEE algorithms because they don't use futilty pruing in quiesce. I should have rephrased: a good SEE greatly increase the strength of an engine that uses futility pruning in the quiesce.

[Rémi Coulom]

It is a lot more dangerous to prune futile captures, mabe thats why nobody is seeing a difference when testing SEE algorithms because they don't use futilty pruing in quiesce. I should have rephrased: a good SEE greatly increase the strength of an engine that uses futility pruning in the quiesce.

I am interpreting your post as meaning that you confirm that my method is the right one.

SEE improved the strength of my engine significantly.

R?mi

[Anonymous]

Pradu,

I entered the thread, but didn't actually followed your first post, am sorry too lazy.. (I actually just wanted to enter a thread to answer anything from remi coulom)

I don't understand how your engine actually played Qxc8 without a bug. It's bug or confusion from my part?

see ya.

[Pradu]

Pradu,

I don't understand how your engine actually played Qxc8 without a bug. It's bug or confusion from my part?

It did have a bug when using simple SEE.