Menu

[ IVLE ]

[ Overview ]
[ Syllabus ]
[ Grading ]
[ Homework ]
  [ >HW 1 ]
  [ HW 2T ]
  [ HW 2I ]
[ Misc. ]

Homework #1: Hex

This assignment is over. You can see the scoreboard for the assignment here.

(Updated on Fri Mar 4 18:56:20 GMT-8 2005 )

Hex is a simple to understand, zero-sum adversarial game. Hex is played on a rhomboid playing field made entirely of hexagons. It is a two-player, stone-placing game, in which players take turns placing a single stone on the board per turn. The goal of Hex is to form an unbroken line of stones between the two opposite edges of the board: Player 1 tries to form a connected path between the top and bottom of the board, while Player 2 tries to form a path between the left and right sides of the board.

In its classic formulation, Hex is a game that always results in a winner and a loser (think of why that is, for a moment). In the classic game, it has been shown that the first player has a strong advantage to win, and boards of up to 7x7 have been solved (there is a winning strategy for these boards). In general, since hex is a fully-observable, deterministic game, the game can always be solved for any board size. However, in practice, the search space is very large and not amenable to complete searching.

As the classic formulation of hex gives the first player a notable advantage, we will implement the center hex move limitation, which says that the first player may not make their first move on the center hex. You should follow and read the links at the end of this description to get a better feel for the game. There is quite a bit of interesting history surrounding it.

How do you go about coding an AI to play this game? Well, as we saw in lecture, one approach is to have a utility function that assigns some value to a move in a particular position. How you arrive at this value is the tricky part: you will need to play the game and, possibly, read some of the literature on the game, in order to come up with a good evaluation function.

One of the key elements of adversarial search is the idea of being able simulate your opponent's move by using your own evaluation function in the minimax algorithm. You can use minimax with alpha-beta pruning to do just this. When you are at a leaf node, you can apply your home-brewed evaluation function to find the utility and propagate this information upwards to the ancestor nodes in the game tree.

Technical description

You will be writing an executable program that takes input on standard input, and will output the required output on standard output. Your program will be run multiple times, as it will be invoked once for every turn of the game.

Input

Any program that requires an interpreter (e.g., Java) to load your program or script will need a simple shell script to do the proper invocation. See the details of the assignment later. Your program should run without any command-line arguments and should respond accordingly to two types of input: move requests and tagline requests.

A tagline request just passes the word tagline as the first and only line of input. It is a string used by the tournament driver to identify your agent. You can put any string of printable characters ASCII characters (up to 255 characters long) to identify your agent. Do not use tabs and carriage returns in your tagline. This should be a static variable (do not change it over multiple invocations).

A move request passes the word move as the first line of input. It is then followed by the following information in subsequent lines. 

Line 2: valid temporary file name (for any state information).
Line 3: current move number and player to move.
Line 4: dimension of board
Line 5-n: the current board state.
An example is shown below: 
move
/tmp/HT000000.txt
3 1
7 7
      - - - - - - -
     - - 1 - - - -
    - - - - - - -
   - - - 2 - - -
  - - - - - - -
 - - - - - - -
- - - - - - -

The tmpfile argument specifies a name of the file that you can use to maintain state between turns. As your program is run multiple times, once for each move, you may find it useful to "remember" past computations by loading and saving states. The temporary file will not be altered by the tournament driver or the other agents between invocations of your agent. You can choose to use or not use the temporary file as you'd like. I suggest that you do not use it unless you have already finished a simple agent and are hitting computational limits.

The third line of the input board gives the turn number and the player to move. In the sample input, it is the third turn and the game agent has been invoked to place a '1' stone on the board.

The fourth line gives the board dimensions as two digits for the x and y dimensions, separated by a single space. In our games, we will always use either congruent dimensions for x and y, of values 7, 9 or 11.

The final portion of the input is the board configuration. Each place on the board will be a either a '-' (dash), a '1', a '2' or an 'X'. A dash indicates a empty spot (legal move), '1' and '2' indicate stones of the respective players, and an 'X' indicates a disallowed move (only used on the first move board for the center hex). The grid will be displayed in the same format as in the sample input: each line will have any necessary leading spaces followed by the board configuration for that row. Successive row entries will have a single space character between them.

Output

For the move command, your program will output a single line containing two integers: the x and y coordinate of your move. These are specified with an index starting at 1. For example the location of the '1' and '2' stones in the sample input above are '3 2' and '4 4', respectively. You are to separate the two integers with a single space.

Your program may not take more than 3 real-time seconds to make a move. If your program does not output a coordinate within 3 seconds, it will be terminated and your agent will be deemed to have forfeited its move. We will be running the agents on sunfire (SunOS Solaris 4), when the system's load is light.

Submission formatting

For me to grade this assignment accordingly, I need you to adhere strictly to the following submission guidelines. They will help me grade the assignment in an appropriate manner. You will be penalized if you do not follow these instructions. Your matric number in all of the following statements should not have any spaces and any letters should be in CAPITALS. You are to turn in the following files:

These files will need to be suitably zipped in a single file called submission-<matric number>.zip. Please use a zip archive and not bzip, rar or cab files. Make sure when the archive unzips that all of the necessary files are found in the current directory (please do not nest your files in internal folders). Upload the resulting zip file to the IVLE workbin by the due date: 17 Feb 05, 11:59:59 pm SGT. There absolutely will be no extensions to the deadline of this assignment. Read the late policy if you're not sure about grade penalities for lateness.

Other useful information for the assignment

I realize some of you may find useful code on the net to do this assignment. You are welcomed to use it but you must cite it and properly acknowledge it in your code and README. As stated, if you do use code from the web or elsewhere, I have the right to exempt that portion of your code from consideration in the grading (depending on how much you used in my judgment). Failure to do so constitutes plagiarism and cheating and will be severely punished.

Links to information about Hex

I guess you can all do your googling, yahooing! or altavistaing to find what you need, but here are some of the more interesting links I've come across:

Min-Yen Kan <kanmy@comp.nus.edu.sg> Mon Dec 6 10:01:55 GMT-8 2004 | Version: 1.0 | Last modified: Mon Mar 7 15:30:23 2005