The Second International RoShamBo Programming Competition

[rock crushes scissors] [paper covers rock] [scissors cuts paper]


Standings | Report | Crosstables | Ratings | Links


last updated: March 20, 2001.

And the winner is:

***   Greenberg   ***     by Andrzej Nagorko

 

The winner of the mini-bot competition is:

***   Membot   ***     by Doug Meserve

 

Both of these gentlemen have written excellent Rock-Paper-Scissors players that dominated their respective categories.

The field was very strong, but Greenberg clearly demonstrated that it was a cut above the rest. MemBot finished a remarkable fourth overall, behind Doug's main entry, MEMinator, and in a virtual tie with last year's champion, Iocaine Powder by Dan Egnor. Doug also wrote LittleMemBot, which is only nine C statements long, but still would have won the mini-bot competition!

In the match-play component of the competition the top ten finishers were all competitive, with Greenberg and MEMinator tying for highest honours. That result was overturned in the "Best of the Best" series, as TinyMetaDave by David Ozenne and Land War in Asia by Jeff Wilkinson eventually rose to the top, against progressively stronger opposition. TinyMetaDave was another entry in the surprisingly tough mini-bot category (40 statements or less).

The round-robin event wasn't as close, with Greenberg winning by an impressive margin, ahead of General Predictor by Don Beal. Greenberg's decisive victories against certain opponents, and overall aggregate score, make it clear that it is the best RoShamBo program to date.

Several thousand Swiss-system tournaments were also conducted to compute numerical ratings, like those in chess, using a program provided by Michael Gherrity for this purpose. Although emphasizing match-play strength rather than margin of victory, Greenberg again emerged as the highest rated player. Eight programs have now achieved master status.

On average, the Second International RoShamBo Programming Competition produced much stronger programs than the first. For instance, improved versions of MegaHAL and Russrocker4, which finished 3rd and 4th in the first contest, were relegated to 19th and 22nd in this year's event; and Roshambot_Off dropped from 9th place into the bottom half of the crosstable. This is a natural progression, of course, since this year's contestants had the advantage of a strong test suite, comprised of last year's best programs.

Tournament Crosstables (full and abridged).

 
Overall Standings

Rk C Program Name Rtg Pts MP Agg Author Name (Country)

1 Greenberg 2307 9268 +53 +993 Andrzej Nagorko (Poland) 2 MEMinator 2284 7110 +53 +885 Doug Meserve (USA) 3 Iocaine Powder 2267 6960 +47 +818 Dan Egnor (USA) 4 s MemBot 2244 6352 +50 +817 Doug Meserve (USA) 5 General Predictor 2206 7807 +39 +780 Don Beal (England) 6 s TinyMetaDave 2208 5570 +48 +758 David Ozenne (USA) 7 Harmless 2178 6526 +39 +716 Steve Dowland (England) 8 Land War in Aisa 2234 5452 +44 +712 Jeff Wilkinson (USA) 9 Philby 2173 6846 +35 +692 Philip Dunstan (Australia) 10 ZQ Bot 2163 5631 +39 +671 Neil Burch (Canada) 11 s SonOfPsychoRock 2091 5549 +35 +627 Petit and Clement (Canada) 12 Rashomon 2134 5931 +32 +616 Johannes Fuernkranz (Austria) 13 s Black Box 2143 5834 +32 +611 Perry Peters (USA) 14 ACT-R Plus 2140 6102 +29 +595 Lebiere, West, Bothell (USA) 15 s AbRasiF 2148 5020 +34 +591 Etienne Clement (Canada) 16 Roshambot 2178 3414 +40 +570 Perry Friedman (USA) 17 Hexbot 2095 5588 +23 +509 Dr. Simon Ronald (Australia) 18 s Griffin 2091 4447 +28 +502 Martin Lechowicz (Poland) 19 MegaHAL-DB 2060 6232 +13 +441 Jason Hutchens (Australia) 20 s PredictorArrayBot 2089 4445 +20 +422 George B. Moody (USA) 21 Two Bit Matcher 2064 4971 +16 +408 Mark Delano (USA) 22 Russrocker5b4 2022 4971 +15 +398 Russ Williams (USA) 23 Paper Chase 2051 4753 +16 +397 John Reeves (Australia) 24 s Buffy: Wonder Dog 2016 4721 +10 +336 Kevin Little (USA) 25 LZ Bot 1990 4351 +7 +287 Emin Martinian (USA) 26 s Mini LZ Bot 1919 4279 +6 +273 Emin Martinian (USA) 27 BillBot 2004 4695 +2 +254 Bill McCollam (USA) 28 d DeBruijnize5 1928 234 +24 +251 29 Gypsy 1953 4755 +1 +247 John O'Laughlin (USA) 30 s The Tao 1993 2103 +14 +245 Mike Krell (USA) 31 s ACT-R Lag2 2011 3236 +8 +241 Lebiere, West, Bothell (USA) 32 s Little Boy 1988 3442 +5 +222 Mark Delano (USA) 33 Immanuel Kant 2011 3770 +3 +218 Nikos Kastellanos (Greece) 34 d DeBruijnize4 1914 206 +17 +180 35 s Henny 1827 1260 +6 +123 Johannes Fuernkranz (Austria) 36 LZDIFF 1926 3107 -4 +115 Michael Callahan (USA) 37 Shrub 1920 3789 -11 +79 Ghislain Lemaur (Belgium) 38 GNADS^2 1918 2757 -11 +27 Denis Papp (Canada) 39 LZ 1889 1995 -10 0 Michael Callahan (USA) 40 LZADAPT 1877 2312 -12 -4 Michael Callahan (USA) 41 d Random (Optimal) 1800 -7 -1 -10 42 s Mixed Strategy2 1811 1451 -21 -137 Thaddaeus Frogley (England) 43 s N Groups 1849 -867 -16 -203 Mike Chartier (USA) 44 Cycles 1751 -362 -23 -248 Bob South (Canada) 45 Roshambot_Off 1894 -1084 -20 -254 Perry Friedman (USA) 46 d Add-Mix2 1678 -1242 -26 -322 47 Sikandarbot 1639 -1257 -30 -362 Jonathan Herr (USA) 48 s Littlestone 1656 924 -41 -363 Johannes Fuernkranz (Austria) 49 s El 1679 32 -39 -388 El Howard (USA) 50 s DrDeductor 1790 -2868 -26 -403 Gaspard Petit (Canada) 51 Vorpalbot 1636 -1904 -36 -455 Marc Raaphorst (Canada) 52 d Add-Mix 1586 -1983 -36 -459 53 s melPlayer 1615 -2080 -38 -484 Mark Lehr (USA) 54 d Shift-Rotate 1534 -1777 -44 -528 55 d Foxtrot2 1586 -2918 -42 -565 56 d Flip-Flop S/F 1541 -3139 -42 -576 57 d Flip-Flop R/B 1457 -2228 -48 -591 58 s Amalgam 1590 -3993 -40 -599 Godfrey Duke (USA) 59 Newton 1708 -7419 -28 -650 El Howard (USA) 60 RoShamBort 1.0 1856 -4088 -52 -724 David Hensley (USA) 61 s WeightedFreq 1423 -27726 -50 -1886 Karl Groethe (USA) 62 s Mouse 1614 -31560 -40 -1978 Brian Nelson (USA) 63 Robbot 1494 -37623 -43 -2311 Robert Pope (USA) 64 s Rock'em Sock'em 1342 -52074 -53 -3133 Jason Schlauch (USA)

Exhibition events (post-deadline or did not qualify):

-- x Land War in Aisa 2234 +6067 +50 +803 Jeff Wilkinson (USA) -- x Concat unr +7469 +40 +773 Michael Callahan (USA) -- x NeuroHog 2180 +5748 +37 +657 Frank Nestel (Germany) -- x Bitlbot unr +3857 +16 +353 Jewell, Setchell, Pope (UK) -- x SMAC Bot 1856 -73 -16 -164 Beaufils, Mathieu (France)

Legend: Overall Rank, Class (open, small, dummybot or exhibition), Program Name, Rating, Round Robin Score, +/- Match Play Score, Aggregate Score (formula: Agg = Pts/20 + MP*10), and Author

 

[rock] [paper] [scissors]

 

Statistics vs Direct History

To date, two major approaches have been used to produce strong RoShamBo players: purely statistical techniques, and the "direct history" method.

The statistical approach, which can be thought of as generalized pattern matching, is intuitive and popular. Programs based on this method include MegaHAL and Simple Predictor. In contrast, "history bots" like Iocaine Powder and Phasenbott search for specific patterns, matching the current context with the best fit occurring previously in the match. They also encorporate the notion of "Sicilian reasoning" (i.e. the six levels of meta-reasoning for any particular prediction method). This was very successful, and they easily outdistanced the other competitors in the first contest.

Naturally, many of the entries in the second contest were modeled on Iocaine Powder. Somewhat surprisingly, Dan Egnor's original program still finished third overall, despite the fact that everyone had access to documented source code, plus a nice description of the underlying ideas.

Trying to beat Iocaine Powder is a daunting task, and many people did not enter because of the difficulty of writing a competitive bot. In fact, there was only a modest increase in the total number of entries for this year's contest, despite a much broader exposure (there were over 20000 visitors to the website after an announcement on SlashDot). The presense of a strong champion, and the realization that the problem is not trivial, probably discouraged dozens of would-be participants.

Of course, it was not necessary to defeat Iocaine Powder directly (it turned out to be possible to win by a small margin, but that alone is not sufficient to ensure a high finish). It is much more important for a program to be more successful against the rest of the field. This wasn't a minor challenge either, and the authors who succeeded can be proud of their accomplishment.

Several participants read Dan Egnor's description of "Sicilian reasoning", and incorporated that into their own programs. But ironically, this may not be the main strength of Iocaine Powder. Less appreciated, but at least as important, is the direct history algorithm which provides a powerful predictor as a foundation. To fully understand this aspect of the program, one must dissect and analyze the actual code.

The most obvious "direct descendant" of Iocaine Powder was Greenberg. Andrzej Nagorko clearly understood the algorithm at its lowest level, and constructed an improved version using a number of new ideas. This is not easy, as the embellishments must be fully integrated, rather than just added piece by piece. (This point is clearly demonstrated by Michael Callahan's meta-program Concat, discussed below).

Doug Meserve developed a new history matching method that was the basis of MEMinator, which finished second overall, and MemBot, which won the mini-bot competition. The technique, which he calls "associative memory", is a faster and more compact method for specific pattern matching. In fact, a toy version called LittleMemBot, which does not use "Sicilian reasoning" and is only nine C statements long, still would have won the mini-bot competition in MemBot's place! This very elegant procedure will be discussed in more detail later.

Before the competition, one might have speculated that the given methods of direct history and meta-reasoning would be difficult to improve. That suggests that the most significant improvements would come from better statistical analysis (which can always be refined further). Don Beal's General Predictor was a healthy step in that direction. It was written immediately after the first competition, and played on par with Iocaine Powder despite being purely statistical in its approach. This is an intriguing result, and suggests that future RoShamBo players should not neglect this aspect of good strategy.

Nevertheless, the primary reason for the success of Greenberg and MemBot were improvements to the direct history approach. It seems that there is room for future improvement in this form of analysis as well. It should be feasible to overtake the new champions by synthesizing the best of both worlds, but that will likely be an even tougher chore than it was to outperform Iocaine Powder. The magnitude of improvement may also decrease, so we may be approaching a point of diminishing returns in the strength of computer RoShamBo players.

 

Bigger is not better!

The RoShamBo programming competition is a contest of algorithms. The best ideas have been expressed with short, elegant implementations. While a sophisticated algorithm will generally outperform a simplistic one, the best players have all been written with striking economy and efficiency.

In this year's contest, several authors wrote a smaller version of their submission, or a second entry to qualify for the mini-bot side competition. In a number of cases, the smaller program performed comparably, or sometimes even better than the full-sized version. Specific examples include Mini LZ Bot vs LZ Bot (26th, 25th), El vs Newton (49th, 59th), and Henny vs Littlestone (35th, 48th). MEMinator was the fourth largest program in the tournament, but it outperformed its predecessor, MemBot, by only a small margin (albeit an important difference in the final result).

Another good RoShamBo player, finishing tenth in two exhibition events, was NeuroHog, by game designer Frank Nestel. This program is a complex composition of ideas, starting as a neural net and later evolving to encorporate pattern recognition, online learning, and adaptive parameter optimization. It is over 700 lines, and pushes the limits of time and memory utilization. Unfortunately, added complexity often carries hidden costs, and a sporadic memory overwrite error caused occasional segmentation faults. We failed to track down the bug despite numerous attempts, and it had to be relegated to the unofficial events.

The exhibition program Concat weighs in at over 3000 lines, including copies of selected bots from the first test suite. It did well, but not nearly as well as one might have expected, given the nature of this meta-program (more on this later).

However, the grand champion of oversized programs was unquestionably Bitlbot, produced by a trio of computing science graduate students in Bristol, England: Nigel Jewell, Chris Setchell, and Jackson Pope. They built a large neural network, and packaged it up in a submission that was more than 22000 lines in length, with over 88000 commas and 1600 C statements, and requiring more than 1.2 megabytes of disk storage. While predominantly filled with large tables of numbers, the sheer mass of this program exceeded all other submissions from the first and second competitions combined.

Unfortunately (or fortunately, depending how you look at it:), Bitlbot did not qualify because it required twice the allotted time on average. In an exhibition event, it was an above average player, but did not rank among the top contenders, finishing 29th in points and 24th in match-play. I expect these three authors are quite knowledgeble about the construction of neural nets, but it may not be a particularly viable technique for computer RoShamBo players.

At the opposite end of the scale were the top mini-bots: MemBot, LittleMemBot, TinyMetaDave, Black Box, SonOfPsychoRock, and AbRisiF, all under 40 C statements in length. Add to that list Doug Meserve's latest creation, TinyMemBot which is only five C statements, and may be stronger than LittleMemBot, at least in match-play.

But the winner in the "most for the least" category is the very cute one-liner called, appropriately, Henny, by Johannes Fuernkranz:

int henny() {

  return((*opp_history?opp_history[random()%*opp_history+1]+1:random())%3);

}

This is a solid positive expectation RoShamBo player, in both point collection and match-play. It narrowly missed the cut for the top 16 in the "Best of the Best" series, and might have gone much further with a bit of luck. What it does is left as an exercise to the reader.

 

Programs and Authors

[ to be continued (soon) (or not) -drb ]

 

[rock] [paper] [scissors]

 
Related Links
The First International RoShamBo Programming Competition

(Sept 1999)   Announcement and Rules   Results (Part 1)   (Part 2)

The Second International RoShamBo Programming Competition

(July 2000)   Announcement and Rules   Crosstables (full)   (abridged)  

the first test suite includes almost all of the top programs from the 1999 contest!
(compile with:   gcc rsb-ts1.c -lm  )
the sample program is a smaller version (with only "dummy bots").
frequently asked questions (FAQ) about the programming competition details.
ratings have been computed for all programs in the first two competitions, using a program provided by Michael Gherrity, based on the Glicko rating system used for chess.
two articles on the first competition are published in The International Computer Games Association Journal (ICGAJ, Vol. 23, No. 1, March 2000).
an article also appears in The Mind Sports Olympiad's "Mindzine".
check out the World RPS Society, home of:
The Official Rock Paper Scissors Strategy Guide
a Rock vs Paper vs Scissors Grudge Match was held, resulting in an overpowering victory for...

 

[rock] [paper] [scissors]


Standings | Report | Crosstables | Ratings | Links


GAMES Group U of A GAMES group

You are visitor to this page since June, 2000.