Program 1 Web page last edited: "2002-02-18 15:07:51 lou"

Programming Assignment 1

This assignment involves the tic-tac-toe code here. Do the following:
  • Finish the code by filling in the functions marked "fill in here". You may add other function as well if you wish. (The static-eval function is not called by any other function yet, but see below.) Be aware that minimax-full may take a couple of minutes to run on a blank board.
  • Time minimax-full on the following board, with X to move:
     |---+---+---|
     |   |   |   |
     |---+---+---|
     | O | X |   |
     |---+---+---|
     |   |   |   |
     |---+---+---|
    
    You can time minimax-full by evaluating
    (time (minimax-full "X" board))
    Put a comment at the beginning of your code file giving the time for minimax-full on the board above. From this time, estimate how long minimax-full will take on a blank board and include that answer in your comments also.
  • Write a function (minimax player board depth) that is like minimax-full, but only searches down to the specified depth and then uses the static-eval function. E.g., if depth = 0, minimax just returns static eval of board.
  • Write (choose-move player board depth) that is like choose-move-all but uses minimax instead of minimax-full. If depth = -1 ask the user for a row and column for the move instead of using minimax.
  • Write a function (play x-depth o-depth) that plays a game of tic-tac-toe using choose-move with x-depth to choose moves for X and choose-move with o-depth for O's moves.