Artificial Intelligence

Programming Project #3

Konane

Due by 12:29:59 on Tuesday, March 14, 2006.

Please email your solution deliverables to my departmental email account by the due date.  Click here to email your solution.  Turn in a hardcopy of your report on Tuesday, March 14.

 

Introduction and Purpose

This assignment involves an implementation of the game Konane (koh-nah-nay).  This is a two player, zero sum game with very simple rules.  This assignment involves implementing the minimax algorithm and Alpha-Beta pruning search with cutoff and collecting statistics related to these search techniques.

Konane is a board game which can be played with black and white stones on the squares of a rectangular board of any size.  This game, also known as Hawaiian checkers, was popular among ancient Hawaiians, who often played it on 18x18 boards.  Initially, the board is filled with stones in a checkerboard pattern, white and black each occupying alternate diagonals.  Initially two stones, one of each color, are removed from an adjacent pair of locations in the center or as near to the center of the board as possible.  Then play begins. Each player, at his turn, must jump an adjacent opposing stone either horizontally or vertically, in either direction.  The jumped piece is removed from the board.  A multiple-jump on the same turn is permitted if in a straight line, but prohibited if it would turn a 90 degree corner.  The number of stones on the board decreases until eventually the game ends when someone has no legal move, and that player then loses.

 

 

Description of Konane 

  1. What you need to play Konane:
    1. A square wooden board with 64 holes in an 8x8 configuration.
    2. 64 small pebbles (32 dark and 32 light)

     

  2. How to play Konane:
    1. Two players are needed to play this game.
    2. Put the pebbles on the board with a dark then light, the dark pattern as shown in the following diagram below (assuming X=dark and O=light)
      3.     
      0 1 2 3 4 5 6 7
    +----------------
  0 | X O X O X O X O
  1 | O X O X O X O X
  2 | X O X O X O X O
  3 | O X O X O X O X
  4 | X O X O X O X O
  5 | O X O X O X O X
  6 | X O X O X O X O
  7 | O X O X O X O X
    3. First, the dark player removes a dark piece either at position (0,0), (3,3), (4,4), or (7,7).
    4. Next the light player removes a piece adjacent to the space created by the first move.
    5. The dark player jumps a dark pebble over a light pebble into an empty space and removes the light pebble.
    6. Next, the light player jumps a light pebble over a dark pebble into an empty space and removes the dark pebble.
    7. The players continue steps e and f taking turns.  One player can jump over more than one of the opponents pebbles but there must be an empty space between the pebbles and an empty space to jump into.  The players can jump up and down, left and right, but only in a straight line.  The players cannot change directions in one turn if jumping over more than one stone.
    8. Each player has to jump in his turn.  When a person cannot jump the game is over and the last person to jump is the winner.

 

Getting Started

  1. Save the konane.py program to your home directory or local machine.  Read and understand the class definitions.  Please document this program according to our documentation standards.
  2. Try executing this program.  The main program at the bottom of the file will prompt you to try several test cases.  Add or modify these test cases to get a feel of the game. 
  3. Try playing a 6 by 6 game as a HumanPlayer against the RandomPlayer. Or try challenging another person to a game.

 

Requirements

  1. Develop the state representation, successor function, initial state, and goal test for this game.
  2. Play the game many times using the SimplePlayer, RandomPlayer, and HumanPlayer objects.  (You might have to modify the program for this.  Provide a description of the strategies used by you to figure out your next move.
  3. Describe the static evaluation functions based on the strategies used by you in step 3.
  4. Develop your own evaluation function.  Note: The evaluation function contributes towards the total time taken by an algorithm to return an action.  This would mean that good evaluation functions take more time to execute.  Average evaluation functions will be able to explore a more nodes in a given time.  You will have to take this into consideration while designing your evaluation function. 
  5. Implement a MinimaxNode class to hold the necessary information for a search node in a minimax game tree. It should include the following data:
  6. The Player class is the base class for creating a Konane player. Implement a MinimaxPlayer class that inherits from both the Player class and the Konane.  Your class must override the abstract methods initialize and getMove from the Player class.
  7. From the initial state of the game (i.e. none of the pieces removed from the board) make the agent run the MinimaxPlayer with a cutoff of 2.  Keep track of the total number of nodes expanded and the time required by the algorithm to return an action.  Also keep track of the maximum number of nodes that need to be stored in memory.  Also experiment with different board sizes.
  8. Repeat step 7 by incrementing the cutoff in multiples of 2 (i.e. 2, 4, 6, etc.) till the algorithm
    1. takes greater than an hour to return an action or
    2. runs out of memory
    3. fails in some other way
    Record the reason for failure if the algorithm fails to find an action at any point.
  9. Assume that your agent has 30 seconds to make a move.  From the statistics collected for the Minimax Search search determine a good cutoff depth for each of your agents.
  10. Now develop an AlphaBetaMinimaxPlayer class that inherits from both the Player class and the Konane.Your class must override the abstract methods initialize and getMove from the Player class.
  11. Repeat steps 8 with "Alpha-Beta Pruning with cutoff".
  12. Assume that your agent has 30 seconds to make a move.  From the statistics collected for the Alpha-Beta search determine a good cutoff depth for each of your agents.

 

Deliverables

  1. Submissions will consist of a single email with multiple attachments containing:
    1. A write-up of the assignment (i.e. answers to the questions above and whatever you need to say to explain your implementation(s).  Write-ups must be in either MS-Word .DOC or .PDF format and be named konane.doc or konane.pdf appropriately.
    2. Source code for your program(s) (konane.py).  You may (probably) be asked to demonstrate your program to myself or the grader.  Be sure to include in your write-up or a separate readme.txt file the basic operation / instructions for your program.  The program should be well commented.

Notes

Use the Python "clock" method in the "time" module to record the wall clock time.  Or use the pstat functions.

Steps 6, 7, and 8 will take some time to complete after you have finished and tested your code.  Plan accordingly!!!!!

Although for the purpose of this assignment the statistics will be collected from the initial state, in practice your programs might have to start searching from arbitrary middle states.