AlphaConnect Four: Combining Deep Neural Networks and Tree Search to Play Connect Four

With computational power increasing rapidly, more and more games such as Kalah (2000) and Checkers (2007) are becoming solvable through the traversal of the entire game tree. However, despite these progressions in processing capabilities, many games remain unsolvable. These games remain unsolvable, because unlike Kalah and Checkers, they have game trees and state spaces so large they exceed existing computing power for traversal. However, the modern inability to programmatically consider large state spaces has led to the creation of many exciting algorithms such as Minimax with Alpha-Beta Pruning, and Monte Carlo tree search. These new algorithms approximate a solution rather than traversing an entire game tree to consider all possible move combinations.

While these game approximating algorithms are never right one hundred percent of the time, humans have learned a great deal about playing complex games expertly by studying these algorithms’ decisions. Despite the aforementioned algorithmic innovations, board games such as Go continue to remain intractable to traditional search-based methods. The alleged insolvability of Go led Google’s DeepMind to invent a new algorithm, AlphaGo. In October 2015, Google’s DeepMind and its AlphaGo program shocked the world by playing its first match against the reigning three-time European Go champion, Fan Hui, and winning 5-0. Since creating AlphaGo, DeepMind has worked to generalize the AlphaGo algorithm to play a wider variety of board games at an expert level by creating the AlphaGo Zero, AlphaZero, and MuZero protocols. While these algorithms have been tested extensively on games with large state spaces, they remain untested on games with smaller game trees. This paper will explore the Alpha Zero protocol’s ability to optimally play Connect Four and will test the algorithm’s efficacy for small state space games.

• final report (including deliverables)
• proposal
• code files