## Friday, September 27, 2013

### An exercise in adversarial search applied to the game of Connect Four

Introduction:
As part of an AI course I took last year, I was tasked with examining adversarial search by developing a Connect 4 game that utilized minmax search.  While minmax search is optimal given enough time and memory to perform its calculations, in a practical sense the method must be refined to become useful for real world applications.  By stipulating a max search depth, ordering potential moves in order of most to least useful, and the use of alpha-beta pruning, a search algorithm is achieved that can consistently beat human players while taking less than 30 seconds per turn.

Implementation:
My game was written in C# using the XNA game framework to handle the graphics and user input.  It is playable by one or two players.  To represent a game state, I created a GameState class.  A board position is stored as an array of lists.  Each list can store an enum value corresponding to which player controls that cell.

Adversarial search is a subclass of search algorithms that attempt to maximize the utility of one player’s state while minimizing that of the other player.  This type of search can be easily visualized as a chess game where one player tries to find a board position that maximizes their benefit while reducing the usefulness of their opponent’s position.

Algorithm:

Minmax:
The type of adversarial search used in this project is minmax search.  The idea is that for a given state, the search space of possible next moves can be explored and the move that maximizes utility for a player and minimizes it for their opponent is chosen.
 Minmax Search Tree

In the tree pictured above, the first node is a max level.  This means that player will pick the available move that maximizes their utility.  Utility is an estimate of the strength of a given state (board position).  The min level node represents the opponent choosing a move that minimizes their opponent’s utility.  You can then see how 5 is first chosen because it is the lowest value at the bottom level, and then the highest value at the middle level.

 Minmax Algorithm Pseudocode Given enough time and memory, the algorithm will search every possible move from the given board position.  For some less complex games such as tic-tac-toe or checkers, assuming that a perfect game is played, it is possible to search the entire game tree and determine the outcome based on the first move.  In these cases, the game is said to be “solved.”

Alpha-Beta Pruning:
In theory, being able to search every possible move from a given state and return the optimal one is great for making a computer play a game well.  However, even for a game with a small branching factor such as Connect 4, the time and space required for this complete search is prohibitive.  One way to improve the performance of the minmax search is to include alpha beta pruning.
Alpha-beta pruning is a method for avoiding the searching states that can’t affect the outcome of the chosen returned state.  During a search, some states may be explored that have values that guarantee them to not be relevant by either being larger than an already found minimum value or smaller than a discovered maximum value.  The image below illustrates alpha-beta pruning.
 Minmax Tree With Alpha-Beta Pruning

Pseudocode for Minmax search with Alpha-Beta Pruning

Alpha-beta pruning only increases the performance if the best moves are searched first so subsequent moves can be pruned.
Because of this, move ordering is important to the performance of alpha-beta pruning.
Move Ordering:
If moves are explored in the worst case order, meaning that the least beneficial moves are explored first, the complexity of minmax with alpha-beta pruning is still doesn't improve from O(b^d).  With random move ordering, the complexity is reduced to O(b^(3d/4)) and if moves are ordered optimally, the complexity is reduced further to O(b^(d/2)).  With optimal move ordering, the search can explore twice as deep with the same amount of computation.
In my implementation moves are ordered from the center outwards.  Column 4 is explored first followed by columns 3,5,2,6,1, and 7.  The idea behind this ordering is that placing a piece in the middle is generally a better move than along the side.

## Deepening the search:

The more moves ahead the computer can look the better it should play.  It’s already been shown that the maximum search depth can be deepened by using alpha-beta pruning with an optimal move ordering.  There are other methods that can be used to efficiently increase the search depth including:
·      Selective evaluation- searching deeper for moves that look more promising.  If a particular move causes a large change in the utility of a branch, it can be explored to a deep depth to see if those increases continue.
·      Forward pruning- pruning branches that appear useless.  This could be done by only exploring the 3 child states with the highest value.
·      As the branching factor decreases, the amount of work needed to search to the max depth also decreases.  Therefore, the max depth can then be increased to search deeper into the remaining tree.  In my implementation, the max depth is increased by 1 each time the branching factor decreases by 1.

While searching deeper can be beneficial, selective evaluation and forward pruning introduce problems of their own.  By only exploring certain branches, or by cutting ones that appear useless, the search is no longer optimal.  It new becomes possible that the search could prune a branch that eventually led to the optimal solution.  It then becomes necessary to weigh the benefits of increased depth and shorter search time against the drawback of potentially missing the optimal solution.

## Evaluation function:

When a terminal node or the max depth is reached, the utility of the state must be evaluated so the algorithm can make a determination on whether that state is valuable or not.  This utility value is returned from an evaluation function.  The values returned from this function can have a large impact on the overall performance of the search.
The evaluation function for my implementation returns a 4 part weighted sum for each board position.

Each of the variables represents the number of unblocked sequences of contiguous pieces of the player’s color.  In this case, unblocked means there is either an empty space at the beginning or the end of connected pieces.

This board position would represent 1 unblocked vertical set of 3, 3 horizontal sets of 1, 3 upward diagonal sets of 1, and 2 downward diagonal sets of 1.

In this board position, the red player has 2 down diagonal sets of 3, 1 horizontal set of 3, 1 horizontal set of 2, 2 horizontal sets of 1, 2 upward diagonal sets of 2, and 2 upward diagonal sets of 1.

## Behavior and performance

My implementation plays well.  Obvious moves by the user are consistently blocked.  After approximately 15 games played by myself and other users, the computer won each time.  Due to the nature of minmax search, the computer doesn’t always take the immediate win, but it always wins when it can.
The behavior did not begin to approximate what I would consider realistic behavior until my evaluation function became more detailed.  By searching for just wins, or a small subset of contiguous rows, it was easy to exploit weaknesses in the computer behavior and win often.  Wins were rarely blocked until my full evaluation function was implemented with the current weights.  Initially, a four in a row was weighted with 1,000 rather than 10,000.  With this weight, winning moves would not always be blocked and the computer wouldn’t take move obvious wins.
The default depth for the search is 7.  This increases as the branching factor decreases.  With this depth, the average time for the computer’s turn is 19 seconds.  A depth of 8 returned a move in an average of 39 seconds in testing.  I ordered my moves to help maximize the benefit of the alpha-beta pruning.

Below are several output images from playing the game.

 Very basic menu to choose the currently running mode

 Board after several turns by each player.

 At this point, the AI can win in several ways.

 Finally, the AI takes one of its winning options