Back in 2010, Backgammon giant Bob Koca was playing tic-tac-toe with his 5-year-old nephew, when the nephew whimsically suggested that they both play as X.
Being a mathematics professor, he used his knowledge to analyze this weird version of the classic game with various rules, boards, and objectives. It turns out that this all-Xs version of tic-tac-toe is a version of our old friend Nim!
To keep the game familiar, I'll stick to the standard 3-by-3 board in this post. The rules are as follows:
• Players alternate taking turns, and neither player may pass on their turn.
• A player marks any empty space on the board with an X on their turn.
• The loser is the first person to mark an X on the board that completes a horizontal, vertical, or diagonal line of 3 Xs.
This game is known to mathematicians as neutral or impartial tic-tac-toe, but I prefer the name given to it by Thane Plambeck, who lectured on this game at G4G10: Notakto (pronounced “No Tac Toe”).
As I mentioned, this is variation of Nim, more specifically a Misère version, so there must be some way to win it. I'll start, however, by explaining how to lose the game, instead:
What YOU Should NOT Do
You should start by going first, but the worst possible opening move is to place your X on any of the edge or corner squares. Why?Because your opponent can basically mirror your moves, and this strategy will ensure that you must eventually make a line of 3 Xs, as shown in the following animation:
As you can see at the end of the animation, when the first player puts their X on an edge or corner square, and the second player mirrors them, this leaves an open diagonal line on the first player's turn that forces them to complete a line.
I mention this strategy mainly so you can be aware of it, and make sure that it doesn't happen to you inadvertently. Should you let the other player go first and they place their first X on an edge or corner square, knowing about this becomes a winning strategy for you!
How To Win
To assure yourself the win, you start by placing your X in the center square. To play from there, Timothy Chow discovered the answer comes with help from a chess knight!Knowing how a chess knight moves (2 squares horizontally and 1 vertically, OR 2 squares vertically and 1 horizontally) is all you need to win.
After the other player makes their move, mark your next X a knight's move away from where their previous move. Keep using this strategy and they'll always be forced to draw the losing X. Watch the following animation carefully, and you'll get the general idea:
When choosing your spaces using the knight's move strategy, you'll usually have more than one space that qualifies. Often, one of the spaces will complete a line of 3 Xs, while the other is safe, so you'll always want to double check that you don't inadvertently make a losing play when you don't have to.
You can find out more about the game from Bob Koca's original discussion or the MathOverflow discussion. For a deeper look at the mathematics of Notakto, you can also read Thane Plambeck's presentation in PDF form.
If you'd like to practice this and you have an iPad, Thane Plambeck has also developed a Notakto app which will let you practice this version, as well as more difficult versions!
There's a closely related game taught on Scam School, called Napkin Chess, which is won using a similar symmetrical strategy. It's interesting to see the similarities, even though it doesn't have a tic-tac-toe board's discrete spaces.
Posts
1 Response to Secrets of Nim (Notakto)
Here's a simple web app that lets a person try up to five board notakto. you have to "earn" your way to it by winning three times on one board, then two, etc
http://plambeck.org/t5.html
this web app was the prototype for the notakto ipad app
Thane Plambeck
Post a Comment