This AI/Web Development project features an interactive interface of the well-known board game Connect Four. This classical example shows how easily AI algorithms reach a super-human performance in game playing. And by now, much harder games have been solved!
Try it out yourself and beat the AI or a friend!
About Connect Four
Connect Four is a board game first published by Hasbro in the 70s. The player who first manages to connect four of his chips horizontally, vertically, or diagonally wins the game.
From a computational point of view, we face a fully observable and discrete game state, making the task suited for analytical algorithms as the minimax search used here. Though at first sight, the game might seem simple, the state space grows quickly with the number of future moves considered. In total there are 4,531,985,219,092 attainable states. Nevertheless, it has been proven that with optimal play, the player beginning can force a win if he places his very first chip in the central column. To make sure it remains possible to beat the AI, the player is always granted the first move.
How the AI works
The AI player uses an analytical minimax tree search to determine the best moves up to a certain lookahead. This basically means enumerating all possible successor states and determining how desirable they are. Although the search space is limited by means of alpha-beta-pruning, it is impossible to simulate the whole game (at least in a second of time). A cache stores computed values for states that were already visited. After a certain number of moves in the future, an evaluation function estimates how useful the state obtained would be for the AI. A neural network trained on states, whose value was computed in advance is used as an evaluator.
The difficulty selected determines the lookahead. When selecting easy, good, and hard, the respective lookaheads are 1, 2, and 10 moves respectively (with 10 being the maximum possible in approx. one second on the hardware).
Implementation
This is a true full-stack project. While the front-end logic is written in JavaScript, the animation only relies on CSS transformations and flex containers while the Bootstrap layout ensures accessibility on phones and tablets. The AI runs on the server side and is written in C++ for maximum computational speed. Neural networks used in the AI were trained with TensorFlow
Acknowledgements
Thanks to my colleague Lukas Werner for showing me some tricks with animations and stacking in CSS and to Google Colab for providing the resources necessary to train the neural network that is used as evaluation function.
