CSE 473: Introduction to Artificial Intelligence

Winter 2019

HW Assignment 3 (Program): 25 pts

Turn In Here

Download the skeleton code here:

Kalah game starter code;

Download the assignment introduction slides:

Kalah slides;

Due Sunday, Feb 10 at 11:59pm, late date Tues, Feb 12 at 11:59pm

Problem Description

The purpose of this assignment is to try out the game playing techniques we have studied as well as adding your own ideas. The game is Kalah with the following rules:
  • Each player has 6 holes and a Kalah as shown in the lecture slides.
  • A turn consists of selecting one of your own holes, picking up all the stones, and distributing them in each consecutive hole, including your Kalah but not the opponent's Kalah, in the counterclockwise direction.
  • If your last stone lands in your own Kalah, you get an extra turn.
  • If your last stone lands in your own empty hole, you take all the stones in the opponent's opposite hole and put them in your Kalah.
  • If you run out of stones on your side, the opponent takes all the stones left on his side and puts them in his Kalah


  • You will work alone. Feel free to discuss strategies but not code with others.
  • Your program must be based on Python2.7.
  • You must use minimax search with alpha-beta pruning as the basic algorithm.
  • You must use the skeleton code provided, so that your program can use the user interface we provide and participate in the tournament.
  • You must design your own heuristic functions and justify it in the report you turn in.
  • You should experiment with different strategies for more efficient or better search from the book or of your own design (e.g. different heuristics, shallow search, searching deeper under a potential move).
  • You should play against your AI, trying out your different variants and different max levels of search, and report on the results.
  • Your report should include the following:
  • This assignment is bigger than the previous two; writing code without debugging will lead to a disaster.
  • You are welcomed to play against each other using the Internet! The TAs have set up a server for Internet games (human vs. human or AI vs. AI)

    Tips on implementation

    System preparation:
    To use the code, you are suggested to use Windows. Otherwise you may need to compile the source code yourself.

    Conda (on Windows, Linux, Mac):
    1. Install Anaconda from here according to your platform.
    This step is optional, but it makes it easier to install some modules, like suds, which is required for this program to work.
    2. Open cmd and create a virtual environment named "hw3" by running: "conda create -n hw3 python=2.7".
    3. Activate the virtual environment: "source activate hw3" ("conda activate hw3" on windows).
    4. Install suds: "easy_install suds".
    5. Install PyQt4: "conda install pyqt=4".
    6. Run python main.py in the skeleton package.

    Build from sources (On Linux and Mac):
    1. Download the Qt 4 libraries here according to your platform.
    2. Install the Qt 4 libraries.
    3. Download the sip source code here.
    4. Compile and install sip.
    5. Download the PyQt 4 source code here according to your platform.
    6. Compile and install the PyQt 4.
    7. suds is a python web service module. If you have installed Anaconda, open cmd and type "easy_install suds". If not, find your version of setuptools here and then install suds.
    8. Run main.py in the skeleton package.

    After the Qt libraries are installed, below is an example of the shell commands used on the Mac. This may vary according to your environment.
    cd /users/yourname/Download/sip-4.15.5
    python configure.py
    sudo make install
    cd /users/yourname/Download/PyQt-mac-gpl-4.10.4
    python configure.py -q /Developer/Tools/Qt/qmake
    sudo make install
    easy_install suds

    To use the UI:
    1. Human vs. local AI.

    2. Human vs. internet human / Local AI vs. internet AI
    You can create a game host or join other's game. Select "Play with human" or "Play with AI" when creating a host. To play via the Internet, the host should first create a game. Then a second player can select the game in the list and click 'play with internet' to join that game.

    3. After game started, the main interface will be like this:

    A known bug of this framework is that occasionally the UI will become stuck and one or more buttons become grey, but the numbers are not 0. You just need to minimize the window and resume and it will be fine. Very seldom it will crash. Just open it again.

    Implement your AI:
    There's a python script file ai.py in which you will implement your code. The other two should not be modified. There's detailed explanation about input and output inside ai.py. Remember the requirements and time limitation mentioned above.

    Note: The game server can only be connected when you are using Campus Internet. If you want to debug your program outside of campus, please use VPN or comment line #43 at main.py.

    Turn-in and Evaluation

    You should turn in the following two files within a single .zip file:


    The TAs will run a Kalah tournament. This is mostly for fun, but the winners will be recognized and there will be some extra points for the tournament winners (top 4).
    Comparison: the following machine will be used for the Kalah tournament.
    OS: Win 7
    CPU: i7 4770 with 4 cores (3.4GHz)
    Memory: 16Gb
    Harddrive: SSD
    You can use whatever you know to improve your AI (multi-thread, special gaming strategy or database, etc). The only limitation is 1 second in searching time on the TA's machine. The framework will time your AI execution and if you exceed 1 sec, you will lose the game.

    Tournament Results