Abstract for Heuristic Connect4 player with Alpha Beta Pruning
Project by: Lan Vu & Ali Anvari, Fall 2000

Introduction

The purpose of this project was to implement a video game version of Connect-4. Connect-4 is a two-player game in which one player is designated 'Red' and the other is designated 'Blue'. Each player has a stack of chips of his/her color. A 7x7 vertical board is placed between the two players. This board has seven 'slots' at the top of it, one slot for each column. When a game chip is dropped into one of these slots, it slides down until it either rests at the bottom of the board or on top of another chip. The two players take turns dropping a chip into a slot of their choice. The first player to connect four of his/her color in a row is the winner. This connection can be vertical, horizontal or diagonal, but it must lie in a straight line and must be connected.

To be an effective game, the computerized player needs to make moves in a timely manner such that the human player would not get bored. Due to this constraint, it is impossible for the computerized player to do an exhaustive search of all possible moves and pick the best one; so that the game would respond quickly enough the players was restricted to looking only four moves ahead.

Hence it was necessary to devise a heuristic function so the computer could reasonably accurately guess at the utility of a board state (and consequently a game move) and not have to think ahead to all possible ways a game could end from that position.

Heuristic

The chosen heuristic function was essentially a static linear weighting function based on material: Value = My material - Opponent's material, where the material is a count of all the contiguous lines of pieces that a player has, weighted thus: 0.1 points for 1-in-a-row, 0.3 for 2-in-a-row and 0.9 for 3-in-a-row.

The count of these contiguous lines only took into account open positions where more pieces can be placed, because a piece that is surrounded and sealed off by opposing pieces can play no further part in the game. The weightings are program variables that can be modified; we chose exponentially increasing weight values to make the program go for longer lines and launch 2-way attacks by placing its pieces where they would form more such lines.

Strategy

The Connect4 player looks ahead to see what are all the possible reactions to each move it plays. It assumes that the opposing player will thwart it where possible, so it plays a conservative game trying to maximize its minimum return. This technique is known as Maximin.

Pruning

It is possible to make the game even faster by not considering certain moves. That is, if the computer looks ahead from one possible response to a proposed move and sees that the opponent can gain if the computer plays that move, the computer need not examine the other possible responses that the opponent might make. The proposed move is already known to be a bad move; Assuming that the opponent is intelligent enough to pick the best move available to him, the computer knows that he will only play an alternative response if that is superior, which would make the board situation even worse for the computer. So the computer stops processing this possibility and starts considering other moves instead, instead of looking at all possible consequences of a doomed move. This method of saving time by disregarding possible moves is called pruning; the method used for this project, which assumes Maximin, is called Alpha-Beta pruning.

Von-Volatility ("Quiescence") Check

The problem with the heuristic is that it's no guarantee; if the Connect4 player sees ahead four moves to a volatile board situation, the heuristic may indicate that this is a good situation whereas there may be a forced defeat on the fifth move. So the computer might pick the losing move because it couldn't see quite far enough ahead. As an extra precaution to guard against this, the Connect4 player checks for possible forced winning or losing board positions a couple of moves beyond the cutoff boundary. This is a limited form of check to ensure non-volatility.

Performance

The Connect4 player is by no means infallible, but it has a good heuristic, which when used with pruning, has reasonable response times and plays well against casual human opponents (it almost always beats its creators!).