Help me program my AI to win a competition!

May 3, 2009 3:04 PM

Teach me how to program a robot for my upcoming programming competition! I'm looking for tips, tricks, and sources of inspiration to help write an awesome AI.

Some details:

I have two days to write the AI. The robot moves and races, and does other things. It's a 1v1 competition. I'm being purposely vague so this doesn't cross the line and become HomeworkFilter. Please tell me if you want more details. I'd really like to read stuff like Iocaine Powder Explained.

posted by theiconoclast31 to computers & internet (7 comments total)

Okay, first off: Are you programming the AI for a real, physical robot or a robot in a simulated environment like player/stage? The answers are dramatically different, as you must be very conservative in the former case, especially if you're hobbled by low-resolution sensors like ultrasound and a low-quality drive train.

Second: what languages do you have available? Some languages have free, high quality AI libraries that you may or may not be allowed to use. Are you using a special-purpose language like the RCX Code used by Mindstorms or NQC on a microcontroller or what?
posted by jedicus at 3:51 PM on May 3

Just a tip, if you're searching on Google for help, use the word "autonomous code" or similar. AI refers to a different field of programming that has more to do with learning and cognition (and which seldom makes its way out of simulation and onto hardware) -- if you're looking for a way for the robot to move and navigate on its own, "autonomy" is the thing to look for.

We definitely need more information about your hardware. If you're using a LEGO brick, you should find plenty of code examples online. I'm personally involved with a robotics competition that has very active forums where people discuss all kinds of programming (including programming for autonomous robots), where you may find some useful tips or ideas.

Also look around for websites from the people involved in the Trinity Firefighting Robot and Sumobot competitions, where people may have published some of their code online for use.
posted by olinerd at 3:58 PM on May 3

I've had fun in a few competitions like this (several virtual robot programming competitions, and one real robot competition). Two days does not sound like a lot of time. My advice is to come up with a very simple strategy and implement it flawlessly, keeping in mind you almost certainly won't be able to counter EVERY strategy.
posted by losvedir at 4:31 PM on May 3

There's no hardware involved. We're running things in a simulated environment, and we're coding in assembly. Sorry, you can see I'm throwing around terms I'm unfamiliar with. That's partly why I asked this question - I don't even know what to Google.

losvedir: We've had more than a week to do this, but we only just started the fun part and we're actually ahead of most students right now.
posted by theiconoclast31 at 4:48 PM on May 3

Check out the Wikipedia page on Core War, which is a highly abstract AI competition with several commonly used strategies. Depending on the nature of your environment and the scoring system you may be able to adapt some of those strategies. Here is another page that explains the common strategies in a high level way.

Does the simulation pit the two opponents against each other only once or is it run multiple times? If you're allowed to save state between runs and there are a lot of runs for each pairing, consider a simple ranking heuristic. You have a list of strategies, each equally weighted. Select a strategy using a weighted probability function, which will at first choose randomly. Each time a strategy wins, increase its weight; each time a strategy loses, decrease its weight. Given enough runs your strategy selection will be optimal.

If your opponents are clever, you may want your increase/decrease function or your weighted probability function to be asymptotic or capped so that your AI does not become too predictable. If you can't save state, still consider using more than one strategy and just always pick randomly.

Is the environment real time or turn-based? If it is real time, choose a simple strategy that will have fast performance even in the naive implementation. You do not have time to do much code optimization. If it is turn-based, then do not worry about efficient implementation: just code it in a straightforward and verifiably correct way. Premature optimization is the root of many kinds of evil, especially in a fragile language like assembly.

In your testing, consider 'goldfishing' your strategies: that is, play them against a goldfish AI, which just does the bare minimum necessary to play according to the rules. In your case a couple of goldfish to test against are an AI that does nothing and an AI that moves randomly but legally. These are easy to code and ensure that your AI won't get tripped up by an opponent that crashes, gets stuck, or behaves erratically. Goldfishing can also be a quick and dirty way to rate various strategies: how quickly does a given strategy win against the goldfish?

Of course, be sure to test your AI against itself, especially if you develop multiple strategies.
posted by jedicus at 5:59 PM on May 3

First, testing an AI is difficult. If you are not careful, you will waste all your time staring at your bots wondering if they are being clever or stupid and whether it's a bug. Then coding anything in assembly is extremely hard. Considering these two sources of difficulty, I advise you be humble about the amount of smart you will be able to code into your robot.

Design something very simple, then spend some time making it simpler. Then implement it in the most straightforward way possible, and writing as many unit tests as you can manage as go along.
posted by gmarceau at 7:30 PM on May 3

We got in the semifinal round and won 2/4 matches (lose two and you're eliminated). I think that puts us in the top 10. As many of you guys said, it's tough to do anything clever when you're working in assembly. But our bot was thoroughly tested and worked smoothly, unlike many of our competitors. I think the winners just unrolled a whole bunch of code to minimize memory accesses.

Thanks for the links (I esp. enjoyed that article about Core Wars).

Ooh, and this was for the SPIMbot competition (PDF) for my CS232 class. If you guys get any clever ideas from reading that, I'm still interested! The competition/submission is over now.
posted by theiconoclast31 at 1:15 PM on May 7