# How do you prove that a game is undecidable?

I'm studying a game that is played on a graph, there are two teams, attackers and defenders. The attackers are attempting to capture the King by occupying all of his neighbours, the defenders are attempting to help the King escape by getting him to a special pre-defined escape vertex (or vertices) E.

The rules are as follows;

1.The game is played on a finite, simple graph which is defined arbitrarily before the game begins. There is also a pre-defined set of escape vertices.

2.There are two players, one playing the King and defenders, one playing the attackers.

3.Every piece is assigned a pre-defined starting position.

4.On a players turn he may move one of his pieces to an unoccupied neighbouring vertex.

5.The attackers and defenders may not occupy an escape vertex.

6.No two pieces can occupy the same vertex.

7.The King is captured if all of his neighbours are occupied, and he escapes if he moves to an escape vertex.

8.The King wins if he is escapes and the attackers win if he is captured. The game is declared a draw if the attackers cannot capture the King and the King cannot escape.

I want to show that it is undecidable to determine if one of the players wins, i.e. the attackers can capture the King or the King escapes, or if it is a draw, i.e. the King neither escapes nor is captured.

I've read up quite a lot about undecidability and I want to do a reduction from the Halting problem, by taking game positions as the input for the TM, then it halts if and only if the above conditions are satisfied. I'm just not sure about the details, any help would be very much appreciated.

-
If it's a finite graph, it's (probably) a finite game, so undecidability doesn't come into it. I write "probably" because you haven't given any details about the game. – Gerry Myerson Jul 1 '12 at 3:05
I added in the detailed rules, hope that helps. I just really need to figure out the complexity of this game but I don't have a lot of experience with complexity theory so I'm not sure exactly what to do. – Fraser Stewart Jul 1 '12 at 3:08
I should also add that the game is not finite, because it can fall into infinite loops. – Fraser Stewart Jul 1 '12 at 3:14
If it's a finite graph, it's still a finite game, since there are only a finite number of possible situations. Anyway, there is a lot of literature on this type of game. Maybe a search using the words "pursuit" and "game" and "graph" will turn something up. – Gerry Myerson Jul 1 '12 at 3:20
Yes that's called cops and robber, totally different game. I've read lots and lots of papers about it, but I have yet to see a single paper about the game I've described. The game that's most similar to it is "Tablut", and again I have not yet found a single paper on it. – Fraser Stewart Jul 1 '12 at 3:23

Your game is an example of a loopy partizan game. While I have been unable to find an exact quote from the literature, it seems that such games can be solved (the value of each position determined) in exponential time. Therefore the most that you can hope for is that your game is EXPTIME-complete, or perhaps only PSPACE-complete.

If your game were impartial (both players have the same moves), then Fraenkel and Perl ("Constructions in combinatorial games and cycles") give an algorithm which finds the Sprague-Grundy function; the situation for partizan games (where the two players have different moves) is more complication, and related to surreal numbers. Siegel's thesis is named "Loopy games and computation", and Lemma 1.1 should give the EXPTIME algorithm for winning your game.

If you're not satisfied, consult either the classic "Winning ways for your mathematical plays" or one of Aviezri Fraenkel's books; perhaps they have a more definite answer.

-
Thanks for that, I'm actually well versed in the literature on combinatorial games. I suspected it might be EXPTIME-complete. I was just hoping to present this as a graph theory problem rather than a game theory problem, having been ostracised from the CGT community for my theories I felt I needed to branch out and try other problems. Thanks for your answer, but I suspect, as will happen with all my papers it will be rejected. If you're interested in why I've ostracised check out my website I explain it all in there. – Fraser Stewart Jul 1 '12 at 4:22
Btw, are you sure that Lemma is correct, has it been peer-reviewed, because you know you can't "lean on" a thesis, so if I write my paper and reference the lemma from his thesis it will be rejected right? – Fraser Stewart Jul 1 '12 at 4:24
Actually I worked out how to solve this problem. Thankfully I don't need any CGT to do it. – Fraser Stewart Jul 1 '12 at 5:56