Yellow: AI | Red: Me
- Language of implementation: Python
- Libraries: Pygame, Numpy, Random, Math
- Algorithms: Minimax, Alpha Beta Pruning
Through games with easy rules, we can model real life problems and find partial solutions with the help of AI. That's why I've looked into games to model and built an AI to play against.
Connect4 is a game that has easy rules and is simply implementable with a 2D array, so I decided to give it a try.
Being an introductry Python project for me, it took some time to implement it. By curiosity, I also tried to create a nice visualization through the library pygame. It was a lot of fun, but the interesting part was still ahead: the AI.
I then looked for algorithms that would work well as an AI. The first AI I built was a random one (yay), but that wasn't enough. And then I found an algorithm called Minimax, which implements forward thinking. Having played chess for 3 years now, I saw that this is exactly the way people think during a game, but simply implemented in code. I found that fascinating!
Connect4 like Chess for instance is a zero-sum game. A zero-sum game is a mathematical representation of a game where the gain or loss of one participant leads to an exactly balanced loss or gain for the other participant. It is called this way because if both participants add up they gains and deduce their losses, it would sum up to zero.
Having that in mind, the Minimax algorithm is perfectly suitable. Firstly, a scoring function for each state of the board was necessary. Online Connect4 players gave me some ideas how to score those states.
The pseudocode on the wikipedia page and the scoring function made it possible to implement it, but I couldn't predict more than 4 moves ahead without overloading computer.
That's why I also implemented Alpha Beta Pruning. This algorithm uses the idea of minimax to prune away parts of the search tree that are not necessary to explore. In short, we add 2 values to the minimax algorithm: alpha and beta. Alpha being used to keep the maxima of a maximizing subtree and beta the minima of a minimizing subtree. Comparing if beta is lower than alpha at each recursive call of the function permits us to prune those subtrees. If this condition holds, the participant would have had a better option earlier already.
I'm open to any optimizing suggestions and new ideas! 🚀