Something I’ve dug into quite a bit but haven’t been able to find an answer to is:
Does there exist a legal game that arrives at a position where multiple different moves by the same player would be disallowed under “Positional SuperKo”, the most general superko, preventing any board position – not necessarily situation – from ever repeating?
I’m building a Go game engine, and essentially I want to know if the list of forbidden moves in any position is ever greater than 1, because as far as I can tell, the answer is likely “no”, but no one has proved it.
Related discussion with many SuperKo examples: here.
I’m open to writing a simulation that explores if this is possible, but of course that would be a large undertaking; ideally the community already knows the answer
EDIT: Thanks for the answers @nptialiu and @martin3141 (it’s yes)! And to clarify my intentions, I’m trying to set up a static notation for a human- and computer-readable “snapshot” of a Go game that allows picking up where one left off and nothing more, much like a FEN in chess.
black fills the board in all but one space, white passing except to take. Do this a few times and multiple forbidden starting moves occur.
A quadruple ko, or generally an n-tuple ko, probably - you can get one at least w/ normal ko (special case of superko) and superko in separate places I think (BBWW, BBBW, WBBW, WBBB, WBWB, BBWB, and now WBWB is forbidden by normal ko and BBWW by superko) (actually triple double ko has the same thing, I was just trying to find an n-tuple ko without multiple non-normal ko preventions when presenting this)
I’d like to clarify this a bit with an example on a 3x3 board (that can be generalised to bigger boards). Black fills the board while white passes. Then white captures, and afterwards black passes while white fills the board. Then black captures etc. …
During the first cycle we have black first play in the upper left corner, then middle left, to reach this position:
This is an important clarification and a great demonstration! It’s not sufficient to just fill the board and capture (since superko would prevent us from placing the capture stone in the same place more than once), but placing the second stone in a common place is what makes multiple illegal moves possible.
Are you familiar with the concept of a zobrist hash?
The standard way that one detects superko is to keep a zobrist hash incrementally updated and add the hashes for all the board’s historical positions to a set. One can also write a method that returns the hash that would result from playing a given move, but without actually playing that move. (xor in the delta of the hashes for all stones in all opponent adjacent adjacent groups if the groups have only one liberty, if there is none and the move would be self-capture, xor in the delta of all the stones in the self-captured adjacent groups. If not self capture, xor in the delta of the stone being added. This is efficient and fast to compute in the common case where nothing is captured, so long as your board also precomputes and tracks the liberty counts of groups so that the tests for capture/self-capture are instant).
Then you can easily check whether a move is superko-banned by seeing if the hash that would result after the move is contained in the historical set of hashes. If you want to be absolutely strictly correct in the event of astronomically rare hash collisions, you can also add an expensive actual check for equality of positions in the case the hash check thinks there’s a repetition.
For situational superko, just include the side to move in the hash as well.
Yes, Zobrist hashes are the shiz niz! I didn’t anticipate folks in the community to be programmers but I’m happy to see it. On that topic, should I be discussing this stuff in a more specific sub-forum someplace?
To clarify my intentions, I’m currently making a “Static Go Notation” that functions analogously to a FEN in chess, so that import and export of individual board states can become human-readable.
So I could use Zobrist hashes, but that’s not in line with my aim for a minimal, human-readable format. I’m trying to guage how much superko information I should include in the (ideally very short) format. One “off limits” square for the current move would be best of course and hence my question, but I’ve also realized past positions shouldn’t be repeatable anyway, so in some way or another I need to store the entire game history if I want a perfect superko state from my “Static Go Notation.”
I think I’m leaning towards simply storing 0 or 1 disallowed moves as that covers the vast majority of real-world scenarios, and just compromising perfect information on my new notation.
TLDR: I’m trying to take a “snapshot” of a board state with as minimal information as possible.
Yup! I’ve edited my post to clarify my intention with the question, which is to create a static exportable board notation that represents a perfect “snapshot” of a Go game with minimal information, in human- and computer-readable text.
I’m not sure how this format will be used, but this wouldn’t let you continue play from the position (since future positions will need the full history anyway under superko).
I think a static position format could get by with simple last move information, same as chess for en passant. All major rulesets (Japanese, Chinese and Korean) use the simple ko rule, so you just need enough info to distinguish ko captures from ko throw ins. And if full AGA support is needed, you may be best off with SGF (with complete history).
It can also happen on the smaller 2x2 board. The shortest such game is
A2 pass
B1 pass
A1 B2
A1 pass
B1 A2
pass A1
B1 B2
and now both A1 and A2 are forbidden for black by PSK.
