Introduction to Artificial Intelligence (CS236501)
Home assignment #2
Class Tournament – Tic-Tac-N
Due date: Monday, 16.01.2006 at 12:00 noon (midday!)
Warning: Absolutely no extensions will be granted!!!
Submit your work in pairs.
Only typed (i.e., not handwritten) submissions will be accepted.
In this exercise, you will be developing and implementing a player for the Tic-Tac-N game. Your player will be tested and judged according to the criteria given below. In addition, we will hold a round-robin tournament among all players. Bonus and honor is guaranteed for the winners (see details in tournament section).
We will first give you the problem definition, followed by the requirements for your Tic-Tac-N player. After that, we willdiscuss the tournament we will be running, and methods of evaluation of your player. Finally, we’ll talk about the submission requirements, as well as some other important points of information.
The Game: Tic-Tac-N
Tic-Tac-N is a two-player game with full information. The game is played on a BxB board (B is a parameter). Each player’s goal is to generate a consecutive series of N(or more) pieces horizontally, vertically or diagonally, with no empty squares in between pieces (N is a parameter, N <= B). The white player begins the game by playing one piece on any square of the board. Thereafter the players take turns playing their pieces, one at a time, on any empty square.
Your player should be prepared to deal with boards as small as 3x3 and as large as 20x20.
What you MUST do
You should develop a Tic-Tac-N player. We require that you base your playing function on an implementation of alpha-beta search.
You must implement the following for your player:
1. Heuristic
2. Time Policy
1. Heuristic
The heuristic function is important, as it is responsible for evaluating various boards in your game tree. Your heuristic function should take two parameters (board and color), and it must return a heuristic value for the board. Given that the current color is white, for instance, a higher heuristic value signifies a better state for the white player. Remember that your heuristic function should take into consideration the actual game parameters: board size (B) and winning sequence length (N).
You should discuss the pros and cons of the heuristic function you designed. If your function makes use of specific numerical constants, you should explain their choice as well.
2. Time Policy
Your player will be allocated an upper time limit for each move. This value will be provided to you at the beginning of each game, and will change between the runs. You should be prepared to deal with values as small as 0.1 seconds per move, and as large as 5 seconds per move (however, during the tournament we may use values smaller or larger than these examples). If your player uses more time than allocated, it loses the game. We will not tell you ahead of time (before submission) what the allocated time will be.
Players that enter infinite loops will be disqualified.
Optional enhancements
You must implement one of the following enhancements to your player:
1) Node ordering: The idea is to reorder the successors according to some heuristics, in an attempt to decrease the effective branching factor for alpha-beta. This allows you to search in deeper trees. Think how you can use previous iterations to achieve better reordering.
2) Quiescence: The general idea behind quiescence-based selective deepening is to deepen the alpha-beta search as long as the difference between the evaluation of a parent and its successor is above some predefined threshold (as a result, the search tree is no longer of uniform depth).
3) Transposition tables: The search graphs of many games contain multiple paths to the same state (for instance, reaching the same node by making the same moves in a different order). By detecting that a state has already been searched, you can avoid re-searching it. One approach is to have a table of (some of) previously searched states with their minimax values, in what is called a transposition table.
In your documentation, specify what option you chose to implement, give details about your implementation, and explain the design and implementation decisions you have taken.
In addition, for the chosen option, you’re required to conduct a parametric research, as explained in the next section.
Parametric research
For the options you chose to implement, you have to report the results of a small parametric study: run self-tournaments of your players, when one player does not use the researched option, while others use it with different parameters. Submit the results of this mini-tournament, compare them graphically, discuss the interesting points, and summarize your findings.
Below are some examples of possible parameters you may examine. However, you’re free to choose other relevant parameters to experiment with:
1) Node ordering: the amount of time allocated for the ordering
2) Quiescence: the value of the threshold
3) Transposition tables: the size of transposition tables
The Tournament
A number of automatic tournaments (with different game parameters, i.e., move time, winning sequence length, and board size) will be performed among your players. Results of the tournaments will be available for the class. The first place winner of the tournament will get a bonus of 7 points toward the final course grade. The second place will get a bonus of 5 points toward the final course grade, and the third place will get a bonus of 3 points.
Please Note: The tournaments are done only FOR FUN! The player that scores first place in a tournament will not necessarily receive a good grade for this assignment. Please focus on the important aspects of the exercise, and consider the tournaments an added bonus!
Implementation details
You can implement your player in either C, C++ or Java. For the purpose of this assignment only, you MUST compile your program on CSL1, and submit this very executable – this will ensure all submissions can run on the very same platform.
è If you don’t have an account on CSL1, you’d better apply for one NOW !
Since we’ll be running your program as an executable (or a Java class file), all input/output will be performed through stdin/stdout + command line parameters.
Command-line parameters:
-bzise <board size>
-n <length of winning sequence>
-time <time per move in msec>
-color <your color [white/black]>
Invocation example: my-player -bsize 17 -n 7 -time 10 -color white
Input/output:
For each move, you program will receive a string representing the current board state as input from stdin, and will produce to stdout a string with the new board state (after your move). You program will not be run anew for each move in order to allow you to maintain data structures throughout the duration of the game. Instead, you program will be run once for an entire game, while we periodically send it the input for the next move (current board state), and monitor its stdout for the board updated with your move. To stop you program, we will send it (to stdin) an input string “end” (without quotes) – in such a case, your program should print “end” (again, without quotes) to stdout, and exit.
Board format:
The board is given as one long string, which contains the rows of the board in consecutive order. Each row has the number of characters equal to the board size, while each character may be either
- ‘b’ for black piece
- ‘w’ for white piece
- ‘.’ (dot) for unoccupied cell
Examples:
1) an empty 3x3 board looks like this: "...... "
2) a winning 3x3 board looks like this: "bbb.w.w.w"
The file player_template.cpp provides a generic template that you can use to model your player. This template is not a working program, but is merely intended to give you a general idea of how your player should look like to conform to the above specifications; obviously, there are many alternative ways to build your player.
Note that this implementation format is important only for the participation in the tournament. You can use any alternative (and less complicated) implementation in order to perform the parametric research described above.
Submission Instructions
Program Submission:
You should use the GR++ submission mechanism. Please note that this mechanism will strictly enforce the submission deadline. Submit your executable (or Java .class file) compiled on CSL1. Remember: your code should be self-contained, i.e., if you use any dynamic libraries (shared objects), triple check that they’re available AND world-readable on CSL1.
Your player should have an interesting one-word name (letters only, no spaces). The name of your executable must be identical to your player name. The program submission should include a single file, which is either your executable or a Java class file.
Hard-Copy Submission:
A printed report (English or Hebrew) describing your program, which should include:
· A description of your playing methods. Why do you think they are good?
· A full description of the program and the various algorithms and data structures.
· A program listing (your very well documented code).
· A description of the option you chose to implement and research.
· A description of the parametric research setup + graphical and verbal presentation of the results.
Submit your work in pairs. In order to find a partner, you might take advantage of the “Find a partner” mechanism available on the course Web page at http://webcourse.technion.ac.il/236501 (see buttons on the left).
Good luck, and may the best player win !
General questions about the assignment: Evgeniy Gabrilovich (gabr@cs)
Technical questions about the implementation and the tournament: Nela Gurevich (nelka@cs)
Flames? /dev/null
Note:
Before sending your question by email, please make sure you’ve checked the “Updates and FAQ” section of the course web site (http://webcourse.technion.ac.il/236501, Assignments -> ex1 -> Updates and FAQ). We will not respond to emails when the answer is available at the FAQ page!