Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Is there a generalization of the GO game that is known to be Turing complete?
If no, do you have some suggestions about reasonable (generalization) rules that can be used to try to prove that it is Turing complete? The obvious one is that the game must be played on an infinite board (positive quadrant). But what about in-game play and end game conditions?
Related: Rengo Kriegspiel, a blindfolded, team variant of Go, is conjectured to be undecidable.
http://en.wikipedia.org/wiki/Go_variants#Rengo_Kriegspiel
Robert Hearn's thesis (and the corresponding book with Erik Demaine) discuss this problem. They prove other problems undecidable through "TEAM COMPUTATION GAME", which is reduced directly from Turing machine acceptance on empty input (see Theorem 24 on page 70 of the thesis). So it seems to me that such a reduction would imply Rengo Kriegspiel is Turing complete.
On the other hand, their discussion says that this reduction would be very difficult (see page 123). So while this is a potential avenue, it appears that it has been looked into previously.
This is a build on my comment, with the idea of using shishos (ladders) as computations. It is merely an attempt to give a computation model that is based on Go, and for which it makes sense to ask whether it is Turing-complete.
We start by fixing some powerful but not Turing-complete computation model that always halts, for instance some typed $\lambda$-calculus, or primitive recursive functions. This is the "cheating" part as we use an external computation model, but it is a weaker one, so hopefully it is the game of Go which will fill the gap and make it Turing-complete.
We consider an infinite goban labeled by $\mathbb Z\times\mathbb Z$. Now the initial configuration of the goban can be infinite, and is given by an algorithm from our formalism: given coordinates $(i,j)$ the algorithm says whether the intersection $(i,j)$ is empty, occupied by a black stone, or occupied by a white stone. We fix a maximal size $N$ of the groups in the initial configuration. This means that given a position, we can always compute the group occupying it and its number of liberties, or answer "invalid configuration".
We also fix a marked stone (say black) at coordinate $(0,0)$. An initial configuration is valid if at the beginning the group of the marked stone has two liberties.
Now we can view this configuration of the goban as the initial configuration of a non-deterministic machine, where a transition consists in playing a white stone at one of the two liberties of the marked group. At each step, black automatically answers at the other liberty.
The run ends if
The run can also continue forever...
As for non-deterministic Turing machines, the input is accepted if there is an accepting run.
It is easy to simulate this machine with a non-deterministic TM, thanks to the existence of the bound $N$ (which is a parameter of the whole model).
Conjecture: For $N$ big enough (probably no more than $10$ to get the necessary gadgets), this model is Turing-complete.
here is some evidence/ analysis/ results leaning against your conjecture that a Go generalization might be undecidable (aka "Turing Complete"); at least there does not seem to be a well known or commonly accepted case, and a search returns more results on the idea that its ("natural"?) generalizations are decidable. the generalization considered in this set of papers is PSpace complete. however, there are no "consistent" or "inevitable" ways to generalize games and it is conceivable someone could come up with a variant that is undecidable.
actually most nontrivial games probably can be modified or generalized in some way to have undecidable variants. (a famous simple game/ example along these lines proved "undecidable" by Conway is Life.) the following references also point to many other references.
another line of thought might be that no game can be undecidable if it is winnable, ie undecidability works against the idea of games terminating with a winner in a finite number of moves. in other words maybe games are better/ more naturally analyzed as within the (decidable) complexity hierarchy as is typically the case.
In my patent application - Turing Complete Sets of Game Components with Divinatory Elements - I describe variants for game rules (including games played on a 19x19 Go board) which add a degree of complexity to games like chess and Go allowing for board positions to simulate linear bounded automata for an arbitrarily long period of time. As mentioned in the comments above, Go on an infinite board would introduce some difficulties as far as determining a game winner, since it is a game with a territorial objective, unlike chess. From my application: "Many other Turing complete game embodiments are possible, but I will give just two more brief descriptive examples to illustrate some other possibilities for adapting games to be played as Turing complete variants and then discuss ramifications. Games like Gomoku (SCARNE, p. 537) and Go (SCARNE, pp. 533-7) which are played on a 19×19 grid with two different colors of pieces are also candidates for Turing complete variants with divinatory elements. In the case of these games, Rogozhin's (2,18) UTM is used. This is also the UTM used by Churchill (2012) as cited in the prior art references. In order to create a game variant of this type, we will use coins for our game pieces. Prepare to play the chosen game variant by sorting large quantities of two different coins--pennies and dimes for example--into piles based on the date on their obverse sides. In this case, dates on the coins will be used as a substitute for colors in the context of the UTM instructions. Colors have been used for UTM instructions in the previously described embodiments, but this embodiment illustrates that another attribute of the game components, in this case a number, may be used. In the most general case, I will refer to this potential for substituting another attribute of the game components in place of colors as a use of a subset of the set of game components. Each player should start with 19 stacks of 19 of their chosen coin. Each stack of pennies and dimes should contain only coins with the same date--let's say, for example, 19 pennies dated 1991, 19 dimes dated 1991, 19 pennies dated 1992, etc. through 19 dimes dated 2009. A coin may only be played in the leftmost column of the board if it has a 1991 date, the next column to the right requires a coin with the 1992 date, etc. through to 2009 in the rightmost column. Play a game of Go or Gomoku as normal except for this rule regarding which pieces may be played where. When the (2,18) UTM is initiated based on pre selected game criteria (in a similar manner to that described in other embodiments) the UTM read/write head will read a heads up coin as being in state 1 and a heads down coin as being in state 2. A coin with the date 1991 will be considered an A coin by the UTM, 1992=B, 1993=C, etc. skipping over the year 2000. Coins are replaced by others with different dates according to the UTM instructions. As far as divinatory elements are concerned, there are 360 degrees in the zodiac and 360 intersections surrounding the central intersection on a Go board, so Sabian symbols (ROCHE) are an obvious fit. For more divinatory aspects of a Go board and game, see "The Religious Dimensions of Go" (SCHNEIDER)." Go game scenarios where a pre agreed UTM analysis of a board position might be useful include boards with triple kos and boards with long ko fights.
Is the trade off between adding additional complexity in rules in order to introduce Turing completeness to tabletop games worth the effort? Likely the answer to that question depends on the game and the players, but Magic: the Gathering is an example that in at least some cases the answer to that question is likely to be yes.
