Homework 5
Adversarial Search

powered by FreeFind

Modified: 

Assignment

  1. Write a nim game using Minimax. The state space of nim may be exhaustively searched. To play nim, a number of tokens are placed in a pile between two opponents; at each move, the player must divide a pile into two nonempty piles of different sizes. Thus, a pile of six tokens may be divided into two piles of [5,1] or [4,2] but not [3,3]. The first player who can no longer move loses. The following illustrates a state space for a game with 7 tokens. MIN should start the game and, with 7 tokens is certain to lose if MAX divides the piles following the heavy arrows.

    Test using 15 in the starting pile.

     

Hints: Use the class example of Tic-Tac-Toe as a starting point. Note that the following can be used to input a list:

pile=input('Your move? ')                                  

  1. Rewrite nim using ALPHA_BETA_SEARCH and test with a pile of 15.
  2. Modify nim to play MIN position, that is, the UTILITY function should return +1 for a MIN win and -1 for a MAX win.
  3. Modify the MIN nim to play an Internet opponent. MIN should follow the protocol:
    1. MIN selects the size of the initial pile
    2. while win == None
      1. MIN divides the pile.
      2. print MIN, pile
      3. MIN sends the pile to MAX at address ('www.csci.ius.edu', 8888).
      4. if not a win
        1. MIN receives the MAX pile
        2. print MAX, pile
    3. print pile, winner

Notes

MAX is stateless meaning that no memory of a previous pile is held. Any pile, for example [1,2,3,4], can be sent to MAX which will return its move.

Problems

Should you see error: (10054, 'Connection reset by peer') sending to the machine failed most likely due to a bad address, no receiving program was bound to the socket or your fire-wall software won't allow Python access to the Internet. The instructor will need to reset the MAX machine.

Turn in

  1. Cover page - Your name, date, and Homework 5 should be on the first page. Staple all pages together.
  2. Printouts - Print the final Python programs for Assignment 1-4 and Shell executions.