CS63 Lab 3: Konane Tournament

Held on Friday, Sept. 30, 2011

Students implemented the minimax algorithm with alpha-beta pruning, and developed their own static evaluators for the Hawaiian checkers game known as Konane. Each Konane player was limited to searching to depth 4, and had to return a move within a specified time limit. If a move was not returned within the time limit, then a random move was chosen for that player.

We held a tournament where each Konane player played every other Konane player in the tournament twice, one time going first and the other time going second. Each player received a +1 for a win. The winner of the tournament was determined by the cumulative score over all of the games. It was possible to have multiple winners.

The field of players also contained a set of control players for comparison purposes:

• Random: Chooses a random move each turn.
• Simple: Chooses the first move option each turn.
• ControlMinimaxDepth2: Used minimax, but only searched to depth 2. Used a static evaluator based on the number of moves each player had.
• ControlMinimaxDepth4: Used minimax and searched to depth 4 using the same move-based static evaluator.
A correct minimax player searching to depth 4 should always be able to beat Random and Simple. However, the move-based static evaluator is quite effective, so even a correct minimax player may not be able to beat ControlMinimaxDepth2 and ControlMinimaxDepth4.

Andrew Stromme developed parallelized tournament code to take advantage of our lab machines that have 16 processors. This led to a significant speed up, allowing us to run the entire tournament several times. Runs 1 and 2 had a time limit of 10 seconds per move. Run 3 had a time limit of 20 seconds per move. Surprisingly the ControlMinimaxDepth4 player won the first run, but subsequent runs saw the top teams change finish order each time.

In the results shown below, the players in the tournament are displayed in a grid. Each row of the grid shows how the player in the leftmost column did against all of the other players in the tournament. The color of a box indicates the results of the two games played between those players. Green indicates two wins, yellow indicates one win and one loss, and red indicates two losses.

Run 1 (10 second time limit)
Run 2 (10 second time limit)
Run 3 (20 second time limit)
Run 4 (10 second time limit)

After the tournament, it was discovered that a number of students had subtle bugs in their minimax algorithm. After all of these bugs were fixed, the tournament was re-run one last time with the following results. Notice that all teams now successfully defeated both Random and Simple.