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.