If n=1, 2, 3 Y will win, if plays optimally.
I believe the player who starts the game will always lose if both the players play optimally.
My reasoning behind it is as follows:
Maximum possible moves for a game with n initial spots = 3n-1
Minimum moves = 6 – 1 = 5
Maximum move = 12 – 1 = 11
For n=5,
Minimum moves = 7 – 1 = 6
Maximum move = 15 – 1 = 14
For n=7,
Minimum moves = 10 – 1 = 9
Maximum move = 21 – 1 = 20
For all n>=4, there is a reasonable margin between the minimum moves and maximum moves that can be made in a game.
Both X & Y will try to make the number of moves left(after their respective turn) an even quantity.
They will do so by creating closed regions and using (or not using) the new spot on opponent’s last move.
At any stage of the game both the players have equal liberty(on whether to add the optional vertex on opponent's last move) except at the first move.
When X makes the first move he/she cannot add a new spot because there is no curve drawn yet.
After X draws the first curve Y can decide whether to put a new spot on this curve.
X doesn’t have this option at the beginning of the game.
May be this one slight advantage can turn the game in Y’s favor, if he/she plays optimally.
We can find out only by computing the game tree.
I was trying to write a code that will compute the game tree and find out who wins if both players play optimally. But I could not figure out how to represent the stages of the game.
Initially I thought the spots & edges can be represented in form of graph but later on I discovered it was not possible to represent the stages of the game in form of graphs. The non equivalent scenarios shown in the previous post cannot be distinguished using graphs.
_________________________________________________________________________________
I find this game very interesting and am trying to build a game application where human will play against computer, and according to the difficulty level, the computer will analyze the game at each stage and make an appropriate move.
Developing the application will require graphics programming, nice algorithms to analyze the game after each stage, proper way to represent the data.
Here is what I have planned so far:
Each vertex can be represented as a node.
Whenever an edge is incident on it, its degree can be increased.
All the vertices with degree 3 can be ignored to limit computation.
False move (intersection of edges & degree exceeding 3) can be checked instantly, as soon as current curve crosses any previously drawn curve or is incident on an invalid vertex(already having degree=3)
After a move is made, we need to analyze and find out how many more moves are possible.
Computer’s strategy should be to make the number of moves left after its turn an even or odd quantity, depending on the difficulty level.
Taking a brute force approach and simulating all the possible moves that the computer can make to find which move is best will take too much time …and probably fail to execute in reasonable time even for small n.
The total moves can be approximated using the degree of vertices.
We compute the total possible moves after a move is made, without considering a new spot on this move.
Then we compute the total moves possible, taking into consideration the new spot.
We compare the results and decide whether to mark a new spot on the current spot.
An algorithm to compute the number of moves possible, given a game scenario:
Divide different regions, as shown here:
Different regions are shown in different
colors.
Let X = {set of all regions}
Algo:
1. Unmark all the nodes having degree less than 3.
2. Total_max_moves =0;
3. Total_min_moves = 0;
4. For each regions R in X
{
5. Int y = (total unmarked nodes within R, including those on boundary) x 3 – (total degree of all these nodes)
// y is total lives that can be used to make a move.
6. Calculate max & min moves possible.
7. If min moves is not a whole number then ignore the spots on the boundary of the region and recalculate y. Repeat this step till all spots on the boundary of the region are exhausted.
8. Mark all the nodes used in computing y.
9. Total_max_moves = Total_max_moves + max moves.
10. Total_min_moves = Total_min_moves + min moves.
}
Using this we can compute the max & min moves left in the game.
But this value is of little use when n is large because difference between max & min moves will be too large and adding/not adding a new spot will not make much difference.
Yet, I will like to code this and see how it works.
I think making random moves initially to reduce the game size and using this algorithm towards the end of the game to calculate number of moves left should work fine. I will know only after I code it.
Here is another approach I have thought of:
I already have the optimal moves for small n(for n=1,2,3). I will store these configurations in the code.
First the computer will try to bring the game to a configuration that is already stored in the code.
Then it will use the optimal moves to win the game.
For this I will need algorithms to detect equivalent scenarios.
I am still working on it.
No comments:
Post a Comment