Assignment 4 information

• Support code for Nim and Coin-strip (UPDATED 10/4 to include the function print-nim-game which should help you debug your MINIMAX function)
• A transcript of me playing against the computer (in case there is any question on how you interact with the support code)
• More examples for problems 1 and 2 (UPDATED 10/6 with "Why your state sequence might be different and how to check it")
• Support code for Othello
• Othello instructions, tips, and documentation
• Game tree for problem 3a (postscript, pdf)

This is a 160 point assignment, broken down as follows:

• Problem 1: 40 points
• Problem 2: 30 points
• Problem 3: Part a: 20 points; Part b: 45 points; Part c: 25 points

Checklist of things to turn in

• Written: Problem 3a
• Electronic:
  • Comments in your code, PARTICULARLY for you Othello evaluation function
  • Problem 1:
    • (minimax start-state get-children game-end?)
  • Problem 2:
    • (coin-end? state)
    • (coin-gc state)
  • Problem 3:
    • (create-minimax-player eval-fn depth-cutoff)
    • (eval-fn board max-player)

Grading notes

• Your minimax function and your minimax function with alpha-beta pruning (implemented somewhere below your create-minimax-player function) should be straightforward implementations of the respective minimax algorithms. Any other student's Othello evaluation function should be able to run with your create-minimax-player function.

• Your Othello evaluation function should be able to run on any other student's (or my) create-minimax-player function.

• I may test your minimax or create-minimax-player function by giving it special get-children, game-end, or eval-fn procedures that will tell me which nodes were evaluated, etc.

• There will be some performance testing of your othello evaluation function. As a minimum level of performance, it should be able to (on average) defeat the random strategy and probably also a heuristic that simply returns the difference in the number of pieces. I will also write a simple heuristic to provide a comparison for a moderate level of performance.

  Don't worry too much about the performance of your heuristic; I don't think it's too hard to write a heuristic that will be able to beat you much of the time. I am looking for students to put a little thought into the design of their heuristic. Hence the importance of commenting this function in particular.

Eratta

There is a small typo on the assignment. In problem 1, the description of the game-end? function should read:

a function of one argument which given a state returns #t or #f if the given state finishes the game.