Mini-max

1. Learn about mini-max (a.k.a. Maxi-min). Wikipedia has an article about it. There are plenty of other good tutorials online too.



2. Implement a tic-tac-toe game that pits a human against a mini-max strategy. (You are welcome to use the programming language of your choice for this assignment. Just be sure to include a build script in your zip file that builds in your favorite language.) A simple console game will be sufficient for this assignment. The human player will always be "X", and will always go first. Example:

   What game would you like to play?
   
    1) Tic-tac-toe.
    2) Global Thermal Nuclear War.
   Choice: 2
   
   Sorry, I cannot allow that.
   Let's play Tic-tac-toe. You start.
   
    1 | 2 | 3
   ---+---+---
    4 | 5 | 6
   ---+---+---
    7 | 8 | 9
   Your move: 1
    
    X | 2 | 3
   ---+---+---
    4 | O | 6
   ---+---+---
    7 | 8 | 9
   Your move: 9
   
    X | 2 | 3
   ---+---+---
    4 | O | 6
   ---+---+---
    7 | O | X
   Your move: 2
   
   Etc.
   




3. Zip or tarball your source code in the usual manner. Don't include any generated binary files in your archive. Click on the "Project submission" link on the main class page to submit your archive file. If you have any difficulties with the submission server, please e-mail your submission directly to the grader.

FAQ:

1. How do I know if my implementation is correct?
   If a world champion Tic-tac-toe player could beat it, your implementation has a bug.



2. How do I debug this?
   Don't start at the beginning:

    1 | 2 | 3
   ---+---+---
    4 | 5 | 6
   ---+---+---
    7 | 8 | 9
   

   Start near the end:

    1 | 2 | X
   ---+---+---
    O | X | X
   ---+---+---
    O | X | O
   

   Then, there won't be much to debug. If you don't find a problem, back off one more move and repeat. If you need more debugging help, ask the automated professor. If you find the automated professor insulting, ask a human.



3. Is that initial dialog about Global Thermal Nuclear War really necessary?
   No. That was the pathetic attempt of a bored professor to entertain himself.



4. Do I have to detect who wins?
   Oh, come on! If it takes more than ten minutes to put a little bit of polish up your work, then you especially need the practice.