Long-term I’m planning to write a chess engine. A reasonable step along the way, to help me learn about optimal games, was to write an optimal tic-tac-toe algorithm. A generalization of tic-tac-toe is called an m,n,k-game. An m,n,k-game refers to a board with dimensions m by n, where winning requires getting k in a row. I also wanted to look at the Misère variant, in which you win by forcing your opponent to get k in a row.
Results are tabulated below, the tool I wrote to play the game can be found here.
| M | N | K | Type | Winner | Max turns to win |
|---|---|---|---|---|---|
| 2 | 3 | 2 | Normal | P1 | 2 |
| 2 | 3 | 2 | Misère | P2 | 2 |
| 2 | 3 | 3 | Normal | Draw | - |
| 2 | 3 | 3 | Misère | Draw | - |
| 2 | 4 | 2 | Normal | P1 | 2 |
| 2 | 4 | 2 | Misère | P2 | 2 |
| 2 | 4 | 3 | Normal | Draw | - |
| 2 | 4 | 3 | Misère | Draw | - |
| 2 | 4 | 4 | Normal | Draw | - |
| 2 | 4 | 4 | Misère | Draw | - |
| 2 | 5 | 2 | Normal | P1 | 2 |
| 2 | 5 | 2 | Misère | P2 | 3 |
| 2 | 5 | 3 | Normal | Draw | - |
| 2 | 5 | 3 | Misère | Draw | - |
| 2 | 5 | 4 | Normal | Draw | - |
| 2 | 5 | 4 | Misère | Draw | - |
| 2 | 5 | 5 | Normal | Draw | - |
| 2 | 5 | 5 | Misère | Draw | - |
| 3 | 3 | 2 | Normal | P1 | 2 |
| 3 | 3 | 2 | Misère | P2 | 3 |
| 3 | 3 | 3 | Normal | Draw | - |
| 3 | 3 | 3 | Misère | Draw | - |
| 3 | 4 | 2 | Normal | P1 | 2 |
| 3 | 4 | 2 | Misère | P2 | 4 |
| 3 | 4 | 3 | Normal | P1 | 4 |
| 3 | 4 | 3 | Misère | P2 | 5 |
| 3 | 4 | 4 | Normal | Draw | - |
| 3 | 4 | 4 | Misère | Draw | - |
| 4 | 4 | 2 | Normal | P1 | 2 |
| 4 | 4 | 2 | Misère | P2 | 4 |
| 4 | 4 | 3 | Normal | P1 | 3 |
| 4 | 4 | 3 | Misère | P2 | 7 |
| 4 | 4 | 4 | Normal | Draw | - |
| 4 | 4 | 4 | Misère | Draw | - |
| 4 | 5 | 2 | Normal | P1 | 2 |
| 4 | 5 | 2 | Misère | P2 | 6 |
Some final boards (mnk-type)
333-Normal (tic-tac-toe)
X | X | O
------------
O | O | X
------------
X | O | X
Draw
333-Misère
O | O | X
------------
X | X | O
------------
O | X | X
Draw
343-Normal
O | O | X
------------
X | X | O
------------
X | |
------------
| |
Player 1 wins
343-Misère
X | O | X
------------
X | O | X
------------
O | X | O
------------
X | O |
Player 2 wins
344-Normal
X | O | X
------------
O | X | O
------------
X | O | X
------------
O | X | O
Draw
344-Misère
X | O | X
------------
O | X | O
------------
X | O | X
------------
O | X | O
Draw
443-Normal
O | O | |
----------------
X | X | X |
----------------
| | |
----------------
| | |
Player 1 wins
443-Misère
X | O | X | O
----------------
X | O | X | O
----------------
O | X | X | X
----------------
O | X | | O
Player 2 wins
444-Normal
X | O | X | O
----------------
X | O | X | O
----------------
X | X | O | X
----------------
O | O | X | O
Draw
444-Misère
X | O | X | O
----------------
X | O | X | O
----------------
X | O | X | O
----------------
O | X | O | X
Draw
452-Misère
X | O | X | O
----------------
X | | |
----------------
X | O | X | O
----------------
| | |
----------------
X | O | X | O
Player 2 wins