Homework 11

Due: 11:59 PM on Friday, November 19, 2004

Reading: No additional reading from last week

1 problem, 50 points (extra credit is also possible)

Problem 1 Connect Four -- Building a game player [topics: some AI topics and more practice with classes ]

In this problem, you will be extending the Connect Four code from last week's assignment so that it actually plays the game (rather than simply hosting a game between two human players). In doing so, you will build a new class, named Player, which will have several methods for selecting Connect Four moves.

Using Assignment 10, Problem 1

You will need to start with your code for Hw10Pr1 (the CS5App and Board classes. Similar code is provided in Hw11Pr1.zip, but you should feel free to replace any of that code with your own! Note that the winsFor, allowsMove, and isFull methods will need to be copied from your Hw10 to your Hw11 code! In addition, you will be creating two or three more methods in the Board class this week.

The `CS5App` class

The main method of your CS5App class will be similar to last week's, but with some crucial differences to take advantage of the Player class. This description will highlight the differences. Your main method inside the CS5App class should do the following:

Assume the board is 6 rows high and 7 columns wide. Do NOT allow allow the user to choose the height and width as you did before.
First, welcome the user(s) to your Connect Four program. Again, be sure that the board is 6 rows high and 7 columns wide.

Second, prompt the user for what sort of lookahead the object playerForX of class Player should have. The choices should be

    (-1)  A human player
     (0)  The computer with 0-ply lookahead
     (1)  The computer with 1-ply lookahead
     (2)  The computer with 2-ply lookahead
     (3)  The computer with 3-ply lookahead
     (4)  The computer with 4-ply lookahead
     (N)  The computer with N-ply lookahead [Optional]

Third, prompt the user for the kind of "tie-breaking" they would like the object playerForX (of class Player) to use. The options should be (0) Tie-breaking to the left of the board (1) Tie-breaking to the right of the board (2) Tie-breaking randomly
Take in the user's answers to these two questions and then create a Player named playerForX using the constructor from the Player class. The Player constructor will take as input three things (1) the checker that the Player will represent ('X' or 'O'), (2) the type of Player (-1 (human) through 4 (4-ply lookahead)), and (3) the tie-breaking type (0 (left-side) through 2 (tie-breaking randomly)). See the Player class (below) for a list of the other methods needed in Player.

Next, repeat this process for 'O' by creating another object, named playerForO, again of type Player with the appropriate, user-defined options.
Then, instead of the line char player='X', you will need to use the objects you just created to represent the two players. Thus, you'll need
```
      Player player = playerForX;    // X starts the game
  
```
During the game itself, rather than asking the human for a move, you should ask the player object for two things -- the first is the scores it assigns to each possible next move. Note that this code should ask a person for a move if player has a lookahead of -1:
```
      double[] s = player.findScores(b);  // s is an array of length 7
  
```
Then, print those scores and call player.breaktie(s), which will return the int of the column of the next move.
Adding the move to the board will be the same as before, except that you will need to access the character checker ('X' or 'O') of the current player by calling player.getChecker() or player.me(). You'll need this in addMoveboard and anywhere else that the char is needed.
Finally, you'll need to swap the value of player between playerForX and playerForO (rather than swapping 'X' and 'O' as in Hw10). In addition, your code should ask the user if they would like to play again and allow for resetting the details of the playerForX and playerForO objects with each game. (It should also clear the board -- see the next section.)

Additional methods required in the CS5App class

None are required, though I created one called getPly that queries the human user for a lookahead type and returns it along with one called getTie that does the same thing for the tiebreaking strategy.

The `Board` class

Additional methods to be placed in the Board class

Your Board class needs three additional methods beyond those required in Assignment 10:

public boolean isOver()

This method should return true if the game is over and false if the game is not over. This method simply combines the isFull and winsFor methods -- note that winsFor will have to be used twice: once for 'X' and once for 'O'.
public void removeMove(int c)

This method should remove the top checker from column c. If c is out of bounds or there are no checkers in column c, this method should do nothing.
public void clear() This method should clear the board -- it will be useful between games... .

The `Player` class

Required data members to have in the Player class

Your Player class should have three data members:
- private char checker;
- private int lookahead;
- private int tiebreakType;
These data members are private because only the Player class should directly access them.

Methods required for the Player class

public Player(char ch, int la, int tbk)

This is a constructor for a Player object that takes three input arguments. It should then assign those inputs to the data members of this Player:
```
     this.checker = ch;
     this.lookahead = la;
     this.tiebreakType = tbk;
  
```
public double[] findScores(Board b)

This method takes a Board as input and returns an array of the seven columns' next-move scores for that Board. This method should not do the heavy lifting of finding the scores -- instead it should simply call one of the following methods, depending on the value of this.lookahead. It can then just return the double[] it receives from the appropriate one of these:
public double[] ply0(Board b)

This method should return an array of 7 doubles containing the 0-ply scores for each possible move. Because 0-ply means NO LOOKAHEAD AT ALL, this means that every spot in the array should be 50.0 except those spots where a column is full -- those should be -1.0, which indicates an invalid move.
public double[] ply1(Board b)

This method should return an array of 7 doubles containing the 1-ply scores for each possible move. This will be covered in detail in class, but the basic idea is to move to each valid column and evaluate the resulting board.
public double[] ply2(Board b)

This method should return an array of 7 doubles containing the 2-ply scores for each possible move. This will be covered in class, but the basic idea is to move to each valid column, then ask an opponent the scores they would give to their next move, and use those opponent scores to compute an appropriate ply-2 lookahead score. Note that the opponent should look ahead only one ply in order for a total of 2-ply lookahead!
public double[] ply3(Board b)

This method should return an array of 7 doubles containing the 3-ply scores for each possible move. This is based on ply2 in the same way that ply2 is based on ply1.
public double[] ply4(Board b)

This method should return an array of 7 doubles containing the 3-ply scores for each possible move. The pattern follows from the previous ply methods.
public double[] plyHuman(Board b)

This method is called when this.lookahead == -1. This method should ask the human user for a move. It should make sure only to accept a VALID move, reprompting as necessary. Note that this method does not return the move, but an array of 7 doubles in which the user's move is larger than any other value in the array. One natural possibility is to return 42.0 for the chosen (valid) move and 0.42 in the six other spots.

Also if the user inputs a value of -1, -2, -3, or -4 as their chosen move, this method should print out the computer's score values of the board with a 1, 2, 3, or 4-ply lookahead, respectively. It should continue to prompt for a valid column move afterwards, as well.
public int breaktie(double[] s)

This method takes a double array of board scores named s and returns the index (the move) corresponding to the bext (maximum) move. This would be straightforward, except that there will often be ties! To break ties, this method should check the value of this.tiebreakType (0,1,2) and it should return the (leftmost, rightmost, random) best move accordingly. Note that if there is only one best move, that same move will be returned regardless of tiebreakType. Suggestion: you might consider using a while loop and H.randInt(0,6) to implement the random tie breaker.
public double evaluate(Board b)

This method should return 100.0 if b wins for this player; it should return 0.0 if b loses for this player; it should return 50.0 if b neither wins nor loses. For extra credit, however, you might want to improve this evaluate method... (see below).
public char getChecker()

This method should return the value of this.checker. This is an example of a common "getter" method, used just to obtain the value of a data member. This method is not really needed if you write the following one:
public char me()

This method should do the same thing as the above getChecker method. It's nice just because it's shorter.
public char opp()

This method should return the checker of the opponent. That is, this method should return 'O' if this.checker == 'X' and vice-versa. Because this method is the foil to me() you might consider calling it you() instead!
public static void printScores(double[] scores)

This method should print the seven scores in the variable scores with some easy-to-read formatting -- the exact formatting is not critical. For example, this is one possibility:
```
  Scores:
  0      1      2      3      4      5      6
  100.0  50.0   50.0   50.0   50.0   50.0   0.0
  
```
Notice that this method is static. This means it is owned by the class Player, not any particular object of type Player. As a result, you can call it with the class name or an object name (whereas the nonstatic methods above must have an object name): Player.printScores(s); or player.printScores(s);

Samples

We will test your code by running a human vs. a human and then asking (with the -1, -2, and -3 options) for the scores that your code assigns to each possible move. We will also run your computer players against each other to check for tie-breaking and lookahead.

Here are some of the test cases we will try -- check to be sure your code works!

    

    TEST CASE 1

    With the following board, obtained through the moves 4-3-4-3-4-5

     | | | | | | | |        (X's move)
     | | | | | | | |
     | | | | | | | |
     | | | | |X| | |
     | | | |O|X| | |
     | | | |O|X|O| |
     ---------------
      0 1 2 3 4 5 6

    It is X's move, and asking for 1-ply scores should produce these scores:

    X's move (-N for an N-ply hint):  -1

     Scores:
     0      1      2      3     4       5      6  
     50.0   50.0   50.0   50.0  100.0   50.0   50.0      

    Of course the best move is column 4, which wins for X.

    -----------------------------------------------------------------

    TEST CASE 2

    With the following board, obtained through the moves 0-6-1-0-2

     | | | | | | | |        (O's move)
     | | | | | | | |
     | | | | | | | |
     | | | | | | | |
     |O| | | | | | |
     |X|X|X| | | |O|
     ---------------
      0 1 2 3 4 5 6

    It is O's move, and asking for 1-ply scores should produce
      no distinction among the columns:

    O's move (-N for an N-ply hint):  -1

     Scores:
     0      1      2      3      4      5      6  
     50.0   50.0   50.0   50.0   50.0   50.0   50.0      


    2-ply (or 3-ply) lookahead should show that column 3 is the best:

    O's move (-N for an N-ply hint):  -2

     Scores:
      0      1      2      3      4      5      6  
      0.0    0.0    0.0   50.0    0.0    0.0    0.0      

    -----------------------------------------------------------------

    TEST CASE 3

    With the following board, obtained through the moves 1-2-1-1-2-4-4-4-4-0

     | | | | | | | |        (X's move)
     | | | | | | | |
     | | | | |X| | |
     | |O| | |O| | |
     | |X|X| |X| | |
     |O|X|O| |O| | |
     ---------------
      0 1 2 3 4 5 6

    It is X's move, and asking for 3-ply scores should produce
      a perfect score in column 3:

    X's move (-N for an N-ply hint): -3

     Scores:
     0      1      2      3      4      5      6  
     50.0   50.0   50.0  100.0   50.0   50.0   50.0      


    Then, if you move 'X' to column 3, you can new ask 'O' what it thinks:

     | | | | | | | |        (O's move)
     | | | | | | | |
     | | | | |X| | |
     | |O| | |O| | |
     | |X|X| |X| | |
     |O|X|O|X|O| | |
     ---------------
      0 1 2 3 4 5 6

    O's move (-N for an N-ply hint): -3

     Scores:
      0      1      2      3      4      5      6  
      0.0    0.0    0.0    0.0    0.0    0.0    0.0      

    O's move (-N for an N-ply hint): -2

     Scores:
      0      1      2      3      4      5      6  
      0.0    0.0    0.0    0.0    0.0    0.0    0.0      

    O's move (-N for an N-ply hint): -1

     Scores:
     0      1      2      3      4      5      6  
     50.0   50.0   50.0   50.0   50.0   50.0   50.0      


   Which, perhaps, sends the message that things might look
   better if you don't look too far ahead... .

   -----------------------------------------------------------------

    TEST CASE 4

    With an almost identical board, obtained through the moves 1-2-1-1-2-4-4-4-4

     | | | | | | | |        (O's move)
     | | | | | | | |
     | | | | |X| | |
     | |O| | |O| | |
     | |X|X| |X| | |
     | |X|O| |O| | |
     ---------------
      0 1 2 3 4 5 6

    Ask O what it thinks of its situation at 4-ply and below:

    O's move (-N for an N-ply hint):  -4

     Scores:
     0      1      2      3      4      5      6  
     0.0    0.0    0.0    0.0    0.0    0.0    0.0      

    O's move (-N for an N-ply hint):  -3  (or -2)

     Scores:
     0      1      2      3      4      5      6  
     50.0   50.0   50.0   0.0    50.0   50.0   50.0      

     because, in this case, it only sees the immediate threat.

Submission Be sure to submit your CS5App.java file under homework 11, problem 1.

Extra Credit

For extra credit this week, create a more "intelligent" evaluate method in your Player class, called tournamentEvaluate.

tournamentEvaluate should return 0.0 on boards where the player has lost, but can return any positive score for other boards. The idea is to provide more information than just the generic score of 50.0 in the most common case -- when there is no clear winner or loser. Note that your tournamentEvaluate should not try to "lookahead" further -- rather, it should simply do a "better" job of deciding which boards favor which players.

Here are some possibilities to consider as you write tournamentEvaluate:

Central columns may be more important than the columns on the sides of the board, so you could give more points for checkers in the center.
Getting two or three in a row may be a good thing -- with three better than two BUT it's only a good thing if the remaining spots are still open!
Getting two or three out of four with blank spaces in between is a good thing (this may include configurations that are _not_ consecutive)
Stopping the opponent from getting three in a row is a good thing

There are many more possibilities -- and lots of ways to tweak the weighting of different factors when evaluating board positions.

To judge your tournamentEvaluate method, we will run a tournament of the Players that people submit for this extra credit. You will receive some credit (3 points), as long as your tournamentEvaluate method does _at least_ as well as the simple evaluate method described in the Player class. Additional credit (up to 15-20 points) will be awarded according to how your Player does in the round-robin tournament.

Submission For this extra credit, submit your Hw11Pr1 code including tournamentEvaluate . Be sure to leave your code so that the basic, default behavior is to use the normal evaluate. We will set up a separate file with all of the tournament entries.

Additional Extra Credit!

You might want to look further ahead than 4 moves! For this extra credit, extend the connect-four Player class to allow the user to choose an N-ply lookahead for any choice of N. You will need a plyN method, and a special interface to let the user get the N-ply scores for any N (however you'd like to do it is OK). You should include a way to print the N-ply lookahead scores, too, from the human interface so that we can check it! There is an example board on the last slide of the handouts whose scores vary up to ply 8 or more... .

Warning: as you might expect, the program slows down as N gets larger. N=42 will solve the game completely, but it also won't finish...