8
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ You can also add in the question the reference to the PSPACE-hardness proof by Lichtenstein and Sipser (perhaps it can be used as a starting point) $\endgroup$ – Marzio De Biasi Sep 6 '13 at 9:27
  • 1
    $\begingroup$ Maybe I'm lacking some background, but in what way is the question of Turing completeness relevant to the game of go? More generally, how can the game be said to compute anything? $\endgroup$ – mhelvens Sep 6 '13 at 9:35
  • 6
    $\begingroup$ If you're playing on a finite board, it can't be Turing-complete. And I'm baffled as to how you decide when a Go game on an infinite board ends. $\endgroup$ – Peter Shor Sep 6 '13 at 10:47
  • 2
    $\begingroup$ @PeterShor: a possible (reasonable?) generalization can be: start playing on $n \times n$ with an initial configuration that represents the input; the winner scores +1, extend the board to $(n+k) \times (n+k)$ (or $2n \times 2n$ or only horizontally to $2n \times n$ ???) and continue to play without removing old stones, stop the sequence of matches and end the game when the difference of scores is greater than $deltawin$ (or alternatively when a fixed computable function $f(score1,score2) = true$). $\endgroup$ – Marzio De Biasi Sep 6 '13 at 11:00
  • 1
    $\begingroup$ I think @PeterShor nailed it. Go doesn't have a king to checkmate. The game ends when there is nowhere profitable left to play. So on an infinite board the game never ends. And I don't see how you could use any other end game condition, because the score (and therefore the winner) cannot be known until the territorial borders and life/death status of the groups have been settled. $\endgroup$ – mhelvens Sep 6 '13 at 22:34
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 marked group is captured, in which case the input is accepted
  • The marked group acquires more than $2$ liberties, in which case the input is rejected.

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
-8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Your link only shows what look like "trading cards" without any discussion of Go that I can see. I think this is an advertisement for your patent and not an answer to the question. $\endgroup$ – Huck Bennett Apr 29 '15 at 2:38
  • $\begingroup$ See the additional embodiments section beginning at paragraph [0135]. I'd quote it here but it won't fit. The gist is to analyse the board using Rogozhin's (2,18) UTM where the standard Go pieces are replaced by pennies and dimes (since they meet the two state requirement, having obverse and reverse sides) with 19 different mint dates (one date for each column on the board). A standard game of Go is played until some pre agreed trigger (triple ko or a ko fight perhaps) in the game mandates a UTM analysis of the board position. $\endgroup$ – Tom Cooley Apr 29 '15 at 20:59
  • $\begingroup$ Sorry, I don't understand this at all. What you're describing still has a finite number of states, so it can't be Turing complete. More importantly, what do "divinatory elements" and "religious dimensions" have to do with anything? $\endgroup$ – Huck Bennett Apr 29 '15 at 22:10
  • $\begingroup$ "Divinatory elements" and "religious dimensions" have to do with my patent (see patent title). As I said previously, what is being simulated is linear bounded automata for an arbitrarily long period of time which (if you trust Wikipedia) is generally what we deal with in the real world - en.wikipedia.org/wiki/… $\endgroup$ – Tom Cooley Apr 29 '15 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.