Students win at game of Cops and Robbers

[img_inline align=”right” src=”http://padnws01.mcmaster.ca/images/cops_robbers.jpg” caption=”Engineering students Shiqi Cao, left, and Wolfgang Thaller were winners of the eighth annual International Conference on Functional Programming contest for their innovative Cops and Robbers game. Photo credit: Eileen Lui”]Remember when you were a child running after your friends in a good game of Cops and Robbers? Remember the skill and finesse required to escape the authorities or to catch the thief? Well, two McMaster students certainly can and they don't have to think back that far. This past June, Wolfgang Thaller and Shiqi Cao spent one long, sleepless weekend mastering the childhood game. Except they did it with computers.

On Sept. 27, 2005, the International Conference on Functional Programming announced the winners of their eighth annual programming contest and McMaster students won first prize. Thaller is a computer science graduate student and Cao is a third-year software engineering undergraduate. Combined, they formed the winning team, “Kieberer And XiaoTou” (which means Cops And Robbers in an Austrian dialect and Chinese, respectively).

With the encouragement of Wolfram Kahl, associate professor of computing & software, Thaller and Cao created a computer program that could negotiate around a pre-set map and either rob banks or catch the robber. Each program was considered a player and each game consisted of six players, one robber and five cops. Judges would play six programs against each other on one computer and the program that was most successful at winning games would be crowned the winner of the contest.

Sounds easy, doesn't it? But it's not.

“Computers, in general, are not very good at communicating,” says Thaller, but communication is the key to creating the best program. The five cops in each game are not necessarily required to cooperate with one another. The trick is to create a program that knows when to cooperate and when not to in order to come out on top. “It's a lot like game theory,” explains Cao.

But there's more. The second part of the contest allows cops to defect and join sides with the robber. This twist increases the amount of communication required between programs as well as complicating the type of communication. Each program must be able to decide when to give whom what types of information. Contestants were asked to take their original program and adapt it to meet these new conditions. Previous years did not include this section of the contest, but it was added this year to better mimic the real difficulties of the computer programming industry. “When you deliver a program to a client, they will usually want things to be changed,” says Kahl. “And programmers will always need to update and adjust their programs over time. The twist tests whether the contestants are able to write a program that can be modified to meet changing requirements.”

With this new component to the contest, Thaller and Cao submitted their entry with no expectations. Having merely three days to design a program, their only hope was to not place last. They needn't have worried. Despite a constant stream of difficulties and challenges, the pair has shown the world that they are able to perform exceptionally well under pressure. So the next time you're preparing to play Cops and Robbers, make sure you call these two; they will tell you how to win the game.