winning strategy algorithm for simple game [2 players moving on grid field]
I'm searching for a winning algorithm in this game:
-game is played on grid (we can say its infinite grid)
-there are two players, 1 (orange) starts and his move is long exactly 1, player 2 (green) is second and his move is long exactly 2, they take turns
-goal for the second player is, to get to the start (he wins even if the player 1 gets there)
-goal for the first player is to never get to starting point or to somehow block the game so there are no more moves
-they cannot go through path (points) where they had already been
here are some examples of the game (in game 3 orange player wins, because there are no more moves) 
I would be grateful for any help on this (links if this is known solved algorithm, or pseudo-code, or just plain simple text from which could be the strategy understood)
thanks
m,
Try this:
Since orange player moves only one, move in the direction away from direction of start point. 1. Initially move top(Suggestion), Green can end up on 7 possible points after its move. Check direction of start from present point. 2. If it is bottom left from start point, move orange either further down or further left. this way you never make a move towards the start point.
To improve this further you can store all moves played till then on a database and decide whether to move down or left(In step 2) based on the following:
if there are more number of moves to the left of the current position, compared to those to the bottom of the current position ----> move down else move left.
PS: The initial move can be anything. The strategy is to move away and avoid getting stuck between moves.
Orange can always win by always moving further away from the origin. Based on nonintersecting random walks in the plane, this strategy is robust against anything green might try.
If you want to do the analysis right, here's how to get started.
With most game theory problems, the key is to work backwards from the end. Let's be green first, and let's assume that we have the last move. For now, to keep things simple, let's ignore the "avoid prior paths" condition. We can add that back in once we understand the simpler version.
Let's digress for a moment to say that "distance" must be hamming distance in our simplified version. Once we account for obstructions, by the "distance between two points" we mean the length of the shortest path that does not intersect an existing game path between the given points. If no such path exists, say the distance is infinite.
In the simple version, each of green's moves changes the distance to the origin by 0 or 2, and each of orange's moves changes the distance to the origin by 1. Keeping this in mind, we work from the end...
If we hit the origin, we win, so we will win if orange puts us distance 2 from the origin. Since orange moves one step per move, we win if we land distance 1 from the origin (since orange must either move to distance 0 or to distance 2). If we land distance 3 from the origin, then we win if orange moves to distance 2, but not necessarily if he moves to distance 4. In this case, we can quickly see that orange can always keep moving away from the origin (as in a nonintersecting random walk) and we never return. However, we still have useful information that two factors are key:
上一篇: 解决图形游戏