Poker research spurs good deal for airport security

ShareThis

Poker is helping to improve security at Pittsburgh International Airport.

Using game theory, a group of computer scientists has developed a set of algorithms to help thwart terrorist attacks by randomizing where and when security checkpoints, officers, canine units and other deterrents are located in and around the airport.

The idea had its start about six years ago. Tuomas Sandholm, a Carnegie Mellon University computer science professor, teamed up with then-doctoral student Andrew Gilpin to come up with a "lossless abstraction algorithm" for poker.

"It just seemed like an interesting problem to work on," said Gilpin, who "had just started playing with my friends on my own."

Other games had helped push work in more weighty areas, he said. "The artificial intelligence work on chess in the 1980s and 1990s" -- including IBM's famous Big Blue computer work that began at CMU -- "led ... to advances in information retrieval and search engine design and databases."

Sandholm, who hadn't played much poker, began spending about a third of his research time working on algorithms to solve poker games. "Poker had been studied in game theory since the 1950s," he said.

Game theory is a branch of applied mathematics that attempts to analyze competition. It's used in a variety of fields, including economics, political science and computer science. Many game theory applications try to find equilibria in a game, such that no player has an incentive to change strategy.

The researchers began applying the Nash equilibrium, created by John Nash, whose life and struggles were featured in the movie "A Beautiful Mind," starring Russell Crowe.

Eventually, in 2005, they became the first to "solve" a poker game, meaning their program consistently could win more hands than any other program or person. They'd played Rhode Island Hold 'Em, a relatively simple game with about 3.1 billion possible nodes, or situations, to account for in the algorithms. By comparison, the popular No-Limit Texas Hold 'Em has almost as many nodes as there are atoms in the universe, Sandholm said. Some believe it's unsolvable because it has so many possible outcomes.

In 2006, CMU and the University of Alberta began hosting the Annual Computer Poker Competition, in which computer programs compete in six different versions of Texas Hold 'Em. (In July, CMU's team of Sandholm, Gilpin and doctoral student Sam Ganzfried found out they had won the head-to-head, bankroll, no-limit Texas Hold 'Em competition for the second time in three years.)

Also in 2006, Sandholm wrote a paper -- with doctoral student Vincent Conitzer -- on solving Stackelberg models, in which one player commits to a strategy before the other player makes a decision.

That paper caught the eye of Milind Tambe, a computer science professor at the University of Southern California who was working on a project to improve security at Los Angeles International Airport.

The paper inspired "a new algorithm," said Tambe, who earned his doctorate at CMU. "We used it as a launching point for our program. Ours is faster, but it would have been much harder to do without their work."

Tambe and his team developed ARMOR -- Assistant for Randomized Monitoring of Routes -- which was launched at the Los Angeles airport in 2007.

ARMOR was so effective that the federal Transportation Security Administration asked Tambe to develop a version that could be implemented in other airports. So he and his team developed GUARDS, for Game-theoretic Unpredictable And Randomly Deployed Security. TSA decided to pilot GUARDS last fall at Pittsburgh International Airport, a smaller airport and one that had been a test site for other security programs.

Its challenge is to provide thorough, moment-to-moment security while also preparing for potential high-risk target areas and times.

Joe Terrell, TSA's federal security director for western Pennsylvania, praised the program but said he has had a hard time understanding the math that went into it. "I've tried to get smart about game theory ... and I got as far as the executive summary and that was enough," he said with a laugh.

One unexpected benefit of the randomization program, Terrell said, is that security personnel -- from TSA to the Allegheny County police -- "enjoy doing something different every day."

Exactly how it helps security overall is hard to describe, Terrell said, though it's clear to him that it has.

"That's always the hard question to ask in the security business: How do you measure success? Well, nothing has happened," and there have been no attacks at the airport, he said. "The best thing you can have up on the scoreboard is a big fat zero and that's what we've had."

And to think it all started with a hand of poker.

(E-mail Sean D. Hamill at shamill(at)post-gazette.)

(Distributed by Scripps Howard News Service, www.scrippsnews.com.)

Must credit Pittsburgh Post-Gazette