Wednesday, 9 October 2013

strategy - Connect 4 Recursive



Here is a variant of the standard connect 4.


There are seven connect 4 grids (size 6 by 7) numbered 1 to 7. Each grid has the columns numbered 1 to 7. The person who starts selects any one of the seven grids and plays a single move in any column of that grid. (Gravity obviously exists in each grid)


Now onwards, a player has to play in the grid corresponding to the column number of the previous move by the opponent.


For example, suppose Alice starts by playing in the 3rd column of the 6th grid. Now Bob has to play in the 3rd grid. Let's say he plays in the 2nd column. Now Alice has to play in the 2nd grid. And so on....



Alice can choose to play in the 2nd column of this grid also, in which case Bob will also have to play back in the same (2nd) grid.


Once a person completes 4 in a row in one of the seven grids, he/she is the winner of that particular grid. However play will continue as per above mentioned rules. Both players are allowed to make more moves in the same grid, but any more 4 in a rows created in the same grid are of no use.


If Bob say plays in the 7th column of the 4th grid and suppose the 7th grid is completely filled (all 42 spaces), then Alice can play a move in any grid (just like the first move of the game). Same goes with Bob also.


The person to win the most number of grids (of the 7) wins the competition.


If Alice and Bob play perfectly, who wins?



P.S. This isn't just a random game, I know the solution to it.



Answer



Bob wins.


Alice plays anywhere. Assume it's grid 3 - if it's not, replace every instance of "3" with whatever number it is.


Bob now plays in column 3 on every single move. This gives Alice grid 3, but while she has to keep playing there, Bob can build up his columns on all the other boards. Eventually, Bob will get four of his other boards' columns up to four in a row.


So can Alice delay this by playing in board 3, column 3, where she's already won? Well, no.


Alice playing in board 3, column 3 isn't a problem because of parity. If she plays there, Bob plays in column 3 again. Eventually, that column fills up, with final state being alternation between the two chips. Since Alice was the first to play in B3C3, Bob was the last. So that column is filled up and it's Alice's turn, giving Bob an easy win.


No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...