Lab 8

This lab builds on Lab 7.

In lab 7, you wrote the classes Model, View and Controller. Together these classes formed the basis of the game Connect 4. In this lab, you are asked to make the computer smarter by adding some artificial intelligence. How this can be done is described in detail below.

In the original Model, the computer used the move method to select the column in which to drop a coin. This move method randomly selected a column that was not filled completely yet. The focus of this assignment is to make the choice of the column more sophisticated. As a result, the game becomes more interesting.

To find the "best" column, one can build a tree containing all the possible boards that are reachable from the current board. If it is the computer's turn, the root of this tree would represent the current board. Its children would represent the boards resulting from the computer dropping a coin in a column that is not completely filled. Hence, the root has at most seven children (given that there are seven columns). For each child of the root, its children (which are the grandchildren of the root) would represent the situations that can result from the player dropping a subsequent coin.

In the above example, each board has three columns and three rows. The player is represented by yellow coins and the computer by red coins. Note that a move from a board on an even level to a board on the next (odd) represents a move by the player and that a move from a board on an odd level to a board on the next (even) level represents a move by the computer.

If we build a tree containing all possible sequences of coin drops, the computer can simply search for a "winning" sequence and choose a move towards it. However, the complete tree may be too large to fully explore, so the usual strategy is simply to "look ahead" a fixed number of coin drops and choose a move towards the most favourable situation. In this lab, the attribute level of the class Model captures the number of moves that will be "looked ahead." By increasing the value of this attribute, the "look ahead" increases and hence the choice becomes "more intelligent."

In order to measure how favourable a board is for either the player or the computer, we will use some sort of heuristic (rule of thumb) to compute a score, an integer, for each board. A larger (more positive) score means a better board for the computer and a smaller (more negative) score means a better board for the player. Next, we discuss how to assign a score to a board.

Let us assume that the board has seven columns and six rows and that one needs four connected coins to win. For a board where neither the computer nor the player has won the game, we look at all the combinations of four consecutive squares in a row (horizontally, vertically or diagonally) on the board. There are 69 of them (24 horizontally, 21 vertically and 24 diagonally). From these combinations, we count the number of them that do not contain any of the player's coins (loosely speaking, the number of ways the computer can still win) and subtract the number of them that do not contain any of the computer's pieces (the number of ways the player can still win). For example, the board (where yellow coins represent the player and red coins represent the computer)

contains 36 combinations that do not contain any of the player's pieces (13 horizontally, 11 vertically and 12 diagonally), and 39 combinations that do not contain any of the computer's pieces (13 horizontally, 13 vertically and 13 diagonally). Hence, the score of this board is -3.

For a board where the computer (or the player) has won the game, we want our score to reflect that this is a most (or least) favourable situation. So the score for a situation where the computer has won the game is 70 (one more than any other possible score), and the score for a situation where the player has won the game is -70 (one less than any other possible score).

Let us consider the above tree again. Assume that one needs three connected coins to win. Below, for each board its score has been added to the right of it.

Now that we can build a tree of boards that "looks ahead" a number coin drops, and assign a score to each board, we can find the "best" move as follows. We assign a value to every board of the tree. Intuitively, the value for a board in the tree is the best score that the computer/player whose turn it is can realistically hope for if the game were to continue from the situation represented by that board for as many as moves as are represented in the tree. The value of a board in the game tree can be defined recursively as follows.

Again, let us consider the above tree. Below, for each board its value has been added to the right of it.

Given the board stored in the root of the tree, the computer would choose the middle column to drop its coin (since the resulting board has the best value).

You are given the jar file lab8.jar containing the classes View and Controller and the classes Model and Main. Their API can be found here. Note that these classes differ a little from the ones of Lab 7. You are asked to add three methods to the Model class. To ensure that your class for Lab 7 and those for Lab 8 do not interfere, create a new Java project for Lab 8.

  1. /**
 * For the given board, return the number of combinations
 * (CONNECTED consecutive slots either horizontally, vertically or 
 * diagonally) that do not contain a coin of the given player (that is, 
 * they either do not contain a coin or contain a coin of another player).
 *
 * @param player a player.
 * @pre. player == Model.PLAYER || player == Model.COMPUTER
 * @param board the board.
 * @pre. board != null
 * @return the number of combinations of the given board that do not 
 * contain a coin of the given player.
 */
private static int count(int player, int[][] board)
    You may use auxiliary (private) methods. Test the count method using the JUnit test CountTest. 
  2.   /**
   * Returns the value of the given board for the given player and level.
   * 
   * @param board the board.
   * @pre. board != null
   * @param level the number of moves that are "looked ahead".
   * @pre. level >= 0
   * @param player the player whose turn it is.
   * @pre, player == Model.PLAYER || Model.COMPUTER
   */
  private static int value(int[][] board, int level, int player)
    You do not have to construct the game tree explicitly. The recursive process itself may be viewed as the tree. In the recursive calls, you may want to use a copy of the board. Test the value method using the JUnit test ValueTest. 
  3.   /**
   * Returns the column number of the column that is not filled and has
   * the best value, given that it is the computer's turn.  If multiple
   * columns have the best value, the smallest one is returned.
   * 
   * @pre. !isFilled()
   * @return the column number of the column that is not filled and has
   * the best value, given that it is the computer's turn.
   */
  public int move()
    Test the move method using the JUnit test MoveTest.

Submission instructions