SEE() is slow and SEE() is fast

[sje]

SEE() is slow and SEE() is fast

Assume that a program has a static exchange evaluator SEE() which produces an exchange score for a piece on a given square, The SEE() routine may have two parts: the first part which identifies all the (ordered) defenders and attackers, and the second part which produces the minimax score of the corresponding exchange sequence.

The second part can run much faster if the minimax score is be pre-calculated and stored in a table. This approach is done in the program Rebel. However, with Rebel the minimax key and result is in a very compact format which can't accurately describe many exchange situations and many of the pre-calculated records will never be used. Expanding the format would require huge amounts of storage but wight still would not have full coverage.

My idea: Instead of a huge pre-calculated table with a limited exchange situation key space, use a transposition table or binary search tree for SEE() look-up.

At the start of a search (or game (or program invocation)), the SEE() persistent store would be cleared. As each call to SEE() is made, the first part of SEE() makes a key from the exchange situation (attacker/defender list) and uses it to access the store. If the store doesn't have a match, then the SEE() second part does the exchange resolution and stores the result. If there is a match, then the result is retrieved and SEE() exits.

[jdart]

Worth a try, but for me see() is pretty far down in the list of time consumers. The evaluation routine is the most expensive, by far.

[Joost Buijs]

Worth a try, but for me see() is pretty far down in the list of time consumers. The evaluation routine is the most expensive, by far.

Transposition table lookup in the quiescence search is the most expensive in my engine, on average it takes about 40% more time than the evaluation. This is why the use of large pages is very beneficial. TT lookup is done at every node and in many cases it is not necessary to call the evaluator. SEE is 3th in rank of time consuming functions. I use SEE throughout, I don't use MVV-LVA at all.

[sje]

Here's the reference for the use of pre-calculated exchange tables, about halfway down the page:

http://www.top-5000.nl/authors/rebel/chess840.htm

In Rebel, the table is loaded from disk at start up time.

[mcostalba]

SEE() is slow and SEE() is fast

Assume that a program has a static exchange evaluator SEE() which produces an exchange score for a piece on a given square, The SEE() routine may have two parts: the first part which identifies all the (ordered) defenders and attackers, and the second part which produces the minimax score of the corresponding exchange sequence.

The second part can run much faster if the minimax score is be pre-calculated and stored in a table. This approach is done in the program Rebel. However, with Rebel the minimax key and result is in a very compact format which can't accurately describe many exchange situations and many of the pre-calculated records will never be used. Expanding the format would require huge amounts of storage but wight still would not have full coverage.

My idea: Instead of a huge pre-calculated table with a limited exchange situation key space, use a transposition table or binary search tree for SEE() look-up.

At the start of a search (or game (or program invocation)), the SEE() persistent store would be cleared. As each call to SEE() is made, the first part of SEE() makes a key from the exchange situation (attacker/defender list) and uses it to access the store. If the store doesn't have a match, then the SEE() second part does the exchange resolution and stores the result. If there is a match, then the result is retrieved and SEE() exits.

Sorry to rain (again) on your posts, but it seems you have never profiled a see() implementation, otherwise you would know that the final minimax is not the bottlneck. Actually its contribution to see time is negligible.

[sje]

Sorry to rain (again) on your posts, but it seems you have never profiled a see() implementation, otherwise you would know that the final minimax is not the bottlneck. Actually its contribution to see time is negligible.

My postings fear no rain as they are protected by the Bumbershoot of Righteousness.

Symbolic's old SEE() included the minimax with the attacker/defender location loop. Also, the routine relied heavily on the AttacksToSquare[] array stored as part of the position's bitboard database.

Somehow, the pre-calculated exchange table in Rebel helped. Why not the same for other programs which have fewer space limitations?

[mvk]

My idea:

Good idea. I'm still doing it that way ever since I started doing that in 1997 (using attacker and defender lists as index into a hash table with SEE results). I'm quite sure I published this.

[sje]

My idea:

Good idea. I'm still doing it that way ever since I started doing that in 1997 (using attacker and defender lists as index into a hash table with SEE results). I'm quite sure I published this.

I hadn't seen it. I saw the Rebel web page and the first thing I thought of was to use a transposition table instead of a disk file.