Return to Answer

It's possible to give a complete theory of 3x3 misere "X-only" tic-tac-toe disjunctive sums by introducing the 18-element commutative monoid $Q$ given by the presentation

$Q = \langle\ a,b,c,d\ | \ a^2=1,\ b^3=b,\ b^2c=c,\ c^3=ac^2,\ b^2d=d,\ cd=ad,\ d^2=c^2 \rangle\ $.

Such a "disjunctive" game of 3x3 neutral tic-tac-toe is played not just with one tic-tac-toe board (as has been previously discussed in this thread), but more generally with an arbitrary (finite) number of such boards forming the start position. On a player's move, he or she selects a single one of the boards, and makes an X on it (a board that already has a three-in-a-row configuration of X's is considered out-of-play). Play ends when every board has a three-in-a-row configuration, and the player who completes the last three-in-a-row on the last available board is the loser.

The game analyzed already in this thread corresponds to play on a 3x3 single board.

The monoid Q arises as the misere quotient of the impartial game

G = 4 + {2+,0}

{2+,0} is the canonical form of the 3x3 single board start position, and "4" is the nim-heap of size 4, which also happens to occur as a position in this game. I'm using the notation of John Conway's On Numbers and Games, on page 141, Figure 32.

One way to think of Q is that it captures the misere analogue of the "nimbers" and "nim addition" that are used in normal play disjunctive impartial game analyses, localized to the play of this particular impartial game, neutral 3x3 tic-tac-toe.

I performed these calculations partly using Mathematica, and partly using Aaron N. Siegel's "MisereSolver" program.

See also

http://arxiv.org/abs/math/0501315

http://arxiv.org/abs/math/0609825

http://arxiv.org/abs/0705.2404

http://www.miseregames.org

It's possible to build a dictionary that assigns an element of Q to each of the conceivable 102 non-isomorphic positions in 3x3 single-board neutral tic-tac-toe. (I mean "non-isomorphic" under a reflection or rotation of the board. In making this count, I'm including positions that couldn't be reached in actuality because they have too many completed rows of X's, but that doesn't matter since all those elements are assigned the identity element of Q). To determine the outcome of a multi-board position (ie, whether the position is an N-position -- a Next player to move wins in best play, or alternatively, a P-position-- second player to move wins), what a person does is multiply the corresponding elements of Q from the dictionary together, and reduce them via the relations in the presentation Q that I started with above, arriving at a word in the alphabet a,b,c,d.

If that word ends up being one of the four words {a, b^2, bc, c^2 }, the position is P-position; otherwise, it's an N-position.

I'm guessing the the 4x4 game does not have a finite misere quotient, but I don't know for sure.

If people want more details, I'm happy to send them. Google my name for my email address.

Best wishes

Thane Plambeck

It's possible to give a complete theory of 3x3 misere "X-only" tic-tac-toe disjunctive sums by introducing the 18-element commutative monoid $Q$ given by the presentation

$Q = \langle\ a,b,c,d\ | \ a^2=1,\ b^3=b,\ b^2c=c,\ c^3=ac^2,\ b^2d=d,\ cd=ad,\ d^2=c^2 \rangle\ $.

Such a "disjunctive" game of 3x3 neutral tic-tac-toe is played not just with one tic-tac-toe board (as has been previously discussed in this thread), but more generally with an arbitrary (finite) number of such boards forming the start position. On a player's move, he or she selects a single one of the boards, and makes an X on it (a board that already has a three-in-a-row configuration of X's is considered out-of-play). Play ends when every board has a three-in-a-row configuration, and the player who completes the last three-in-a-row on the last available board is the loser.

The game analyzed already in this thread corresponds to play on a 3x3 single board.

The monoid Q arises as the misere quotient of the impartial game

G = 4 + {2+,0}

{2+,0} is the canonical form of the 3x3 single board start position, and "4" is the nim-heap of size 4, which also happens to occur as a position in this game. I'm using the notation of John Conway's On Numbers and Games, on page 141, Figure 32.

One way to think of Q is that it captures the misere analogue of the "nimbers" and "nim addition" that are used in normal play disjunctive impartial game analyses, localized to the play of this particular impartial game, neutral 3x3 tic-tac-toe.

I performed these calculations partly using Mathematica, and partly using Aaron N. Siegel's "MisereSolver" program.

See also

http://arxiv.org/abs/math/0501315

http://arxiv.org/abs/math/0609825

http://arxiv.org/abs/0705.2404

http://www.miseregames.org

It's possible to build a dictionary that assigns an element of Q to each of the conceivable 102 non-isomorphic positions in 3x3 single-board neutral tic-tac-toe. (I mean "non-isomorphic" under a reflection or rotation of the board. In making this count, I'm including positions that couldn't be reached in actuality because they have too many completed rows of X's, but that doesn't matter since all those elements are assigned the identity element of Q). To determine the outcome of a multi-board position (ie, whether the position is an N-position -- a Next player to move wins in best play, or alternatively, a P-position-- second player to move wins), what a person does is multiply the corresponding elements of Q from the dictionary together, and reduce them via the relations in the presentation Q that I started with above, arriving at a word in the alphabet a,b,c,d.

If that word ends up being one of the four words {a, b^2, bc, c^2 }, the position is P-position; otherwise, it's an N-position.

I'm guessing the the 4x4 game does not have a finite misere quotient, but I don't know for sure.

If people want more details, I'm happy to send them. Google my name for my email address.

Best wishes

Thane Plambeck

Postscript (added 8 Jan 2013) Here's a paper http://arxiv.org/abs/1301.1672 I just put up in the arXiv that has more details.

It's possible to give a complete theory of 3x3 misere "X-only" tic-tac-toe disjunctive sums by introducing the 18-element commutative monoid Q given by the presentation

Q = < a,b,c,d | a^2=1, b^3=b, b^2c=c, c^3=ac^2, b^2d=d, cd=ad, d^2=c^2 >.

Such a "disjunctive" game of 3x3 neutral tic-tac-toe is played not just with one tic-tac-toe board (as has been previously discussed in this thread), but more generally with an arbitrary (finite) number of such boards forming the start position. On a player's move, he or she selects a single one of the boards, and makes an X on it (a board that already has a three-in-a-row configuration of X's is considered out-of-play). Play ends when every board has a three-in-a-row configuration, and the player who completes the last three-in-a-row on the last available board is the loser.

The game analyzed already in this thread corresponds to play on a 3x3 single board.

The monoid Q arises as the misere quotient of the impartial game

G = 4 + {2+,0}

{2+,0} is the canonical form of the 3x3 single board start position, and "4" is the nim-heap of size 4, which also happens to occur as a position in this game. I'm using the notation of John Conway's On Numbers and Games, on page 141, Figure 32.

One way to think of Q is that it captures the misere analogue of the "nimbers" and "nim addition" that are used in normal play disjunctive impartial game analyses, localized to the play of this particular impartial game, neutral 3x3 tic-tac-toe.

I performed these calculations partly using Mathematica, and partly using Aaron N. Siegel's "MisereSolver" program.

See also

http://arxiv.org/abs/math/0501315

http://arxiv.org/abs/math/0609825

http://arxiv.org/abs/0705.2404

http://www.miseregames.org

It's possible to build a dictionary that assigns an element of Q to each of the conceivable 102 non-isomorphic positions in 3x3 single-board neutral tic-tac-toe. (I mean "non-isomorphic" under a reflection or rotation of the board. In making this count, I'm including positions that couldn't be reached in actuality because they have too many completed rows of X's, but that doesn't matter since all those elements are assigned the identity element of Q). To determine the outcome of a multi-board position (ie, whether the position is an N-position -- a Next player to move wins in best play, or alternatively, a P-position-- second player to move wins), what a person does is multiply the corresponding elements of Q from the dictionary together, and reduce them via the relations in the presentation Q that I started with above, arriving at a word in the alphabet a,b,c.

If that word ends up being one of the four words {a, b^2, bc, c^2 }, the position is P-position; otherwise, it's an N-position.

I'm guessing the the 4x4 game does not have a finite theory of disjunctive sums in misere play, but I don't know for sure.

If people want more details, I'm happy to send them. Google my name for my email address.

Best wishes

Thane Plambeck

It's possible to give a complete theory of 3x3 misere "X-only" tic-tac-toe disjunctive sums by introducing the 18-element commutative monoid $Q$ given by the presentation

$Q = \langle\ a,b,c,d\ | \ a^2=1,\ b^3=b,\ b^2c=c,\ c^3=ac^2,\ b^2d=d,\ cd=ad,\ d^2=c^2 \rangle\ $.

Such a "disjunctive" game of 3x3 neutral tic-tac-toe is played not just with one tic-tac-toe board (as has been previously discussed in this thread), but more generally with an arbitrary (finite) number of such boards forming the start position. On a player's move, he or she selects a single one of the boards, and makes an X on it (a board that already has a three-in-a-row configuration of X's is considered out-of-play). Play ends when every board has a three-in-a-row configuration, and the player who completes the last three-in-a-row on the last available board is the loser.

The game analyzed already in this thread corresponds to play on a 3x3 single board.

The monoid Q arises as the misere quotient of the impartial game

G = 4 + {2+,0}

{2+,0} is the canonical form of the 3x3 single board start position, and "4" is the nim-heap of size 4, which also happens to occur as a position in this game. I'm using the notation of John Conway's On Numbers and Games, on page 141, Figure 32.

One way to think of Q is that it captures the misere analogue of the "nimbers" and "nim addition" that are used in normal play disjunctive impartial game analyses, localized to the play of this particular impartial game, neutral 3x3 tic-tac-toe.

I performed these calculations partly using Mathematica, and partly using Aaron N. Siegel's "MisereSolver" program.

See also

http://arxiv.org/abs/math/0501315

http://arxiv.org/abs/math/0609825

http://arxiv.org/abs/0705.2404

http://www.miseregames.org

It's possible to build a dictionary that assigns an element of Q to each of the conceivable 102 non-isomorphic positions in 3x3 single-board neutral tic-tac-toe. (I mean "non-isomorphic" under a reflection or rotation of the board. In making this count, I'm including positions that couldn't be reached in actuality because they have too many completed rows of X's, but that doesn't matter since all those elements are assigned the identity element of Q). To determine the outcome of a multi-board position (ie, whether the position is an N-position -- a Next player to move wins in best play, or alternatively, a P-position-- second player to move wins), what a person does is multiply the corresponding elements of Q from the dictionary together, and reduce them via the relations in the presentation Q that I started with above, arriving at a word in the alphabet a,b,c,d.

If that word ends up being one of the four words {a, b^2, bc, c^2 }, the position is P-position; otherwise, it's an N-position.

I'm guessing the the 4x4 game does not have a finite misere quotient, but I don't know for sure.

If people want more details, I'm happy to send them. Google my name for my email address.

Best wishes

Thane Plambeck

It's possible to give a complete theory of 3x3 misere "X-only" tic-tac-toe disjunctive sums by introducing the 18-element commutative monoid Q given by the presentation

Q = < a,b,c,d | a^2=1, b^3=b, b^2c=c, c^3=ac^2, b^2d=d, cd=ad, d^2=c^2 >.

Such a "disjunctive" game of 3x3 neutral tic-tac-toe is played not just with one tic-tac-toe board (as has been previously discussed in this thread), but more generally with an arbitrary (finite) number of such boards forming the start position. On a player's move, he or she selects a single one of the boards, and makes an X on it (a board that already has a three-in-a-row configuration of X's is considered out-of-play). Play ends when every board has a three-in-a-row configuration, and the player who completes the last three-in-a-row on the last available board is the loser.

The game analyzed already in this thread corresponds to play on a 3x3 single board.

The monoid Q arises as the misere quotient of the impartial game

G = 4 + {2+,0}

{2+,0} is the canonical form of the 3x3 single board start position, and "4" is the nim-heap of size 4, which also happens to occur as a position in this game. I'm using the notation of John Conway's On Numbers and Games, on page 141, Figure 32.

One way to think of Q is that it captures the misere analogue of the "nimbers" and "nim addition" that are used in normal play disjunctive impartial game analyses, localized to the play of this particular impartial game, neutral 3x3 tic-tac-toe.

I performed these calculations partly using Mathematica, and partly using Aaron N. Siegel's "MisereSolver" program.

See also

http://arxiv.org/abs/math/0501315

http://arxiv.org/abs/0705.2404

http://arxiv.org/abs/math/0609825

It's possible to build a dictionary that assigns an element of Q to each of the conceivable 102 non-isomorphic positions in 3x3 single-board neutral tic-tac-toe. (I mean "non-isomorphic" under a reflection or rotation of the board. In making this count, I'm including positions that couldn't be reached in actuality because they have too many completed rows of X's, but that doesn't matter since all those elements are assigned the identity element of Q). To determine the outcome of a multi-board position (ie, whether the position is an N-position -- a Next player to move wins in best play, or alternatively, a P-position-- second player to move wins), what a person does is multiply the corresponding elements of Q from the dictionary together, and reduce them via the relations in the presentation Q that I started with above, arriving at a word in the alphabet a,b,c.

If that word ends up being one of the four words {a, b^2, bc, c^2 }, the position is P-position; otherwise, it's an N-position.

I'm guessing the the 4x4 game does not have a finite theory of disjunctive sums in misere play, but I don't know for sure.

If people want more details, I'm happy to send them. Google my name for my email address.

Best wishes

Thane Plambeck

It's possible to give a complete theory of 3x3 misere "X-only" tic-tac-toe disjunctive sums by introducing the 18-element commutative monoid Q given by the presentation

Q = < a,b,c,d | a^2=1, b^3=b, b^2c=c, c^3=ac^2, b^2d=d, cd=ad, d^2=c^2 >.

Such a "disjunctive" game of 3x3 neutral tic-tac-toe is played not just with one tic-tac-toe board (as has been previously discussed in this thread), but more generally with an arbitrary (finite) number of such boards forming the start position. On a player's move, he or she selects a single one of the boards, and makes an X on it (a board that already has a three-in-a-row configuration of X's is considered out-of-play). Play ends when every board has a three-in-a-row configuration, and the player who completes the last three-in-a-row on the last available board is the loser.

The game analyzed already in this thread corresponds to play on a 3x3 single board.

The monoid Q arises as the misere quotient of the impartial game

G = 4 + {2+,0}

{2+,0} is the canonical form of the 3x3 single board start position, and "4" is the nim-heap of size 4, which also happens to occur as a position in this game. I'm using the notation of John Conway's On Numbers and Games, on page 141, Figure 32.

One way to think of Q is that it captures the misere analogue of the "nimbers" and "nim addition" that are used in normal play disjunctive impartial game analyses, localized to the play of this particular impartial game, neutral 3x3 tic-tac-toe.

I performed these calculations partly using Mathematica, and partly using Aaron N. Siegel's "MisereSolver" program.

See also

http://arxiv.org/abs/math/0501315

http://arxiv.org/abs/math/0609825

http://arxiv.org/abs/0705.2404

http://www.miseregames.org

It's possible to build a dictionary that assigns an element of Q to each of the conceivable 102 non-isomorphic positions in 3x3 single-board neutral tic-tac-toe. (I mean "non-isomorphic" under a reflection or rotation of the board. In making this count, I'm including positions that couldn't be reached in actuality because they have too many completed rows of X's, but that doesn't matter since all those elements are assigned the identity element of Q). To determine the outcome of a multi-board position (ie, whether the position is an N-position -- a Next player to move wins in best play, or alternatively, a P-position-- second player to move wins), what a person does is multiply the corresponding elements of Q from the dictionary together, and reduce them via the relations in the presentation Q that I started with above, arriving at a word in the alphabet a,b,c.

If that word ends up being one of the four words {a, b^2, bc, c^2 }, the position is P-position; otherwise, it's an N-position.

I'm guessing the the 4x4 game does not have a finite theory of disjunctive sums in misere play, but I don't know for sure.

If people want more details, I'm happy to send them. Google my name for my email address.

Best wishes

Thane Plambeck