Spring 2009»CSCI 470 Homework 4

CSCI 470 Homework 4

Assigned Date: Thursday, Apr. 2, 2009
Due Date: Tuesday, Apr. 21
Due Time: 11:55pm

Last modified on November 05, 2013, at 06:21 PM (see updates)

Purpose

This assignment focuses on:

  • developing "AI" for games
  • minimax and alpha-beta prunning
  • creating a simple UI for a game
  • having fun!

This is a pair-programming assignment (i.e., you may work with a partner). You may discuss the assignment only with your partner or the instructor.

Assignment

Write a Python program that plays a game of Pentago. Pentago is similar to Tic-Tac-Toe, except:

  • it is played on a 6x6 board
  • the board is divided into 4 quarters, each of which can turn clockwise or counter-clockwise
  • you need five-in-a-row to win
  • a move consists of placing a marker AND turning a quarter-board 90 degrees (clockwise or counter-clockwise)

Here is an illustration:

Specification

  • The game has two players, the human (user), and the computer.
  • Human always goes first.
  • Computer uses minimax (bonus: alpha-beta pruning) with limited lookahead to find a good move. The lookahead should be limited in terms of time spent.
  • Computer player should not take more than x seconds to find a move (where x is one of the inputs).
  • You should use the object-oriented graphics library designed by John Zelle to create a user interface for the game. (Download graphics.py or graphics22.py into the same directory as your pentago.py file.)
    • Feel free to use this draft of a Pentago user interface.
    • Follow its documentation and coding style in your own code.

Input

  • To play the game you should issue the command "python pentago.py x", where x is the time limit (number of seconds) for the computer to "think".
  • The program should output a graphics window with an empty board.
  • The user inputs by clicking the mouse on one of the empty holes. A white ball is placed there.
  • The program displays turn-arrows (two for each quadrant, signifying clockwise and counter-clockwise turn).
  • The user clicks on one of the turn-arrows.

Output

  • A graphics display of the game as it evolves. (No animation is expected for turning the quarter boards.)
  • When the game is over, display a message indicating who won.

Testing

If you are doing the bonus (i.e., alpha-beta pruning), you should first get minimax to work.

Also, to further simplify things, remove turning from a move (i.e., move consists of placing a ball in an empty hole). I.e., the game is reduced to a 6x6 tic-tac-toe.

  • Test with an almost filled board, where the winning move is one move away.
  • Test with an almost filled board, where the winning move is two moves away (note: there are many such moves, try some -- avoid symmetries).
  • Test with a win that's three moves away.
  • Test with an almost empty board where the winning move is one move away. Will your code find it? (Here you can determine the need for a depth or time limit.)
  • Swap who is winning (black vs. white) and repeat.
  • Test for draw.

Of course, this is just a subset of the possible tests one could run.

Documentation

All programs that you complete in your career as a student and as a professional developer should be fully documented. Obviously, you should comment any variable, obscure statement, block of code, method, and class you create. Your comments should express why something is being done, as opposed to how the how is shown by the code. Also, include opening comments as specified in previous assignment.

Submission

  1. Submit a README.txt file. Include your names, class, homework assignment, date. Also discuss the following:
    1. How to play your game. Feel free to rephrase the above.
    2. Any known limitations of your game (e.g., if/when it crashes, or something not implemented, etc.). You get more points by knowing and documenting your program's limitations (in the README file, and in your code).
  2. Your source code, pentago.py, fully documented and tested.
  3. The view code, pentagoView.py, with any changes fully documented and tested.
    1. Also include, graphics22.py, minimax.py or alpha-beta-search.py (whichever you used), utils.py, and all necessary images.

Grading

Your grade will be based on how well you followed the above instructions, and the depth/quality of your work.