We are going to implement the Game of Connect Four as our term project. We chose this game since it has relatively smaller search trees compared to other games, so that we will be able to finish it on time. However, the search tree is still very large. In our term project, we will first do some researches on different algorithms, compare the running time and the cost among them. Finally, we will pick the most feasible algorithm to implement the game.
Connect Four is a two-player game using a seven by six (seven columns and six rows) rack. The objective of the game is to connect four tokens with the same color horizontally, vertically or diagonally.
Each player alternate to drop a token of their own color into a column from the top of the rack, then it will fall in the lowest non-occupied entry. The players will continue to switch turn to drop the tokens, and for each turn, the player has at most 7 choices of entry point to choose from. The game will end in a state either one-player gets four tokens on a row or when the rack is full.
Basically, the game involves a large number of possible moves for the players. The opponent’s moves are not always predictable, so it is necessary to find the best and most efficiency way to estimate the opponent’s next move. Since, the search space can be extremely huge, it is impractical to go through the entire search space to find the best move. Thus, trying to minimize the total number of searches is a must. The informed search methods use a heuristic function to help searching the state space in order to discard the inefficient or that do not lead to a solution quickly. There are two common searching techniques that we have considered: the Best First Search Heuristic (A* Search) and the MiniMax with Alpha Beta Pruning.
A* is a search technique that seeks the minimal cost solutions and is also directed towards the goal states. Basically, A* is a common search technique derived from Breadth-First Search.
The A* search is based on the heuristic evaluation function, f(n) = g(n) + h(n), where g(n) is the actual cost from the start node to n which is the breadth-first search component to the evaluation function, and h(n) is the estimated cost from node n to one of the goal. The function of h(n) also serve as a n indicator to indicate if the path is workable or not.
In order to achieve an admissible heuristic, h(n) must be simple so that it can search in uniform-cost through parts of the search space.
One of the properties of a good heuristic is to compute in a short period of time. Since if it takes too long to compute a single node, it may have been more preferable to have just expanded more nodes using a cheaper heuristic. A good heuristic can reduce the complexity of the original problem so that it is simpler to solve. It can also allow successive nodes on a single path to be expanded in succession even when good and bad steps mixed up.
Using the Best-First search, the estimated distance to the goal would be used with the heuristic value of a state. In A*, we need to add the estimated value of the remaining cost to the actual cost needed to reach the current state from the goal. The A* search technique combines being leaded by knowledge about where good solutions might be and the knowledge is incorporated into the estimate function, while at the same time keeping track of what is the total cost of the solution.
A* search is derived from the Best First Search technique. However, the main drawback of any Best First Search technique is that the need of memory is proportional to the size of the search space that has already been explored. Also, A* often suffers since it cannot explore down a single path unless it is almost continuously having success, for example, when h(n) is decreasing, the search will switch immediately to another path if it fails to decrease h(n).
In conclusion, A* is a complete and optimal search technique that searches for the result in a speedy manner.
First, we pick the start node S on the nodes list, called
OPEN. Then we check if OPEN is empty, if so we will exit. Next, we remove from OPEN and place on
CLOSED a node n for which the function of n is minimum. After that, we will have a loop that says,
first if n is a goal node, then exit and trace back pointers from n to S. Second, expand n and generate all its
successors and attach to them pointers back to n. For each successor n' of n we will have 2 cases again. If n' is not already on OPEN or CLOSED, then
we have to estimate h(n'), g(n')=g(n)+ c(n,n'), f(n')=g(n')+h(n'), and place it
on OPEN. And if n' is already on OPEN
or CLOSED, then check if g(n') is lower for the new version of n'. If it is, then redirect pointers backward
from n' along path yielding lower g(n') and put n' on OPEN.
Finally if g(n') is not lower for the new version, do nothing. At last we check for OPEN and see if it is empty. If so, we will exit and so on.
The main idea behind the algorithm is that the nodes are expanded according to the priority that is the selected heuristic function. The g(n') function of the expanded node are placed into the priority queue.
Fig 1 An example of the edge cost tree of our connect four game.
Fig 2 An example of the estimate cost h(n) tree of our connect four game.
n g(n) h(n) f(n)
S 0 60 60
A 1 34 35
B 3 30 33
G 8 1+34+x 0 (where x is the total cost of all the paths to goal node.)
MiniMax search that makes moves by first generating the whole game tree is used in the basic game playing. By viewing the MiniMax tree, a player may be able to foresee which moves are more considerable and beneficial for in terms of winning. The root of the tree represents the starting position of the current player. Thus, depending on the number of levels that is to be searched, all odd levels represent the first player while the even levels represent the second player.
In a two-player game, the first player moves with max score and the second player moves with min score. A MiniMax search is used to determine all possible continuations of the game up to a desired level. A score is originally assigned to the leaf. Then by evaluating each possible set of moves, a score is assigned to the upper level by the MiniMax algorithm. The MiniMax algorithm performs a pre-order traversal and computes the scores on the fly. The same would be obtained by a simple recursive algorithm
Under the MINIMAX strategies, pruning is the most common one that making moves by generating only a portion of the whole game tree. It reduces the time required for the search so no time is wasted searching for moves that are obviously inconsiderable for the current player. The exact implementation of alpha-beta keeps track of the best move for each side as it moves throughout the tree. We proceed in the same (pre-order) way as for the MiniMax algorithm. For the min nodes (β), the score computed starts with + ∞ and decreases with time. For max nodes (α), scores computed starts with - ∞ and increase with time. The efficiency of the Alpha-Beta procedure depends on the order in which successors of a node are examined. If we were lucky, at a β node we would always consider the nodes in order from low to high score and at a α node the nodes in order from high to low score.
When maximizing, expand no node once a node whose evaluation is lower than α has been seen. Also, when minimizing, expand no node once whose evaluation is greater than the β has been seen.
An alpha-beta algorithm consists of two functions: min and max that are used to evaluate the min node and the max node respectively.
Function: Min(minnode, B)
Α ß + ∞
Repeat for all the children
Value ß max(maxnode, B)
A=minimum of A and Value
If A <= B
Exit this loop
Function: Max(maxnode, B)
A ß - ∞
Repeat for all the children
Value ß min(minnode, B)
A=maximum of A and Value
If A <= B
Exit this loop
Fig 3 An example of the Alpha Beta Pruning search tree
In fact, the effectiveness depends on the order of the node generation. If a good move is tried first, then more pruning is needed. Also, if a bad move is tried first, then less pruning is necessary. It has proved that Connect Four is possible for the first player to always win. Since MiniMax Alpha Beta Pruning is a better searching technique over the A*, so we have decided to use it to implement our Game of Connect Four.
Later, we have improved our medium fidelity prototype. Here is our high fidelity prototype done using graphics in a more realistic sense. Now, it is more attractive and colorful. The main idea is still based on the Connect Four Game.
The two players can place their own token in the preferred column in their turn until one of them can get four tokens of the same colors in a row or until the rack is full.
Right now, what we have done so far is choosing the search technique and the programming language we will use for this project. After doing some researches on different algorithms, we found that MiniMax search technique is the best one, and we will try to implement the game using it. For the programming language, we think that Java is a suitable language for us to use in a efficient way, so we pick Java Applets.
Next, we have also designed an interface for our program with the screenshot available in this report along with some degree of description.
Finally, we have been started implementing the program by starting to write the pseudo code for Connect Four game. As mentioned above, we are going to implement it using the MiniMax strategy.
Generally, the main goal of this project is to implement the Connect Four Game. Therefore, searching technique is the most important. By eliminating the huge number of moves, the search of the game is made more efficient. So choosing which searching technique is our main problem that we have come across. Although we have chosen the informed search method, several other searching techniques are similar in this category. Thus, it is not an easy job to choose the most suitable one.
Firstly, we all did some researches about both Best First Heuristic Search (A*) and the MiniMax Alpha Beta Search. Then, we tried to compare the advantages and disadvantages between them. In fact, both are so similar so we cannot make our decision easily. Luckily, we found that MiniMax Alpha Beta Search is better than the A* because it can make the Connect Four Game be more efficiency by eliminating a number of moves that maybe unreachable. Then, it can speed up the game by reducing the time for the players who might need to take a possibly long time to decide where the next token should be placed.
On the other hand, we also struggled with the design of the user interface because it is the first impression for the players. If it is not user-friendly, the players may not want to play it anymore. Also, if it is more attractive, the players can really enjoy playing it.
Although the first simple low fidelity prototype includes the basic function for the game, it is not user-friendly enough. After the evolution, we made it in a more user-friendly type. We added some attractive graphics in order to let the players feel more realistic. However, it is still not quite perfect, so in the implementation, there is a chance that we may change it later.
Here are the things that we need to do in this month to finish the term project.
First of all, we have to implementing the Connect Four game. We assumed that we can finish it within two weeks of time.
Then, we can spend approximately a week to do testing and debugging to make sure that the program will work properly in any situations.
After that, we have to write the user manual in the next two days. The user manual will include some instructions of how to play the game, what are the buttons for, how to start the game, how to drop the token and how to quit the game, etc.
In the next two to three days, we have to prepare for the final presentation. We need to prepare a short demonstration of our program, how it works and runs, as well as separating the workload.
Finally, we need to finish the final report and the web page in a week. This final report will include the summary of what do we learn, what we did, how do we achieve our goal, what kind of problems we encountered and how can we improve our term project, etc. And we will post all the reports and the program on the website.
Actually, from the beginning of this term, we did a lot of researches on the searching techniques. Now, we have decided to use the MiniMax Alpha Beta Search to implement the Connect Four Game after comparing different aspects. Then, we will start to implement pretty soon and we will follow our schedule tightly as well. Hopefully, we can implement this Connect Four Game as perfect as possible and hold a wonderful presentation at the end of the term.
1. Best First Heuristic Search (A*): a search technique that seeks the minimal cost solutions and is also directed towards goal states
2. MiniMax Alpha Beta Search: a search technique that minimizes the number of nodes that are possibly unreachable in order to speed up the search