## The Connect 4 Game

Download
the program

**Connect 4**
has been developed for Windows Platform with Borland C++ Builder. The GUI is
intuitive You have to arrange 4 balls of the same color in a row , either
horizontal, vertical or diagonal. The computer competes against you to achieve
the same.

The algorithm
used in developing this game is the Artificial Intelligence Algorithm called
MINMAX algorithm which works by creating a game tree for a particular situation
and then evaluating the best possible next move.

**The Algorithm
works like this :**

To each board
configuration, we assign a score which tells about the goodness which the the
player is in ( how good is he faring at the moment ).

A high score
indicates that player is doing well and vice versa. This score can be easily
evaluated by comparing the current configuration with the known winning
configurations and how close is the current configuration to winning.

Now once the
scoring strategy is decided, to decide the next move from a given situation, a
recursive game tree is generated which evaluates all possible moves and selects
the best one. This is done by simulating a sequence of moves and assuming that
the opponent is intelligent and always chooses the best possible move, a larger
number of combinations are tried out and combined with the scoring strategy, the
best move is chosen.

This is the
basic working of the MINMAX algorithm.

This above
algorithm is exhaustive hence to improve the efficiency, a pruning technique is
used which shortens the game tree significantly and decreases the computer
response time. If a particular path’s score is worse than an already known one,
that path is abandoned and the tree is pruned. This reduces the running time
drastically.

If number of
columns is x, then without pruning the recursion may branch x^z times where z is
the number of empty slots. However by pruning the algo runs very fast. In the
given program , it usually responds in less than 1 second on average size games
( 7 x 6 etc. ).