CSc 180 -- Spring 2014
2014 Tournament Results - "Refusal"
The 12th Annual AI Strategy Game COntest took place April 8-10 2014.
The atmosphere was very lively, and we had many spectators in the form
of students, faculty, alumni, and previous champions and contestants.
No less than FOUR former champions were in attendance, including the
very first champion Jonathon Pullen (author of "Mr. X" in 2002), who
drove up from Los Angeles just to watch.
The game this year was "Refusal", which is a sort of reduced version
of Fred Galvin's famous chess variant "Refusal Chess". In "Refusal",
each player has the option of "refusing" the opponent's move - once
per move. When a move is "refused", the player must retract it and
play a different move instead. The rule led to wildly exciting
tactical games that were often in doubt and required sophisticated
tree searching for high quality play. Dr. Galvin himself supplied
the greeting that kicked off the event, and he followed the
development of the game and the assignment with interest.
This year there were 25 entrants. Most programs used minimax with
alpha-beta pruning and iterative deepening. Some used history tables,
killer move heuristic, and other clever sorting methods to enhance the
pruning and increase search depth. An impressive FOUR entrants this year
implemented bitboards - a difficult but highly efficient way of generating
legal moves. Three entrants implemented transposition tables with Zobrist
key hashing for even greater efficiency. Most examined several million
positions within the 5-second time limit per move. Refusal has a high
branching factor, despite which many of the programs examined 7 plies
deep, sometimes more than 10 plies later in the game. About a quarter of
the students claim that they cannot beat their own program. The programs
routinely announce forced wins to the dismay of their hapless human opponents.
Languages used this year included an approximately equal distribution of
C++/C and Java. One entrant used Perl, and another used Scheme.
As always, each match consisted of two games, so programs could lose
individual games along the way and still win by amassing more total
victories. It was a very strong field, as evidenced by the meager
6th place finish by the instructor's program "The Decider". As the
event drew to a close, it became a closely contested final round with
four programs all in contention: "Nibbles" (Ben Botto), "Minimaxploitation"
(Timothy Shea), "Intuition" (Nicolaus Clayton), and "Rocky 4" (Ethan Weidman).
In the end, it was "Nibbles" in first, with "Minimaxploitation" and
"Intuition" tied for second and only one point behind the winner.
"Rocky 4" ended up in fourth place, but was 2-0 against "Minimaxploitation".
What ultimately set "Nibbles" apart from other entrants was it's ability
to think on the opponent's time, by launching several predictive threads
while the opponent was considering its move. It lost only two individual
games over the course of the two-day event. "Nibbles" was written in C++
and utilized many of the latest features of the language.
Many of the programs improved substantially between day 1 and day 2.
Christopher Lawson's program, the cleverly-named "Galvinizer", secured
the coveted "Grand Hamster" award for the most improved program of the
tournament, winning the Hamster elimination round in its second day
of competition after faltering badly on day 1.
Complete results are shown below, including results from prelims,
eighths, quarters, semis, finals, and all consolation rounds
(finals results shown are combined with already-played semis):
1. Nibbles (Botto)...... f:4-2 s:3-1 q: 4-0 p:4-0 14-2
2. MinimaxPloit. (Shea)....... f:3-3 s:2-2 q: 4-0 p:4-0 11-5
Intuition (Clayton).... f:3-3 s:2-2 q: 4-0 p:3-1 12-4
4. Rocky 4 (Weidman).... f:2-4 s:4-0 q: 3-1 p:3-1 12-4
5. TweetleBeetle (Willis)........... s:1-3 q::4-0 p:4-0 fc:4-0 13-3
6. The Decider (Gordon)........... s:0-4 ...... p:2-0 fc:2-2 4-6
7. QuickScare (Reed)............ r2:4-0 q: 1-3 p:4-0 pc:5-1 14-4
Jackmerius (Forrest)......... r2:3-1.q: 1-3 p:2-2 pc:1-1 7-7
Varion.c (Lozano).......... r2:4-0 ...... p:4-0 fc:0-4 8-4
10. Combinatoric (Mistyuk)......... r2:2-2 p2:4-0 p:0-4 6-6
11. LegenDary (Fountain)........ r2:2-2 q: 2-2 p:2-2 pc:0-2 6-8
12. DixieFlatl. (Prior)........... r2:1-3 q: 2-2 p:2-2 5-7
Bob (Perry)........... r2:1-3 q: 1-3 p:3-1 5-7
14. NIRD (Lanier).......... r2:1-3 q: 2-2 p:2-2 5-7
Farva (Carlin).......... r2:0-4 q: 2-2 p:2-2 4-8
16. Galvinizer (Lawson)................. q: 0-4 p:2-2 H: 6-2 8-8 [GH]
17. Gandalf (Creswell)............... p2:0-2 p:0-4 H: 4-2 4-8
18. God (Thompson)............... p2:3-1 p:1-3 H: 1-1 5-5
19. System_0 (Guillot)................ p2:3-1 p:1-3 pc:0-2 4-6
Eleven (Richter)................ q: 0-4 p:1-3 H: 0-2 1-9
21. Trimaxion (Jare)................... p2:2-0 p:0-4 H: 2-2 4-6
22. Random Wins (Perez).................. p2:1-3 p:0-4 H: 4-2 5-9
Mango (Neal)................... p2:1-3 p:2-2 H: 2-2 5-7
24. LittleRefuser (Lewis).................. p2:0-4 p:0-4 H: 1-1 1-9
Super Doge (Stevens)................ q: 0-4 p:2-2 H: 0-6 2-12
As always, the top programs played very strongly throughout, certainly
stronger than their human handlers. It is doubtful that any of us authors
would place in the top 10 against this field, were we to try and match wits
with our programs. Although none of the authors incoporated a GUI into their
programs, some used color in their display to make the game easier to follow.
There were a wide variety of opinions regarding which heuristics work the
best for this game. "Nibbles" and several others played largely defensively,
trying to outlast their opponents until they ran out of legal moves. Others
took a more aggressive approach, since the game seemed so inherently tactical.
It also is unclear whether it is advantageous to move first or second, and
the authors of the strongest programs couldn't offer an opinion at the end
of the tournament in this regard.
"Refusal" was a great game and it is still far from being solved.