(no subject)
We had a three person team organized in the week before the contest: myself (EA/Maxis), Jeff Gates (EA/Maxis), and Tod Semple (Popcap). We had also talked to a couple of other people including Alex Lam (EA/Maxis) but they all dropped out due to other plans or disinterest in the contest task.
At first the task seemed a lot less interesting than the past couple of years, but I think it was really rescued by being a real-time application; that kept it interesting throughout. Since you only were given telemetry information from the server every 100ms, there were long periods of time where you had to guess at where your rover was and plan accordingly.
We used C++ because everyone knew it, along with SVN for source conrol. I prototyped some of the math for the analyzer component (see below) in Haskell, but then implemented it in C++ for the final project. We met at Popcap in San Mateo; we focused on having fun, taking long lunch and dinner breaks and actually going home to sleep :)
Tod got the LiveCD working on a laptop before the contest started, although apparently it destroyed two other machines beforehand (although who knows if they were working before?). Neither Tod nor Jeff was particularily experienced with UNIX, so I had to take care of the laptop and package the submissions.
Tod and Jeff implemented our local simulation & network code, while I did system administration on the laptop, writing scripts to keep starting the server over and over again. Then we split up tasks:
- Jeff was in charge of writing our rover AI
- Tod would build a visualizer that showed the current known state & simulation of the remote state.
- I would analyze the incoming telemetry data and use it to derive the hidden parameters to the simulation, which would feed back into the simulation.
Jeff was definitely the MVP; the problem was definitely similar to some of the AI he had to write for Spore's cell game, so he had a good set of domain-specific knowledge to build on.
We ignored pathfinding almost completely and treated the problem as a "routing" problem. The algorithm for our lightning-round submission was as follows:
for each turn state of the rover (L, l, -, r, R)
for each acceleration state of the rover (brake, -, accel)
simulate 200ms in 10ms increments with that turn/accel state
score the result with a heuristic
send commands to the server to set the state to the best scoring state
Our heuristic was pretty simple: Death was bad, and earlier death was worse. Winning was great, and winning early was better. Otherwise, the route that ended closest to the center was best. In total we scored 15 results after running 300 simulator steps.
This was done in time for the lightning-round submission deadline, so we sent it in. It was pretty good even on some of the "weird" map settings we tried, with odd rover parameters.
The next two days were spent making minor improvements.
I added support for figuring out braking and turn speed parameters to the analyzer, and changed the routing AI to a two-stage planner, which led to 15^2 possible routes instead of 15, and the number of simulated timesteps from 300 to 2400. We got a big speedup when we decided that you never wanted to coast; you should always be accelerating or braking, which reduced the number of routes to 100 and the number of simulation steps to 1100. We kept "straight" and "light turn" as we found we got empirically better results including them. Theoretically you should never need to "light turn", although for our heuristic analysis having the additional points helped, as well as keeping the response time fast as we didn't need to switch rapidly between different turn states.
I also added a testing harness perl script that allowed us to run our tests against many maps.
Jeff added additional AI modes for "martian avoidance" and "wall handling"; normally we basically ignored martians, treating them as tiny craters, but if we died once we grew the radius that we treated martians as occupying. If we died twice to martians we went into "super-avoidance" mode, where we would run away from martians if we were faster than them, or run *towards* them if we were slower, turning at the last moment to "play chicken" and dodge out of the way. The "wall avoidance" mode was triggered if we timed out; instead of heading towards the center, we would head towards the center if there was a clear path, but if there wasn't we would head counterclockwise around the map until we saw a clear path.
Tod wrote a local server and better martian AI to simulate what might happen if the martians got more intelligent. He also added a "cautious" AI mode that got triggered if our rover hit a crater. The goal of "cautious" mode was to handle low-visibility and/or bad handling on the rover and guaranteed that we could always brake to a stop before hitting any obstacle that came into view.
Overall it was a fun task and I'll definitely be competing again next year.
At first the task seemed a lot less interesting than the past couple of years, but I think it was really rescued by being a real-time application; that kept it interesting throughout. Since you only were given telemetry information from the server every 100ms, there were long periods of time where you had to guess at where your rover was and plan accordingly.
We used C++ because everyone knew it, along with SVN for source conrol. I prototyped some of the math for the analyzer component (see below) in Haskell, but then implemented it in C++ for the final project. We met at Popcap in San Mateo; we focused on having fun, taking long lunch and dinner breaks and actually going home to sleep :)
Tod got the LiveCD working on a laptop before the contest started, although apparently it destroyed two other machines beforehand (although who knows if they were working before?). Neither Tod nor Jeff was particularily experienced with UNIX, so I had to take care of the laptop and package the submissions.
Tod and Jeff implemented our local simulation & network code, while I did system administration on the laptop, writing scripts to keep starting the server over and over again. Then we split up tasks:
- Jeff was in charge of writing our rover AI
- Tod would build a visualizer that showed the current known state & simulation of the remote state.
- I would analyze the incoming telemetry data and use it to derive the hidden parameters to the simulation, which would feed back into the simulation.
Jeff was definitely the MVP; the problem was definitely similar to some of the AI he had to write for Spore's cell game, so he had a good set of domain-specific knowledge to build on.
We ignored pathfinding almost completely and treated the problem as a "routing" problem. The algorithm for our lightning-round submission was as follows:
for each turn state of the rover (L, l, -, r, R)
for each acceleration state of the rover (brake, -, accel)
simulate 200ms in 10ms increments with that turn/accel state
score the result with a heuristic
send commands to the server to set the state to the best scoring state
Our heuristic was pretty simple: Death was bad, and earlier death was worse. Winning was great, and winning early was better. Otherwise, the route that ended closest to the center was best. In total we scored 15 results after running 300 simulator steps.
This was done in time for the lightning-round submission deadline, so we sent it in. It was pretty good even on some of the "weird" map settings we tried, with odd rover parameters.
The next two days were spent making minor improvements.
I added support for figuring out braking and turn speed parameters to the analyzer, and changed the routing AI to a two-stage planner, which led to 15^2 possible routes instead of 15, and the number of simulated timesteps from 300 to 2400. We got a big speedup when we decided that you never wanted to coast; you should always be accelerating or braking, which reduced the number of routes to 100 and the number of simulation steps to 1100. We kept "straight" and "light turn" as we found we got empirically better results including them. Theoretically you should never need to "light turn", although for our heuristic analysis having the additional points helped, as well as keeping the response time fast as we didn't need to switch rapidly between different turn states.
I also added a testing harness perl script that allowed us to run our tests against many maps.
Jeff added additional AI modes for "martian avoidance" and "wall handling"; normally we basically ignored martians, treating them as tiny craters, but if we died once we grew the radius that we treated martians as occupying. If we died twice to martians we went into "super-avoidance" mode, where we would run away from martians if we were faster than them, or run *towards* them if we were slower, turning at the last moment to "play chicken" and dodge out of the way. The "wall avoidance" mode was triggered if we timed out; instead of heading towards the center, we would head towards the center if there was a clear path, but if there wasn't we would head counterclockwise around the map until we saw a clear path.
Tod wrote a local server and better martian AI to simulate what might happen if the martians got more intelligent. He also added a "cautious" AI mode that got triggered if our rover hit a crater. The goal of "cautious" mode was to handle low-visibility and/or bad handling on the rover and guaranteed that we could always brake to a stop before hitting any obstacle that came into view.
Overall it was a fun task and I'll definitely be competing again next year.