Recursive Tree Search and AI Applications

GREAT TIGER Tournament
University of Science & Technology Beijing

---

Summer 2014 Results - "4-in-a-Row"

The AI Strategy Game Contest took place July 4, 2014 at the University
of Science & Technology Beijing.  The atmosphere was very lively,
and we also had a few spectators.  The winning program would earn the
title of "Great Tiger", and be presented with the coveted plush tiger
in an in-class awards ceremony.

The game that students were tasked with implementing was "4-in-a-Row",
which is a slightly simplified form of "Go-Moku", where players take turns
placing stones on an 8x8 board, until one player achieves four in a horizontal
or vertical row, diagonals not counting.

Students had only 3 days to prepare their programs for the tournament, which
meant that those who participated spent many hours outside of class, in the
lab and at home, to create competitive programs.  Although the game itself is
relatively simple, developing a program that can both play the game and defeat
other programs (and humans) in just 3 days is a hard challenge!  Despite this
short timeframe, the best programs utilized minimax with alpha-beta pruning,
killer move heuristic, and clever sorting methods to search millions of nodes
within the 5-second time limit for making a move, in some cases searching 7
or more plies deep.  This was impressive given the high branching factor for
4-in-a-Row.  Although none of the programs played perfectly, the best programs
often defeated their human developers.

Eight (8) students developed programs for the competition.  All of the
programs were written in C++.  By the day of the competition, two of those
programs weren't sufficiently stable to compete.  The remaining 6 programs
played a series of matches against each other.  Each match consisted of two
games, so programs could lose individual games along the way and still win
by amassing more total victories.  Final standings are shown below:

     program          author         Score 
   ----------------------------------------
 1. Smart Tiger     (Zhang YanFei)     7
 2. Big Game Hunter (Cui Can)          5.5
 3. Trial           (Liu Liwen)        4.5
 4. Typhoon         (Zhen Ye)          3
 5. Desert Eagle    (Wang Xian Qiang)  1
 6. 915             (Huang Jian)       1
 7. Sunshine        (Odmaa)

"Smart Tiger" was the clear winner, losing only 1 game in the entire
tournament (to "Trial").  Smart Tiger, developed by Zhang YanFei, used all
of the techniques described above, plus a clever technique of using a smaller
size board during the first few moves to reduce the branching factor.  It
searched 7 plies deep and was very stable.  Also worth noting is "Typhoon",
developed by Zhen Ye.  Typhoon was probably the most sophisticated program -
in addition to the techniques mentioned earlier, Typhoon also incorporated
iterative deepening and history tables to achieve the greatest search depth
of all the entrants... it was the favorite going into the tournament, but
turned out to be less stable than "Smart Tiger".

Students discovered that it is a big advantage to move first in 4-in-a-Row.
If you download Smart Tiger (above), try letting it move first - it is very
difficult to beat if it moves first!

Of the 60 students in the 4-day AI course, those who took on this extra
challenge are to be commended.  They put in extraordinary effort to produce
very impressive and intelligent game programs, and held a tournament amongst
their creations, all in only 3 days - a remarkable achievement!

Here are some more pictures taken during the tournament: