Different analysis result when doing parallel search

[Ratta]

Hi, i'm getting interested in parallel search algorithms because i'm planning to implement it in my engine, and i noticed that Crafty and Glaurung sometimes give a different result (ie chose a different best move) when thinking at the same maximum depth, depending if the number of spawn threads is 1 or 2.

What is the cause of this behaviour? that some variations get different extensions/reductions in an SMP search? In Crafty i find this behaviour even more strange since IIUC it has no LMR (at least in the 20.14 open source version i'm testing).

Regards!

[bob]

Hi, i'm getting interested in parallel search algorithms because i'm planning to implement it in my engine, and i noticed that Crafty and Glaurung sometimes give a different result (ie chose a different best move) when thinking at the same maximum depth, depending if the number of spawn threads is 1 or 2.

What is the cause of this behaviour? that some variations get different extensions/reductions in an SMP search? In Crafty i find this behaviour even more strange since IIUC it has no LMR (at least in the 20.14 open source version i'm testing).

Regards!

20.14 definitely has LMR. But that isn't the issue. Two threads search in parallel and store stuff in the hash table. Sometimes, this information stored from one thread influences the search done by the other thread, and in some cases actually causes changes in the score and possibly the best move.

It's a known issue, it is perfectly normal, and can not be eliminated without huge SMP performance penalties...

[Ratta]

Thanks for your answer, i did not know that version of Crafty had LMR.
I'd be happy if i could get an explaination (or a link to, if this issue has been discussed before) of why this is perfectly normal, i mean, after all if the engine is going to play a different move, may this different move be a bad move?
Ah, BTW, this is material that may go to the wiki @chessprogramming, i will write it myself if i'm able to gather enough experience about this issue.
Regards!

[bob]

Thanks for your answer, i did not know that version of Crafty had LMR.
I'd be happy if i could get an explaination (or a link to, if this issue has been discussed before) of why this is perfectly normal, i mean, after all if the engine is going to play a different move, may this different move be a bad move?
Ah, BTW, this is material that may go to the wiki @chessprogramming, i will write it myself if i'm able to gather enough experience about this issue.
Regards!

Think about this example. Fine #70. Most programs solve this in 18-19-20 plies. Yet if you study the position, you absolutely can not win a pawn until ply 27, which means (since there are no checks are captures prior to that point, thus no extensions) you need a 26 ply search. How then can we solve it quicker? It is an artifact of hashing that goes like this.

You start your search and white plays optimally but black plays poorly, and after 10 plies you reach position P where you can force a win in just a few more moves.

Now you search other black moves and now begin to follow the optimal moves for black and when you get to ply 15 or so and even with optimal play by black you can force the game to reach position P. If you have to search from P forward, you can't find the win as there are not enough plies left, but if you probe the hash table, you find P, use it and realize "OK, I can force the game to reach position P, and I know position P is winnable, so here's a path to win the game that is deeper than the nominal search depth.

Now take the parallel search case. Suppose some of the time the processor that is searching position P completes it before the other processor forces its branch to reach P. It will find that good result in the table, use it, and find the better move quicker. But the next time, that processor is slower, and it does not complete and store the result for P before the other processor gets there, and now rather than having a deep-draft hash entry that says "P is won" it has to search on its own, it can't see deep enough, and thinks it is still drawish...

That's what non-deterministic parallel search does, over and over and over.

[Ratta]

Allright, i'm now understanding perfectly what you where trying to say, thanks for the example.
I suspect that this problem, ie that 'accidentally' analisysing a position resulting from bad play of one of the two players (or both) and storing this result in the HT may actually be useful because the same position would occur anyway (but later) with good play from both, may have an unwanted impact (and i never realized the importance of this) also in other tests that i usually perform, such as counting the number of nodes to see how good the heuristic move ordering is, or if the evaluation produces values that are good approximations of the outcome of shallow searches.
Next time i try to tune heuristics in my engine i will do so allowing to retrieve from the HT only positions searched at exactly the same depth, so at least i will have one less random factor to take care about

[bob]

Allright, i'm now understanding perfectly what you where trying to say, thanks for the example.
I suspect that this problem, ie that 'accidentally' analisysing a position resulting from bad play of one of the two players (or both) and storing this result in the HT may actually be useful because the same position would occur anyway (but later) with good play from both, may have an unwanted impact (and i never realized the importance of this) also in other tests that i usually perform, such as counting the number of nodes to see how good the heuristic move ordering is, or if the evaluation produces values that are good approximations of the outcome of shallow searches.
Next time i try to tune heuristics in my engine i will do so allowing to retrieve from the HT only positions searched at exactly the same depth, so at least i will have one less random factor to take care about

Here's the bad news part. If you have _perfect_ move ordering, you will require 26 plies to solve fine 70 every time. Because you always search the best path before you search that inferior path. So you can't use the inferior path to help with the best path search at all.

Sad...

BTW your hash idea is not a good one. It will greatly slow you down when you require an exact depth match rather than a >= match. It will eliminate most (but not all) of the funny business (you still get wrong draws and such and miss repetitions) I mentioned.

[Ratta]

My idea was only for testing of course, to remove as many random factors and just check how good the heuristic move ordering is, i never thought to leave hashing at ==.
Or are you trying to say that such a test would not be effective, in the sense that it would not reflect what would happen in "real life"? My point was that "better heuristic move ordering at == hashing also means better heuristic ordering at >=, and may provide a less stochastic testing environment", but i may be wrong.

That even in this way i would miss some draws by repetition is another very good point, and yet another i never thought about enough before. This time i'll try tro produce an example myself: I store a value x for the position P in the hashtable, and to calculate x i had to analyze many position including Q that is in the PV starting from P, and as such the value @P depend on the value @Q. Later i realize that Q may happen early, i analyze it and i find that i need the value of P, that i take "as is" without realising that the value of P had been calculated in the ipothesis of being able to go to Q without repetitions, and that this ipothesis is false at the current node. And i guess it is not possible to get around this problem without disabling hashing at all!
Regards!

[bob]

My idea was only for testing of course, to remove as many random factors and just check how good the heuristic move ordering is, i never thought to leave hashing at ==.
Or are you trying to say that such a test would not be effective, in the sense that it would not reflect what would happen in "real life"? My point was that "better heuristic move ordering at == hashing also means better heuristic ordering at >=, and may provide a less stochastic testing environment", but i may be wrong.

That even in this way i would miss some draws by repetition is another very good point, and yet another i never thought about enough before. This time i'll try tro produce an example myself: I store a value x for the position P in the hashtable, and to calculate x i had to analyze many position including Q that is in the PV starting from P, and as such the value @P depend on the value @Q. Later i realize that Q may happen early, i analyze it and i find that i need the value of P, that i take "as is" without realising that the value of P had been calculated in the ipothesis of being able to go to Q without repetitions, and that this ipothesis is false at the current node. And i guess it is not possible to get around this problem without disabling hashing at all!
Regards!

My only concern would be that if you hash one way while testing, and another way while playing, there is an opportunity to miss a bug in the way you hash while actually playing. I always use the "dance with the one that brung ya" type approach and test exactly as I play, except that I generally test without SMP search if I am just testing search/eval improvements, to reduce the variance of the results somewhat. Ditto for pondering so that I can play one game per cpu, rather than requiring two cpus for both programs to ponder. But eventually I test "pedal to the medal" to see how everything works together.