5 day forecast
Research on poker a good deal for airport security
-
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.
Share with others:
Poker is helping to improve security at Pittsburgh International Airport.
That's right, poker.
Using game theory, a group of computer scientists has developed a set of algorithms to help thwart the planning of terror attacks by randomizing where and when security checkpoints, officers, canine units and other deterrents -- such as the placement of air marshals on planes -- are placed 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 Dr. Gilpin. "And at the time, poker was getting really popular and I had just started playing with my friends on my own."
Initially, the idea piqued Dr. Sandholm's interest -- though, Dr. Gilpin said, "I had to do a little selling."
It helped that there was ample evidence that research into other games had helped push work in other, more weighty areas.
"The artificial intelligence work on chess in the 1980s and 1990s" -- led by IBM's famous Big Blue computer work that began at CMU -- "led to a computer becoming the best chess player in the world, and it didn't benefit humanity directly, but the work on that led to advances in information retrieval and search engine design and databases," Dr. Gilpin said.
Dr. Sandholm was in. He 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," said the professor, who had not played much poker before starting the work. "And I was in search of problems where the best way of playing the game is non-truthful, such as bluffing in poker."
Game theory is a branch of applied mathematics that attempts to analyze competition, and it's used in a variety of fields, including economics, political science and computer science. Many game theory applications try to find the equilibria in a game, such that no player has an incentive to change their strategy.
They began applying to poker problems the main game theory equilibrium concept that Dr. Sandholm had been working on for a decade, 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 -- meaning no one could ever consistently win hands over the computer program -- a poker game, Rhode Island Hold 'Em. But Rhode Island Hold 'Em is a relatively simple poker game, with about 3.1 billion possible nodes, or situations, to account for in the algorithms.
By comparison, the popular poker game No-Limit Texas Hold 'Em -- which some believe is unsolvable because it has so many possible outcomes -- has almost as many nodes as there are atoms in the universe, Dr. Sandholm said.
In 2006, CMU, along with the University of Alberta, began hosting the Annual Computer Poker Competition, in which computer programs play against each other in six different versions of Texas Hold 'Em.
Just last month, CMU's team of Dr. Sandholm, Dr. 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.
Research ideas that came out of that competition dove-tailed into Dr. Sandholm's work in 2006 with another doctoral student, Vincent Conitzer. They wrote a paper that focused on solving Stackelberg models, a mathematical model 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 by creating efficient, randomized security patterns.
"From that we developed a new algorithm," said Dr. Tambe, who earned his doctorate at CMU. "But their paper in 2006 was the inspiration for it. 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."
Dr. Tambe and his team developed ARMOR -- Assistant for Randomized Monitoring of Routes -- and put it into work at the Los Angeles airport in 2007.
ARMOR was so effective that the federal Transportation Security Administration asked him to develop a new version that could be implemented in other airports. So Dr. Tambe and his team developed GUARDS -- for Game-theoretic Unpredictable And Randomly Deployed Security.
TSA decided to pilot GUARDS at Pittsburgh International Airport last fall.
Pittsburgh's airport was chosen because it had already been a test site for other security programs, and TSA wanted to try it out on a smaller airport.
Its challenge is to provide thorough, moment-to-moment security while also preparing for potential high-risk target areas and times.
"We try to be random, but there's a tendency for people to diminish randomness because of what they know intuitively," said Joe Terrell, TSA's federal security director for Western Pennsylvania. "When something's predictable and people can see what's happening it makes it useful for them to do something to you."
In the nearly one year GUARDS has been deployed in Pittsburgh, Mr. Terrell said it has proven its effectiveness, even if he has had a hard time himself understanding all the math that went into it.
"I've tried to get smart about game theory and all this stuff and I got as far as the executive summary and that was enough," Mr. Terrell said with a laugh. "We've made an effort to make sure everyone understands the theory. I think everyone pretty much gets it."
One benefit of the randomization program that they hadn't really thought about, Mr. Terrell said, is that the security involved -- from TSA to the Allegheny County police -- "enjoy doing something different every day."
Exactly how it's helped security overall is hard to describe, Mr. 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.
First Published August 2, 2010 12:00 am
