The Progression Report
The Game of Connect Four

1.0      Introduction. 1

2.0      Searching Techniques. 1

2.1      Best First Search Heuristic (A* Search) 2

2.1.1 Algorithm.. 3

2.1.2.1     Example of our term project 4

2.1.2.2     Example of our term project (cont.) 5

2.1.3        Example of g(n), h(n), f(n) = g(n) + h(n) 5

2.2      MiniMax with Alpha-Beta Pruning. 6

2.2.1 Algorithm.. 6

2.2.1.2     Example. 8

3.0      User Interface. 9

3.1.1        Medium Fidelity Prototype. 9

3.1.2        High Fidelity Prototype. 10

4.0      Time Management 10

5.0      Problems Encountered and Possible Solutions. 11

5.1.1        Decision of the Searching Technique. 11

5.1.2        Design of the User Interface. 11

6.0      Schedule. 12

7.0      Conclusion. 12

8.0      Glossary. 12

1.0   Introduction

 

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.

 

2.0   Searching Techniques

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.

 

2.1    Best First Search Heuristic (A* Search)

 

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.

 

2.1.1 Algorithm

 

 

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.


 

2.1.2.1       Example of our term project

 

Fig 1 An example of the edge cost tree of our connect four game.

 


2.1.2.2       Example of our term project (cont.)

 

 

Fig 2 An example of the estimate cost h(n) tree of our connect four game.

 

2.1.3 Example of g(n), h(n), f(n) = g(n) + h(n)

 

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

 

2.2    MiniMax with Alpha-Beta Pruning

 

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.

 

2.2.1 Algorithm

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.

2.2.1.1 Pseudo code:

Function: Min(minnode, B)

Α ß + ∞

If minnode=leaf

            Return score

Else

            Repeat for all the children

            Value ß max(maxnode, B)

            A=minimum of A and Value

            If A <= B

            Exit this loop

 

Return A

 

Function: Max(maxnode, B)

A ß - ∞

If maxnode=leaf

            Return score

Else

            Repeat for all the children

            Value ß min(minnode, B)

            A=maximum of A and Value

            If A <= B

            Exit this loop

 

Return A


2.2.1.2                   Example

 

 

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.


 

3.0         User Interface

3.1.1 Medium Fidelity Prototype


 

 


This is the medium fidelity prototype of the main interface that we decided for the first time.  It is a seven by six table that represents the Connect Four Game.  The one to seven buttons are used for representing which column that the players want to place his/her next token by clicking on them.  It also shows whose turn (player or computer) at the bottom.


3.1.2   High Fidelity Prototype

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.

 

4.0   Time Management

 

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.

 

5.0   Problems Encountered and Possible Solutions

 

5.1.1 Decision of the Searching Technique

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.

 

 

5.1.2 Design of the User Interface

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.

 

6.0   Schedule

 

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.

 

7.0   Conclusion

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.

 

 

8.0   Glossary

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