Unbeatable Tic Tac Toe Update
I was originally going to edit my previous post, but this started getting a little verbose, and figured it may make more sense to write a brand new post as an update. Have a look at the below before reading this:
I want to start this post out by apologising in advance for any typos or errors in this post. I’m pretty exhausted from…medium.com
My previous post didn’t really go into the reasons why I started a new project, rather than continuing with my old project when I started this unbeatable tic tac toe game.
I started out by researching quite a bit of the Minimax algorithm, which I used for the AI component. I started to get my head around how it worked, but at the time I was quite confused about it.
I also had the benefit of time and the ability to look over my old code with fresh eyes prior to extending it.
One example of my decisions that I’m now questioning is that my Player object tracks who’s turn it is. The reason I had initially chosen this is that I felt that the Player object should be responsible for everything to do with the player (including the turn). A bit more thought about this made me realise that the the game controls the player turns. A real world example; say we are playing with a pen and paper — If I were put down an X, it would be your turn, right? Well if the player was in charge of the turn, I could just say “Nope — I’m playing again”.
Another example of something that I probably didn’t need, is that my board object had a function that checked if the board was clear; though I never used this function.
One thing that I am semi proud of in my first implementation of the game (though I changed to something a bit more clever in my second after having thought about it more) was my way of checking if the game had been won.
It’s a really big function, but time was the main issue, and I was able to get something that worked. In my newer implementation I came up with something a bit more clever (and less bulky), but sometimes when there is limited time done is better than perfect.
The algorithm that I used (more details in my original post) relies on the computer having entire visibility over the board. Just like humans do while playing.
One of the first things I noticed when I went to see how I’d implement it, is that I had built my ‘chooseSpace’ function to do a TON of different things — choose the space on the board, increase the turn number (something I left out completely in my later implementation), check if the game is won and switch the turn. It didn’t adhere to the single responsibility principle at all…
At the time, I felt that decoupling those functions might be a bit more effort than it was worth. With the benefit of hindsight, I now see that it would have been quite simple.
Another thing that the Minimax algorithm needs is the ability to see all the available spaces on the board. I hadn’t set that up in my original implementation, but that’s something I could have done quite easily.
Overall, I found the Minimax algorithm quite hard to understand. While doing a ton of research, I found this blog to be the one that explained it the very best to me out of anything that I had read.
It used a max_by enumerable that I hadn’t used previously. What max_by does is:
Returns the object in enum that gives the maximum value from the given block.
So, after a good three hours, I chose to give myself a clean slate and set my game up to work nicely with it. With the confusion I had, I decided to do it in the language I am the most comfortable in, and also the language that the resources that made the most sense to me were in.
In the real world, you are almost always working on projects with legacy code. You don’t just get the opportunity to trash everything that is there and start again in a different language because it is a bit easier.
Right now things are crazy, but when I have more time I’m going to do what I was originally planning; refactor my old code base enough so that I can extend it so that the computer can play and always wins.
In my opinion there is a huge benefit to repetition. I think that when I get a chance to extend my original code it will still be difficult but I have no doubt that I’ll be able to do it.