loop detection and hash table

[TAILLE]

Hi Rein,

Hi Gerard,

Here's another guess at your algorithm. Whenever there is at least 1 king for each side, you do the following. If you detect a hash hit where the stored remaining depth is at least 2 higher than the remaining depth in the search, you will follow the best moves stored in the hash table and check if one of these new positions has already occured in the current variation. If it does, you treat this position as a repetition. In this way, you can avoid the double symmetric masking of repetition paths that mask each other during iterative deepening. You only have to do this "hash table repetition checking" once, because the next iteratation already knows about the repetition. Only hash table overwrites can occiasionally destroy this information.

How close am I to your algorithm?

Rein

Hi Rein,

I do not quite understand your proposal.

Let’s take my example

Black to move

Analyse at depth 4 plies :
I) After 1...11-02 2.32-19 (position A) 02-07 3.19-23 (position B) you conclude that you reach a position with a big advantage to white (3 men ahead). I imagine here you store in your hash table that position B leads a big advantage at depth 0, and position A leads to the same big advantage but at depth 2
II) Now you run the second sequence beginning by 1...11-07 2.32-23 (position B) 07-02 3.23-19 (position A) . According to your proposal you look for position A in the hash table and you find a big advantage to white at depth 2, and you look for the best moves recorded in the hash table. You find the moves 02-07 19-23 and you discover that this sequence leads to the position B which was already seen in the sequence. Then, if I understand correctly, you conclude that position B is a draw by repetition.
This seems not a correct conclusion because now you cannot explore any more a sequence like 1…11-07 2.32-23 (position B) 07-02 3.23-46 which leads to a small advantage (1 man ahead) but avoid the repetition. I perfectly know that this sequence leads also to a draw but supposing you do not have the 5 pieces endgame database then your algorithm is not allowed to demonstrate this draw!

I guess I miss something in your proposal.

OK, so I slightly modify my proposal. If you have marked position B as a potential repetition, you should again check the hash table moves whenever you encounter it again. This is precisely the simulation procedure in the Kishimoto-Muller solution in their GHI-paper. My proposal was to avoid the "double masking" where you never detect a repetition. In their paper they don't discuss this because I don't think they use iterative deepening. Curiously, Campbell makes the remark that iterative deepening softens the GHI problem. He may be right in the sense that you get less errors because of draw propagation, but you can also miss draws as your example nicely shows!

So in your variation 1... 11-07 2.32-23 (B) 07-02 you first try the hash table moves, and find a repetition. If the alternative 23-46 gives a better score, you take that of course. Why would white want a repetition draw if he can achieve a heuristic advantage? BTW, I think I need to think a bit more carefully about the existence of ways to break out of the loop. In your example, black can force the repetition, but if you would place 3 more black pieces on the board, black would not want to force it. This "outside option effect" is not discussed in the GHI-papers.

Rein

Oops, I am completely lost! For positions with at least one king in each side it seems now you only use the best move information in the hash table, ignoring any (evaluation, depth) couple information. Do you really think it could be efficient?
Clearly I will wait for a deeper analysis before answering your question. Interesting (theoretical?) problem, isn’t it?

[Rein Halbersma]

Oops, I am completely lost! For positions with at least one king in each side it seems now you only use the best move information in the hash table, ignoring any (evaluation, depth) couple information. Do you really think it could be efficient?
Clearly I will wait for a deeper analysis before answering your question. Interesting (theoretical?) problem, isn’t it?

OK, I guess I was a bit confused myself. But tell me, does your solution involve the following 2 ingredients?
1) detecting irregularities in remaining search depth and stored hash depth?
2) in a hash table entry, do you store the position's ancestor's key (so not just the best move + eval score)?

If true, then your solution is similar to one desribed in the literature (applied to proof number search).

Rein

[TAILLE]

Hi Rein,

Answers to your questions:

1) detecting irregularities in remaining search depth and stored hash depth?
Rein

Comparing search depth and stored hash depth is a major point in my algorithm (but I guess it is true in any other implementation!) but I do not know what you mean by "irregularities". Maybe you mean "stored hash depth > search depth" but it is not an irregularity, isn't it?

2) in a hash table entry, do you store the position's ancestor's key (so not just the best move + eval score)?
Rein

No, my current hash table entry is not that big : I use only 16 bytes (5 bytes for the hash key of the position, 1 byte for a kind of time stamp to handle the interest of the hash entry, and 10 bytes for various information useful for the search)

[Rein Halbersma]

Comparing search depth and stored hash depth is a major point in my algorithm (but I guess it is true in any other implementation!) but I do not know what you mean by "irregularities". Maybe you mean "stored hash depth > search depth" but it is not an irregularity, isn't it?

Yes of course, but the usual comparison is to use the hash result if the score is exact (win/loss/draw) or if the score is an eval value and stored_depth >= search_depth. My point is that if you have used a hashed score with stored_depth > search_depth (not exactly equal), then the path of the root to the leaf node does not have a monotonically decreasing remaining depth along the nodes. That's why I call it "irregular". The most frequent transpositions are the ones with simply a few moves interchanged, with the same depth.

BTW, there is also other subtle depth-related hashing behavior. One is called "grafting", which can occur with bad move ordering. E.g. if you first search a few moves that delay a particular winning solution, and later search the quickest win, the hash table can "graft" the inefficient solution onto the fast solution (at least for my program, my score values have the distance to mate encoded, so a win in 5 ply has a different value than a win in 7 ply e.g.). This usually occurs in endgames: e.g. I have found artificial win-in-200 ply scores for searches of 30 ply. On the next iteration such values usually disappear and my program always finds the correct win (I have tested this on many database positions).

Did you ever come across such behavior? (on Talkchess there are some discussions).

[TAILLE]

Yes of course, but the usual comparison is to use the hash result if the score is exact (win/loss/draw) or if the score is an eval value and stored_depth >= search_depth. My point is that if you have used a hashed score with stored_depth > search_depth (not exactly equal), then the path of the root to the leaf node does not have a monotonically decreasing remaining depth along the nodes. That's why I call it "irregular". The most frequent transpositions are the ones with simply a few moves interchanged, with the same depth.

OK Rein, now I clearly understand what you mean by irregularity. Then my answer to your question is “no” : I do not care about what you call irregularity.

BTW, there is also other subtle depth-related hashing behavior. One is called "grafting", which can occur with bad move ordering. E.g. if you first search a few moves that delay a particular winning solution, and later search the quickest win, the hash table can "graft" the inefficient solution onto the fast solution (at least for my program, my score values have the distance to mate encoded, so a win in 5 ply has a different value than a win in 7 ply e.g.). This usually occurs in endgames: e.g. I have found artificial win-in-200 ply scores for searches of 30 ply. On the next iteration such values usually disappear and my program always finds the correct win (I have tested this on many database positions).

Did you ever come across such behavior? (on Talkchess there are some discussions).

I do not handle the distance to the win in Damy. Damy is only concerned by the distance to conversion and I do not have this “grafting” behavior.
If you handle only the dtw you can miss a draw due to the 25 moves rule. With the dtc you cannot miss such draw. In the great majority of cases dtw leads to a quicker solution than dtc but in very exceptional cases (certainly no harm if you ignore them) the dtw might fail to find the correct result. For that theoretical reason I prefer to use only the dtc even if it is not the most efficient way to end a game.
If you do not take into account the 25 moves rules then dtw is definitely better than dtc.

[TAILLE]

Hi,

Hi Rein,

Answers to your questions:

1) detecting irregularities in remaining search depth and stored hash depth?
Rein

Comparing search depth and stored hash depth is a major point in my algorithm (but I guess it is true in any other implementation!) but I do not know what you mean by "irregularities". Maybe you mean "stored hash depth > search depth" but it is not an irregularity, isn't it?

2) in a hash table entry, do you store the position's ancestor's key (so not just the best move + eval score)?
Rein

No, my current hash table entry is not that big : I use only 16 bytes (5 bytes for the hash key of the position, 1 byte for a kind of time stamp to handle the interest of the hash entry, and 10 bytes for various information useful for the search)

I have just changed my hash key. 40bits is definitely not enough to avoid collisions. I use now 64 bits.
The point is the following: 40bits allows to distinguish 10^12 positions but imagine you calculate the hash key for only 1 million different positions. The probability to have a collision is about 50% (see birthday paradox) which is quite inacceptable.
What about the 64 bits hash key? Let’s suppose your engine is able to generate 200 millions of different positions before chosing a move. The probability of a collision is then equal to 0.1% which is significant but probably acceptable. What is your view?

[Ed Gilbert]

http://www.cis.uab.edu/hyatt/collisions.html