Permalink
Browse files

Another attempt at evaluation shortcut

In this case we try a rather drastic
approach: we simply don't futility prune
in qsearch when arriving from a null move.

So we save evaluating and also save to mess
with eval margins at all because margin is used
only in futility.

Also accuracy should not be affected, actually it
improves because we don't prune anything anymore.

bench: 5404066
  • Loading branch information...
mcostalba committed Nov 5, 2012
1 parent a5b1f47 commit c581b7ea36274826b95497570231335dd6b77468
Showing with 9 additions and 2 deletions.
  1. +9 −2 src/search.cpp
View
@@ -1102,11 +1102,12 @@ namespace {
Key posKey;
Move ttMove, move, bestMove;
Value bestValue, value, ttValue, futilityValue, futilityBase;
- bool givesCheck, enoughMaterial, evasionPrunable;
+ bool givesCheck, enoughMaterial, evasionPrunable, fromNull;
Depth ttDepth;
ss->currentMove = bestMove = MOVE_NONE;
ss->ply = (ss-1)->ply + 1;
+ fromNull = (ss-1)->currentMove == MOVE_NULL;
// Check for an instant draw or maximum ply reached
if (pos.is_draw<false, false>() || ss->ply > MAX_PLY)
@@ -1144,7 +1145,12 @@ namespace {
}
else
{
- if (tte)
+ if (fromNull)
+ {
+ ss->staticEval = bestValue = -(ss-1)->staticEval;
+ ss->evalMargin = VALUE_ZERO;
+ }
+ else if (tte)
{
assert(tte->static_value() != VALUE_NONE || Threads.size() > 1);
@@ -1192,6 +1198,7 @@ namespace {
if ( !PvNode
&& !InCheck
&& !givesCheck
+ && !fromNull
&& move != ttMove
&& enoughMaterial
&& type_of(move) != PROMOTION

11 comments on commit c581b7e

@hongzhicheng

This comment has been minimized.

Show comment Hide comment
@hongzhicheng

hongzhicheng Nov 5, 2012

Contributor

Good try!

I am happy to report a successful implementation of this idea in one of my Chinese chess engines. This engine is based mainly on Stockfish. So the idea that works in it can be easily applied to Stockfish. My implementation almost perfectly keeps the functionality of the program unchanged, but due to some specific codes in the program, there should be some round-off errors inherent in it and the bench signatures for the modified and original versions are not the same. But after introducing those round-off errors back into the original engine, the bench signatures become identical. So I am quite sure that the modified version can’t have much regression because of any change of functionality. The search speed is increased, for example, it goes up by about 5% for the start position. So I expect some sure elo gain by this idea. I did a 1000-game match between the modified and original versions. The TC is 5000ms + 100ms. CPU is intel i3 330m. There is only one thread for each engine and only one game at a time. The result is very encouraging: wins: 168 losses : 134 draws 698 for the modified version. So there is an elo gain of 12 for this TC. Of course, the number of games is not enough yet.

What I did is as below,

  1. In Search::Stack, evalMargin is defined as an int array of 2 elements. In TTEntry, staticMargin is defined as an uint8_t array of 2 elements. evalMargin will save attackUnit instead of the real Value. The real eval margin can be be refered to by attackUnit. This way we can keep the size of TTEntry unchanged. A bool variable named symmetric is introduced in Search::Stack. In TTEntry, this variable is saved in the most siginificant bit of move16, since that bit is not used by a move. This variable is a property of a position. If it is true, it means that the static evaluation of a position is symmetric in terms of side to move except for a tempo value.
  2. When evaluating a position, three types of information are collected, the static evaluation, the attackUnits for both white and black sides and the symmetric property of a position in terms of side to move.
  3. In function interpolate(), the last several bits of a Value are not reset. This better preserves the symmetric property of a position.
  4. In search() and qsearch(), if (ss-1)->currentMove == MOVE_NULL and (ss-1)->symmetric is true, we will confidently skip a call to evaluate() and the static eval would be
    2 * Interpolate(Tempo, mi->game_phase(), mi->scale_factor(pos, WHITE)) – (ss-1)-> staticEval
    where mi is the MaterialEntry for the current position.

There isn’t much work as long as we have all the concept clear in mind. The number of lines of code that need to write is less than 200. or even less than 100 and the speedup is 5% for the mid game. This is definite worth the effort.

For “chess”, the speedup should be less as the size of the board of Chinese Chess is larger and the evaluate() function of my engine consumes more time.

Marco, if you like I can send to you the codes of my Chinse chess engine for your reference. Thank you very much for taking this idea seriously.

Hongzhi

Contributor

hongzhicheng replied Nov 5, 2012

Good try!

I am happy to report a successful implementation of this idea in one of my Chinese chess engines. This engine is based mainly on Stockfish. So the idea that works in it can be easily applied to Stockfish. My implementation almost perfectly keeps the functionality of the program unchanged, but due to some specific codes in the program, there should be some round-off errors inherent in it and the bench signatures for the modified and original versions are not the same. But after introducing those round-off errors back into the original engine, the bench signatures become identical. So I am quite sure that the modified version can’t have much regression because of any change of functionality. The search speed is increased, for example, it goes up by about 5% for the start position. So I expect some sure elo gain by this idea. I did a 1000-game match between the modified and original versions. The TC is 5000ms + 100ms. CPU is intel i3 330m. There is only one thread for each engine and only one game at a time. The result is very encouraging: wins: 168 losses : 134 draws 698 for the modified version. So there is an elo gain of 12 for this TC. Of course, the number of games is not enough yet.

What I did is as below,

  1. In Search::Stack, evalMargin is defined as an int array of 2 elements. In TTEntry, staticMargin is defined as an uint8_t array of 2 elements. evalMargin will save attackUnit instead of the real Value. The real eval margin can be be refered to by attackUnit. This way we can keep the size of TTEntry unchanged. A bool variable named symmetric is introduced in Search::Stack. In TTEntry, this variable is saved in the most siginificant bit of move16, since that bit is not used by a move. This variable is a property of a position. If it is true, it means that the static evaluation of a position is symmetric in terms of side to move except for a tempo value.
  2. When evaluating a position, three types of information are collected, the static evaluation, the attackUnits for both white and black sides and the symmetric property of a position in terms of side to move.
  3. In function interpolate(), the last several bits of a Value are not reset. This better preserves the symmetric property of a position.
  4. In search() and qsearch(), if (ss-1)->currentMove == MOVE_NULL and (ss-1)->symmetric is true, we will confidently skip a call to evaluate() and the static eval would be
    2 * Interpolate(Tempo, mi->game_phase(), mi->scale_factor(pos, WHITE)) – (ss-1)-> staticEval
    where mi is the MaterialEntry for the current position.

There isn’t much work as long as we have all the concept clear in mind. The number of lines of code that need to write is less than 200. or even less than 100 and the speedup is 5% for the mid game. This is definite worth the effort.

For “chess”, the speedup should be less as the size of the board of Chinese Chess is larger and the evaluate() function of my engine consumes more time.

Marco, if you like I can send to you the codes of my Chinse chess engine for your reference. Thank you very much for taking this idea seriously.

Hongzhi

@jromang

This comment has been minimized.

Show comment Hide comment
@jromang

jromang Nov 5, 2012

Contributor

After the first 500 games (time control is 40/8+0.05 - running only 2 concurrent games one a quad core), this looks very promising...maybe too much.
Score of c581b7e vs a878312: 129 - 83 - 288 [0.546] 500
ELO: 32.05 +- 99%: 40.92 95%: 30.95
LOS: 99.92%
Wins: 129 Losses: 83 Draws: 288 Total: 500
I will let it run overnight.

Contributor

jromang replied Nov 5, 2012

After the first 500 games (time control is 40/8+0.05 - running only 2 concurrent games one a quad core), this looks very promising...maybe too much.
Score of c581b7e vs a878312: 129 - 83 - 288 [0.546] 500
ELO: 32.05 +- 99%: 40.92 95%: 30.95
LOS: 99.92%
Wins: 129 Losses: 83 Draws: 288 Total: 500
I will let it run overnight.

@hongzhicheng

This comment has been minimized.

Show comment Hide comment
@hongzhicheng

hongzhicheng Nov 5, 2012

Contributor

Really? Too good to be true. Actually I had the same kind of experience too. In Marco's codes, he didn't add two times the tempo value back to the negative of static eval from ss-1. I have tried to used different tempo values here and the results fluctuated very much. In one of a 100-game match, the modified versions scored 60%. Anyhow, the idea of not pruning any nodes in qsearch following a null move might be good and worths a try.

Contributor

hongzhicheng replied Nov 5, 2012

Really? Too good to be true. Actually I had the same kind of experience too. In Marco's codes, he didn't add two times the tempo value back to the negative of static eval from ss-1. I have tried to used different tempo values here and the results fluctuated very much. In one of a 100-game match, the modified versions scored 60%. Anyhow, the idea of not pruning any nodes in qsearch following a null move might be good and worths a try.

@mcostalba

This comment has been minimized.

Show comment Hide comment
@mcostalba

mcostalba Nov 5, 2012

Owner
Owner

mcostalba replied Nov 5, 2012

@mcostalba

This comment has been minimized.

Show comment Hide comment
@mcostalba

mcostalba Nov 5, 2012

Owner
Owner

mcostalba replied Nov 5, 2012

@mcostalba

This comment has been minimized.

Show comment Hide comment
@mcostalba

mcostalba Nov 5, 2012

Owner
Owner

mcostalba replied Nov 5, 2012

@hongzhicheng

This comment has been minimized.

Show comment Hide comment
@hongzhicheng

hongzhicheng Nov 5, 2012

Contributor

It is my honour to give all my ideas to you. I have written two Chinese engine's, one is based on Stockfish and the other IPPOLIT. IPPOLIT has many good ideas in terms of search speed. But Stockfish scales much better. In CEGT's 40/120 list, Stockfish is number one now, ahead of Houdini 1.5.

Now the engine I will send to you is almost a copy of stockfish, with necessary changes to make it play Chinese Chess, and some ideas from IPPOLIT to improve speed. I hope you don't laugh at me to see all your codes in my engine.

Last question. Where can I send the file? email ?

Contributor

hongzhicheng replied Nov 5, 2012

It is my honour to give all my ideas to you. I have written two Chinese engine's, one is based on Stockfish and the other IPPOLIT. IPPOLIT has many good ideas in terms of search speed. But Stockfish scales much better. In CEGT's 40/120 list, Stockfish is number one now, ahead of Houdini 1.5.

Now the engine I will send to you is almost a copy of stockfish, with necessary changes to make it play Chinese Chess, and some ideas from IPPOLIT to improve speed. I hope you don't laugh at me to see all your codes in my engine.

Last question. Where can I send the file? email ?

@mcostalba

This comment has been minimized.

Show comment Hide comment
@mcostalba

mcostalba Nov 5, 2012

Owner
Owner

mcostalba replied Nov 5, 2012

@jromang

This comment has been minimized.

Show comment Hide comment
@jromang

jromang Nov 6, 2012

Contributor

New results after 3000 games (still 40/8+0.05) :
Score of c581b7e vs a878312: 699 - 595 - 1706 [0.517] 3000
ELO: 12.05 +- 99%: 16.42 95%: 12.46
LOS: 99.81%
Wins: 699 Losses: 595 Draws: 1706 Total: 3000
I will let it run longer to reduce the error margins, but it already looks good !

Contributor

jromang replied Nov 6, 2012

New results after 3000 games (still 40/8+0.05) :
Score of c581b7e vs a878312: 699 - 595 - 1706 [0.517] 3000
ELO: 12.05 +- 99%: 16.42 95%: 12.46
LOS: 99.81%
Wins: 699 Losses: 595 Draws: 1706 Total: 3000
I will let it run longer to reduce the error margins, but it already looks good !

@jromang

This comment has been minimized.

Show comment Hide comment
@jromang

jromang Nov 6, 2012

Contributor

Final result after 5000 games :
Score of c581b7e vs a878312: 1163 - 970 - 2867 [0.519] 5000
ELO: 13.35 +- 99%: 12.71 95%: 9.65
LOS: 100.00%
Wins: 1163 Losses: 970 Draws: 2867 Total: 5000

Contributor

jromang replied Nov 6, 2012

Final result after 5000 games :
Score of c581b7e vs a878312: 1163 - 970 - 2867 [0.519] 5000
ELO: 13.35 +- 99%: 12.71 95%: 9.65
LOS: 100.00%
Wins: 1163 Losses: 970 Draws: 2867 Total: 5000

@mcostalba

This comment has been minimized.

Show comment Hide comment
@mcostalba

mcostalba Nov 6, 2012

Owner
Owner

mcostalba replied Nov 6, 2012

Please sign in to comment.