Unbeatable Tic Tac Toe

I want to start this post out by apologising in advance for any typos or errors in this post. I’m pretty exhausted from a huge weekend of coding.

Over the last two days I wrote a Tic Tac Toe game. If you are a regular reader of this blog (shout out to Mom, Dad, Al and Sara!) you may be thinking “Wait, is this groundhog day? Didn’t you just do a Tic Tac Toe game?”

If you picked that up you are correct. I did one about a week and a half ago.

That one was for two human players to play against each other. This one is a bit more complex as it has a computer who needs to win (or at the very least tie!) If the player wins, I’ve done something wrong.

When I took on this task I thought that it would be easy — I’d just change around my JavaScript code that I’ve already been done, throw in an algorithm and be on my way. Nope.

This was hard!

I started off by making my interface for my JavaScript project nicer, which I wanted to do anyway. Then I started looking into the algorithm.

Lucky for me, this is a pretty common coding challenge, so there’s plenty of info out there. A quick google search makes it pretty apparent what the most commonly used algorithm is, and there’s even some blogs and YouTube videos that explain it.

After a good two or three hours of seeing how I could make it work with my current code, I made the tough decision to start fresh. I figured that starting over I could not only set up my code to work with the algorithm, but if I did it in Ruby rather than Javascript, I would have the luxury of using Ruby’s lovely enumerables.

So a few hours in I started again. At first things were relatively quick, but I kind of thought they would go quicker considering I’d done it before (in a IMO harder language), but then I got to the algorithm again, and it didn’t like me.

I’m not going to explain it here, because there are much better blogs that explain it, but the tl;dr version of it is

• It’s called Minimax
• It uses recursion, meaning it is a function that calls itself. I’ve literally never used recursion before this weekend, and I have been quite scared of it for that reason.
• Essentially, the algorithm looks at the board, and calculates all possibilities of outcomes. It then chooses which move it makes based on the biggest chance of it winning the game, and the smallest chance of it losing.
• This blog does a great job of explaining it

Recursion in a gif

I had a few ups and downs with it; the biggest excitement was when I first got it to work! My biggest upset what when I realised it wasn’t actually working, it was just going to the next available space on the board. There’s no way I could have done it without Dr Google.

This afternoon I finally got it to work and couldn’t believe it! Binding.pry was my best friend.

I really wanted to finish it this weekend, so due to time constraints, this evening I decided to make it a command line application rather than a web interface. It’s been quite some time since I wrote a command line app.

I had one horrifying moment, when after a few hours of my algorithm working whenever I tested it, I created the Computer vs Computer game in the command line, and for some reason X would let O win. This absolutely FLOORED me! I could not figure it out.

After a mild (ok — moderate..) freak out, I realised that I’d hard coded in player2 when I was calling my computer player in the command line app, so both player 1 and player 2 were trying to make player 2 win!

Now, thankfully it works!

Here’s the computer beating me:

============================
Let's play Tic Tac Toe!
     0 | 1 | 2
   -------------
     3 | 4 | 5
   -------------
     6 | 7 | 8
Select 1 for a two player game
Select 2 to play against the computer
Select 3 for two computers to play against each other
2
Against the computer? You won't win!
Who do you want to go first?
X(You!) or O(computer)?
x
X goes first!
X, which cell are you after?: 0
     X | 1 | 2
   -------------
     3 | 4 | 5
   -------------
     6 | 7 | 8
The computer, O is thinking
     X | 1 | 2
   -------------
     3 | O | 5
   -------------
     6 | 7 | 8
X, which cell are you after?: 1
     X | X | 2
   -------------
     3 | O | 5
   -------------
     6 | 7 | 8
The computer, O is thinking
     X | X | O
   -------------
     3 | O | 5
   -------------
     6 | 7 | 8
X, which cell are you after?: 3
     X | X | O
   -------------
     X | O | 5
   -------------
     6 | 7 | 8
The computer, O is thinking
     X | X | O
   -------------
     X | O | 5
   -------------
     O | 7 | 8
============================
O is the winner!
============================

Here’s the computer not letting the other computer win

============================
Let’s play Tic Tac Toe!
 0 | 1 | 2
 — — — — — — -
 3 | 4 | 5
 — — — — — — -
 6 | 7 | 8
Select 1 for a two player game
Select 2 to play against the computer
Select 3 for two computers to play against each other
3
Watching two computers battle it out? Nice!
X and O are both computer players
Who do you want to go first?
X or O?
x
X goes first!
The computer, X, is thinking
 X | 1 | 2
 — — — — — — -
 3 | 4 | 5
 — — — — — — -
 6 | 7 | 8
The computer, O, is thinking
 X | 1 | 2
 — — — — — — -
 3 | O | 5
 — — — — — — -
 6 | 7 | 8
The computer, X, is thinking
 X | X | 2
 — — — — — — -
 3 | O | 5
 — — — — — — -
 6 | 7 | 8
The computer, O, is thinking
 X | X | O
 — — — — — — -
 3 | O | 5
 — — — — — — -
 6 | 7 | 8
The computer, X, is thinking
 X | X | O
 — — — — — — -
 3 | O | 5
 — — — — — — -
 X | 7 | 8
The computer, O, is thinking
 X | X | O
 — — — — — — -
 O | O | 5
 — — — — — — -
 X | 7 | 8
The computer, X, is thinking
 X | X | O
 — — — — — — -
 O | O | X
 — — — — — — -
 X | 7 | 8
The computer, O, is thinking
 X | X | O
 — — — — — — -
 O | O | X
 — — — — — — -
 X | O | 8
The computer, X, is thinking
 X | X | O
 — — — — — — -
 O | O | X
 — — — — — — -
 X | O | X
============================
The game was tied!
============================

If you want to try to play it, please do! The code is on my Github. There’s instructions in the Readme.

pelensky/unbeatable_tic_tac_toe

Things I learned

• Basics of recursion
• Minimax algorithm
• Using established algorithms
• It’s ok to not reinvent the wheel
• Command Line applications are fun

Things I want to focus on

• I would love to be able to explain recursion really well, and use it myself (rather than following an algorithm)
• Time management — I probably shouldn’t have spent so long trying to make the JavaScript one work

Things I’m struggling with

• Nothing now, but if you’d asked me a few hours ago it would have been a different story!

Now I’m off to sleep before starting final week at Makers tomorrow morning! I’m looking forward to getting back into Swift after a weekend with my first love, Ruby!