Permalink
Browse files

Introduce Null Threat extension

In case of null search at low depths returns a fail low
due to a threat then, rather than return beta-1 (to cause
a re-search at full depth in the parent node), we set a flag
threatExtension = true (false by default) that will cause
moves that prevent the threat to be extended of one ply
in the following search.

Idea and patch is by Lucas Braesch.

Lucas also did the tests:
1500 games in 5"+0.05":
SF_threatExtension vs SF_20121222: 366 - 331 - 803 [51.2%] LOS=90.8%

3000 games in 10"+0.1":
SF_threatExtension vs SF_20121222: 610 - 559 - 1831 [50.8%] LOS=93.2%

Tests confirmed by Gary after 10570 games,
ELO: 2.79 +- 99%: 8.72 95%: 6.63
LOS: 94.08%
Wins: 1523 Losses: 1438 Draws: 7607

And finally by me at 15"+0.05, single thread, 3824 games
threatExtension vs master 768 - 692 - 2364  +7 ELO

bench 4918443
  • Loading branch information...
1 parent b5b799b commit 894c43a1d648d4cf160de006bde59aa5b6ba0190 @mcostalba committed Dec 24, 2012
Showing with 8 additions and 5 deletions.
  1. +8 −5 src/search.cpp
View
@@ -485,12 +485,13 @@ namespace {
Value bestValue, value, ttValue;
Value eval, nullValue, futilityValue;
bool inCheck, givesCheck, pvMove, singularExtensionNode;
- bool captureOrPromotion, dangerous, doFullDepthSearch;
+ bool captureOrPromotion, dangerous, doFullDepthSearch, threatExtension;
int moveCount, playedMoveCount;
// Step 1. Initialize node
Thread* thisThread = pos.this_thread();
moveCount = playedMoveCount = 0;
+ threatExtension = false;
inCheck = pos.checkers();
if (SpNode)
@@ -675,16 +676,15 @@ namespace {
// The null move failed low, which means that we may be faced with
// some kind of threat. If the previous move was reduced, check if
// the move that refuted the null move was somehow connected to the
- // move which was reduced. If a connection is found, return a fail
- // low score (which will cause the reduced move to fail high in the
- // parent node, which will trigger a re-search with full depth).
+ // move which was reduced. If a connection is found extend moves that
+ // defend against threat.
threatMove = (ss+1)->currentMove;
if ( depth < 5 * ONE_PLY
&& (ss-1)->reduction
&& threatMove != MOVE_NONE
&& yields_to_threat(pos, (ss-1)->currentMove, threatMove))
- return beta - 1;
+ threatExtension = true;
}
}
@@ -802,6 +802,9 @@ namespace {
if (PvNode && dangerous)
ext = ONE_PLY;
+ else if (threatExtension && prevents_threat(pos, move, threatMove))
+ ext = ONE_PLY;
+
else if (givesCheck && pos.see_sign(move) >= 0)
ext = ONE_PLY / 2;

15 comments on commit 894c43a

Contributor

lucasart replied Dec 26, 2012

Marco,

Really a two cent cosmetic detail here, but I don't really like the names yields_threat() and prevents_threat().
How about allows_move() and prevents_move(). This has a more general appeal, at least, and is more self-documenting:

  • allows_move(m1,m2) is true when m1 allows m2
  • prevents_move(m1,m2) is true when m1 prevents m2

(in practice m2 is always going to be the threat move, but who know, maybe it will be used somewhere else in the future)

Contributor

lucasart replied Dec 26, 2012

Marco,

I have another patch for you, which is the natural extension of this one:

  • instead of extending by one ply, extend by (ss-1)->reduction
  • this is more consistent with Tord's initial idea of "cancelling the reduction" when a credible threat appears

8000 games in 10"+0.1" (in progress) on my new powerful computer:
test vs SF_20121225: 608 - 510 - 1562 [0.518] 2680

Contributor

lucasart replied Dec 26, 2012

I forgot the signatures:

  • test = 5627788
  • SF_20121225 = 4918443

I was quite surprised by the large increase in number of nodes on the ./stockfish bench. But that's hardly relevant. Results are still looking good:
test vs SF_20121225: 684 - 565 - 1761 [0.520] 3010

Contributor

lucasart replied Dec 26, 2012

Ok, that should be enough games, given that the results are quite clear:

test vs SF_20121225: 1249 - 1091 - 3260 [0.514] 5600
LOS = 99.95%

I think we've milked dry the null threat area for the moment. Perhaps increasing a little the "depth < 5*ONE_PLY" condition could improve something, but I doubt it would give much.

I'm going to play with the eval now, and see if I can remove some useless things there. The more I experiment with my eval, the more I understand the "less is more" concept ;-)

Owner

mcostalba replied Dec 26, 2012

Contributor

glinscott replied Dec 26, 2012

Hi Lucas,

Great stuff :). I'm running a test of the (ss-1)->reduction idea right now, results don't seem quite as clear locally. I will keep the test running. One thing I've noticed is running all cores of my system caused results to be inaccurate. So on my 4 core machine, I typically run 3 1-thread games at a time.

ELO: -1.31 +- 99%: 15.28 95%: 11.60
LOS: 34.32%
Wins: 511 Losses: 524 Draws: 2412

Owner

mcostalba replied Dec 26, 2012

Contributor

glinscott replied Dec 26, 2012

I've stopped testing the (ss-1)->reduction by itself, and started with Marcos idea as well. It was still at 50% almost exactly when I stopped.

Current version: https://github.com/glinscott/Stockfish/compare/null_threat

Contributor

lucasart replied Dec 27, 2012

Gary,

You're right about testing with N-1 games in parrallel, when having N processors. I'm going to do that from now on. It seems that everyone who knows what they are doing, is doing that. I remember a post on talkchess, where Robert Houdart was running 31 concurrent games on a 32 CPU machine.

I am going to run the same experiment as you. Ideally that means we can sum up our results and have more games in this way, and more precise error bar.

master = 4918443
test = 5045645

test running with 7 concurrent games (1 thread for each stockfish process): 8000 games in 10"+0.1".

Contributor

lucasart replied Dec 27, 2012

I'm really not SMP knowledgeable at all :-(
Do you think that enabling hyper threading in the BIOS will allow me to run 8 concurrent games safely (on 8 CPU) ?
Or is it better to switch hyper threading off, and play 7 concurrent games ?

PS: I'm using Linux 3.5.0-15 (x86_64 SMP)

Contributor

lucasart replied Dec 27, 2012

On second thought, I'm not sure it's a good idea to do the threat extension with captures. At low depths, quiet moves are often victim of aggressive reuction/pruning in SF, but not so much captures. What we typically want not to miss here are quiet moves than may refute the threat. So I am restarting a test with this patch only, as I did before:

   else if (threatExtension && prevents_move(pos, move, threatMove))
  •      ext = ONE_PLY;
    
  •      ext = (ss-1)->reduction;
    

Just wanna verify that my result wasn't biaised due to (i) early stopping, or to (ii) using 8 concurrent games i/o 7. This time I run 6000 games and I don't stop until finished, regardless of the result (early stopping is a very dangerous source of biais).

signatures:

  • test = 5627788
  • bench = 4918443
Contributor

glinscott replied Dec 27, 2012

I would definitely avoid hyperthreading when running engine matches. Engines push the cpu cores so hard that hyperthreading is usually not very effective. So if there are 8 physical cpu cores, running 7 games with no pondering is safe. That leaves a core for the OS/XWindows/ssh/etc.

Contributor

lucasart replied Dec 27, 2012

OK I tedted both versions, and my conclusion is that none of them is either an improvement or a regression (within error bar, after 6000 games, concurrency=7 no early stopping biais).

(1) signature=5627788: 2221-2222-3557 49.99% LOS=49.40% (ss-1)->reduction
(2) signature=5045645: 2235-2312-3453 49.52% LOS=12.67% (ss-1)->reduction + marco's modification to prevent_threat() for captures

So you can commit whichever version you prefer, or nothing at all. Up to you Marco: you're the boss!

Owner

mcostalba replied Dec 27, 2012

Contributor

lucasart replied Dec 27, 2012

You're right Marco: less is more :-)

Please sign in to comment.