MechMania
MechMania is a weekend-long AI programming competition held by the University of Illinois at Urbana-Champaign's chapter of the Association for Computing Machinery. For two years in a row, I was part of a 3-person team from Polytechnic University that trekked out all the way to the middle of nowhere for the competition—with unexpected results.
The year was 1998. I was early in my sophomore year of college at Polytechnic University in Brooklyn. I was very involved in Polytechnic's local chapter of the Association for Computing Machinery (ACM), and one day we found ourselves looking through artifacts we had unearthed deep in a closet in the ACM office. We found plaques, trophies, medals, for programming teams years earlier, sometimes decades, who won various ACM programming competitions. Three of us were inspired by this archaeological find, and in October of that year we traveled to the University of Illinois at Urbana-Champaign (UIUC), to enter MechMania, an AI programming competition that was part of the annual ACM UIUC Reflections Projections conference. Each year, teams would compete by writing the AI for a game or game-like scenario. For example, one year, teams wrote an AI to control bots on a tile-based Capture the Flag grid, while another year their AIs would control ships orbiting a network of star systems.
MechMania IV's premise was straightforward: in the future, vinyl used for creating vinyl records was scarce, and ships would go out into space and mine the valuable vinyl ore from asteroids. There were also fuel asteroids, which ships would use to refuel along the way. Matches were played by two teams at a time, in a 2D area of space; each team had a base containing 4 ships, on opposite sides of the asteroid field. The goal was to gather more vinyl than your opponents by sending out your ships to collect vinyl asteroids, then docking them back into your base to gain the vinyl. Ships could be controlled in real-time by a team's AI to perform different actions, all of which used up fuel: they could thrust forward or backwards, rotate, and fire lasers, which would break apart asteroids, damage opposing ships, or destroy the vinyl reserves of the enemy's base. If a ship ran out of fuel, it was adrift, and if it was carrying any vinyl you would hope it wouldn't accidentally dock with the opposing base rather than your own (or collide with a fuel asteroid, which would replenish its engines). After 3 minutes, the team with the most vinyl would win the round (with ties broken by total score in previous rounds), and a tournament bracket would determine the overall winner.
Naturally, we began by discussing various methods for choosing asteroids to chase, intercepting them, aiming weapons at opposing ships, etc. It was pretty early in the day, and we all took a break to listen to Bjarne Stroustrup, creator of C++, give his keynote address to the Reflections Projections attendees. I don't know if it was his inspiring words, or the half-waking state of delirium the warm lecture hall had left us in, or the sudden intake of caffeine, but on our way back to the computer lab after the keynote, we were struck with inspiration: if we sent all 4 of our ships to pound the opposing base, we could be all but guaranteed a 0-0 tie in every match. This "Scorched Earth" policy wouldn't win us the tournament, but it would be entertaining. Wait, one of us said, what if we gather a very small amount of vinyl, and then blast the opponent down to zero right at the end? We could win by a tiny margin each time!
We got right to work implementing this plan. One of us implemented the "gatherer" ship, which we named "Tim." Tim was designed to gather exactly one vinyl asteroid, bring it back to base, and then wait. We calculated that three ships would be needed to blast a full base down to zero without having to refuel, so the other two of us implemented these three "blaster" ships, naming them "Heresy," "Blasphemy," and "Sacrilege" (can you tell we were a bunch of over-the-top college kids?). We set them up to trigger partway through the match, travel to the opponent's base, and blast every last bit of its vinyl to smithereens.
Finally, it was time for the tournament. The game was projected on a big screen, and as we watched a few matches played before ours, we saw most teams had gone with a general plan to gather vinyl, then fuel, with varying degrees of success. Finally, it was our turn. The match started, the other team's ships were moving, and all 4 of our ships stayed put. The crowd was murmuring, wondering, had our AI failed completely? Then someone noticed out loud that one of our ships had left the base. Tim had decided it was time to gather his single asteroid, so he set out, grabbed it, brought it back to base, and then sat there, satisfied with a job well done. More murmuring. Sure, our ship had gathered something, but we were still losing something like 15 to 200—unopposed, the enemy ships had managed to gather the rest of the vinyl without too much difficulty. Finally, a minute before the match ended....the screen saver came on. The crowd groaned as the operator moved the mouse to wake up the screen....revealing that it had already begun: Heresy, Blasphemy, and Sacrilege were halfway to the enemy base. They came to a stop, surrounding the base on 3 sides, and opened fire. The crowd cheered. It was the most exciting match yet by far, and we won it 15 to zero and advanced to the quarterfinals.
Our next match began the same way, and even though the crowd knew what would happen, it did not dampen their enthusiasm any. Tim gathered a small vinyl asteroid, and then the other 3 ships closed in on the enemy base and blasted it down to zero, then docked inside their base. But wait—one of the other team's ships was derelict, out of fuel, but carrying a large vinyl asteroid and drifting right for their base! It docked, and suddenly they were winning! But their lead was short-lived: Heresy, Blasphemy, and Sacrilege immediately left the enemy base, whipped around 180 degrees, and blasted them down to zero again. Victory #2, and into the semifinals we went.
The semifinals were the first time we encountered another team that attacked our vinyl reserves, though it had only happened by accident. Tim was sitting comfortably back in base after gathering his one asteroid, when one of their ships took a potshot at him—but hit the base instead, and left us in the precarious situation of having 0 points. Luckily, Tim was smart enough to see that the base was empty and set out again to gather more vinyl, giving us the small number of points we needed to secure victory #3, and suddenly, we were in the finals.
The other team in the finals was quite impressive. Their AI had two ways in which it was stronger than almost every other: first, their vinyl-gathering code was extremely tight, gathering MUCH faster than any other team, and second, they sent a single ship into their opponent's base right in the beginning of the match, which would sit there until there were 5 seconds left, exit, spin around, and blast the vinyl reserves as much as it could. In a way, their strategy was an inverse of our own, as they had 3 gatherers and 1 blaster. In any event, when the match was underway, their gatherer ships were so efficient that they gathered every last bit of vinyl before Tim could get any, leaving us with 0 points. Our blaster ships emerged and brought them down to 0 points at the end. It was a tie, and as per the tiebreaker, we were anticlimactically declared the second-place finishers, since the other team had earned more points throughout the tournament. We still felt like winners, though, and all three of us returned home triumphant.
We returned to MechMania the following year, where the game was a robot fighting game state machine. Each robot would be in one of three states: standing, crouching, or jumping, and from each state would perform a single move that would put them into another state (or the same state again). Moves were things like punching, uppercuts, knee thrusts, and similar, and each one did damage to the opponent depending on the opponent's state as well; each robot evaluated its state transitions simultaneously, applying damage based on the new state the opponent chose.
For our AI, we decided to try to predict which move an opponent would perform based on the state they were in. We went through each state and each transition and determined the best counter for it; if our robot KNEW that the opponent would do a specific move from a given state, it would know exactly the move that would avoid being damaged, and even damage the opponent as well.
We figured that most of the other AIs would not be very adaptive, so we decided to keep track of which moves the other robot performed from each state, and simply counter the one that the opponent had performed most often. It turned out that this was exactly the right way to do this, as most of the AIs involve offline calculation of the best moves to do (as we had done), but without the adaptive component.
Unfortunately, there were some issues with the state machine as it had been designed by the contest organizers, and too many teams decided that the best move was to stand in place and punch straight ahead while waiting for the opponent to walk into the punch (which, if both AIs did it, obviously did not make for an exciting match). However, there were several matches our AI was in where the opponent fought in the proper spirit of the tournament, and watching our robot start out getting hit a whole bunch, learn what the opponent would do, and then finally learn to bob and weave and avoid every single attack, was really cool, and definitely earned some cheers. We didn't win that year, but we earned a lot of praise, and had a lot of fun doing it.