Best move and parallel alpha-beta

[FeikeBoomstra]

Today I found for the first time a position, where the best move isn't constant.
If I analyze this position several times in a row, I get sometimes a different best value and sometimes a different move with a different best value.

So it is not the case: different move, same best value, that wouldn't bother me.

I remember Bert wrote once that he was facing the same problem. Has anybody a clue?

With one thread, I don't see the problem. The problem occurs even if I start with a "clean" hash. I am using the alpha-beta algorithm of Aske van der Plaat.

Any idea's?

[TAILLE]

Hi Feike,

Today I found for the first time a position, where the best move isn't constant.
If I analyze this position several times in a row, I get sometimes a different best value and sometimes a different move with a different best value.

So it is not the case: different move, same best value, that wouldn't bother me.

I remember Bert wrote once that he was facing the same problem. Has anybody a clue?

With one thread, I don't see the problem. The problem occurs even if I start with a "clean" hash. I am using the alpha-beta algorithm of Aske van der Plaat.

Any idea's?

Damy has also this problem. I analysed it and finally found the explanation but, for the time being, I did not fond a way to correct it.
The probem you have may be the same as mine but I have first three questions :
1) Do you use a shared hashtable ?
2) Do you store the evaluation of the position and its depth in the hash table ?
3) Does this problem appear more often with kings ?
If you answer yes at each question then I think I can help you.

[FeikeBoomstra]

Hi Gerard,

Yes, I use a shared Hashtable.
Yes I store the value of the position and the depth in the hashtable.
I don't know if it occurs more with kings, I have found only one position in which I see two different moves and three different values.

I am very interested in a possible explanation.

Feike

[FeikeBoomstra]

Your remark about the kings triggered me.

If there are kings, the same position can be found on a different distance from the root and therefor with a different value.

In my case, the closer to the root position value, overwrites the previous value in the hash.

So the order of evaluation of the positions can have an influence on the aggregated value
in the root.

How about this theory?

[TAILLE]

Hi Gerard,

Yes, I use a shared Hashtable.
Yes I store the value of the position and the depth in the hashtable.
I don't know if it occurs more with kings, I have found only one position in which I see two different moves and three different values.

I am very interested in a possible explanation.

Feike

With these "yes" answers I guess you have exactly the same problem as me. For Damy the explanation is the following :
During the exploration of the tree you may have to explore the two following sequences of moves :
sequence 1 : move a1, move a2, ... move ak, ...
sequence 2 : move b1, move b2, ... move bl, ...
Suppose now that we reach exactly the same position P after move ak and move bl and suppose k < l.
The evaluation of sequence 2 will then depend on weither or not the sequence 1 till move ak, has been already evaluated:
-if it is has been already evaluated to eval(k) then the position P reached after move bl of sequence 2 will also be evaluated to eval(k)
-otherwise the position P reached after move bl of sequence 2 will be evaluated to eval(l).

In a multithread environment you never know in which order two sequences of moves will be evaluated and that is the problem.
With no kings on the board the problem may happen but not very often because in the great majority of the cases when the same position is reached in two sequences this position in reach at same depth in the tree.
As soon as depth becomes high and kings appear in the tree the problem appear more often.

For the time being I found some solutions to limit the problem but without solving it completly.

[FeikeBoomstra]

In case of kings, we agree.

If there are no kings, I am not sure. Can you construct two sequences of different length that result in the same position? I thought I read once that, as long as there are no kings, the same position can occur only at the same depth?

[BertTuyt]

Feike/Gerard,

if there are no Kings on the board, or during a sequence no man will promote to king. And if next to that plain "alfa-beta" is used, so without pruning, moves-extension and/or soft-evaluations, then I think even parallel alfa-beta should always find the same move with the same score.
Or do I miss something.

Bert

[FeikeBoomstra]

That's what I think too.

[TAILLE]

In case of kings, we agree.

If there are no kings, I am not sure. Can you construct two sequences of different length that result in the same position? I thought I read once that, as long as there are no kings, the same position can occur only at the same depth?

sequence 1 :
1.27-22 18x27 2.37-31 26x37 3.42x11 06x17 4.48-42 24-29 5.33x24 14-20 6.25x14 09x40
sequence 2 :
1.37-31 26x37 2.42x31 14-20 3.25x14 09x20 4.27-22 18x27 5.31x11 06x17 6.48-42 25-29 7.33x24 20x40

[FeikeBoomstra]

6, ... 25-29 should be 6. ... 24-29
but it's really convincing!

[Ed Gilbert]

if there are no Kings on the board, or during a sequence no man will promote to king. And if next to that plain "alfa-beta" is used, so without pruning, moves-extension and/or soft-evaluations, then I think even parallel alfa-beta should always find the same move with the same score.

Since most programs use extensions and truncations, it is not even necessary that two paths transposing into the same position have different path lengths.

For the time being I found some solutions to limit the problem but without solving it completly.

I don't see why this should be considered a problem. A search with heuristics gives a very inexact result, so if a few positions get searched to slightly different real depths depending on the paths, I don't see that this causes any problems.

A similar situation occurs in the detection of draws by repetition. This is actually a real problem, because the draw score that gets stored in the hashtable for one path can be horribly incorrect for another path. It is commonly called the 'graph history interaction' problem. There are papers describing some solutions, but I could not understand the algorithms enough to try to implement them. AFAIK all the chess programmers ignore this problem.

-- Ed

[TAILLE]

A similar situation occurs in the detection of draws by repetition. This is actually a real problem, because the draw score that gets stored in the hashtable for one path can be horribly incorrect for another path. It is commonly called the 'graph history interaction' problem. There are papers describing some solutions, but I could not understand the algorithms enough to try to implement them. AFAIK all the chess programmers ignore this problem.
-- Ed

I agree with you Ed., a draw by repetition is almost always incorrectly handled by the hash table.
In theory it may happen that you can find a win (which is the correct result) without a hashtable, while you may find only a draw if you use (badly) a hashtable.
BTW I do use badly my hashtable !