MutliPV behavior?

[Joerg Oster]

So you want to see the info of the move that fails-low until it gets replaced by another move?

No, I want Stockfish to stick with the move that fail-lows until its score is resolved, without jumping to check alternative moves that would replace it.

This is how old Multi-PV used to work, and still works in many engines that implement it.

Stockfish does resolve the fail-low before it checks for alternative moves.

A fail low happens when search<Pv> returns a value at or below alpha at the root of the search. Stockfish then lowers alpha (widens the aspiration window) and searches all moves again, etc. If another move is above alpha before the current best move is above alpha, the PV of the current best move will not be resolved and so cannot be shown.

You're right, of course!

Now I wonder if we really want this in MultiPV mode?
How about doing the following?

Code: Select all

      if (rootNode)
      {
          RootMove& rm = *std::find(thisThread->rootMoves.begin(),
                                    thisThread->rootMoves.end(), move);

          // PV move or new best move ?
          if &#40;moveCount == 1 || &#40;value > alpha && moveCount + thisThread->PVIdx > multiPV&#41;)  <==
          &#123;

Does this already break the PVS algorithm?

[syzygy]

Now I wonder if we really want this in MultiPV mode?

I don't think we want to change this, not even for MultiPV > 1. MultiPV=N should show the N best lines and that's what it does. Spending more time than necessary would seem to be decrease the usefulness of MultiPV.

As far as I am aware, Stockfish has never exhibited the "old behaviour". (If it did in the past, it must have been before 2013.)

Of course my opinion is just an opinion.

[Joerg Oster]

Now I wonder if we really want this in MultiPV mode?

I don't think we want to change this, not even for MultiPV > 1. MultiPV=N should show the N best lines and that's what it does. Spending more time than necessary would seem to be decrease the usefulness of MultiPV.

But my patch doesn't change that.
After some first tests, it seems to save time.

Thinking a bit further, does it even make sense to loop through all the other moves in MultiPV mode while searching the k-best pv moves?
Looping through all other moves only after searching the last pv move seems to be sufficient. No?

As far as I am aware, Stockfish has never exhibited the "old behaviour". (If it did in the past, it must have been before 2013.)

Yes, I am not aware of it, either.

[syzygy]

Now I wonder if we really want this in MultiPV mode?

I don't think we want to change this, not even for MultiPV > 1. MultiPV=N should show the N best lines and that's what it does. Spending more time than necessary would seem to be decrease the usefulness of MultiPV.

But my patch doesn't change that.
After some first tests, it seems to save time.

I would have to to a better look at it, but if it does what is being asked for here, then I'm reasonably sure it costs more than it saves.

Thinking a bit further, does it even make sense to loop through all the other moves in MultiPV mode while searching the k-best pv moves?
Looping through all other moves only after searching the last pv move seems to be sufficient. No?

I don't think the current MultiPV implementation is optimal, but the fail-low behaviour seems OK to me, at least for MultiPV=1. For fail highs improvement seems possible (as shown by the recent skipping-fail-high-resolution tests... of course not resolving fail highs is not an option for MultiPV).

[Ovyron]

After some first tests, it seems to save time.

Thank you! This is what I suspected!

The reason it saves time is because the new behavior will waste time looking at the other moves whenever they don't beat alpha, plus, Stockfish will have to look at them anyway in the next PV line.

So, I think the fastest approach would be to apply your patch in the all the MultiPV lines, except the last one (in MultiPV=2, only the first one, in MultiPV=3, only the first 2, in MultiPV=4, only the first 3, and so on - this would be consitent with not using the patch in SinglePV, since the only one is the last one), since for the last one Stockfish will not get a chance to look at alternative moves again in a new PV, the last one behaves like in SinglePV.

As far as I am aware, Stockfish has never exhibited the "old behaviour". (If it did in the past, it must have been before 2013.)

Probably.

This is Glaurung 2.1's behavor, and Stockfish comes from its codebase:

[d]rnbqkbnr/ppp1pppp/3p4/8/3PP3/8/PPP2PPP/RNBQKBNR b KQkq -

9 0:05 +0.13 2...f5 3.Nc3 Nf6 4.Bd3 Nc6 5.Nf3 fxe4 6.Nxe4 Be6 (223.961) 42
9 0:05 +0.39 2...Nc6 3.Nc3 Nf6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Bf5 7.Bxc6+ bxc6 (223.961) 42
9 0:05 +0.39 2...Nf6 3.Nc3 Nc6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Bf5 7.Bxc6+ bxc6 (223.961) 42
9 0:05 +0.84 2...Bd7 3.Nf3 Nc6 4.Bc4 Nf6 5.Ng5 d5 6.exd5 Nb4 (223.961) 42
-----
10 0:06 +0.90 2...f5 3.exf5 Bxf5 4.Bd3 Bxd3 5.Qxd3 c5 6.dxc5 Qa5+ 7.Nc3 Qxc5 8.Nf3 (436.774) 64
9 0:06 +0.39 2...Nc6 3.Nc3 Nf6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Bf5 7.Bxc6+ bxc6 (436.774) 64
9 0:06 +0.39 2...Nf6 3.Nc3 Nc6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Bf5 7.Bxc6+ bxc6 (436.774) 64
9 0:06 +0.84 2...Bd7 3.Nf3 Nc6 4.Bc4 Nf6 5.Ng5 d5 6.exd5 Nb4 (436.774) 64
-----
10 0:06 +0.39 2...Nc6 3.Nc3 Nf6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (455.579) 66
10 0:06 +0.90 2...f5 3.exf5 Bxf5 4.Bd3 Bxd3 5.Qxd3 c5 6.dxc5 Qa5+ 7.Nc3 Qxc5 8.Nf3 (455.579) 66
9 0:06 +0.39 2...Nf6 3.Nc3 Nc6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Bf5 7.Bxc6+ bxc6 (455.579) 66
9 0:06 +0.84 2...Bd7 3.Nf3 Nc6 4.Bc4 Nf6 5.Ng5 d5 6.exd5 Nb4 (455.579) 66
-----
10 0:06 +0.39 2...Nc6 3.Nc3 Nf6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (464.298) 67
10 0:06 +0.39 2...Nf6 3.Nc3 Nc6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (464.298) 67
10 0:06 +0.90 2...f5 3.exf5 Bxf5 4.Bd3 Bxd3 5.Qxd3 c5 6.dxc5 Qa5+ 7.Nc3 Qxc5 8.Nf3 (464.298) 67
9 0:06 +0.84 2...Bd7 3.Nf3 Nc6 4.Bc4 Nf6 5.Ng5 d5 6.exd5 Nb4 (464.298) 67
-----
10 0:06 +0.39 2...Nc6 3.Nc3 Nf6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (560.748) 80
10 0:06 +0.39 2...Nf6 3.Nc3 Nc6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (560.748) 80
10 0:06 +0.90 2...f5 3.exf5 Bxf5 4.Bd3 Bxd3 5.Qxd3 c5 6.dxc5 Qa5+ 7.Nc3 Qxc5 8.Nf3 (560.748) 80
10 0:06 +1.21 2...Bd7 3.Nf3 Nf6 4.Bd3 Nc6 5.O-O Bg4 6.Be3 e5 7.dxe5 dxe5 (560.748) 80
-----
10 0:07 +0.39 2...Nc6 3.Nc3 Nf6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (659.887) 92
10 0:07 +0.39 2...Nf6 3.Nc3 Nc6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (659.887) 92
10 0:07 +0.90 2...f5 3.exf5 Bxf5 4.Bd3 Bxd3 5.Qxd3 c5 6.dxc5 Qa5+ 7.Nc3 Qxc5 8.Nf3 (659.887) 92
10 0:07 +1.11 2...g6 3.Nf3 Nf6 4.Bd3 Nc6 5.O-O Bg7 6.Nc3 O-O 7.Bf4 (659.887) 92
-----
10 0:07 +0.39 2...Nc6 3.Nc3 Nf6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (766.116) 105
10 0:07 +0.39 2...Nf6 3.Nc3 Nc6 4.Nf3 d5 5.exd5 Nxd5 6.Bb5 Nxc3 7.Bxc6+ bxc6 8.bxc3 (766.116) 105
10 0:07 +0.90 2...f5 3.exf5 Bxf5 4.Bd3 Bxd3 5.Qxd3 c5 6.dxc5 Qa5+ 7.Nc3 Qxc5 8.Nf3 (766.116) 105
10 0:07 +0.92 2...h6 3.Nf3 g5 4.Bb5+ c6 5.Be2 Nf6 6.Nc3 g4 7.Nh4 Be6 (766.116) 105

Please note f5 fails-low, but Glaurung resolves it before checking second best.

It does the same for 2...Bd7 and 2...g6 (in bold), so the user knows the actual score, and can add these moves to their tree:

0.39 2...Nc6
0.39 2...Nf6
0.90 2...f5
0.92 2...h6
1.11 2...Bd7
1.21 2...g6

The new behavior wouldn't have resolved Bd7 or g6 at all, and wouldn't have resolved 2...f5 until Nf6 was resolved, ommiting Bd7 and g6 completely so the user wouldn't have known those moves were interesting (and given "for free").

So, Stockfish changed its behavior at some point between Glaurung and the current version.

[syzygy]

So, Stockfish changed its behavior at some point between Glaurung and the current version.

So at some point between 2008 and 2013. The really old root-search code is indeed very different from the current code.

[Joerg Oster]

After some first tests, it seems to save time.

Thank you! This is what I suspected!

The reason it saves time is because the new behavior will waste time looking at the other moves whenever they don't beat alpha, plus, Stockfish will have to look at them anyway in the next PV line.

So, I think the fastest approach would be to apply your patch in the all the MultiPV lines, except the last one (in MultiPV=2, only the first one, in MultiPV=3, only the first 2, in MultiPV=4, only the first 3, and so on - this would be consitent with not using the patch in SinglePV, since the only one is the last one), since for the last one Stockfish will not get a chance to look at alternative moves again in a new PV, the last one behaves like in SinglePV.

That's exactly what I tried to implement now.
You can find the source here: https://github.com/joergoster/Stockfish ... ultipv_old

[Joerg Oster]

And here is a sample output of the given position.

Code: Select all

setoption name Contempt value 0
setoption name MultiPV value 4
position fen rnbqkbnr/ppp1pppp/3p4/8/3PP3/8/PPP2PPP/RNBQKBNR b KQkq -
go depth 12
info depth 1 seldepth 1 multipv 1 score cp -42 nodes 59 nps 29500 tbhits 0 time 2 pv g8f6
info depth 1 seldepth 1 multipv 2 score cp -107 nodes 59 nps 29500 tbhits 0 time 2 pv d6d5
info depth 1 seldepth 1 multipv 3 score cp -128 nodes 59 nps 29500 tbhits 0 time 2 pv a7a6
info depth 1 seldepth 1 multipv 4 score cp -142 nodes 59 nps 29500 tbhits 0 time 2 pv b7b6
info depth 2 seldepth 2 multipv 1 score cp -57 nodes 197 nps 98500 tbhits 0 time 2 pv g8f6 f2f3
info depth 2 seldepth 2 multipv 2 score cp -97 nodes 197 nps 98500 tbhits 0 time 2 pv d6d5 f2f3
info depth 2 seldepth 2 multipv 3 score cp -103 nodes 197 nps 98500 tbhits 0 time 2 pv e7e5 b1c3
info depth 2 seldepth 2 multipv 4 score cp -150 nodes 197 nps 98500 tbhits 0 time 2 pv a7a6 d4d5
info depth 3 seldepth 3 multipv 1 score cp -62 nodes 553 nps 276500 tbhits 0 time 2 pv g8f6 b1c3 e7e5 d4e5 d6e5 d1d8 e8d8
info depth 3 seldepth 3 multipv 2 score cp -67 nodes 553 nps 276500 tbhits 0 time 2 pv e7e5 d4e5 d6e5
info depth 3 seldepth 3 multipv 3 score cp -97 nodes 553 nps 276500 tbhits 0 time 2 pv c7c6 b1c3 g8f6
info depth 3 seldepth 3 multipv 4 score cp -122 nodes 553 nps 276500 tbhits 0 time 2 pv d6d5 b1c3 g8f6
info depth 4 seldepth 4 multipv 1 score cp 2 nodes 964 nps 482000 tbhits 0 time 2 pv g8f6 h2h3 d6d5 e4d5 d8d5
info depth 4 seldepth 5 multipv 2 score cp -67 nodes 964 nps 482000 tbhits 0 time 2 pv e7e5 d4e5 d6e5 d1d8 e8d8
info depth 4 seldepth 4 multipv 3 score cp -73 nodes 964 nps 482000 tbhits 0 time 2 pv d6d5 b1c3 g8f6 e4d5
info depth 4 seldepth 4 multipv 4 score cp -123 nodes 964 nps 482000 tbhits 0 time 2 pv c7c6 b1c3 g8f6 h2h3
info depth 5 seldepth 5 multipv 1 score cp -73 nodes 2222 nps 555500 tbhits 0 time 4 pv g8f6 b1c3 d6d5 e4d5 f6d5
info depth 5 seldepth 5 multipv 2 score cp -77 nodes 2222 nps 555500 tbhits 0 time 4 pv a7a6 h2h3 g8f6 b1c3 e7e5
info depth 5 seldepth 6 multipv 3 score cp -105 nodes 2222 nps 555500 tbhits 0 time 4 pv e7e5 d4e5 d8h4 b1c3 d6e5
info depth 5 seldepth 5 multipv 4 score cp -158 upperbound nodes 2222 nps 555500 tbhits 0 time 4 pv d6d5 e4e5 f7f6 b1c3 f6e5 d4e5
info depth 6 seldepth 7 multipv 1 score cp -74 nodes 4903 nps 817166 tbhits 0 time 6 pv c7c5 b1c3 g8f6 d4c5 d8a5 c5d6
info depth 6 seldepth 6 multipv 2 score cp -122 nodes 4903 nps 817166 tbhits 0 time 6 pv g8f6 b1c3 d6d5 e4e5 f6e4 g1f3 e4c3
info depth 6 seldepth 7 multipv 3 score cp -175 nodes 4903 nps 817166 tbhits 0 time 6 pv a7a6 g1f3 g7g6 d4d5 g8f6 b1c3
info depth 6 seldepth 7 multipv 4 score cp -186 upperbound nodes 4903 nps 817166 tbhits 0 time 6 pv e7e5 d4e5 d6e5 d1d8 e8d8 g1f3 g8f6 f3e5
info depth 7 seldepth 8 multipv 1 score cp -74 nodes 9704 nps 1078222 tbhits 0 time 9 pv c7c5 d4c5 g8f6 d1d3 d6c5 g1f3 d8d3
info depth 7 seldepth 8 multipv 2 score cp -75 nodes 9704 nps 1078222 tbhits 0 time 9 pv c7c6 b1c3 g8f6 h2h3 d8a5 c1d2 e7e5
info depth 7 seldepth 7 multipv 3 score cp -103 nodes 9704 nps 1078222 tbhits 0 time 9 pv g8f6 b1c3 c7c5 g1f3 d8a5 d1d3 c8d7 d4c5
info depth 7 seldepth 9 multipv 4 score cp -152 nodes 9704 nps 1078222 tbhits 0 time 9 pv a7a6 g1f3 c7c5 d4c5 d8a5 d1d2 a5d2 b1d2 d6c5
info depth 8 seldepth 10 multipv 1 score cp -85 nodes 17088 nps 1220571 tbhits 0 time 14 pv e7e5 d4e5 b8c6 e5d6 d8d6 d1d6 f8d6 g1f3
info depth 8 seldepth 9 multipv 2 score cp -107 nodes 17088 nps 1220571 tbhits 0 time 14 pv c7c5 d4c5 d8a5 b1c3 g8f6 d1d3 a5c5 g1f3 c5b4
info depth 8 seldepth 9 multipv 3 score cp -112 nodes 17088 nps 1220571 tbhits 0 time 14 pv c7c6 b1c3 g8f6 h2h3 e7e5 g1f3 e5d4 d1d4
info depth 8 seldepth 8 multipv 4 score cp -112 nodes 17088 nps 1220571 tbhits 0 time 14 pv g8f6 b1c3 c7c6 h2h3 e7e5 g1f3 e5d4 d1d4
info depth 9 seldepth 14 multipv 1 score cp -60 nodes 51674 nps 1291850 tbhits 0 time 40 pv b8d7 g1f3 e7e5 b1c3 e5d4 d1d4 g8f6 d4e3 d7e5
info depth 9 seldepth 12 multipv 2 score cp -69 nodes 51674 nps 1291850 tbhits 0 time 40 pv e7e5 d4e5 b8c6 b1c3 c6e5 h2h3 g8f6 g1f3 e5f3 d1f3 c7c6
info depth 9 seldepth 12 multipv 3 score cp -87 nodes 51674 nps 1291850 tbhits 0 time 40 pv c7c5 d4c5 g8f6 b1c3 b8c6 f1b5 d6c5 g1f3 d8d1 e1d1
info depth 9 seldepth 12 multipv 4 score cp -92 nodes 51674 nps 1291850 tbhits 0 time 40 pv c7c6 g1f3 b8d7 f1d3 e7e5 e1g1 e5d4 f3d4 g8f6
info depth 10 seldepth 16 multipv 1 score cp -67 nodes 118495 nps 1331404 tbhits 0 time 89 pv e7e5 g1f3 e5d4 d1d4 b8c6 f1b5 g8f6 e1g1 a7a6 b5c6 b7c6
info depth 10 seldepth 14 multipv 2 score cp -87 nodes 118495 nps 1331404 tbhits 0 time 89 pv c7c6 g1f3 b8d7 f1d3 e7e5 b1c3 e5d4 f3d4 d7e5 e1g1 g8f6 d4f3
info depth 10 seldepth 13 multipv 3 score cp -99 nodes 118495 nps 1331404 tbhits 0 time 89 pv b8d7 g1f3 e7e5 f1c4 e5d4 d1d4 d8f6 d4d2 d7b6 c4e2 f8e7 e1g1
info depth 10 seldepth 14 multipv 4 score cp -137 upperbound nodes 118495 nps 1331404 tbhits 0 time 89 pv c7c5 d4c5 g8f6 b1c3 d8a5 f1d3 a5c5 g1f3 c8g4 e1g1 b8c6 d3b5
info depth 11 seldepth 17 multipv 1 score cp -66 nodes 191522 nps 1311794 tbhits 0 time 146 pv g8f6 b1c3 b8d7 g1f3 e7e5 a2a4 e5d4 d1d4 f8e7 f1c4 e8g8 e1g1 c7c5
info depth 11 seldepth 15 multipv 2 score cp -82 nodes 191522 nps 1311794 tbhits 0 time 146 pv e7e5 d4e5 d8e7 g1f3 d6e5 b1c3 g8f6 f1e2 b8c6 e1g1 c8d7 h2h3
info depth 11 seldepth 15 multipv 3 score cp -86 nodes 191522 nps 1311794 tbhits 0 time 146 pv c7c6 g1f3 b8d7 f1c4 b7b5 c4d3 e7e5 c2c3 g8f6 e1g1 c8b7 h2h3 f8e7
info depth 11 seldepth 16 multipv 4 score cp -89 nodes 191522 nps 1311794 tbhits 0 time 146 pv b8d7 g1f3 e7e5 f1c4 e5d4 d1d4 d8f6 d4d2 d7e5 f3e5 f6e5
info depth 12 seldepth 15 multipv 1 score cp -70 nodes 290788 nps 1309855 tbhits 0 time 222 pv b8d7 g1f3 g8f6 b1c3 e7e5 a2a4 f8e7 f1c4 h7h6 e1g1 e8g8 b2b4 c7c6
info depth 12 seldepth 18 multipv 2 score cp -76 nodes 290788 nps 1309855 tbhits 0 time 222 pv c7c6 g1f3 b8d7 b1c3 e7e5 f1e2 g8f6 a2a4 f8e7 e1g1 e8g8 e2c4 e5d4
info depth 12 seldepth 17 multipv 3 score cp -83 nodes 290788 nps 1309855 tbhits 0 time 222 pv g8f6 b1c3 b8d7 f1c4 e7e5 g1f3 f8e7 a2a4 h7h6 e1g1 e8g8 b2b4 c7c6 c4b3
info depth 12 seldepth 16 multipv 4 score cp -83 nodes 290788 nps 1309855 tbhits 0 time 222 pv e7e5 d4e5 d8e7 g1f3 d6e5 b1c3 g8f6 f1e2 c8g4 h2h3 g4f3 e2f3 b8d7 e1g1 a8d8
bestmove b8d7 ponder g1f3

[Ovyron]

Thanks Joerg!

[Joerg Oster]

Thanks Joerg!

You're welcome!
Thanks for bringing this up.

This should also be slightly advantageous for my next experiment.
In SMP mode, I want to do a full PV search for all root moves,
eventually splitting the root moves over all helper threads.
I'm very interested in seeing how this competes with the current SMP search
at some longer TC or in analysis mode.