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. ).
