Posts tagged positive

I was talking to Michael Bowling yesterday on the train and somehow the topic of his experience in robocup competitions came up. He’s got lots of great stories about the odd things that happen at these competitions, and it’s always really cool to talk to him about his experiences. In this conversation, I had my own experience to talk about. You see, in CMPUT 366 a few years ago, our introductory course on AI held a robocup simulation tournament. For those who don’t know, robocup is the robot soccer competition, and it has many tournaments from a simulation based league to actual robots. Since this was an AI course, we were concentrating on the AI side of things and thus robots didn’t come into play. I figured that since it’s an interesting subject, I’d talk a bit about how I approached the problem and maybe give you an idea of what it is like to work in AI.

First of all, AI research is a whole lot more glitzy on the outside than it is internally. From the outside, game playing programs like Chinook and Deep Blue were able to make intelligent looking moves. On the inside though, the programs were unintelligently exploring millions of game states looking for the best move. So while I describe my approach to the soccer playing program, keep this in mind.

The tournament was run using a copy of the actual robocup simulation program. The simulation runs as follows: A server is started up that keeps track of where each player is, where the ball is, what the score is, etc. It enforces rules such as offside, and returns players to their half of the field after someone scores a goal. The server communicates with the programs that we, the students, wrote for the players taking in the actions that each player on the field makes at each timestep. One of the things that made this project a little difficult was that the actions the players were allowed to do were not very well documented and each student had to spend some time getting used to the interface to build their soccer playing program.

Each student was provided with a sample program that played elementary student style — all players run towards the ball and kick it towards the opponent goal. My expectation was that many students would not build programs that were much more complicated than this style. So my goal was to be able to beat that program reliably first.

I spent a great deal of time examining the documentation that did exist for the simulator, and stumbled across a very interesting piece of information about how goaltenders had a special ability. Apparently, the simulator allowed the goalie to ‘catch’ the ball, and then teleport to another spot in the crease area. I spent several hours figuring out just how to get this to work, and succeeded after not too long. This was the biggest step I made in beating the “swarm the ball” type teams. Since the goaltender was now capable of teleporting to the other side of the goal and kick it down field, I had an easy way of getting the ball away from a large number of players in a concentrated space.

Now that I had my defensive position setup, I had to figure out a good way to generate some offense. Due to time constraints, and my doubts on getting a slick system working with no bugs, I decided to avoid complicated and potentially dangerous attempts to getting real communication and passing between players. Instead, I decided to try building in a heuristic-like system where players would tend to stay in their parts of the field unless the ball came near by. I had a set number of “forward”, “defense”, and “midfield” players who each had a home location. Next, to simulate passing, I had the defensemen kick the ball upfield at an angle towards the sides of the field (and incidentally where a player’s “home base” was). Kicking to the sides of the field meant that the opponent players who clogged up the center of the field wouldn’t intercept my “pass”.

After I had this system working, my team looked strikingly intelligent. They’d clear the ball upfield down the sides (a lesson I learned from floor hockey), players looked very much like they were passing to one another, despite the lack of real communication. The players were blindly kicking the ball towards a place where another player tended to be. But most of the time that player had no reason to be elsewhere so he was there to retrieve the ball! Probably the least intelligent looking part of my end product was the finishing touch: kicking the ball into the net. At that point, my forwards behaved almost identically to the “swarm-the-ball” type players … except that there wasn’t nearly as many of them. So if my opponent had a good defensive position, I had trouble scoring on them. Unfortunately, I didn’t have time to figure out how to improve that before the tournament started.

I did quite well in the tournament. The tournament was organized into 2 parts: a round robin seeding and then a bracketed finals system. I won my pool fairly handily which meant that I got a decent starting placement in the brackets. My program reached the quarterfinals before getting knocked out – which was a pretty happy result for me considering the size of the class. I think if my program’s offense was tweaked a little more, I would’ve gone a little further.

The winning program? His strategy was almost a purely defensive strategy. He had a goalie and at least one other player sitting around the goal protecting it. Teams had a really hard time scoring on this program. The games were low scoring affairs, since this program had less players to form an offensive attack. Still, since players lacked offensive prowess, the defensive strategy was the right way to go for this tournament.

So … that’s what it is like to work on a program’s AI. At least, that has been my experience with it. The later projects I’ve worked on, such as the Hex project and the Poker project have introduced much more complexity … but underneath the bright shiny hood of AI is an ugly mess of hacks and unintelligent heuristics. Still, you can’t argue with results, can you?

Heraldk