Binary tic-tac-toe

[bonanova]

In the all-digital future, X and O are banished from the game of tic-tac-toe.

They are replaced by 1 and 0, the the result of such a game might look like this:

1 | 0 | 1

- + - + -

0 | 1 | 1

- + - + -

0 | 1 | 0

Under the usual rules that require getting 3-in-a-row, it would be a draw.

But this is the digital age, and there are different rules for winning.

If we sum the eight rows of three numbers we get 2, 2, 1 (horizontally) 1, 2, 2 (vertically) and 2, 2 (diagonally).

Six of the sums are even, and two are odd.

The final parity of the board is thus even, and the game is said to have an even outcome.

If there were more odd sums than even, the game would have an odd outcome.

If there were four even (and therefore four odd) sums, the game would have a neutral outcome.

The game is played as follows:

The winner of a fair-coin toss (call him player A) chooses whether to play first or second.

The other player (call her player B) decides whether she wants an odd, even, or neutral game outcome.

On each turn, a player places his choice of either a 1 or a 0 on any unoccupied place on the grid.

As in normal tic-tac-toe, players alternate turns; but here on each turn a player may play either a 0 or a 1.

When the places are filled, the board is examined to determine whether it is odd, even or neutral.

If the final board parity matches player B's choice, player B wins; otherwise player A wins.

The questions to answer are:

1. Is there an advantage to winning the coin toss?
2. Is there a winning strategy for either player?

[Rainman]

A wins the game by choosing to play first and placing his first digit in the middle. If B chooses even or odd, wherever B places her digits henceforth, A places directly opposite through the middle, making the sum of that row whatever B didn't choose. This way six of the rows will have the wrong sum for B, and B loses. If B chooses neutral, A plays the same way as if B had chosen odd and there will be six even rows, so B loses anyway.

Edited February 20, 2014 by Rainman

[plasmid]

I may be missing something, but by playing on the opposite side of the center square as player B, player A seems to be able to control the outcomes of four rows (both of the diagonals and the horizontal and vertical rows through the center), not six. The topmost and bottommost horizontal rows, and the leftmost and rightmost vertical rows, are not so easily determined. Player A can control four row outcomes, which is enough to prevent B from being able to win if B goes for either an even or an odd outcome, but it's not clear if A can prevent B from achieving a neutral game outcome using that strategy.

But tweaking the strategy slightly would do it. If player A plays first and knows that player B is going for a neutral game outcome, then rather than shoot for an even or odd row sum, A can just continuously play the opposite number as B (A plays 0 if B played 1, A plays 1 if B played 0) across from the center square. The sum of the top row will be the opposite even/oddness as the bottom row, and the left will be the opposite of the right, so those four will have 2 even and 2 odd. If player A played a 1 in the middle then all four rows going through the center square would be even, and if player A played a 0 in the middle then all four would be odd. Either way, there would end up being 6 evens and 2 odds, or 2 evens and 6 odds, so not the neutral outcome that B would have to achieve.

[Rainman]

Yep, I got it wrong.

[bonanova]

I may be missing something, but by playing on the opposite side of the center square as player B, player A seems to be able to control the outcomes of four rows (both of the diagonals and the horizontal and vertical rows through the center), not six. The topmost and bottommost horizontal rows, and the leftmost and rightmost vertical rows, are not so easily determined. Player A can control four row outcomes, which is enough to prevent B from being able to win if B goes for either an even or an odd outcome, but it's not clear if A can prevent B from achieving a neutral game outcome using that strategy.

But tweaking the strategy slightly would do it. If player A plays first and knows that player B is going for a neutral game outcome, then rather than shoot for an even or odd row sum, A can just continuously play the opposite number as B (A plays 0 if B played 1, A plays 1 if B played 0) across from the center square. The sum of the top row will be the opposite even/oddness as the bottom row, and the left will be the opposite of the right, so those four will have 2 even and 2 odd. If player A played a 1 in the middle then all four rows going through the center square would be even, and if player A played a 0 in the middle then all four would be odd. Either way, there would end up being 6 evens and 2 odds, or 2 evens and 6 odds, so not the neutral outcome that B would have to achieve.

In a neutral outcome, the four outer rows have the parity that is opposite of the four directly controlled ones. The outer parities can be made (all) even by placing 1's in the corners or (all) odd by putting 1's on the centers. But these placements do not happen. What Rainman's method seems to achieve is outer rows having two even and two odd parities. That outcome thwarts any choice by Player B. Is there a counterexample?

[plasmid]

Player B chooses Neutral. Player A places a zero in the center, and aims to make all of the rows he can control be even parity. Player B places a 1 in the upper left corner, so player A places a 1 in the lower right corner so that diagonal is even. Player B places a 0 in each of the other positions, and player A places 0s opposite to make those rows even. The final board setup would be

1|0|0

-----

0|0|0

-----

0|0|1

The four rows going through the center are even. The topmost and bottommost rows, and leftmost and rightmost columns, are odd. So player B wins.

[bonanova]

Player B chooses Neutral. Player A places a zero in the center, and aims to make all of the rows he can control be even parity. Player B places a 1 in the upper left corner, so player A places a 1 in the lower right corner so that diagonal is even. Player B places a 0 in each of the other positions, and player A places 0s opposite to make those rows even. The final board setup would be

1|0|0

-----

0|0|0

-----

0|0|1

The four rows going through the center are even. The topmost and bottommost rows, and leftmost and rightmost columns, are odd. So player B wins.

If A always places the opposite mark, as Rainman suggests, doesn't it always come out 6-2? If so, neutral never happens.

And if B chooses odd (even) A places 1 (0) in the center, making the final board 6-2 even (odd).

I may be wrong, but I did not find a way for B to prevent 6-2, and A seems able to control, on his first play, the prevailing parity.

A always plays opposite (1 or 0) to B.

If A's center move is 1 the result is 6-2 even.

If A's center move is 0 the result is 6-2 odd.

A is in control, and B cannot correctly predict.

[plasmid]

My reading of Rainman's original answer was

1. Player A puts any ol' number in the middle (either 0 or 1)

2. For every move player B makes, player A makes a move on the opposite side of the center square to make the row going through the center be even (if B is trying for an odd board), or odd (if B is trying for an even board), or even as a sort of arbitrary choice (if B is trying for a neutral board)

The counterexample was pointing out that if that algorithm were followed there could be a scenario resulting in a win for B if B is going for a neutral board.

You're correct that the counterexample would not beat a strategy where A places the opposite of whatever B places if B is going for a neutral board, which is the bit of strategy I amended to Rainman's answer so A would win in all possible scenarios.

[bonanova]

OK, got it. I did mis-read the solution.

I ran across this puzzle some time ago, and wondered whether it could break the deterministic nature of 3x3 tic tac toe by giving freedom of choosing which marker to place, and found that it doesn't. Maybe ANY 3x3 game allows Player 1 to either win or at least avoid a loss.