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

Requirements

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:

A brief description of the game.
The definition of your heuristic function and its justification. Illustrate how it works with example moves it chose and explain why it chose them in terms of the function.
The details of your program design, experiments and results, which should include:
- How long it takes to make a move at different search depths and specify your CPU speed in the report. Timing restrictions are only for the tournament.
- How each heuristic function you designed affect the performance, e.g., the algorithm with this heuristic function vs the algorithm without this heuristic function.

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
make
sudo make install
cd /users/yourname/Download/PyQt-mac-gpl-4.10.4
python configure.py -q /Developer/Tools/Qt/qmake
make
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:

your well-commented code (ai.py), 17 points:
- Working program: 15 points.
- Well-commented code: 2 points.
report describing your implementation (at most 5 pages, 1” margins, 11pt, double-spaced) 8 points:
- A brief description of the game: 1 points.
- The definition of your heuristic function and its justification. Illustrate how it works with example moves it chose and explain why it chose them in terms of the function: 3 points.
- The details of your program design, experiments and results:
  - How long it takes to make a move at different search depths and specify your CPU speed in the report. Timing restrictions are only for the tournament: 2 points.
  - How each heuristic function you designed affect the performance, e.g., the algorithm with this heuristic function vs the algorithm without this heuristic function: 2 points.

Tournaments

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.
TO BE UPDATED
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

HERE.