?

Log in

No account? Create an account

Previous Entry | Next Entry

The ICFP programming contest challenge this year was a game called Cops and Robbers. Six players at a time compete: one robber (who knows the position of each cop) and five cops (who try to find the robber based on very incomplete evidence and who can collaborate). Each team implements a program to play a cop and another to play a robber. Moving around a graph representing a map of Chicago, the robber wins points by robbing banks and not getting caught, and the cops win points by collectively catching the robber, collecting the most evidence, coming up with plans of action that the other cops like, and individually nabbing the robber.

The interface between the game manager and players was a really straightforward line-based messaging system over stdin and stdout. And the graph problem had already been solved by Dijkstra. So it seemed to me that the main challenge was in the field of artificial intelligence. The robber has to look at where he can go and make a decision that keeps him away from the cops and, ideally, near a bank with a lot of money in it. Our robber decides each round, based on the proximity of cops and of banks, whether to go for the money or just get as far away from the cops as he can. Ideally, he would keep track of every piece of information the cops could have about his location and model their thinking so as to stay one step ahead. But inferring how they think based on their behavior isn't necessarily straightforward, and we didn't try making a robber who could.

The cop is more complicated; she has an incentive to work with the other cops so they capture the robber, but she also has a competing incentive to be the first cop to find any evidence and to be the cop to make the arrest, so maybe she doesn't want to help her comrades too much. Maybe she wants to share the evidence she's found, or maybe she wants to make up evidence to throw the other cops off track. Ideally, she'd weigh the communication she receives from the other cops against the meager evidence she has to assess the trustworthiness of her colleagues. She'd propose plans that give her an advantage over them or even plans that she doesn't intend to follow. Maybe she could act differently based on whether the other cops generally seemed to be following the most popular plans. She could vote strategically so as to reward or punish colleagues as she sees fit. She could be really sophisticated, but our cop isn't. Our cop is honest and helpful (i.e., she shares the evidence she finds with the other cops), devising plans that give her no advantage over the other cops. Her only guile is her voting strategy, which strives to knock down any comrades who propose popular plans.

I'll be happy if our entry passes the first round (against fairly naïve cops and robbers). Come to think of it, it isn't clear to me whether any rounds of play will take place before the second task—a modification to our original entry—is announced, almost two weeks from now. Based on the comments on the contest mailing list, we can expect that some of the cops will be blundering fools, while others will be finely honed thief-catching machines submitted by teams with over a dozen members and tens of thousands of lines of code. Teams are pitted against each other only in a second round of play, in which our entry would surely not fare well. When we pit our robber against our cop (assisted by four simple, obedient cops), our cop wins most of the time. When we pit our robber against five of our cops, our cops' stubbornness leads them to fare somewhat less well, à la Keystone Kops.

Tags: