Alpha-Beta Pruning

Another page I made to play with is a Tic-Tac-Toe game.

Originally, I just used the MiniMax algorithm for the player. The game is a small one, and MiniMax can solve the complete game pretty quickly.

On my very old phone, though, there was a noticeable delay if the game searched the whole way to the end from the first move.

So, I converted MiniMax to Alpha-Beta. I always manage to mess that up on the first try, but eventually got it working. For a game like this, the result is still amazing. With MiniMax, the first move required about 550,000 searches to get an answer. With Alpha-Beta, that is down to less than 20,000.

And now it works fine on my phone.