Tic-Tac-Toe You can never beat.

Using the mini-max algorithm, I was able to create a game of tic-tac-toe in java and swing that you can never beat.

Blank Game Board.
I make a move in the top right (old pro TTT trick) and the ai makes the most optimal move.
Following up with a move in the bottom-left (again TTT pro here) the ai forces the path towards a tied game.

I used a pretty common OOP process that one of the best professors in the world, Prof. David North (O.C.) wanted everyone in my class to understand.

  • Ask how you can separate out concerns i.e. UI from actual functionality (keeps with the SOLID model).
  • Draw out a conception of the problem by thinking on the basic functionality at each step of the game, tasks, etc.
  • Pretend like you have already solved the problem.
    • This step was the hardest to understand. It is a rare way of working backwards, which helps you get out of your head / code. It really can make a difference.
    • This step also is quite literal for plotting the AI’s next move as I had to generate a Tree of every win / tie which is the desired outcome / solved problem of the program.
  • Use George P├│lya’s four principles.

Following these I worked on getting the Player, AI, Board, Tree, and Game Manager classes of the project planned out. I implemented each of them starting with the Board, moving backwards to Player, GM, and Move Tree. I then went to work on making the AI use the Move Tree and the Mini-Max algorithm to always beat / tie the player.

This was the hardest part. I had everything done within 30 minutes to an hour of starting the project, except Move Tree and Mini-Max. It took me a few days and supervised instructions to get the AI to pick the best move every turn it played. I was so frustrated that I started the UI just to stop working on this part of the problem as a 10 minute break. I should have asked for help to start with, it would have saved some time. I definitely do not want to make that mistake again.

Even keeping the frustration in mind, the project was fun and I am ecstatic that I have been dethroned as TTT master by my own pupil.

Leave a Reply

Your email address will not be published. Required fields are marked *