Overview

Connect 4 is one of the classic games that every one has played many a time. This game is a stepping stone to get some Artificial Intelligence (AI) programming into all of my future games.

Features of the game include a tally of games won, lost and drawn for the current session, highlight of where the computer moved. Flashing counters to show the winning lines. Undo moves right back to the beginning of the game except when a player has won. Change the computer difficulty during a game.

Objective

Take it in turns to insert your pieces into the board. The aim of the game is to become the first player to get four of your pieces in a row. Either vertically, horizontally or diagonally. If there are no slots free, then the game becomes a draw and a re-match is in order.

AI

There are three levels of AI used in the game. There is a random player to start of easy, then there is a normal player which uses heuristics and lastly a hard player which uses the minimax search algorithm.

Heuristics - Normal Level

The heuristics is used in conjunction with influence maps and are basically rules to score a move, the higher the value the better the move. The process is broken down into the following:

1. Work out all of the possible moves
2. For each move use the heuristics to score it and store the result in the influence map
3. Search the influence map for the highest score i.e. best move, if there are moves with the same score then choose one at random

The heuristics used are:

1. Player 1: Connect 4; return very big number
2. Player 1: Check for possibility of connect 4; return number based on the number of counters in row and the number possible
3. Player 1: Ignore everything else
4. Player 2: Check for the same things above - i.e. look for ways of blocking the opponent.
5. Player 2: Player 1 to make a move and player 2 to check the above again - i.e. check that we aren't giving away connect 4

Minimax - Hard Level

The minimax search algorithm basically plays a set number (called the ply) of moves into the future. All possible moves are evaluated before the computer decides on which move to make. The computer plays moves for both sides, until it has found a winning move or played enough moves into the future. The board is then evaluated for the position in terms of the opponent which went first. Then at each level the player whose turn it is looks at the scores for each move and decides on the best move to make. If it is the computer to choose then it will choose the move which produces the best score, if it is the opponent to choose then they will choose the best move for them. Or if you think of it from the computer perspective the score with the lowest value because they want to win.

The following is used to score the board when enough moves have been made.

1. Computer: Search the board and list the number of lines with connect 4, 3 in a row, 2 in a row, 1 in a row only include those which have the possibility of getting connect4
2. Opponent: Repeat the above from their perspective
3. Both: Score the number of lines as follows: connect 4 + Infinite + 3 in a row * 20 + 2 in a row * 5 + 1 in a row
4. Computer Score - Opponent Score (The score for the board is always in terms of the computer)