Confused by MultiPV

[hgm]

I don't like the "increase in performance". I have seen users play a real game using multi-PV mode, not knowing they are killing the program, because that lops off plies compared to what the normal search would reach.

best-2 is bad in that every iteration takes 2x as long. Moving the EBF from 2.0 to 4.0. In an exponential problem, that is murder...

Well, people sometimes also play with ponder switched off, too few cores enabled, the depth limited to 4 ply, a hash table larger than their physical memory, etc. I would not worry about it. If the ask the computer to do the wrong thing, they don't get what they want. That is unavoidable in dealing with computers.

I agree that veto-Chess is pretty tough on a search engine. I don't think the effective branching factor would double, though. Only the second move that scores above beta can cause a cut-off, but all nodes remain all nodes. So you lose a factor two in tree size for every 2 ply, i.e. sqrt(2) per ply. And wherever the null move fails high, you would take the cutoff immediately, as the null move represents any passive move, and there are likely to be at least two of those.

[Zach Wegner]

I agree that veto-Chess is pretty tough on a search engine. I don't think the effective branching factor would double, though. Only the second move that scores above beta can cause a cut-off, but all nodes remain all nodes. So you lose a factor two in tree size for every 2 ply, i.e. sqrt(2) per ply. And wherever the null move fails high, you would take the cutoff immediately, as the null move represents any passive move, and there are likely to be at least two of those.

For this variant, wouldn't it be easier on the search (and your brain) to just generate a veto move normally? Then on the next ply the vetoed move is excluded from the move list.

[hgm]

I am not completely sure ho you want to do it. You could consider vetoing a seperate move, where you are allowed to move the opponent's piece back where it came from. (Not a null move, but a minus-one move, so to speak. ) And then forbid the same side does the same move twice in row. This would make you effectively search at very uneven depth, unless you extend all such minus-one moves by 2 ply. And it would cause all kind of problems with hashing, as the same position would not really be the same if it was reached by a different move.

I think all in all it might be much easier to simply use an alpha-beta search where alpha tracks the second-best move so far, in stead of the best.

Code: Select all

int Search(alpha1, beta)
{
    int alpha2 = alpha1;

    for(ALL_MOVES)
    {
        score = -Search(-beta, -alpha2)
        if(score > alpha2) 
        {
            alpha2 = score;
            if(alpha2 > alpha1) SWAP(alpha1, alpha2);
            if(alpha2 >= beta) return beta.
        }
    }
    return alpha2;
}

That is not so bad, is it?

And in the root, you now automticlly hve at least 2 PVs!

[bob]

I don't like the "increase in performance". I have seen users play a real game using multi-PV mode, not knowing they are killing the program, because that lops off plies compared to what the normal search would reach.

best-2 is bad in that every iteration takes 2x as long. Moving the EBF from 2.0 to 4.0. In an exponential problem, that is murder...

Well, people sometimes also play with ponder switched off, too few cores enabled, the depth limited to 4 ply, a hash table larger than their physical memory, etc. I would not worry about it. If the ask the computer to do the wrong thing, they don't get what they want. That is unavoidable in dealing with computers.

I agree that veto-Chess is pretty tough on a search engine. I don't think the effective branching factor would double, though. Only the second move that scores above beta can cause a cut-off, but all nodes remain all nodes. So you lose a factor two in tree size for every 2 ply, i.e. sqrt(2) per ply. And wherever the null move fails high, you would take the cutoff immediately, as the null move represents any passive move, and there are likely to be at least two of those.

The problem I see is that in a normal search, the best move at the next-to-last iteration remains best at the last iteration something like 85% of the time. Which means you incur one large tree to search the best move, and N small trees to dismiss the rest. With N-best, N=2, that has to double. You now incur two large trees and N-1 small trees. Which for me is a ply. If you do N=4 best, that is (again for me) two plies. 8 = 3 plies. That's getting significant...

[hgm]

I think we are by now talking about a different problem. I thought you were taking about the veto Chess I mentioned, but apparently I was wrong, and what you were saying still pertained to multiPV. I am not sure how the EBF comes in, then. You did mean "effective branching factor" by that, not?

If every iteration takes twice longer, this just means the total time is twice longer. That is in the pre-factor. The EBF will be exactly the same.

Only in veto-Chess you drive up the EBF.

[bob]

I think we are by now talking about a different problem. I thought you were taking about the veto Chess I mentioned, but apparently I was wrong, and what you were saying still pertained to multiPV. I am not sure how the EBF comes in, then. You did mean "effective branching factor" by that, not?

If every iteration takes twice longer, this just means the total time is twice longer. That is in the pre-factor. The EBF will be exactly the same.

Only in veto-Chess you drive up the EBF.

Yes, and I was still talking about "multi-PV" in my comments. As far as the EBF voes, it goes up by 4 if you do best-4, or by 8 if you do best 8 which is what I was referring to...

[jwes]

Your approach does seem to search all the later moves N times with closed window, though, while my method searches them only once (also with closed window).

Of course the closed-window searches are not very expensive in comparison to the first N, but there are a lot of other moves, so it might still add up to something significant.

There is a difference. A typical position has 38 legal moves. Suppose you want the "best 10" moves.

To find the best move, you search 1 with full window, 37 with null-window.

To find the second best, you search 1 with full window, 36 with null window.

...

To find the tenth best, you search 1 with full window, 28 with null-window.

Total is 10 with full window, 323 moves searched with null-window.

Now to compare effort. I looked at a few positions from the last CCT event where we used an 8-way box. The first move searched on the final iteration that was completely finished took from 50% to 75% of the total time. With most being closer to 75 (I did not do an exhaustive comparison however so this is just a close guess).

That means that 10 of my searches above will take 10 x 75 computation units, while the remaining moves will take what is effectively 10 x 25. So that the entire process takes about 10x longer. Since you can't know which of the 38 moves are the 10 best, it would seem to me that the only alternative would be to search all 38 with a wide window, which translates into 38 * 75 computation units. 38*75 is > 10*100, so it would appear to me that the best approach was the one I described. Not the easiest to program, but the best from a search space point of view...

You could search 10 with wide window and then search the rest with a null window based on the lowest score of the 10 and research on fail high. The big difference is with the hash table. In crafty, you clear the hash table between variations to avoid weirdness. If you search with n open windows, there is no need to clear the hash table.

Which 10 do you search with wide window? How do you know one of the best 10 is not ranked last at the root?

You search the 10 that had the highest scores from the previous iteration, of course.

What does that have to do with the best 10 for the _current_ iteration? Any move can become best in the current iteration, and some of the best 10 from the previous iteration may well not be in the best 10 for this iteration.

How is this different from taking the the best move from the previous iteration in PVS ?

If you don't clear hash tables, the scores interact and don't make a lot of sense. The second-best move can return a higher score than the best move, for example, because some scores from the best move get grafted into the tree for the second-best...

And searching with open windows doesn't solve the hashing issue at all. I already search each best move with an "open window" and the hash table causes interaction between the different best moves... That problem remains and can't be eliminated except by clearing things.

I believe that most ot the hash problems occur when combining shallow searches with deep hash entries. The multiple open window is essentially similar to the single PV search, so I don't see why the hash table would cause more problems.

Here's the original complaint: "Bob, why is it that when I do a multi-pv annotate, the scores you show can't be reproduced with a normal search? Also, why is the score for the nth move sometimes higher than the score for the move given as best?" Crafty would work just fine without the clear operation, but the scores suddenly are not consistent. The best can be lower than #4, etc, because of how hash entries graft information from one search to the next and change the scores...

I think that the first problem occurs much less, for the reason above. The second cannot occur, since the scores are sorted before being output. The problem with clearing the hash is that it takes much longer to search to a given depth.

[hgm]

Yes, and I was still talking about "multi-PV" in my comments. As far as the EBF voes, it goes up by 4 if you do best-4, or by 8 if you do best 8 which is what I was referring to...

I think this is completely wrong. The EBF stays the same, and it is just the search time that goes op by a factor 4 or 8. Unless you are doing things even more inefficiently then you told us so far.

[pijl]

I've put multipv to the test. I've done four positions, each of them searched up to 12 ply with CTD in 1 to 4 pv mode.
Of course, the conclusion is that multipv generally hurts, but how much depends on both hashtable, score distance between best and nth move and the amount of pv changes that occur, both in the normal mode and in the nth best lines.

The first one is a position with lots of transpositions: The start position. An additional characteristic is that all moves are within a small score window, so multi pv should not hurt as much.
CTD is stubborn concerning its bestmove, so the normal search has no PV change:

10 ply:
1 pv: 2.2M nodes
2 pv: 2.3M nodes
3 pv: 3.4M nodes
4 pv: 3.6M nodes
5 pv: 4.3M nodes

11 ply:
1 pv: 6.5M nodes
2 pv: 6.0M nodes!
3 pv: 11.3M nodes
4 pv: 11.2M nodes!
5 pv: 12.0M nodes

12 ply:
1 pv: 13.0M nodes
2 pv: 12.8M nodes!
3 pv: 21.3M nodes
4 pv: 27.3M nodes
5 pv: 29.3M nodes

Interesting to see is that the 2pv mode sometimes needs less nodes to complete a ply. I guess that is due to the larger amount of relevant exact scores in the hashtable due to the number of transpositions the search will find.

The next position is the first positional test position from LCT2:
[d] r3kb1r/3n1pp1/p6p/2pPp2q/Pp2N3/3B2PP/1PQ2P2/R3K2R w KQkq -

10 ply:
1 pv: 1.4M nodes
2 pv: 4.0M nodes
3 pv: 9.2M nodes
4 pv: 10.3M nodes

11 ply (here the single pv version has a pv change to the solution move):
1 pv: 12.2M nodes
2 pv: 10.9M nodes!
3 pv: 18.5M nodes
4 pv: 23.9M nodes

12 ply:
1 pv: 28.1M nodes
2 pv: 25.4M nodes
3 pv: 47.4M nodes
4 pv: 61.7M nodes

Due to the pv change, which is expensive in any program, the 2 pv version needs less nodes at 11 and 12 ply searches. But the main conclusion from this position should be that when the program is sure about its bestmove, multi pv will hurt a lot.

The next position is also from the LCT suite, but here CTD does not find the solution. It did not change its pv in the test run, but in the multi pv runs there were some changes in the selection of the nth move:
[d] r2qkb1r/1b3ppp/p3pn2/1p6/1n1P4/1BN2N2/PP2QPPP/R1BR2K1 w kq -

10 ply:
1 pv: 8.1M nodes
2 pv: 13.8M nodes
3 pv: 19.4M nodes
4 pv: 27.4M nodes

11 ply:
1 pv: 13.5M nodes
2 pv: 25.3M nodes
3 pv: 39.3M nodes
4 pv: 57.8M nodes

12 ply:
1 pv: 25.4M nodes
2 pv: 51.9M nodes
3 pv: 78.1M nodes
4 pv: 111M nodes

Finally the previous position after playing Ne5. This position has a number of pv changes:
[d] r2qkb1r/1b3ppp/p3pn2/1p2N3/1n1P4/1BN5/PP2QPPP/R1BR2K1 b kq -

9 ply ( 2 pv changes):
1 pv: 7.3M nodes
2 pv: 7.8M nodes
3 pv: 9.2M nodes
4 pv: 8.5M nodes

10 ply (1 pv change):
1 pv: 14.5M nodes
2 pv: 18.4M nodes
3 pv: 19.9M nodes
4 pv: 19.4M nodes

11 ply (no pv change):
1 pv: 23.5M nodes
2 pv: 30.0M nodes
3 pv: 53.1M nodes
4 pv: 47.7M nodes

12 ply (no pv change):
1 pv: 43.9 M nodes
2 pv: 60.2M nodes
3 pv: 124M nodes
4 pv: 139M nodes

[bob]

Your approach does seem to search all the later moves N times with closed window, though, while my method searches them only once (also with closed window).

Of course the closed-window searches are not very expensive in comparison to the first N, but there are a lot of other moves, so it might still add up to something significant.

There is a difference. A typical position has 38 legal moves. Suppose you want the "best 10" moves.

To find the best move, you search 1 with full window, 37 with null-window.

To find the second best, you search 1 with full window, 36 with null window.

...

To find the tenth best, you search 1 with full window, 28 with null-window.

Total is 10 with full window, 323 moves searched with null-window.

Now to compare effort. I looked at a few positions from the last CCT event where we used an 8-way box. The first move searched on the final iteration that was completely finished took from 50% to 75% of the total time. With most being closer to 75 (I did not do an exhaustive comparison however so this is just a close guess).

That means that 10 of my searches above will take 10 x 75 computation units, while the remaining moves will take what is effectively 10 x 25. So that the entire process takes about 10x longer. Since you can't know which of the 38 moves are the 10 best, it would seem to me that the only alternative would be to search all 38 with a wide window, which translates into 38 * 75 computation units. 38*75 is > 10*100, so it would appear to me that the best approach was the one I described. Not the easiest to program, but the best from a search space point of view...

You could search 10 with wide window and then search the rest with a null window based on the lowest score of the 10 and research on fail high. The big difference is with the hash table. In crafty, you clear the hash table between variations to avoid weirdness. If you search with n open windows, there is no need to clear the hash table.

Which 10 do you search with wide window? How do you know one of the best 10 is not ranked last at the root?

You search the 10 that had the highest scores from the previous iteration, of course.

What does that have to do with the best 10 for the _current_ iteration? Any move can become best in the current iteration, and some of the best 10 from the previous iteration may well not be in the best 10 for this iteration.

How is this different from taking the the best move from the previous iteration in PVS ?

It isn't. But the best move from the previous iteration is not always best at this iteration. And what about the other 9 moves (in a best-10 search). How do you get those? Only by searching with an open window, or else a normal search with proven better moves excluded...

If you don't clear hash tables, the scores interact and don't make a lot of sense. The second-best move can return a higher score than the best move, for example, because some scores from the best move get grafted into the tree for the second-best...

And searching with open windows doesn't solve the hashing issue at all. I already search each best move with an "open window" and the hash table causes interaction between the different best moves... That problem remains and can't be eliminated except by clearing things.

I believe that most ot the hash problems occur when combining shallow searches with deep hash entries. The multiple open window is essentially similar to the single PV search, so I don't see why the hash table would cause more problems.

Here's the original complaint: "Bob, why is it that when I do a multi-pv annotate, the scores you show can't be reproduced with a normal search? Also, why is the score for the nth move sometimes higher than the score for the move given as best?" Crafty would work just fine without the clear operation, but the scores suddenly are not consistent. The best can be lower than #4, etc, because of how hash entries graft information from one search to the next and change the scores...

I think that the first problem occurs much less, for the reason above. The second cannot occur, since the scores are sorted before being output. The problem with clearing the hash is that it takes much longer to search to a given depth.

You can sort or whatever, but the issue is this:

If, after you search the first move and get a score of N, you now search other moves and get a score for one of them that is > N. Is this possibly true (second move is really better)? yes. Is it likely? No. You just seeded the hash table with stuff that changed the score of the second best move. And if you go back and re-search the best you might get a better score for it as well due to left-over stuff in the hash from the other searches. So "sorting" is not the answer. To get consistent results, the approach I explained works. Anything else will produce some peculiar stuff that generates questions and confusion.

So, do you want an actual ordering of the moves at a depth=N search? Crafty gives that every time. Or do you want some scores that are inconsistet when compared? not clearing the hash guarantees that here and there...

It's just the way this stuff works...