Gridwars

Gridwars (aka GRID WARS) was a programming contest announced in November 2002 by Engineered Intelligence (EI) [ [http://www.supercomputingonline.com/article.php?sid=2908 Supercomputing Online - Homepage for the World′s High-Performance Computing, Networking & Storage Professionals ] ] . The competition was devised to promote EI's product called CxC (a parallel programming language) introduced the same day [ [http://www.supercomputingonline.com/article.php?sid=2909 Supercomputing Online - Homepage for the World′s High-Performance Computing, Networking & Storage Professionals ] ] . Gridwars was also announced in selected forums and through personal invitations. [ [http://www.xent.com/pipermail/fork/2002-December/016093.html [Fwd: EI & Gridwars Championship ] ]

Four contests were held in total: in February 2003, in June 2003 (Gridwars II), in November 2003 (Gridwars Interactive), and in April 2004 (Gridwars III).

EI was founded by Matt Oberdorfer; in the late 2005 EI discontinued CxC and announced a new product called "I/O accelerator". In the early 2006 EI changed name to Gear6 and replaced Gridwars front page with the announcement of discontinuation. Shortly after the web site www.gridwars.com was shut down.

Game concept and core rules

The game is played on a board aka "battlefield" -- orthogonal grid of given size drawn on a torus (thus opposite edges of the field are in contact).

Each cell of the battlefield can be either empty or owned by one of several codes competing for the cells of the battlefield. The code which manages to take over the battlefield or owns most cells after a specified number of cycles is the winner.

The original terminology used by EI was peculiar in that it referred to the competing codes as "the warriors" and to the cells as "processors" of a virtual computing grid (hence "the battle for processors") capable, however, of "firing bullets" at each other.

The game proceeds in turns (cycles). At the beginning of the game, each code owns one cell. Every cycle, codes are executed for cells they own. As it happens, framework program supplies the codes with some data: who are the cell's eight immediate neighbors (by warrior number, 0 for free cell) and its own warrior number. Based on this data, warriors can "fire three bullets" at one/two/three of its 8 neighbors. Gridwars II introduced a principal extension of original rules: warriors could now return 32-bit word, called communication variable or comvar for short, which framework program would supply to each of its 8 neighbors during the next cycle of battle execution.

After all of the cells made their shots, control program evaluates how many bullets in total arrived at every cell from the neighboring warriors, i.e. cells executing the same code. Whichever warrior sends more bullets at the cell (and not less than three in total), takes it over. In case of a tie, cell ownership remains the same.

In principle, the game can be played without a computer: on a board whose size is small enough to make it fun. Players can use private boards or paper to specify shooting directions for all of their cells and then show the shots and update the board together.

Alternatively, firing directions can be specified on the main board in the cell-by-cell manner (using matches, for example), opponents taking turns.

Winners

With the exception of Gridwars Interactive, top three finishers in each competition were honored in EI's press releases and received prizes provided by Hewlett-Packard who sponsored Gridwars (pocket PCs, digital cameras, printers, and 5-node Xeon cluster to the winner of Gridwars III).

Gridwars [ [http://www.gridtoday.com/03/0428/101349.html Gridtoday: Grid Wars' Victors Emerge ] ]

1. Scott Balaban (Cleveland, Ohio)2. John Ours (Cleveland, Ohio)3. Robert Macrae (London, UK)

Gridwars II [ [http://www.hoise.com/primeur/03/articles/monthly/AE-PR-08-03-36.html Russia wins Grid Wars 2 ] ] [ [http://www.hpcwire.com/hpcwire/hpcwireWWW/03/0718/105560.html Ei Announces Winners Of Grid Wars Challenge At Clusterworld ] ]

1. Vasiliy Gromov (Moscow, Russia)2. Mark Wenig (Maryland, USA)3. Robert Macrae (London, UK)

"MEGA GRID WARS" league of Gridwars II

1. Robert Macrae (London, UK)2. Paul Klinge (VTT, Finland)3. Shanming Loh (Singapore)

Gridwars III [ [http://www.hoise.com/primeur/04/articles/monthly/AE-PR-04-04-21.html Grid Wars III ] ] [ [http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0312/107193.html Win An Hp Proliant Cluster In The Grid Wars Iii Challenge ] ] [ [http://www.prweb.com/releases/2004/4/prweb119447.htm EI Announces Winners in the GRID WARS III Parallel Programming Challenge ] ]

1. Mark Wenig (Greenbelt, Maryland, USA)2. Paul Klinge (VTT, Finland)3. Chris Mueller (Katy, Texas, USA)

In the interests of objectivity, table below provides additional details with regard to participation.

There were reports in the forum that certain codes from a prior competition were resubmitted for participation by EI, and available information of this kind is taken into account.

Press and media

The event that attracted most attention from the press was, by far, Gridwars II. In particular, the final battle between programs written by Vasily Gromov and Mark Wenig:

New Scientist: "Gladiator-style 'wars' select out weak programs" [ [http://space.newscientist.com/article/dn3922 Gladiator-style 'wars' select out weak programs - 12 July 2003 - New Scientist Space ] ]

New Scientist: "Russian programmer defeats NASA in code war" [ [http://space.newscientist.com/article/mg17924031.300-russian-programmer-defeats-nasa-in-code-war.html Russian programmer defeats NASA in code war - 12 July 2003 - New Scientist Space ] ]

BBC Russian: "NASA programmer was bitten by Cobra" [ [http://news.bbc.co.uk/hi/russian/sci/tech/newsid_3105000/3105747.stm Би-би-си | Технологии | "Кобра" победила программиста НАСА ] ]

Russian TV channel news: "Our Vasa has beaten NASA" [ [http://www.vesti.ru/doc.html?id=101978 Вести.Ru: новости, видео и фото дня ] ]

Competition and Judgment in Gridwars III

After battle files were published by EI, it became clear that Chris Mueller's code took an extremely lucky victory in the battle for 3rd place when the battle was played at Clusterworld: the probability of winning is likely <1%. Furthermore, from EI's description of the battle followed by Chris Mueller's clarification it turned out that the victory was managed with code based on Mark Wenig's Borg code which won Gridwars Interactive and was the strongest known code as of Gridwars III code development period -- and not trivial to beat one too.

However, when Chris Mueller finally published the code (which happened months after the competition) it became clear that the algorithm of the Borg was left intact. What was contributed is the spreading part which is only used in the beginning of the battle to spread over the empty space; once the cells get in contact with enemy, Mark Wenig's code starts working, in which the only thing modified by Chris Mueller was the variable names.

There were discussions among the programmers, whether it is in accordance with the rules to use someone else’s code, but it turned out to be the case. Publishing the code after each tournament favors improvements because programmers can build on the winning code.

Time matters

One of the official rules included with the Gridwars kit was the time limit -- code executing on 1000 cells must not take more than 0.5s per cycle on a 1.13 GHz PC. While it is generally agreed that the rule was introduced by EI in order to avoid the danger of having to deal with programs that would be boring to watch or could bust the schedule (Gridwars contests were held live at ClusterWorld and SuperComputing) and that in 2004 much faster computers were available, the rule had a very important effect for participants considering that CxC was implemented as a bytecode interpreter: once the code hits the limit, it was time to either stop making it stronger at further expense of execution time, or start looking for optimization opportunities. The latter takes time and effort and in both cases the end result is strongly determined by programmer's skill.

Gridwars kit did not include any special tool to time the code; apparently participants were expected to work out their own ways to satisfy that requirement. Using different benchmarks showed that of the four final codes, Chris Mueller's exceeded the time limit by more than 2x, Paul Klinge's and Mark Wenig's were close to the limit. After a protest filed by Andy Monakov who wrote one of the benchmarks EI posted a response, and in doing so did not provide their own benchmark or at least timing results to disprove the claim of rule violation.

Another point to note is EI's statement that the time limit was introduced in the original Gridwars competition after several participants said they wanted to use file IO (perhaps implying this way that the rule was not to be considered a valid limitation ever since, even though it was mentioned in the rules). [http://en.wikipedia.org/wiki/Talk:Gridwars#EI.27s_statement_on_the_time_limit] However, during development period EI stated clearly that the time limit was to be respected. [http://en.wikipedia.org/wiki/Talk:Gridwars#Time_limit_during_Gridwars_III_code_development_period]

Several other programmers provided timing results and Paul Klinge's and Mark Wenig's programs turned out to be within the time limits according to their benchmarks. EI announced that Chris Mueller's programs were very slow, but since no programmer voiced any concerns, Chris Mueller's programs were allowed to participate in the tournament. Andy Monakov complained later after his program lost against Chris Mueller's.

Subtle differences with unforeseen consequences

After Gridwars III was held, Andy Monakov detected differences in the execution of battles compiled with codes published by Mark Wenig and Paul Klinge from the battle files published by EI -- not only cycle count statistics were not the same, but whereas Paul Klinge's code clearly had a chance to win in the battle compiled using codes published by both participants, in the battle published by EI Mark Wenig's code looked completely unbeatable.

Repeated requests addressed to EI to explain the difference or publish the source code used to build official battles were not satisfied. Following another persistent request to publish the source code in order to find the bug and eliminate it, EI closed the forum with the official statement of the need for preparation to Gridwars 4.

The exact reason behind different execution and unbeatability of Mark Wenig's code was nailed down by Andy Monakov who, in search for the answer, reverse-engineered the Gridwars battle files after EI refused to provide the source code and closed the forum.

The reason of different execution was the rule that at least 3 bullets are required to capture a cell -- this check was mysteriously missing in the official battle files published by EI and used to determine the winner during live demonstration at Clusterworld. As a result, the difference in execution could only be detected for codes written in such a way that the total number of bullets sent at an enemy cell could equal 1 or 2: whenever such cell is not protected by friendly fire, it would be easily captured by such program in violation of the rules.

Of the final four codes, two were found to produce 1- and 2-bullet shots and therefore could have gained an advantage when executed without the 3-bullet check (as done by EI during the official show at ClusterWorld): those written by Mark Wenig and Paul Klinge who took 1st and 2nd place respectively and were awarded a 5-node Xeon cluster (est. value $15,000-20,000) and a pocket PC correspondingly.

EI didn't replay Gridwars in accordance with all rules in order to announce the real winners after it was found that published battle files were compiled without the 3-bullet check. Apparently they refused to do so, since after they were asked to do so in the forum, no response was given and Gridwars was closed shortly after. Later on, following an email message, EI didn't respond to the request to circulate codes submitted for participation in Gridwars III so that the real winners could at least be known.

Mark Wenig, Paul Klinge and Chris Mueller ignored the proposal to agree to hand over the prizes to people who would have won them had the contest been held with due respect to the rules, whereas respect to the rules was the very motive used by Paul Klinge to protest and win the argument with EI who had accepted the proposal to employ gridwise arrangement instead of in-line but backpedaled after Paul Klinge's claim that the rules must not be changed. It should be noted that the claim itself contained an element of false reasoning: in-line starting arrangement was not even mentioned in the official rules, let alone declared as one.

Even though programs which split shots have a bigger advantage without the 3-bullet-rule, they were developed because they are strategically optimal to beat programs with a good defense, because more than 3 bullets are needed to conquer a cell defended with 3 bullets, which is what most programs do.Fact|date=March 2008 None of the programmers knew that the 3-bullets-rule would be dropped. Most likely it was a mistake by the organizers. Therefore, none of the programmers intentionally capitalize on this.Fact|date=March 2008

Most programmers made their battle programs public after the tournament, including Mark Wenig, Paul Klinge and Chris Mueller, and a tournament between those programs shows that the prices indeed went to the rightful owners.Fact|date=March 2008

Footnotes