Homework 1 (due 9/17 by 6 p.m.)

Group assignment (100 pts)

Check out some of the online versions to get an idea of the game if you are not familiar with it:

• Connect four (with minimax and alpha-beta pruning)
• A perfect connect four player

1. A "computer player" (which is basically the minimax procedure with alpha-beta pruning plus an evaluation function).
2. The playing environment for you to test the player (including input functions for the human player and a graphical display of the board).
   

// your connect4 class
public class Connect4<GID> implements Connect4Interface {
  <put in your code here>
}  

// interface that should be implemented by your connect4 class
public interface Connect4Interface {
  // this initialized the board
  void initializeBoard(int rows,int cols);

  // player X places a piece in a row
  void moveX(int col);

  // player O places a piece in a row
  void moveO(int col);

  // tells the computer to be player X
  void setComputerX();

  // tells the computer to be player O
  void setComputerO();

  // displays the current board on the screen
  void displayBoard();

  // gets the move from the human player, returns the column
  int getHumanMove(); 

  // returns true if the current board is a win for X
  boolean isWinX();

  // returns true if the current board is a win for O
  boolean isWinO();
  
  // returns true if the current board is a tie, i.e., all positions are filled
  boolean isTie();

  // tells the computer to make a move and return the column
  int getComputerMove();

  // sets the ply number for minimax search
  void setPly(int ply);

  // sets a parameter determining whether to use alpha-beta pruning
  void useAlphaBeta(boolean on);
}

The main loop for playing connect4 based on this interface then could be something like this (we will use the interface to be able to run a tournament with the various connect4 programs):

void play(Connect4Interface c4,int rows, int cols, boolean humanX, int ply, boolean usealphabeta) {
  // player X always starts
  boolean turnX = true;

  // initialize the board
  c4.initializeBoard(rows,cols);
  c4.setPly(ply);
  c4.useAlphaBeta(usealphabeta);
  
  // let the computer know who is who
  if (humanX)
    c4.setComputerO();
  else
    c4.setComputerX();

  // loop until the game is over
  while (!c4.isTie() && !c4.isWinX() && !c4.isWinO()) {
    if (turnX) {
      c4.moveX(humanX ? c4.getHumanMove() : c4.getComputerMove());  
      turnX = false;
    }
    else {
      c4.moveO(humanX ? c4.getComputerMove() : c4.getHumanMove());
      turnX = true;
    }
    c4.displayBoard();   
  }

  // print the results
  if ((c4.isWinX() && humanX) || (c4.isWinO() && !humanX))
     System.out.println("Humanity prevails");
  elseif (c4.isTie())
     System.out.println("Tie");
  else
     System.out.println("Silicon prevails");
}

Note: it will be helpful to write--in addition to the above and to the evaluation function, minimax-search with alpha-beta pruning--lots of little helper functions for the evaluation function (e.g., functions that access the board and report the presence of certain properties such as three Os in a row).  The evaluation function is critical as we will test your code with different values for "ply" and with different board sizes (so make sure you don't make any assumptions about the size of the board--the 6x7 board is only the standard size, we will write general functions that work for boards of all sizes!).

Code and comments

Academic honesty

Submission information

  /afs/nd.edu/coursefa.04/cse/cse471.01/group-dropbox/

where group members have full permission to their respective directories.  Please submit all your code in a file called

  c4<GID>.java

in  the hw1 subdirectory in your group directory before class on the day the assigment is due.

Furthermore, submit an ASCII text file called

  info<GID>.txt

which lists the responsibilities of the group members (i.e., of which part of the problem and code they were in charge).

Individual assignment (100 pts)

Part 1 (25 pts)

Write two short paragraphs (about 200 words each at most) about the above topic.  Be as precise and concise as you can.  What counts here is not whether you are right or wrong, in fact, there might not be a "right answer".  Instead, emphasis is put on your arguments, how you present them, and how conclusive they are.

Part 2 (75 pts)

Academic honesty

Submission information

  hw1.txt

in the hw1 directory in your space in the course dropbox

  /afs/nd.edu/coursefa.04/cse/cse471.01/dropbox/<yourAFSid>/hw1/