Katago's Inefficient Reversion

[lightvector]

Each move of each reversion sequence abides by the used superko rule.

Yes, but the value of situation Q may depend on the sequence that it was reached from, for example if you reach situation Q via move sequence A, it might be that a *later* followup from situation Q might have an illegal move because the move would result in a intermediate board configuration that occurred within A, whereas if you reached situation Q via move sequence B, then the later followup from situation Q would have that same move be legal.

A simple example this often occurs when you carefully time the capture of a ko to occur last after you play various mutually forcing exchanges (sequence A), so that the opponent has to find the first external threat. If instead if you captured the ko early then the opponent would play all the same mutually forcing exchanges and then recapture the ko (sequence B), forcing you to find the first external threat. The board position and player to move just after the ko capture in sequence A is identical to the board position and player to move after the opponent plays the last of the mutual forcing exchanges and you respond in sequence B, but the ko recapture is legal for the opponent if that state was reached via B, and illegal if reached by A. You cannot combine the nodes in this case because the game theoretic value may differ due to the difference of legality of ko recapture, if the single ko threat makes a difference.

Just out of curiosity: How would this word with superko rules, where it might later matter how you got to a particular position?

KataGo uses a heuristic that theoretically is not sound, but in practice I know of zero cases where optimal play from the root node depends on passing through nodes where the heuristic incorrectly combines two nodes that need to be kept separate.

Consider a situation where a move was just played on a location L in Go.
Let S be the number of stones in the group of stones containing L (or 0, if the move was a self-capture)
Let E be the number of empty spaces in all empty regions that touch the group of stones containing L (or in the empty region that contains L itself, if the move was a self-capture).
Let C be the length of the smallest cycle that contains the move played. (i.e. the total number of turns in the shortest possible repeating loop of board situations under alternating play and/or passes that includes the move made).

Theorem: C >= S + E

Proof: Exercise for the reader.

Application: KataGo considers the "transposition-protected-state" of a node to be the current board situation together with the maximal sequence of board situations in recent history so long as all moves in that recent history have S + E <= 11. (The value of 11 is a default, and is configurable). Two nodes are mergeable if their transposition-protected-state exactly matches. In other words, KataGo "forgets" or "clears" the history any time there is a move with S + E > 11 for the purposes of transposition detection.

Notes: Simple ko captures have S+E = 2. The moves in https://senseis.xmp.net/?EternalLife have S+E <= 4. Almost all moves in the opening or midgame of a normal game have S+E = large, due to touching the huge open space on the board, making it practically impossible that they are part of a cycle, and a reasonable number of endgame moves have S+E = large, because they touch a large-sized territory or a connect to a group with a large number of stones, making it also practically impossible that they are part of a cycle.

I would be curious if anyone can construct a position in which optimal play from that position onward depends on a long cycle that contains a move with S + E > 11, such that this heuristic might merge two nodes that should not be merged. Does anyone know of a fight in which one of the main lines depends on a cycle where some move in that cycle touches a decently large empty space and/or forms a decently large group of stones?

[RobertJasiek]

For years, the known maximum S+E has been 8, see the quadrupel ko stones cycle.
https://home.snafu.de/~jasiek/ko.pdf

[Schachus]

Good to know, very interesting!

[Harleqin]

I'm not sure if I understand correctly: do you mean the known maximum or the maximum known? I. e. do we know that there cannot be more, or is it just the largest found yet?

[RobertJasiek]

The largest found thus far.

If it were the exact theoretical maximum, you would have seen a proof of mine:) However, I expect such to be extremely difficult to establish and prove, except for the trivial upper bound 361.

[Jowels]

Newbie question, does reversion mean the same thing as the chess term "transposition"? (i.e. achieving the same board state but through a slightly different move order?) I searched for reversion on SL and on google but to no avail.

[dfan]

Yes, see the beginning of this response by lightvector.

[RobertJasiek]

achieving the same board state but through a slightly different move order?

Yes.

I searched for reversion on SL

Actually, I have at least mentioned it on SL:
https://senseis.xmp.net/?PositionalJudgment

and on google but to no avail.

Even dull Google finds the URL above after giving enough search hints:) However, Google is too weak to easily list occurrences on my webpage...

[lightvector]

Was it in significant use prior to your own usage in research as well? Unfortunately, I would guess that "transposition" is still probably 10 to 100 times more common, if for no other reason that it is the term in chess and chess players both greatly outnumber Go players among English speakers, as well as computer chess being the game with the biggest early influence on the algorithmic side of computer board game playing, i.e. the major applied field that would care about that kind of theory or concept regarding game trees.

[RobertJasiek]

1) For go theory for go players: Yes, reversion was the common term in verbal use and the go literature long before I started using it in my texts. (I have invented many terms, as necessary or good for clarity, but not reversion. It was also long before combinatorial game theory spread its own abuse of the word reversal to expert go players.) I do not recall to have seen the term transposition once.

2) It is quite possible that chess uses other terms. Hey, chess does not even know what is a move or pass!;)

3) Informatics or mathematics research: Terms often differ from go terms for go players, even in texts written by go players. Terms have often changes over time. E.g., army, unit, group etc. were abused with the meaning of string / chain. Some research fields, such as combinatorial game theory, have established their own terminology, such as abusing reversal for a different meaning. This has these reasons: a) different domains (or particular games) have different terminologies so research may well develop its own terminology; b) quite a few researchers are relatively weak go players and have not studied go theory enough to know its typical terminology; c) not everybody has enough personal contacts to other go players and reads much of the go literature so may not know common terms there; d) some teaching in speech or writing is insufficient and forgoes quite a few terms and concepts; e) some terms change (hey, e.g., Koreans try to impose theirs, but also some teachers have a desire or see necessities to develop terminology, e.g., I think it was James Davies who introduced snapback).