Introduction to Artificial Intelligence with Applications to Public Health

Assignment 1: Nic-Mac-Goe - Playing Games with Artificial Intelligence

• Assigned: February 14, 2005
• Due: March 14, 2005 at 2pm

Background

Nic-mac-goe is generalized (n,m,g) tic-tac-toe. It is played on a N by M board, and G (for goal) cells in a row count as a win. So traditional tic-tac-toe is just (3,3,3) nic-mac-goe.

In this assignment, you will be given a Python framework for playing nic-mac-goe complete with several simple if stupid agents which can play the game. Your task will be to write a sequence of improved game-playing agents that apply knowledge, search for solutions, learn play patterns, and even help design better agents.

Assignment

• Task 0: Obtain Nic-Mac-Goe
  Download the software for nic-mac-goe. You can play a simple game of tic-tac-toe against the standard player by running tictactoe.py from the command prompt (or by clicking on it if your Windows is set up correctly).

  You can play a more complex game of nic-mac-goe using a commands like:

  from nicmacgoe import *
  from human import Human
  from machine import Machine
  game = Game( "Five by Five", Board(5,5,3), Human(X), Machine(O) )
  game.play()
  

• Task 1: Analyze Nic-Mac-Goe
  Play a few games, on both the regular 3x3 board size and at larger sizes, against the standard "Player" distributed with the nicmacgoe source and against the and the "Machine" player. Make the default Player play itself and play the Machine on 3x3, 5x5 and 7x7 boards. Collect data about the behavior of the system and use that data to answer the following questions:
  • Which usually wins, the standard "Player" or the "Machine" player? Why?
  • Why do both the Player and the Machine do so poorly against humans?
  • When the Player plays itself on larger and larger board sizes, what happens to the length of games? Does the same thing happen when the Player plays the Machine opponent?
• Task 2: Playing with Knowledge
  Make a copy of machine.py called production.py and create a new automatic player based on the production system framework outlined in class. Your first target is just a 3x3 board, but after you feel your agent is playing "well" try it out on the 5x5 and 7x7 sizes. Answer the following questions:
  • How many productions are necessary to play good tic-tac-toe?
  • How large do the productions get?
  • How well does the system play 5x5 and 7x7 tic-tac-toe?
  • How well does your system play against the Player or the Machine?
• Task 3: Alpha-Beta Search
  Make a copy of machine.py called alphabeta.py and create a new automatic player based on the alpha-beta search framework outlined in class. Your target is "perfect" play on all board sizes. Answer the following questions:
  • How well does the alpha-beta pruning system play? Can you (or the other machine players) beat it on a 3x3 system if it goes first?
  • What happens to the system's speed as board sizes grow from 3x3 to 5x5, 7x7 and 9x9?
• Extra Credit: Neural Networks
  Make a copy of machine.py called network.py and create a new automatic player based on the neural network framework outlined in class. Use the alpha-beta pruning system you developed in the last step to train your network. Train your network for 3x3, 5x5 and 7x7 sizes.
  • How many games does the neural system need to play as well as alpha-beta pruning?
  • Can you apply a network trained on 3x3 to a 5x5 board? If so, what happens? If not, how would you modify the system so that play on different boards was possible?
  • What happens to the system's learning speed as board sizes grow from 3x3 to 5x5, and 7x7? What about the system's performance?

Deliverables

Turn in the following files packaged as a .zip archive:

• answer.doc (or .pdf): Answers to the questions above.
• production.py - source code for Task 2
• alphabeta.py - source code for Task 3
• neural.py - source code for Extra Credit
• Any support files you used.

• http://www.aaai.org/Publications/Author/authorinstructions.pdf
• http://www.aaai.org/Publications/Author/macros-link.html

(While AAAI accepts only PDF files, I will also accept Microsoft Word or Postscript).

Submit one hardcopy (in class) and one electronic copy (to centaur@dresan.com) by the start of class on the due date. (If I am not present on the due date, submit the paper to my substitute if available or at the next class if not available. The electronic copy must still be mailed before the due date).