Economic and Game Theory
Forum

20 5 10 20 50 100 all
Ask a question about: Forum
Respond to the question: 5inarow solution?

05/16/2003 04:20 PM by david; 5-in-a-row solution

hi.

i'm trying to figure out the general solution for a game of getting n-in a row.. in an infinite game board with the restriction that moves must be made adjacent (horizontal, vertical, diagonal) to a previous move be it by yourself or by your opponent

the solution for 1 in a row is obvious win for player 1. he moves and he wins. simple

for 2 in a row it's pretty simple to.. player 1 moves then player 2 moves anywhere.. then playre 1 has 7 moves that get 2 in a row

for 3 in a row.. it's pretty simple as well.. player 1 moves. then player 2 moves. then player 1 pretty much makes any move that puts a piece adjacent to his first move. then he has 2 in a row with no caps at either end. so if player 2 doesn't cap either end. player 1 caps either end and wins. if player 2 caps an end. playre 1 caps the other end and wins..

for 4 in a row.. it's a tad bit more complicated but nothing to check yourself into an insane asylum for: player 1 moves. player 2 moves, then player 1 chooses his move like this: he move counter clockwise or clockwise around player 2's piece starting from his first move. then places his piece there.. so rotationaly there is only one gap between his first and second move. (rotationaly around the origin being player 2's first move)
so now the position is this: (or an equivelant one)

legend: E = empty space, X = player 1, O = player 2

XO
EX

which is obviously equivelant to other positions like

EOE
XEX

and a lot others you coudl get from rotation and reflection and what not

anyways. we'll go with the second one i showed. you see that player 2 can't let player 1 get his 3 X's in a row cause then that's a forced 4 in a row one move after.. so O has to go between the X's. if he goes in between them then X moves here:

EOE
XOX
EXE

then you see X has 2 uncapped 2's in a row.. and O can't avoid X getting 1 uncapped 3 in a row then a 4 in a row

if O goes anywhere else.. X can either make this same move.. or put an X in between the 2 X's

so X plays first and wins

i'm having a real difficulty solving this game for 5 in a row though.. though i'm sure the solution exists and is not too complicated

lines after a simpilar first and second move (similar to the solution for 4 in a row) seem to look good for X but i can't prove it's a forced win.. if anyone could find the solution.. and maybe possibly a solution for N-in a row.. i would be very appreciative of your assistance

-david

dwb1729@yahoo.com [Manage messages]