Two questions

[Arash]

Hi all,

This is my first post to this forum.

I have two questions:
1- When I use hash table, first occurrence of a position is stored in the hash table, then when the position is met again, I can either check for two fold repetition or probe the hash, no way to check for three fold repetition. Is there anyway to check for the third occurrence of a position when the hash table is active?

2- Is there any relationship between real Elo of an engine and its Elo in FICS and ICC. My engine "ARChess" currently is ~2400 in ICC and ~2100 in FICS, but with its many blunders, I think it is far from "real" 2100 Elo. Is there any way to guess the real Elo?

Thanks,
Arash Panahi Rad

[tiger]

Hi all,

This is my first post to this forum.

I have two questions:
1- When I use hash table, first occurrence of a position is stored in the hash table, then when the position is met again, I can either check for two fold repetition or probe the hash, no way to check for three fold repetition. Is there anyway to check for the third occurrence of a position when the hash table is active?

2- Is there any relationship between real Elo of an engine and its Elo in FICS and ICC. My engine "ARChess" currently is ~2400 in ICC and ~2100 in FICS, but with its many blunders, I think it is far from "real" 2100 Elo. Is there any way to guess the real Elo?

Thanks,
Arash Panahi Rad

1- I suggest you do not use the hash table to check for repetitions, because it can happen that the hash table slot you wanted to use the first time you encountered the position was already in use by a position with greater priority (it had a greater search depth associated with it for example). So you could not store it in the hash table and you will not detect it the second time it occurs. It can also happen that the hash table slot has been overwritten in between.

Also, normally a position will be stored in the hash table with its associated score only when the tree below it has been searched. So during the search below a position, this position has NOT been recorded in the hash table yet. So you cannot use the hash table to detect repetitions. Unless you use a very unusual hash table management of course.

The right way is to store the hash key of all previous positions in the tree (parent positions) in a dedicated stack ("repetition stack") and to check for an occurence of the current hash key in this stack. This way you can easily check for twofold or threefold repetitions. BTW the current consensus is to give the current position a draw score if it has occured once or more in the repetition stack. The correct way would be to give a draw score the THIRD time it occurs (not the second time), but giving it the second time allows to detect repetitions earlier with almost no negative effect.

2- There is no reliable relationship I believe. To assess the strength of your engine you should play LONG matches (several hundreds games) against other known engines (engines with a known elo).


// Christophe

[Gerd Isenberg]

Hi all,

This is my first post to this forum.

I have two questions:
1- When I use hash table, first occurrence of a position is stored in the hash table, then when the position is met again, I can either check for two fold repetition or probe the hash, no way to check for three fold repetition. Is there anyway to check for the third occurrence of a position when the hash table is active?

Hi Arash,

welcome in the club!

The boolean "entry is locked" information inside the hash is not enough to distinguish beween twofold or threefold repetitions. Instead of a boolean lock, one can maintain some more information in a hash-entry, like a lock-counter with a few more bits than one.

But working with the hashtable to detect repetitions has - despite possible collision issues - problems if you later implement multiple threads or processes sharing the same table.

It is recommend to keep a stack or zobrist- hashkeys of the current line, plus keys from the game history and to itereate those keys as long one has reversible moves in that path - comparing current hashkey with hashkey[i-4], hashkey[i-6], hashkey[i-8], ..., until same hashkeys occurs before once or twice.

One may distinguish between the first occurence appeared already in the game record or not. If the first occurence was already inside the current search, it is appropriate to return the draw-score immediatly. Otherwise, with the first occurence in the game-record, one may take the third occurance only for draw score.

see also
http://www.seanet.com/~brucemo/topics/repetition.htm

Gerd

[hgm]

The main point is that you need some extra information aboat positions that are being repeated, that you don't need for positions that are not in the game or the current path in the tree. Like how many times it already occurred, if this was in the game or in the tree, if in the tree, at what level, etc. Now there are millions of positions in your hash table, and only a hundred or so in the game or in the current tree branch. So it would be really wasteful to reserve space for the repetition information in the main hash table: it would only be used for 0.01% or less.

The most efficient way I could find to implement the repetition check is to have a separate table for this extra information that only is needed for positions in the game or on the current branch. This table contains only 256 entries, which is more than enough for the 100 positions that can occur in the game before it is a 50-move draw, plus the maximum tree depth. (On any irreversible move in the game the table is completely cleared, as any position before it can no longer be repeated.)

I then use the normal hash key modulo 256 for indexing this repetition hash table, and on a collision it simply goes through the table in steps of 1 (modulo 256) until it finds the sought position or an empty entry. As the table is always at least half empty, you find the position (or an empty entry to put it) on the average in less than 2 tries. Thus this linear (wrap-around) search with hashed starting point is almost perfectly efficient, and there is no need to look for more advanced re-hashing schemes. The table is small enough and probed frequenly enough to be always in cache.

When you return from searching a position the corresponding entry is marked empty again. (This is a side effect from decreasing the repeat count: an entry with repeat count zero is considered empty.)

[Arash]

Dear Christophe Théron, Gerd Isenberg, H.G.Muller

Thank you. I think I did not explain my problem correctly, but your complete answers solved my problem. Actually I use a stack of hash keys of previously visited positions, but when in "IsDrawByRepetition" function I check for third repetition, AlphaBeta never returns draw score. Because the first time a position is visited it is stored in the hash table then in the second visit the repetition test fails (because I check for third repetition) and after that if the position has not been replaced yet, the hash probe hits and this cuts more recursions of AlphaBeta and so it prevents any further repetitions. So in my case I can never check for third repetitions. But checking for second repetition solves the problem.

Best Regard,
Arash Panahi Rad

[hgm]

Indeed, if you do third-occurrence draw, it is essential that you don't probe (or store into) the hash on a second occurrence.

Joker did third-occurence draw, to minimize hash pollution, but I was not really happy with it. So I added a mechanism that tops of the score to a draw score if the best continuation of the current node (the 'PV') goes through a repetition of that node.

[Edsel Apostol]

Hi Arash,

There is one simple way to solve that. Just call your repetition routine before the call for the transposition table. Check how engines like Fruit do it. Just follow how it order things inside search, like the repetition, tranposition table, null move, etc. You can now use the exact 3 fold repetition instead of just 2 repetition.

Edsel Apostol (Twisted Logic)

[Arash]

Hi dear H.G.Muller,

It seems that not probing the hash on second occurrence will degrade performance. So I currently decided to test for two fold repetition. Your solution for Joker is interesting. But (if Joker is fail-hard) doesn't this prevent it from doing three fold repetition if it is in trouble (draw score fails high)?

Best Regards,
Arash Panahi Rad

[Arash]

Hi dear Edsel,

I looked at Fruit. It seems at Fruit checks for two fold repetition ("board_is_repetition" function in "board.cpp"). If three fold repetition check fails(third occurrence not met yet) and after that hash probe succeeds then you will never get draw score, because hash hit cuts the AlphaBeta recursion.

Best Regards,
Arash Panahi Rad

[hgm]

It seems that not probing the hash on second occurrence will degrade performance.

Compared to what?

One should always be careful comparing performance of non-equivalent things. For what good is it if you obtaain a result faster, when it is the wrong result?

Joker does not score the second occurrence as a draw to prevent hash contamination with path-dependent scores.

So I currently decided to test for two fold repetition. Your solution for Joker is interesting. But (if Joker is fail-hard) doesn't this prevent it from doing three fold repetition if it is in trouble (draw score fails high)?

I am not sure why you think that. If the draw score fails high, it will fail high on the third occurrence. The nodes between the second and third occurrence will then decide if the side who does not like the draw has better alternatives. So the second occurrence will only get the draw score if neither side wants to avoid it, i.e. if the draw is truly forced. In the latter case the position is a draw independent of the path leading to it, and can safely be propagated towards the root, without fear for contaminating the hash entries for the nodes between first and second occurrence with path-dependent scores.

Joker is fail soft, but I don't see why that would be relevant.