Note: I have not completely tested this implementation on the hardest cases yet, so it may not be fully functional. I will update this README once I have tested it thoroughly.
Connect Four is a two-player game where the players take turns dropping colored discs into a 7x6 grid. The first player to get four of their discs in a row (either vertically, horizontally, or diagonally) is the winner. The game ends when the board is full or the players run out of discs, at which point the game is a draw (1). It is also a strongly solved perfect information strategy game: first player has a winning strategy whatever his opponent plays (2).
This projects aims to implement a Connect Four solver in Java. Then, it will be tested against some common test cases and eventually be used to play against a real opponent.
I have previously done this project using a simple Minimax algorithm, but I have decided to implement a Negamax algorithm with alpha-beta pruning. To improve performance, I have also added move ordering, killer and history heuristics, and a transposition table to store and retrieve previously computed results for a given position.
The solver should be able to solve a given board in a reasonable amount of time: with every move, the solver should be able to determine whether it is winning or losing.
- If it is winning, it should return a winning move for itself.
- If it is losing, it should block the opponent from winning if there is a winning move available for the opponent.
I would like to thank @PascalPons for his tutorial on the perfect Connect Four Solver: it was a great help to understand how the algorithm should be implemented. Additionally, many thanks to Nick Drohan and Rishab Nayak for guiding me through this and providing assistance - you guys are amazing.