26. October 2017

Memories from University: Teaching the Computer to play Connect Four

How do you teach a computer to play games? I took a classic brute-force approach along with some techniques to make the search for a good move faster. Can you beat the machine?

Several years back, in 2009, I took a seminar course in Artificial Intelligence (no, the course wasn’t about building machines that take over the world, we have Terminator movies for such entertainment). I cannot remember how I chose the topic, I assume I picked it from a list provided by the supervisors. But in any case, I learnt about adversarial search in zero-sum games.

A zero-sum game a game where your gain is equal to your opponent’s loss. Many two-player board games fall into this category: among them classic games such as Chess, Go, and also somewhat simpler games such as Connect Four. So I chose to program a computer to play Connect Four:

Play Connect 4 against the machine here!

Did you win? Did you draw? Or did you lose? In theory, Connect Four on the 7×6 board is a solved game (see here for details): i.e. we know for example that the player who starts can always win if playing correctly. So how does the computer select its move? Hint: the computer is not playing Connect Four as The Turk is playing chess…

There are several ways to program a computer to play games. Very recently, with use of Neural Networks, DeepMind has famously won games at Go against the best human players on the planet. But for my program playing the much simpler Connect Four game, I chose a brute-force approach, just making the machine search as efficiently through all possible moves, looking ahead in the game as much as it can within (the arbitrary) limit of a second. But within that second, the program will look at about a million possible board positions on a personal computer from 2009.

  1. Presentation (in German)
  2. Seminar paper (in German)
  3. Source code (in C)