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.
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.
