Homework 12

Assignment: 1 problem, 50 points (plus up to 10 percent Extra Credit), due on

11:59 pm on Sunday, November 20, 2005 (M/T sections)

11:59 pm on Monday, November 21, 2005 (W/Th sections)

Reading: Your CS5 lecture notes and the online readings for Section 5.3

Problem 1 Connect Four -- An AI game player (50 points) [topics: some AI topics and more practice with classes ]

Problem 1 is this homework's Pair Programming problem and can be worked on in groups of two as described at http://www.cs.hmc.edu/cs5/pair_programming.html.

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.

I've provided basic menus and guts for human Connect Four game-playing---essentially giving you a working Homework 10 assignment with a few extra bells and whistles (e.g. there is infrastructure in place that will later make it easy for you to run multiple simulations of AI players dueling against each other!). Initially, while developing your player, using my {\tt Board} code should help---it is (presumably) bug-free (um...er...it is a dangerous proposition to swear no bugs exist!). Thus, you can concentrate solely on getting your player code working. Later, if you'd like to replace my {\tt Board} code with your own---so that the overall beast is entirely yours---please do so!

The `CS5App` class

I've provided everything you'll need in this class; instead of just main there are now several other functions added to make it easier to run multiple games before quitting (check out the code in the CS5App class for more; it is clean and well documented).

Here's the main menu:


Welcome to Connect Four!

Options: (0) play single game
         (1) play some number of games
         (9) quit

Which option would you like?

Option 0's primary use is for two human players or one human and one computer player. Out-of-the-box, this option will let you enter a board's size, e.g.:


Setting up the game...
Enter number of rows: 6
Enter number of columns: 7

where an example user input is shown in blue. At this point, because a lot of code still needs to be written by you (search in the CS5App.java file for You need to write this function! text), you don't yet have the full flexibility you'll have later. Currently, option 0 only automatically sets up two human players, and so in principle you could play a game with another person. The only problem is that, until you write the whoAmI and whoIsOpponent functions, both players' checkers are ? to begin with.

To allow yourself more flexibility, you'll have to write the getValidPlyValue and getValidTieValue functions in the Player class, which are needed before computer players can be requested. Once computer playing is feasible, it makes sense to use option 0 to play a computer player against yourself (a great way to debug your Player code). Option 1, which can run multiple games and report overall results, can only be used when both players are computer players. A great way to use that option is to play a lower-ply player against a higher-ply player (one would expect the higher-ply player to win more often). Again, you can use this option to explore whether or not your code is doing what you think it should.

As usual, option 9 quits the program.

The `Board` class

This class was essentially lifted from my solution to Week 10's homework. I added a few functions (most notably, clear, which the CS5App class uses when running multiple games). You will also need to fill in the code for some new function signatures:

public void removeMove(int c) should remove the most recently added checker in row c.
public boolean isOver() should return true when the game is over.
public int numCols() should return how many columns the board contains.

These functions were added because the Player class needs such functionality.

The `Player` class

Writing this class is the bulk of your work in this assignment. The Player class handles both computer and human players, providing a standard interface by which main in the CS5App class can interact with both participant types. I provide public int make_move(Board, boolean), the function that provides this standardization.

When make_move is called for a human player, the human is presented with a picture of the board, along with a prompt. Here is an example for human player X, taking place in the middle of a single-game partially-played 6-by-7 board:


| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | |O| | | |
| | |X|O| | | |
| | |X|O|X| | |
---------------
 0 1 2 3 4 5 6

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

If the user enters a number between 0 and the number of columns (6), their checker is placed in that column. If the user enters a negative number, this signifies that they'd like the computer to give them some advice (via evaluate_ply, described later). In particular, they'd like advice regarding the scores the columns receive using the absolute value of their negative number as look ahead.

For example:


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

  Player X Scores: 
  Column: 0     1     2     3     4     5     6     
  Score:  50.0  50.0  50.0  50.0  50.0  50.0  50.0

indicates that, for a 1-ply lookahead, all columns appear equally good for player X.

When larger-than-1-ply advice is requested, the user also has to specify the tie-breaking method to use. For example, with 2-ply lookahead, the user will see the following menu:


  X's move (type -N for an N-ply hint) -2

  Choose tiebreaker type:
   (0) Take leftmost best score
   (1) Take rightmost best score
   (2) Take a random best score

Enter type: 2

In this interaction, they've chosen for the advice to break ties randomly, which results in the following advice:


  Player X Scores: 
  Column: 0     1     2     3     4     5     6     
  Score:  0.0   0.0   0.0   50.0  0.0   0.0   0.0

This advice makes perfect sense: If player X doesn't go in column 3, they will loose, a fact that is only visible after 2 checkers (hence 2 ply) have been played.

When make_move is called on a computer player, the resulting move choice is automatically determined via the player's lookahead and tiebreakType values (also via evaluate_ply). The chosen column (and corresponding scores) are only shown when make_move's boolean debugging-flag is set to true.

For details concerning make_move refer to CS5App.java.

Provided Player Members

Data:
- checker should be 'X' or 'O'.
- lookahead should be -1 for a human player and a non-negative integer for computer players (be careful---if this value is too large, it will take too long or require too much memory for your computer to look that far ahead).
- tiebreakType should be 0 (ties break to left), 1 (ties break to right), or 2 (ties break randomly).
Methods:
- Player(char, int, int) is the constructor.
- public String toString() prints an indicative string.
- public void printScorees(double []) prints the values in the array (used to, for instance, produce the advice shown above).

Method Members You Need to Write:

public static int getValidTieValue() should query the user with the following menu:
```
Choose tiebreaker type:
 (0) Take leftmost best score
 (1) Take rightmost best score
 (2) Take a random best score

Enter type: 
```
and then ensure they enter a proper value. Note this function is static: it doesn't access any non-static data members. Rather, it returns an int specifying a legal tiebreakType value. Because this function is also public, it is available in the CS5App class, where it is used to let the user specify what type of Player they'd like for both X and O.

public static int getValidPlyValue() should query the user with the following menu:
```
Choose ply lookahead:
  (-1)  Human player
   (0)  0-Ply computer player
   (1)  1-Ply computer player
   (2)  2-Ply computer player
   (3)  3-Ply computer player
 (...)  N-Ply computer player

Enter player choice: 
```
and then ensure they enter a proper value. Analogous to the last function, this one allows the user to specify a player's lookahead strategy (or human-ness).

private int break_any_ties(double []) should return the best column associated with the double array of scores passed in, breaking any ties that might exist via tiebreakType. Aside: This function, like all the other private methods described here, are so designated because CS5App does not need to know this level of detail about how a Player works "under the hood."

public char whoAmI() should return the calling player's checker.

public char whoIsOpponent() should return the calling player's opponent's checker.

private double evaluate(Board) should return the evaluation score for the calling player given the contents on the Board. As described in class, this function should only return values within 0.0 and 100.0 inclusive. In fact, 0.0 should be assigned to boards in which the Player looses, 100.0 for wins, and 50.0 for anything else. If you end up doing the extra credit, you'll be modifying this function to make it "better" than just the coarse 3-value criteria described here.

private static double getMax(double []) should return the maximum value found in the double array that was passed in. (Again, this function is static because no instance data members are used; it is private because it is merely a helper for evaluate_ply, described below).

private double[] evaluate_ply(Board) should return the scores associated with the columns for the calling player given that lookahead plays into the future have been performed when evaluating a column's score for that player. This function is most elegantly written recursively, the details of which are described in class. For instance, there we described how this function will use the Board class's remove_move function to enable us to add future moves and then undo them (so that the original Board's state can remain unchanged). As another example, we describe why scores of -1 should be assigned to invalid board moves.

Sample Runs

We will test your code by running a human vs. a human and then asking (e.g. via 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 (and breaking ties to the left)

     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 (and breaking ties to the right)

     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 (and breaking ties randomly)

     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 (breaking ties randomly):

    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) (breaking ties to the left):

     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.

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

    Below gives the result of running a simulation. We're testing an 
    a 2-ply player ('X') against a 4-ply player ('O'), both breaking
    ties randomly. The board is 6-by-7 and we're running 25 games in total.

    Welcome to Connect Four!
    
    Options: (0) play single game
             (1) play some number of games
             (9) quit
    
    Which option would you like? 1
    
    Setting up the game...
    Enter number of rows: 6
    Enter number of columns: 7
    
    Select Player X's Features...
    
    Choose ply lookahead:
      (-1)  Human player
       (0)  0-Ply computer player
       (1)  1-Ply computer player
       (2)  2-Ply computer player
       (3)  3-Ply computer player
     (...)  N-Ply computer player
    
    Enter player choice: 2
    
    Choose tiebreaker type:
     (0) Take leftmost best score
     (1) Take rightmost best score
     (2) Take a random best score
    
    Enter type: 2
    
    Select Player O's Features...
    
    Choose ply lookahead:
      (-1)  Human player
       (0)  0-Ply computer player
       (1)  1-Ply computer player
       (2)  2-Ply computer player
       (3)  3-Ply computer player
     (...)  N-Ply computer player
    
    Enter player choice: 4
    
    Choose tiebreaker type:
     (0) Take leftmost best score
     (1) Take rightmost best score
     (2) Take a random best score
    
    Enter type: 2
    
    How many games would you like to play? 25
    
    Player O wins! Congratulations!
    
    Player X wins! Congratulations!

    >snipped to save trees<    
    
    Player X has lookahead 2 and tiebreakType 2 wins 5 times
    Player O has lookahead 4 and tiebreakType 2 wins 17 times
    There are 3 ties

Submission

Be sure to submit your CS5App.java file under homework 12, 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, and 100.0 on a board where the player has won, but may return any positive score in between these values 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 when the end of the game is not yet known.

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 that will be played against all the students who submit extra credit for this problem.

To submit extra credit, submit your Hw12Pr1 code including tournamentEvaluate and make sure you mention in the header of your file that you are turning in extra credit. 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. Note: You'll still want to test your tournament evaluation function, even if you can't access it from main in the code you submit. Or, better yet, feel free to expand on the Player constructor, so you can specify which type of evaluation function to use (if you do this you can then duel two equal-ply players against themselves, one using the "smarter" evaluation function and the other using the default one).