0
$\begingroup$

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.

  • 1
    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.2012-07-01
  • 0
    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.2012-07-01
  • 0
    I should also add that the game is not finite, because it can fall into infinite loops.2012-07-01
  • 2
    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.2012-07-01
  • 0
    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.2012-07-01
  • 0
    "Fox and Geese" is almost of this type, and has attracted close scrutiny, so that might give you a better entry point to the literature.2012-07-01
  • 0
    Yes I was really hoping you wouldn't say that, I'm really trying to stay away from CGT research wise at the moment and was using this as a platform for further research into Graph Theory. If I try to publish this as a CGT paper it will be rejected.2012-07-01
  • 0
    My next suggestion was going to be that you email Richard K. Guy and ask if he knows anything about generalized forms of Tablut, but I suppose you won't like that idea either.2012-07-01
  • 0
    Richard Guy, John Conway, Elwyn Berlekamp, Richard Nowakowski and pretty much anyone who researches CGT hate me, and I mean HATE me. The reason is because I wrote a paper explaining why Elwyn's book Mathematical Go is wrong and they don't like that at all. I also game up with a brand new theory for combinatorial games which totally goes against everything they've been doing for the last 30 years. So because of that I am extremely unpopular.2012-07-01
  • 0
    It also probably doesn't help that after my paper Mathematical Go: Revisited was rejected I posted a rebuttal on my website explaining why the guy was totally wrong and why the paper should have been accepted. The reason it was rejected as I've said is simply because my name is not Elwyn Berlekamp, so therefore they don't believe a word I say.2012-07-01

1 Answers 1