Sven Schüle wrote:Also it may be possible that there is some clever solution to combine both loops in one, although I would not recommend that.
In Joker I hash the last stretch of reversible moves into a 256-entry table. This table stores the key and the repeat count. (Count = 0 indicates the entry is empty.) This way you find the position always with a single loop, which either finds the current position, or an empty entry (usually on the first try).
With this system you can score a draw when you hit a position that has count >= 2. If the position has count < 2 you would increment that count by 2 in search, and by 1 at game level. Leaving the position you decrement its count again by 2 to restore the original value (as this only happens in search).
Yes, that sounds sufficiently clever indeed.
But why 256 entries? Wouldn't it be sufficient to maintain two tables (one per color) with 50 entries each?
Well, for efficient hashing I want the size to be a power of two. And 128 (or 2x64, if you separate by color) is too small. You can clear the table only on irreversible moves at game level; in the search you will have to be able to UnMake. So besides storing 99 game plies, it will have to store the current branch of the search as well, which could easily be deeper than 28 ply.
I also don't want the table to be nearly full. The chance your first probe in the table will hit an empty entry (if the position was not a repeat) is the empty fraction of the table. So I want the table to be at least half empty, so that on average I would not have to search through more than 2 entries even if the 50-move counter gets high.
Add-the-hash rehash would be good enough to prevent clustering with a half-empty table.
Why are you reducing the problem to the level of "assumptions"?
Because certain "assumptions" are responsible for the design of our algorithms.
E.g. a fundamental assumption in all chess programs is "we assume" our opponent plays his best move". We can't be sure, so it is an assumption.
The assumption behind "awarding a draw score for the 1st repetition is good enough" reads "an engine that plays a bad move once will most likely play it twice."
This assumption will only hurt in cases where an engine misses a draw by repetition when it first sees a position but spots it when it encounters it again. In a game of human players that might be common but in an engine - engine match this should be rare. So rare that fixing it will not produce an ELO gain.
Why are you reducing the problem to the level of "assumptions"?
Because certain "assumptions" are responsible for the design of our algorithms.
E.g. a fundamental assumption in all chess programs is "we assume" our opponent plays his best move". We can't be sure, so it is an assumption.
The assumption behind "awarding a draw score for the 1st repetition is good enough" reads "an engine that plays a bad move once will most likely play it twice."
This assumption will only hurt in cases where an engine misses a draw by repetition when it first sees a position but spots it when it encounters it again. In a game of human players that might be common but in an engine - engine match this should be rare. So rare that fixing it will not produce an ELO gain.
Apparently you missed a lot of what I wrote in this thread above. As I spotted based on the example given by the OP, that assumption will also hurt in cases where a losing move is incorrectly evaluated as a draw and therefore a better (i.e., not losing) move will be missed. Please show me why this should be part of the design and not a BUG.
No, I did not missed it. And your additional code will probably solve it. I don't question that.
I just question the need to change it.
It can be a design decision to accept imperfection, if fixing it does not make the engine stronger or makes the code more complex.
Do you have implemented a transposition table that recognizes whether a position is encountered for the 1st, 2nd or third time or do you just accept that imperfection here ?
tpetzke wrote:Do you have implemented a transposition table that recognizes whether a position is encountered for the 1st, 2nd or third time or do you just accept that imperfection here ?
My current approach is not to store draw scores in the TT. I don't recall at the moment which problem exactly occurred in my engine without that restriction. It might even be possible that the restriction is no longer needed, I'll have to check. But if it is needed then yes, I accept that imperfection since otherwise I would get into even bigger trouble, so I would have a very strong reason to accept it.
I don't think this compares well to the question of fixing the repetition problem of this thread. There you don't get into even bigger trouble by applying the right fix.
it does not hurt much because in an engine - engine match this position will likely not occur.
I would not be surprised if "fixing" it would somewhat hurt engine strength. Scoring first repetitions of positions in the game history immediately as a draw and not searching those branches further likely makes the tree a bit smaller.
Fixing it would also annoy some (other) users, because the engine will now sometimes choose a line that it can see to lead to a (first) repetition but that (with the fix) still seems better than other lines.
I still consider Sven's approach to be "more correct" and I have implemented that in my engine, but there seem to be good reasons for the approach of Stockfish.
Also the transposition table is blind to repetition problems and we could solve that by storing path information. But it will not make the program stronger so I guess nobody does that.
Indeed. Users can also complain about such problems, but considering them "bugs" that need to be fixed is simply not an option. This also reminds me of the complaints about smp variability of some time ago.
Sven Schüle wrote:Also it may be possible that there is some clever solution to combine both loops in one, although I would not recommend that.
In Joker I hash the last stretch of reversible moves into a 256-entry table. This table stores the key and the repeat count. (Count = 0 indicates the entry is empty.) This way you find the position always with a single loop, which either finds the current position, or an empty entry (usually on the first try).
With this system you can score a draw when you hit a position that has count >= 2. If the position has count < 2 you would increment that count by 2 in search, and by 1 at game level. Leaving the position you decrement its count again by 2 to restore the original value (as this only happens in search).
How about storing in this table only the positions from the game history that have occurred twice (together with the positions on the current path from root to the node you are searching)? You then only have to test whether the position occurs in the table or not (so no need for a counter field), and the table does not fill up as much when the 50-move counter of the position on the board approaches 100.
Yes, that would be a nice further optimization. The underlying idea would also work for the conventional linear search through a stack of keys, btw. Only put all keys from the game history that occurred twice (usually none) on that stack before you start the search, so that you don't have to loop over those that occurred oly once.
As you can only have 25 positions per side that occured twice, a table of 64 entries per side would allow you a search depth of 2 x 39 ply before it entirely fills even in the worst case.
When you want to exclude null-spanning repeats it becomes a bit more complex again, however. You would be forced to remember the ply where each position was last seen (all game positions could get ply 0), and in case of a match compare the difference of the current ply and the remembered one with the reversible-move counter (which presumably would be reset on null moves).
hgm wrote:Yes, that would be a nice further optimization. The underlying idea would also work for the conventional linear search through a stack of keys, btw.
I know, because that's what I am doing now
In addition to the stack of keys I have small hashtable with byte-size entries that I increase and decrease when entering/leaving a node. If the value is 0 on entering, I don't need to search through the history stack.
When I have some time I will implement your idea to see what is faster (if at all measurable).
