Stockfish 1.7 - nullmove blunder

[Edward German]

Without EGTB of course.

I have installed 32-Bit only on my Core Duo 2.6 GHz.

Diagramm:

[d]8/7P/8/8/K2b4/p7/1k6/1B6 b - -

Black is here easy winning, but Stockfish 1.7 is blind!

Engine: Stockfish 1.7 JA (256 MB)
von Tord Romstad, Marco Costalba, Joona Kii

1.00 0:00 0.00 1...a2 (99) 1

2.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (130) 1

3.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (224) 2

4.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (326) 3

5.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (460) 4

6.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (1.125) 11

7.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (1.628) 17

8.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (2.051) 21

9.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (2.911) 30

10.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (5.320) 56

11.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (6.525) 69

12.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (8.287) 88

13.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (10.364) 95

14.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (13.083) 120

15.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (16.506) 151

16.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (20.964) 192

17.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (26.773) 245

18.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (35.630) 285

19.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (45.283) 362

20.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (57.817) 462

21.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (74.802) 530

22.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (104.189) 667

23.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (127.736) 742

24.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (162.164) 867

25.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (222.480) 1015

26.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (388.261) 1244

27.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (457.720) 1274

28.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (560.230) 1379

29.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (766.919) 1444

30.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (1.019.947) 1517

31.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (1.304.146) 1606

32.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (1.571.708) 1649

33.01 0:01 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (2.315.185) 1703

34.01 0:01 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (3.147.781) 1737

35.01 0:02 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (4.313.493) 1770

36.01 0:02 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (5.284.193) 1789

37.01 0:05 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (9.314.405) 1840

38.01 0:06 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (12.051.977) 1854

39.01 0:09 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (16.871.978) 1864

40.01 0:10 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (18.815.101) 1875

41.01 0:29 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (56.149.657) 1922

42.01 0:37 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (72.455.902) 1926

43.01 0:48 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (93.438.434) 1929

ED.

[Martin Brown]

Without EGTB of course.

I have installed 32-Bit only on my Core Duo 2.6 GHz.

Diagramm:

[d]8/7P/8/8/K2b4/p7/1k6/1B6 b - -

Black is here easy winning, but Stockfish 1.7 is blind!

Engine: Stockfish 1.7 JA (256 MB)
von Tord Romstad, Marco Costalba, Joona Kii

1.00 0:00 0.00 1...a2 (99) 1

2.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (130) 1

3.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (224) 2

ED.

How odd. You would think that at some early stage it would spot that
1. ... Bc3 leaves black with no good moves at all. Though I suspect that is related to the reason why the null move has gone awry here.

Perhaps someone who understands the internals of this engine can explain why the null move cutoff the crucial line.

[Tord Romstad]

Without EGTB of course.

I have installed 32-Bit only on my Core Duo 2.6 GHz.

Diagramm:

[d]8/7P/8/8/K2b4/p7/1k6/1B6 b - -

Black is here easy winning, but Stockfish 1.7 is blind!

Engine: Stockfish 1.7 JA (256 MB)
von Tord Romstad, Marco Costalba, Joona Kii

1.00 0:00 0.00 1...a2 (99) 1

2.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (130) 1

3.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (224) 2

ED.

How odd. You would think that at some early stage it would spot that
1. ... Bc3 leaves black with no good moves at all. Though I suspect that is related to the reason why the null move has gone awry here.

Perhaps someone who understands the internals of this engine can explain why the null move cutoff the crucial line.

It's a simple bug, introduced when we recently started storing the results of null move searches to the transposition table. If you simply comment out line 1391 in search.cpp and recompile, Stockfish finds the win instantly.

Thanks to Eduard for pointing out this bug! We'll see if we can find a better solution than just removing this line of code.

[Eelco de Groot]

Without EGTB of course.

I have installed 32-Bit only on my Core Duo 2.6 GHz.

Diagramm:

[d]8/7P/8/8/K2b4/p7/1k6/1B6 b - -

Black is here easy winning, but Stockfish 1.7 is blind!

Engine: Stockfish 1.7 JA (256 MB)
von Tord Romstad, Marco Costalba, Joona Kii

1.00 0:00 0.00 1...a2 (99) 1

2.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (130) 1

3.00 0:00 0.00 1...Kxb1 2.h8D Lxh8 3.Kxa3 (224) 2

ED.

How odd. You would think that at some early stage it would spot that
1. ... Bc3 leaves black with no good moves at all. Though I suspect that is related to the reason why the null move has gone awry here.

Perhaps someone who understands the internals of this engine can explain why the null move cutoff the crucial line.

It's a simple bug, introduced when we recently started storing the results of null move searches to the transposition table. If you simply comment out line 1391 in search.cpp and recompile, Stockfish finds the win instantly.

Thanks to Eduard for pointing out this bug! We'll see if we can find a better solution than just removing this line of code.

Thanks Tord, Marco And Joona for the new Stockfish!

I have not really looked at all the new code changes but just looking at the line 1391 that Tord pointed out as causing this I was wondering if, to avoid the bug, it would be safe enough to only store verification search results higher or equal beta and not store null move searches at this level?

The code for it I thought would be approximately like this, but I can't vouch for it or say it tested it, with some changed parts in the middle of the code from Stockfish nullmove search:

Code: Select all

    // Null move dynamic reduction based on value
    if (refinedValue - beta > PawnValueMidgame)
        R++;

    pos.do_null_move(st);

    nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);

    pos.undo_null_move();

    if (nullValue >= beta)
    {
        // Do not return unproven mate scores
        if (nullValue >= value_mate_in(PLY_MAX))
            nullValue = beta;
			
        // Do zugzwang verification search for high depths, don't store in TT
        // if search was stopped.
			if (depth >= 6 * OnePly)
			{
				Value verificationValue = search(pos, ss, beta, depth - (ttMove == MOVE_NONE ?  3*OnePly : 5*OnePly), ply, false, threadID);
				if (verificationValue >= beta)
				{
					nullValue = verificationValue;
					if (!AbortSearch && !TM.thread_should_stop(threadID))
					{
						assert(value_to_tt(nullValue, ply) == nullValue);
						TT.store(posKey, nullValue, VALUE_TYPE_LOWER, depth - (ttMove == MOVE_NONE ?  3*OnePly : 5*OnePly), MOVE_NONE);
					}
					return nullValue;
				}
				if (ttMove == MOVE_NONE)
				{
					ttMove = ss[ply].pv[ply];
					tte = TT.retrieve(pos.get_key());
					ss[ply].eval = value_from_tt(tte->value(), ply);

					refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible
					update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
				}
         }
         else
         {
	return nullValue;
         }
    } else {
            // 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).
            if (nullValue == value_mated_in(ply + 2))
                mateThreat = true;

Just trying to get a first idea where the new Stockfish search is going and of all the changes, it's very interesting, thanks again!

Eelco

[Tord Romstad]

Thanks Tord, Marco And Joona for the new Stockfish!

You're welcome.

I have not really looked at all the new code changes but just looking at the line 1391 that Tord pointed out as causing this I was wondering if, to avoid the bug, it would be safe enough to only store verification search results higher or equal beta and not store null move searches at this level?

We've already discussed it a little internally in the team, and what we'll probably end up doing is adding a new flag saying that "this value was found by a null move search" to the transposition table entries, and not allowing TT cutoffs based on such entries at nodes where allowNullmove is false.

[Eelco de Groot]

Alternative version B, with one minor change, I thought it should be possible to store the first move of the verification search, as long as you also store it with the exact searchdepth. The verification seach will also store its best move I think, so this is only making a duplicate TT entry as far as I understand? But it can't hurt to store it here again also because there was apparently a TT miss at the beginning of the normal search and it is good enough to cause a beta cutoff at this point, so it should not hurt too much if the verification result is a bit inaccurate because of the limited depth. I would not store it with the three plies higher depth the normal search would get though, it seems risky. Especially if you are interested in longer timecontrols, TT space is at a premium then

Eelco

(Not tested any of this:)

Code: Select all

    // Null move dynamic reduction based on value
    if (refinedValue - beta > PawnValueMidgame)
        R++;

    pos.do_null_move(st);

    nullValue = -search(pos, ss, -(beta-1), depth-R*OnePly, ply+1, false, threadID);

    pos.undo_null_move();

    if (nullValue >= beta)
    {
      // Do not return unproven mate scores
      if (nullValue >= value_mate_in(PLY_MAX))
          nullValue = beta;
			
      // Do zugzwang verification search for high depths, don't store in TT
      // if search was stopped.
      if (depth >= 6 * OnePly)
      {
          Depth verificationDepth = depth - (ttMove == MOVE_NONE ?  3*OnePly : 5*OnePly);
          Value verificationValue = search(pos, ss, beta, verificationDepth, ply, false, threadID);
          if (verificationValue >= beta)
          {
              nullValue = verificationValue;
              if (!AbortSearch && !TM.thread_should_stop(threadID))
              {
                  assert(value_to_tt(nullValue, ply) == nullValue);
                  TT.store(posKey, nullValue, VALUE_TYPE_LOWER, verificationDepth, ss[ply].pv[ply]);
              }
              return nullValue;
          }
          if (ttMove == MOVE_NONE)
          {
              ttMove = ss[ply].pv[ply];
              tte = TT.retrieve(pos.get_key());
              ss[ply].eval = value_from_tt(tte->value(), ply);

              refinedValue = refine_eval(tte, ss[ply].eval, ply); // Enhance accuracy with TT value if possible
              update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
          }
      }
      else
      {
            return nullValue;
      }
    } else {
        // 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).

[Eelco de Groot]

Thanks Tord, Marco And Joona for the new Stockfish!

You're welcome.

I have not really looked at all the new code changes but just looking at the line 1391 that Tord pointed out as causing this I was wondering if, to avoid the bug, it would be safe enough to only store verification search results higher or equal beta and not store null move searches at this level?

We've already discussed it a little internally in the team, and what we'll probably end up doing is adding a new flag saying that "this value was found by a null move search" to the transposition table entries, and not allowing TT cutoffs based on such entries at nodes where allowNullmove is false.

That sounds reasonable too Tord! We will just wait for any new code the team comes up with. Is this bug serious enough to make a direct bugfix version do you think Tord, or are you guys waiting if more bugs will turn up? Ingo has already started a live test of Stockfish 7 in his IPON list:

http://rybkaforum.net/cgi-bin/rybkaforu ... ?tid=16225

http://www.inwoba.de/

Going by Uri's post there no engine seems to have scored more than 50%, only Deep Shredder 12 could keep up with Stockfish scoring a tournament 9½-9½ draw! Including the latest Rybka 3, but Rybka 4 is already on its way, and excluding the Rybka clones that are not in Ingo's list anymore, so I leave them out of consideration here.

Regards, Eelco

[Graham Banks]

It's a simple bug, introduced when we recently started storing the results of null move searches to the transposition table. If you simply comment out line 1391 in search.cpp and recompile, Stockfish finds the win instantly.

Thanks to Eduard for pointing out this bug! We'll see if we can find a better solution than just removing this line of code.

Does this mean that a bugfix will be coming shortly? Just wondering if I should hold off testing.

Cheers,
Graham.

[Tord Romstad]

Does this mean that a bugfix will be coming shortly? Just wondering if I should hold off testing.

It's possible that there will be a bugfix release soon, but the difference in strength between 1.7 and the hypothetical 1.7.1 will be too small to measure. We'll almost certainly recommend that they're rated as a single engine on the various rating lists.

[Graham Banks]

Does this mean that a bugfix will be coming shortly? Just wondering if I should hold off testing.

It's possible that there will be a bugfix release soon, but the difference in strength between 1.7 and the hypothetical 1.7.1 will be too small to measure. We'll almost certainly recommend that they're rated as a single engine on the various rating lists.

Thanks Tord.