"min-max-tic-tacs" is a simple, yet annoying game of Tic-Tac-Toe.
✨ Playing this game will activate close-to-zero dopamine receptors. ✨
My game contains three primary modules: gameField
, gameController
, and displayController
.
What are advantages of the module pattern? Modules provide code encapsulation and prevent global namespace pollution.
In other words, modules can prevent spaghetti code! They allow me to organize my code by keeping the front-end isolated from the back-end. This makes the code easier to read and maintain. I can still return functions and variables between modules as needed.
Modules can also provide security through obscurity. It would be somewhat difficult to modify the game logic from the console. To be fair, my game isn't a high value target for attackers, but dynamic web apps certainly are. It's best to incorporate security as early as possible in the Software Development Life Cycle, even if it's just an extra layer of abstraction.
gameController
contains a sub-module minimaxLogic
, which implements the famous Minimax algorithm from zero-sum game theory.
Theoretically, Minimax can simulate all 362,880 game states of Tic-Tac-Toe. This is made possible by recursion! By the time you've made your second move, Minimax will have calculated all possible outcomes of the current game.
In 1997, GM Garry Kasparov was defeated by IBM's supercomputer, named "Deep Blue".
Deep Blue's secret weapon? You guessed it:
Minimax!
In Tic-Tac-Toe, the game tree can be visualized like this:
An expected loss is worth -10 points. An expected win is worth +10 points. An expected draw is worth 0 points. These are known as "terminal states". Terminal states are essentially the AI's plan to steal your dopamine.
For the efficiency police, time complexity is O(bm), but this implementation only looks at empty squares as the game progresses. Branches of the game tree are ignored if they're irrelevant to the current game state. This is also known as "pruning".
When implemented correctly, it's impossible to win against Minimax. It will nullify every single one of your moves. If you leave an opening, it won't hesitate to win against you.
Dont, worry. We, too, can prevent Minimax from winning. That way, neither of you get to have fun.
Thanks for reading. I had a blast while making this project. It helped me reinforce my understanding of data structures and algorithms.
Huge thanks to The Odin Project, GeeksforGeeks, NeverStopBuilding, and FreeCodeCamp for helping me understand Minimax!
Also, Deep Blue did not only use Minimax against Garry Kasparov. It also used alpha-beta pruning (along with other techniques) to scrape by, because processing power was limited compared to today's standards.