For reasons I cannot remember now, I once searched tic tac toe on Google. I noticed that when you search it, Google gives you a game board where you can play the game. You can even choose the difficulty. What spiked my interest the most is, that there was a difficulty option named "Impossible". It completely blew my mind that there is a way to make sure you never lose. I became so fascinated that I started to dig deeper. And that's how I ended up here.
Dig Deeper π€¨
I found that the secret ingredient for such a bold claim was a very simple algorithm that can be written in less than 30 lines of code. It's called the MiniMax algorithm.
Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-making and game theory. It provides an optimal move for the player assuming that opponent is also playing optimally - JavaPoint
As soon as I saw that it was not actually a machine learning solution, but rather an algorithm, I became very demotivated.
Why?
Confronting my fears πͺ
Because it was the same time I took the Algorithms course at my university. And I did miserably. I did not want anything to do with algorithms. I was planning to recreate the impossible tic tac toe game but was not sure if I'd learn an algorithm for it. On one hand, this could be a great opportunity for me to lose my fear of algorithms, on the other hand, it would mean tackling something I feared most of my life.
That's when I found this video by Sebastian Lague, one of my most favorite YouTubers. This video really made me think I can complete the project if I tried. And I did. The rest is a story of sheer perseverance, and an eagerness to improve myself.
Hard Decisions π€
The first decision I needed to make is what I'm going to use for the frontend. Basically displaying the game board and handling the user interactions. I knew it had to be a cross-platform solution. Because I had a play store account where I want to publish the app as a technical project, but also wanted to host it on the web so that my friends could play it easily without downloading an app. My first choice was Unity. It passed all my requirements and is a solid framework for game development. But it was also very overkill for a simple game like this. Not to mention, the learning curve is also very high. I undertook this project to learn about algorithms. I didn't want to learn game development as well. This is why I decided to go with Flutter.
Why Flutterβ
Because I already knew the framework well enough and it supports more platforms than Unity. I realized it would take me significantly less time to develop the frontend with Flutter. Now, you may be thinking, if Flutter is so great, why wasn't this your first choice? Because Flutter is primarily an application development framework. It never occurred to me that, a tic tac toe game board is nothing but some grids and common app UI elements. Flutter is great for them. It can also take any type of interaction from the user, be it single taps, press and hold, or even gestures.
After I had chosen my framework of choice, it was now time to build the UI. And surprisingly, It only took me around 2 hours to do so. I then watched this video by another personal hero of mine, Daniel Shiffman from the Coding Train. His video really helped me understand the implementation, and edge cases for the algorithm.
The not so fun part π
Although it took me a very short time to create the UI, I wish I could say the same for the algorithm. The programming language I'm using, called Dart, is actually very similar to javascript, the language Dan used to create the AI. So in my mind, I thought it was going to be a very easy task. But boy was I wrong. While trying to code, I faced the infamous StackOverflow error for the first time in my life. And this has to be one of the scariest errors I've gotten in my life. The program would take up so much resources that I had no option but to shut down my then crappy PC. But one bug at a time, I managed to fix all of them. But it was not smooth sailing yet.
Optimizations β‘
I managed to complete the project finally. I could play the game and the AI would check for all the possible moves ahead and choose the best one. But there was one problem. After I place my first "X", the AI had to check for 255,168 possible steps ahead (If I'm not mistaken). This meant that I had to wait a long time for the AI to complete the calculations and choose the best option. Which, not to mention, was not fun at all. This meant only one thing. I had to optimize the algorithm. That's when I learned about alpha-beta pruning.
Alpha-beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree - Wikipedia
In layman's terms, it drastically reduced the number of steps the AI has to check. And believe it or not, even this wasn't enough for me. I then learned about Isolates. This is actually a fancy way of saying I implemented multithreading. This would allow me to not block the UI while the calculation is going on in the background since both these tasks are handled in separate threads. After all of these was done, the project was finally complete. I created a tic tac toe game that no one can beat. And I cannot explain how happy I was.
Taste of success π
I undertook a challenge, did extensive research, defeated one of my biggest fears, and successfully completed the project. I know I'm making it sound like I'm describing the plot of IT (2017), but that's what it felt like to me.
Thank you very much if you came this far. This is the first time I wrote something for myself. So your thoughts and criticisms are much appreciated. Don't forget to leave a comment.
Try it out! π
The actual algorithm if you are interested:
minimax(board, depth, isMaximizingPlayer) {
checkCount++;
var result = checkAIWinner(board);
if (result != 'NONE') {
return scores[result];
}
if (isMaximizingPlayer) {
int bestScore = -999999999;
for (int i = 0; i < board.length; i++) {
if (board[i].isEmpty) {
board[i] = 'O';
var score = minimax(board, depth + 1, false);
board[i] = '';
if (score > bestScore) {
bestScore = score;
}
}
}
return bestScore;
} else {
int bestScore = 999999999;
for (int i = 0; i < board.length; i++) {
if (board[i].isEmpty) {
board[i] = 'X';
var score = minimax(board, depth + 1, true);
board[i] = '';
if (score < bestScore) {
bestScore = score;
}
}
}
return bestScore;
}
}
Tech Stack Used:
Credits:
