| CSE 415: Introduction to Artificial Intelligence
Spring 2014
|
HW Assignment 3 (Program): 30 pts
Turn In Here
Download the skeleton code here:
Kalah game Removed Due Friday, May 30 at 11:59pm,
late date Sunday, June 1 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 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 may work alone or in groups of two. Please infrom Prof. Shapiro if you are forming a group. Groups will be expected to do more work than singles, ie. try more strategies, have more experiments, etc.
You must use minimax search with alpha-beta pruning as the basic
algorithm.
You must use the skeleton code provided. Do not use other's code!
You must design your own heuristic function 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.
You should play against your AI, trying out your different
variants and different max levels of search, and report on the results.
You should report on how long it takes to make a move at different
search depths and mention your CPU speed.
Timing restrictions are only for the tournament.
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.
You must use debugging properly. This assignment is bigger than previous two, writting 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 game (human vs. human or AI vs. AI)
Tips on implementation
System preparation:
To use the code, you are suggested to use Windows. Otherwise you need to compile the source code yourself.
Windows:
1. Install PyQt4-4.10.4-gpl-Py2.7-Qt4.8.5-x64.exe or x32 version according to your platform here
2. 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.
3. Run the main.py in skeleton package
Mac and Linux:
1. Download the Qt 4.8.6 libraries here according to your platform.
2. Install the Qt 4.8.6 libraries
3. Download the sip 4.15.5 source code here.
4. Compile and install sip 4.15.5
5. Download the PyQt 4.10.4 source code here according to your platform.
6. Compile and install the PyQt 4.10.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 is installed, below is an example of the shell commands used on 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 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.
Turn-in
You should turn in the following within a single zip file:
- your well-commented code (ai.py)
- report describing your implementation
- a text file saying if you are willing to participate the Kalah tournament
Tournaments
The TAs will organize a Kalah tournament. This is mostly for fun, but the winners will be recognized and there will be some extra points for participating.
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 TA's machine.
The framework will time your AI execution and if you exceed 1 sec, you will be judged as loser.
Evaluation
30 points total, 15 for a working program, 10 for the report, 5 for code and comments. There's 3 extra points for participating the Kalah tournaments, and 5 extra points for winners (top 3). Tournament result. Congratulation to the winners!