CSc 180 -- Spring 2012
Intelligent Systems

2012 Tournament Results - "PaoQi"

The 10th Annual CSc-180 Two-Player Strategy Board Game Programming Contest
took place the first week in April.  It featured 20 programs battling
it out in the game of "PAOQI", a newly-invented game patterned loosely
after Chinese Chess (XiangQi).  Players try to capture their opponent's
king on a 7x7 board.  The game is named after the dominant piece, the
"cannon" (or "pao" in Mandarin), which captures by jumping over another
piece to capture the enemy piece on the other side.  The two-day
competition included programs written in Java, C, and C++.

The clear winner was Mike Vollmer's "Batty".  Going into the last round,
Batty and the instructor's program "TuoLaJi" were tied for first, and Batty
would need a 2-0 win over TuoLaJi to take first outright.  It did that in
two lengthy hard-fought games.  Joshua Eiler's program "Lion" came in 2nd,
"TuoLaJi" in 3rd, and Chris Liberatore's "Prime" finished in 4th.

Interestingly, in the semifinal round, "Prime" actually beat "Batty" 2-0.
But Mike made last-minute changes to Batty, and in their rematch, Batty
turned the tables on Prime, winning 2-0.  During it's match with TuoLaJi,
Batty twice reported that TuoLaJi could win the game if it found the correct
combination.  But TuoLaJi didn't look deeply enough, failed to find the
right moves, and Batty was able to capitalize and find a win of its own.

Batty clearly had the strongest firepower amongst the competitors, 
utilizing minimax and alpha-beta pruning, iterative deepening, sophisticated
move ordering, killer move heuristic, and most notably, transposition tables
with Zobrist key hashing to search 10+ plies deep right from the opening
position.  Besides "Prime", only "Lion" was able to get a single game
off of Batty - otherwise "Batty" went undefeated.  Batty is written in C.

There were many other strong programs.  Of particular note were Sam
Fredrickson's "Yazhou" which also used transposition tables, Max Hennum's
"Smarti" which "evolved" it's heuristics.  Second-seed James Leighton's
"PaoQi Master 3000" actually had scored higher than "Prime" in the quarters,
before getting knocked out in the semis.  It ended up tying for 5th with
Enrique Salazar-Turner's "Superion".

The "most improved" program during the two-day contest was Martin Zimmerman's
"PaoCao".  It went from having stability issues and losing every match on
Day 1, to garnering a 2-0 win over a program which had scored 6-0 in the day 1
consolation round.  For this, PaoCao captured the coveted "Grand Hamster" award.

Here are the complete results, showing prelims, quarters, semis,
and finals, as well as consolation rounds:

      Program        Author         F   S   Q   P  cons-rds  total
 1.   Batty         (Vollmer)      5-1 4-2 4-0 4-0           17-3
 2    Lion          (Eilers)       3-3 5-1 4-0 4-0           16-4
 3.   TuoLaJi       (Gordon)       3-3 4-2                    7-5
 4.   Prime         (Liberatore)   1-5 5-1 2-2 5-1           13-9
 5    PaoQiMaster   (Leighton)         2-4 3-1 3-1            8-6
(tie) Superion      (Salazar-Turner)   3-3 1-3 4-0            8-6
 7.   Shui          (Alire)            0-6 3-1 3-1            6-8
 8.   NOP           (DeGough)          1-5 2-2 5-1            8-8
 9.   Cupcake       (Pace)                 1-3 4-0     6-0   11-3
(tie) Yazhou        (Fredrickson)          1-3 2-2     4-0    7-5
11.   Grapeshot     (Shaltes)              1-3 2-2     4-2    7-7
(tie) aChan29       (Chandra)              1-3 2-2     2-2    5-7
13.   Smarti        (Hennum)               1-3 2-2            3-5
14.   PaoCao        (Zimmerman)                0-4 1-1 2-4    3-9 [GH]
(tie) GreenTea      (Phong)                    2-4 1-1 3-1    6-2
16.   Soul Power    (Hachiya)                  0-2 6-0 0-6    6-8
17.   M.P.S.Purse*  (Varela)                   0-4 4-2 0-4    4-10
18.   PAI           (Vo)                       0-6 0-4 1-1    1-11
19.   AILP          (Pan)                      0-4 0-4 0-2    0-10
20.   Adramlech     (Throne)                   0-4 0-4        0-8

* full name: "Miss Pink Shoe Purse"

We had many spectators for Thursday's final rounds including the 2008
champion Tim Bender ("Time Bender"), alumnus Micheal Daniels, department
chair Cui Zhang, and various faculty and students checking out the action.
Tim and Mike both brought implementations of PaoQi.

A HUGE thanks to Dwayne Alexander (author of 2008 Grand Hamster "The Tick")
for generously volunteering his time on Tuesday.  Dwayne has kindly
volunteered to help out in this event for each of the past three years!

The game of PaoQi turned out to be a tense, strategic game in which it seems
important to reduce the value of pieces as they move down the board.  Programs
which did this often outperformed other programs that searched deeper.  It was
unlear whether moving first or second is an advantage.  And, although the
top 10 (or more) programs all regularly defeat their authors, as of yet the
game of PaoQi remains - unsolved.


2010 results