AGA ko rule says: Repeated Board Position (Ko): It is illegal to play in such a way as to exactly recreate a previous full board position from the game, with the same player to move
It’s very easy to make a situation where it repeats the board position, yet has the other player’s turn to move. It can happen when you play a second stone, then your opponent captures the two stones, and you capture one stone back. There are several examples, but this is a situation that is allowed under AGA rules, and not allowed on OGS’s implementation of these rules.
As you investigate, it seems the “very old code” only checks whether the potential move will exactly duplicate any previous full board position, but does not check whose turn it was for that position – is this true? Also, does it mean the code keeps a record of all full board positions since move 1?
(semi-related: how does this particular AGA rule apply to pair Go?)
Yep that’s right, I implemented positional superko but looks like I never got around to situational, it shouldn’t be hard to patch up. And yes, we keep track of all the previous board states. It looks like I only check the past 30 moves though too as an optimization. (It’d be pretty darn wild if a real life game repeated after 30 moves… more so if that was actually a problem.)
Ok situational superko has been properly implemented. If anyone wants to test it a bit it’s up on the beta site, https://beta.online-go.com . I’m not going to do a release to the production site this morning since events are starting soon I think, I’ll probably do it late tonight after things are over for the day.
Passing is always a legal move under the various common rulesets. Ko and superko rules of various forms are worded to prohibit playing a stone that causes repetition of some form.
No, on purpose. What you’re thinking of is natural situational superko, which is what the BGA uses and is s perhaps what was intended, but unfortunately/fortunately was not specified with as much clarity as was needed, so now the accepted norm is situational superko which does not consider passing.
By the way, if you care about optimization, you could consider using a 64 bit zobrist hash as a first-pass filter. Maintain a map/hashtable/dictionary from zobrist hash -> list of turn numbers with that hash. Every new board position, add the (hash,turnnumber) entry to the map. Every new move, to check for legality, simply query the map with the new hash. If it exists, only then do you do the expensive stone-by-stone check whether the new position is the same as the one on the turn number(s) you retrieved from the table.
If you need undo as well, then maintain a second map from turn number -> zobrist hash as well. When undoing a move, use this table to look up the hashes for the turn number(s) being undone (while also removing them), so you know what entries to remove from the first map.
This would remove the 30 turn limit and might act as a further optimization, since almost always a single map probe would find no matching zobrist hash and would enable you to skip all comparison of board states.
(https://en.wikipedia.org/wiki/Zobrist_hashing)
(The thing that makes zobrist hashing fast is that it it can be updated entirely incrementally - you only need to xor one or two values per each stone that changes. Optionally also include the player to move depending on positional/situational).
