Trying to implement an efficient SEE

[pedrojdm2021]

Hello there! i hope you all are doing great

I have a question, about something that i'm having hard time to understand, due to the lack of information about this.
The thing is, i am implementing the "Static Exchange Evaluation", i made it work using the very basic algorithm from the chess programming wiki:
https://www.chessprogramming.org/Static ... Evaluation

It does it's job for sure, but as we all know, that algorithm is very slow and cpu intense, especially when you use that to prune some nodes inside a QS for example, that is begin called very often.

I did some research and trying to figure out to implement an efficient SEE.
And then i found the Ed's lookup implementation, it seems to be just a lookup table but i don't understand how that thing works
https://www.chessprogramming.org/Attack ... #EDsLookup

In the arcticle it says:

As described by Ed Schröder in Evaluation in REBEL, Rebel uses two board tables for both sides, one byte entry each, the three lower bits contain an attack counter, while the five upper bits indicate the presence of least one pawn or piece attacking/defending

Code: Select all

char see_table [14][256][256];   // 14*64 K = 896 KByte
see = see_table[Piece][attackByte][defendByte];

My question is How does that [256] entries work?
i do understand that i have to binary-encode the number of attackers for lower bits, and attacker type for upper bits, but that are actually doing the [256] arrays there? i can't be an square index because an chess board is only 64 squares, and also how can i get the attackers and defenders to fill that information?

if anyone knows a guide about this or more information about this would be of great help! thanks

[hgm]

These 'attack codes' can have 256 different values, and you use those to index the array.

[Steve Maughan]

I believe Maverick's approach is quite efficient — it's a sort of branch-and-bound algorithm. You can read more here:

https://www.chessprogramming.net/static ... -in-chess/

or take a look at the source here:

https://github.com/stevemaughan/maveric ... er/see.cpp

— Steve

[gflohr]

I believe Maverick's approach is quite efficient — it's a sort of branch-and-bound algorithm.

How do you order moves, when your SEE just returns a boolean?

[algerbrex]

I believe Maverick's approach is quite efficient — it's a sort of branch-and-bound algorithm.

How do you order moves, when your SEE just returns a boolean?

You can have an implementation where your SEE routine returns true or false depending on if the capture is winning or losing. So if the SEE value returned is false, you know the capture is losing, and you can prune it.

[Steve Maughan]

How do you order moves, when your SEE just returns a boolean?

Maverick orders captures in MVV/LVA order. It does a SEE on each move just before playing it. If the SEE is negative it skips this move and adds it to the "losing captures" list which is played later after the winning captures and killer moves.

Hope this helps!

Steve

[Desperado]

I believe Maverick's approach is quite efficient — it's a sort of branch-and-bound algorithm.

How do you order moves, when your SEE just returns a boolean?

If you use "see_sign", you only check for loosing captures/moves. Most engines use this information to delay the move which means,
to move them at the end of the movelist or into another movelist which is handled in another stage of a move picker.
That means you don't search them immediately and pick the next move with a positive see score.

Of course you can use the see value to sort a movelist (captuers or quiet moves) by the see value. But there are faster
heuristics for quiet moves that are more efficient at the leafs.

"See sign" in QS or close the leafes will be used mainly to prune moves which makes the search more effective although the speed might drop.

Regards.