sunfish
sunfish copied to clipboard
thomasahle
Add three-fold repetition draw
This draw comes up all the time when sunfish is winning, and it always jump straights in, giving away the victory. Also the stalemate draw is still not well tested. Perhaps sunfish needs a draw_in_k test, just like the ones for mating.
Wiki: http://chessprogramming.wikispaces.com/Repetitions Micro max: http://home.hccnet.nl/h.g.muller/repdraw.html
As it turns out, there aren't any good ways to do this with transposition tables.
For my chess variant program which is based on sunfish I tried the naive approach to feed the past postitions into the tt with depth 99 and a very bad score and gamma (I want to make repetitions impossible); this got overwritten all the times; now i implemented this in the move_gen method which works but is very expensive (nodes dropped about 50 %)
Right, sunfish doesn't have a way to mark a TT entry as "don't replace". Rather you might want to use a separate set() for keeping the previous positions.
I guess if only done at root, something like if root and pos in history: return 0 might prevent the worst repetitions.. Sunfish won't see the repetitions before the very last moment though.
No wait, that's not even true. Adding the check in the beginning of bound for if root will only check if the initial position is already drawn, and not if the move we are considering is going to draw.
On the other hand, if we make the check deeper than at root, the TT lookup at root might give us an immediate fail-high, so we don't ever notice that the proposed move is actually a repetition. I don't see how to fix this other than not looking at the TT at all at root. (Or making the TT dependent on the path)
one question: i didn´t study your recent changes (thank you for the study material!!!), but before these changes the key to the hashtable has been "pos" which is a named tuple with board, score, ep and kp. Doesn 't "score" change with the depth of the search, so if the score is different this is treated as a new position? i guess it does not make a big difference, the table will just grow faster ...
If two pos.boards are equal, their pos.scores are equal as well. The pos.score is simply pst values and not the same as the score returned by the search, which may detect e.g. a stalemate. The result of score = search(pos) may be seen as a refinement of pos.score.
I agree, the only pos.score which is based on a deep search is the one from the root position which was returned from the search one move ago. But I still have an understandig problem: sunfish doesn`t clear the hashtable between each move, she uses the tables from previous searches. Are these "pos.score"s (which are part of the key) compatible? They "pos.score"s are the result of a root pos.score which might differ due to a deeper or shallower search 2 moves ago. Sorry for being so inquisitive ....
Don't be sorry, inquisitivity is great!
Scores from search are never stored to pos.score. Not at root either.
You can always assume the invariant pos.score = sum(pst ... for i, p in pos.board)
For my chess variant program which is based on sunfish I tried the naive approach to feed the past postitions into the tt with depth 99
For my rewrite in Rust I did exactly the same, giving them score 0 if not at root, and seems to be kind of working fine (won't recognize repetitions in future moves, it's definitely not perfect, but seems to be working, haven't seen thrown away wins so far, and even saved one loss)
This should be fixed in commit 965b631. I ended up going with the classic "just test against moves already made" as was also suggested in this thread.
Since adding to the history changes the "true" value of positions in the tree, we should really clear the transposition table to avoid search instabilities / be correct. I'm considering whether this is possible without a loss in strength.
Nice to see you're still working on sunfish! From sunfish_rs i found that some situations can be tricky (sometimes when at a disadvantage it's not optimal to repeat once), but doing something trivial that works 95% of the time can be useful
Because the opponent is not guaranteed to keep repeating and you need to repeat three times to draw. Even stockfish sometimes repeats once just to have more time to think about a position, and in blitz human games often people miss a mate / a capture and try to get the opponent repeat once
Right. You should, of course, be able to continue playing in these situations. This is the reason sunfish now only checks for 3fold draws at nodes other than root.
I ended up going with the "clearing the TT at every move" approach. Maybe it's overkill, but whatever. At least it means draws are always correctly identified at the root.