Go (the surrounding game) is over 4000 year old strategy game between two players. It is played with Black and White tokens (called stones) on a square board with intersections drawn. The goal of the game is to surround opponent's territory (intersections on the board) using the stones. Also you can surround your opponent's stones to capture them and remove them from the board. The game ends when each intersection on the board has clearly decided to which player's territory it belongs, or both players consecutively pass a move. The player that surrounds more territory than his opponent wins the game. Each surrounded intersection counts as one point of territory and each captured stone reduces the opponent's territory by one point. The rules of Go are very simple and can be learned in just a few minutes, but to perfect your game it might take you a lifetime, as Go is very rich in strategy and the number of possible games outnumbers the number of atoms in the observable Universe.
Go being so complex, yet so simple, my question is, if computation (a Universal Turing Machine) can be simulated by it? If such a thing is possible, what about a Go game itself being simulated on such a machine?
The rules of Go:
http://gobase.org/studying/rules/?id=0&ln=uk
Good point Peter, thanks. I guess playing Go on the lattice points of the first quadrant of the plane might cut it closer. Rules will maybe have to be modified somewhat.
Konrad,
as it looks to me, you did not even the self-suggesting reasonability checks prior to formulating your question. Running the Turing simulation has to be deterministic. Go, by its very nature of a strategic game, can't determine the next step. So,unless you add newly invented rules, it can't run as an automaton.
Ulrich, I had something like this in mind when I was formulating my question. It's the proof that GO is PSPACE hard. QBF formulas are coded into a Geography game which is then converted to a GO position. Maybe Turing computation, or some weaker form of computation can be similary coded.
http://www.cs.bu.edu/faculty/gacs/courses/cs535/papers/Lichtenstein_Sipser_go.pdf
@Peter,
what we both remember of the 'Game of Life' as a simulator - does it not support my point of view that the character of the 'game' as a deterministic evolution (from an arbitrary initial state) is essential ?
Oh Peter,
why do you burden me with caring of JWHC and Richard Guy?
Your idea of establishing determinism looks ridiculous to me: Having reached the next Breuer state (a set of allowed Go states obtained by a set of allowed Go moves) allows a set of Breuer states as a next step - determinism perdu.
Having played a few dozens of Go parties so far, I would locate your ideas in cloud-cuckoo-land.
Dear Ulrich and Peter, thank you for your answers. Regarding the determinism issue, I suggest you have a look at an article about Go being PSPACE hard i posted earlier to this thread. The trick is to first fix a position on the board in such a way that when the game starts it makes the opponent play a certain way, and if he does comply he will lose a large part of his territory which will cause him to lose the game. This is of course just a suggestion. I also suggest you play at least a couple of Go games first so you can get acquainted with the mechanics of the game.
GO is EXPTIME-complete (at least the GO game I consider (Japanese rules), so it falls in the class of decidable problems.
This being said, I am unsure if GO could simulate a Turing Machine because that would imply the GO game could determine the decision problem in finite time for any instance. Though, I may suspect it may be possible if you encoded movements in the right way, but this would "add" axioms to the game that may no longer make it EXPTIME-complete and instead potentially undecidable.
It all really boils down if you can prove it.
You could prove that an infinite generalization of the game is undecidable through reduction from the halting problem.
A possible generalization is the following:
* the game is played on a infinite board that corresponds to the positive quadrant of the plane
* the board has an initial finite configuration (this is a way to simulate the input of the Turing machine)
* the players must place their stones in a n x n "play square" (on the origin), after completing a game on it (the winner gains one point), the "play square" is extended to 2n x 2n and the players can continue the game (without removing the stones of the previous smaller square)
* a possible end game condition is when the number of points scored by one player is greater than a fixed function of the score of the other
(for example SCORE1 >= k * SCORE2)
* the problem is "Have black a winning strategy?"
I'd bet that in this form the problem is Turing complete.
To Ulrich Mutze: what about making self-suggesting knowledge checks prior to criticizing other's questions? :-) See for example the open question: "Is infinite chess decidable?" http://arxiv.org/pdf/1201.5597v4
- Badges
- Science topic
- Similar topics
- Mathematics