CSc 180 -- Fall 2008
Intelligent Systems


2008 Tournament Results - "Sidestep"



The 7th Annual AI Strategy Game Contest took place Nov 3-5 2008.
The atmosphere was lively, and we had many spectators.  The game this
year was "Sidestep", which is a sort of reduced chess, with some unusual
features: (1) the king can only move sideways, (2) there are four
pieces roughly equivalent to the queen, (3) there are five "pawns",
and (4) a king is allowed to capture its own pieces!  A player wins by
capturing the opponents king.  The name of the game is derived from the
limitation on how the king can move - a sidestepping maneuver which leads
to some particular strategies for entrapping it.  I would like to thank
Marcus Watstein for helping run the event, and also to Johnny Duong for 
helping to proctor some of the programs.  They helped make the event
run very smoothly; we even finished on time!  Also a big thanks to the
ACM for again helping generate interest in the event.

The competition was extremely close, and the final decision was not
known until the last round.  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.  In the end, the clear winner was Tim Bender's
program "Time Bender".  But going into the final round, Dr. Gordon's program
"The Surgeon" had a slight lead, and Time Bender could only win if it
defeated The Surgeon 2-0.  It did just that, drawing a huge sigh of relief
from Tim as his program eeked out the narrow victory.  In a close third,
and securing one of the few wins over Time Bender along the way, was "Fiend"
by Sterling Schulkins.  The only other program able to get a win over Time
Bender during the tournament was Lolwut9000.  But it wasn't enough to make
the final round, and finishing in fourth place was "Napolean" by Morgan
Darke, who defeated Lolwut9000 2-0.

Time Bender was written in Java.  This is a bit of a milestone, as it is
the first time that a program written in Java has won this event.  Time Bender
utilized minimax with alpha-beta pruning, iterative deepening, and a unique
variation on history tables that allowed it to search 8-10 plies deep within
the 5 seconds allotted per move.  The search algorithm was so clever that it
actually succeeded in searching deeper than other programs that were faster
and utilized more efficient bitmapping for move generation.  It was a triumph
of clever pruning over brute force.

Complete results are shown below, including results from prelims,
quarterfinals, semifinals, finals, and all b/c consolation rounds:

 1. Time Bender  (Bender)..... f:5-1 s:3-1 q:3-1 p:4-0
 2. Surgeon      (Gordon)..... f:4-2 s:3-1 q:4-0
 3. Fiend        (Schulkins).. f:2-4 s:2-2 q:3-1 p:2-0
 4. Napolean     (Darke)...... f:1-5 s:2-2 q:3-1 p:4-0
 5. Lolwut9000   (Bolles)........... s:1-3 q:2-2 p:4-0
tie W.O.P.R.     (Walker)........... s:1-3 q:2-2 p:2-0
 7. BananaHammik (Stofle).......... sq:1-3 ..... p:2-2 bx:3-1,4-0
 8. Boardbot     (Kodani)................. q:0-4 p:4-0 bx:7-1
 9. Content      (Alva)................... q:0-4 p:3-1 bx:4-4
10. Chuck Norris (Reynolds)............... q:1-3 p:4-0 bx:4-4
11. Hal9000      (Edwards)...................... p:2-2 bx:3-1,1-3,3-5
12. WeakestLink  (Linden)....................... p:2-2 bx:4-0,2-2,2-6
13. Profector    (Eden)......................... p:0-2 bx:2-2 cx:5-1
14. GraveDigger  (Lott)......................... p:1-3 ...... cx:4-0,4-0
15. B.Ri.S.K.    (Griffin)...................... p:1-3 bx:3-1 cx:4-2
16. SnakeHammer  (McNeal).................................... cx:6-2
17. RushHour     (Coggeshall)................... p:2-2 bx:0-4 cx:4-2
18. MirrorStep   (Olivera)...................... p:2-2 bx:0-4 cx:4-4
19. Grimus       (Rogers)....................... p:1-3 bx:1-3 cx:2-4
20. The Tick     (Alexander).................... p:0-2 bx:1-3 cx:2-6
tie CannonFodder (Yamada)....................... p:0-4 ...... cx:0-4,3-5
22. Princess     (Slater)....................... p:0-4 ...... cx:2-2,3-3
23. The Imp      (Garibaldi).................... p:0-4 ...... cx:3-1,2-6
24. Beattle      (Yevsyukov)................................. cx:1-1,1-1
25. Shatranj     (Srivistava)................... p:0-4 ...... cx:0-2
26. ChessMeister (Duong)............................................

As always, there were numerous funny bugs and other unexpected hiccups
displayed by some of the competitors.  "The Imp" would often play through
most of the game, then prematurely announce that it had lost.  "Mirrorstep"
would occasionally capture its own pieces.  "Beattle", "Tick", and "Grimus"
required repairs throughout the event.  Even the 5th place "W.O.P.R." played
illegally at a crucial moment.  Once again, the coveted "Grand Hamster"
award was bestowed on the program that won the C consolation elimination
series - this year for the first time it was a tie, between "The Tick" and
"Cannon Fodder".

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 such a powerful field.  Also, special note
should be made regarding the wonderful graphics in Matthew Alva's program
"Content" - by far the nicest user interface this year (and one of the
stronger programs, too!).

The game itself had a considerably larger branching factor than has
been the case in years past.  With a branching factor of about 20, most
programs were lucky to search 5 or 6 plies deep in the early stages.
There were a wide variety of opinions regarding which heuristics work
the best, and it is still unclear whether it is an advantage to move
first or second.  For now, the game is still far from being solved.

    

2007 results