3

First: We assume that every player is playing at its best

Rules 5x5 board

Player 1 begins and puts every turn one cross “X”.

Player 2 puts every turn two circles “O”. They don’t have to be next to each other.

A player wins as soon as he has five of his pieces in a horizontal or vertical line.

We also agree that player 1 “X” wins if the board is completely full.

Example

What is the best strategy for each player to win the game?

5
  • 1
    If we're assuming both players play optimally, only one of them is going to have a winning strategy.
    – murgatroid99 ♦
    Mar 23, 2015 at 20:19
  • 1
    @murgatroid99 I'm not sure that's true because the victory conditions are different for the two players.
    – corsiKa
    Mar 23, 2015 at 20:25
  • 6
    I'm pretty sure that there is a proof somewhere that any deterministic two player game has a winning strategy for at most one player. And this game has no ties, so there will be a winning strategy for exactly one player.
    – murgatroid99 ♦
    Mar 23, 2015 at 20:51
  • 2
    It goes something like this: if player 2 has a winning strategy for every initial move player 1 can make, player 1 wins. Otherwise, player 1's strategy is to start with a move for which player 2 does not have a winning strategy, so player 1 wins.
    – murgatroid99 ♦
    Mar 23, 2015 at 20:55
  • Would this question be better suited for puzzling.stackexchange.com ?
    – freekvd
    Mar 26, 2015 at 13:29

2 Answers 2

Reset to default
6

This is a generalized version of @Guvante's answer.

O (player 2) always wins in 4. The diagonals are not necessary to achieve a win.

Examples are included in bold, but this strategy works for all choices made by X.

  1. X places a piece at (a,b): (1,1)
  2. O chooses a row that is not a, and places two pieces in that row, but not in column b: (2,2) and (2,5)
  3. Now, O is attacking on the chosen row (2), and on two columns (2 and 5). X will have to defend against one of these three attacks: (2,3)
  4. O chooses a free row and places two pieces above or below his previous pieces: (5,2) and (5,5)

This is what the board looks like at this point:

 X1|  |  |  |  
   |O1|X2|  |O1
   |  |  |  |  
   |  |  |  |  
   |O2|  |  |O2

Now O has 3 different attacks going on. In our example these are row 5 and columns 2 and 5. X can block one of these, and O can expand the other two to three-in-a-rows. Then X can block one of those, and O completes the other. Game over.

Since this is done in 4 moves, there's no risk of X getting 5 in a row so this is of no concern.

EDIT: step by step images, colors depict dominance.
X1 O1 X2 O2 X3 O3

4
  • I avoided X2 being where you put it since winning is trivial in that case, having X pre-empt the O2 move makes winning much more complex (as I don't think you can win if you allow X to pre-empt past the second turn)
    – Guvante
    Mar 25, 2015 at 19:39
  • @Guvante Having X play at O2 is exactly equivalent to playing where this answer puts it. In either case, after their second move O has a rectangle with three fully free 'lines', which is all this argument needs to go through..
    – Steven Stadnicki
    Mar 26, 2015 at 0:10
  • 2
    @Guvante X's first move is wholly moot to this solution. O just places his first move(s) on any two squares which do not share a row or column with X's first move, and then his second move on two squares which do share either rows or columns with his first move, and which leave three 'open sides' to the rectangle. X has only had two moves at this point.
    – Steven Stadnicki
    Mar 26, 2015 at 0:32
  • @Guvante In your example, if O just makes their second move at (1,2) and (1,4) they will win by turn 4.
    – Steven Stadnicki
    Mar 26, 2015 at 0:34
2

I have flip-flopped a few times, but think that Player 2 has an unbeatable strategy. The trick is that Player 1 needs an X in each row and each column while Player 2 needs a "box". Four O's that form a rectangle with no X's that share a row or column with said rectangle.

  1. First two O's sharing a row with self and separated by 1 square. Never put below or above or in line with X on this move. If possible (X not in center column) also make the square not in line with the X.
  2. If X is not above or below your O's then place two more O's above or below your current ones, at this point you can make two three in a rows on your next move, which means X cannot win.
  3. If X is above or below your O's then they blocked the box and you need to work to make it. This involves forcing X's move every turn by making a three in a row with holes where you want him to go. The first move is to add a third O to your line forcing X to block, make this third O on a free column that does not have an X and place another O on that column not sharing a row with an X.
  4. After X's move they have an X in three columns and rows assuming good play, if they do not it is easier. The objective is to minimize the reach to avoid X gaining the needed diversity of locations. Place an O in the same row as your fourth O and sharing a column with one of the original row's Os. Place the second O in the same column in the row that does not have an X. X is now forced to block this column without blocking a new row (as you win if they don't play in that column and both those rows are blocked by new Os).
  5. Whichever one they block you now have two rows/columns with two O's and no X's. Place an O in each and finish whichever X does not block on your final move.

For instance the following moves show this algorithm:

X (3,3) O (2,2&2,4) X (4,4) O (1,2&1,5) X (5,2) O (2,1&2,5) X (2,3) O (1,3&3,5) X (1,1) O (4,5&5,5)

X chooses the middle and then blocks the first box. However after this X is forced to make each move it makes (or an equivalent or inferior move). In fact past the second move the only moves that would change Os moves would involve immediate wins by O.

If X goes (3,1) as their second move it ends sooner, with O (2,4&4,4) followed by two three in a rows on the next turn. (X (3,4) follows with O (2,3&4,3) then either (2,1&2,5) or (4,1&4,5) and X (2,3) follows with O (3,4&4,3) then O(1,4&5,4) or (4,1&4,5))

Player 1's strategy would be to block any three in a rows and always attempt to play in a row and column that does not contain an X, but that doesn't block the above from winning.

4
  • Your example uses (2,5) twice. Also I don't understand why X would play on (2,3) if he already has (3,3).
    – freekvd
    Mar 25, 2015 at 17:56
  • @freekvd: Oops, the X was (5,2) fixed it. X must play (2,3) or (2,4) to avoid O winning, since O has (2,1),(2,2), and (2,5) at that point.
    – Guvante
    Mar 25, 2015 at 18:05
  • O can win faster here: let their turn 3 be (1,3) & (2,3); now X has no squares in the first or second rows and whichever one he puts a piece in, O will win on turn 4 in the other.
    – Steven Stadnicki
    Mar 26, 2015 at 0:36
  • @StevenStadnicki: Missed that, feel free to replace the moveset if you like, I only went as far as the above because I assumed it was at least somewhat complicated to win, didn't notice that the box was unblockable if you went up.
    – Guvante
    Mar 26, 2015 at 0:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .