Game theory research takes aim at security threats
Last year in a world first, researchers at the University of Alberta made global headlines with a computer program that plays an essentially perfect game of heads-up limit Texas hold’em poker, a two-player version of the card game. It turns out that milestone in artificial intelligence and game theory was just the beginning. A year later, the university’s Computer Poker Research Group showed how those same techniques could be used for more complex “games”, namely optimizing security deployments to prevent a terrorist or cybersecurity attack.
Those advances would have never occurred had it not been for the scale of resources provided by Compute Canada, Calcul Québec and WestGrid: 1000 years of processing power, 200 distributed high performance computers and 17 terabytes of data storage. Some members of the team presented their research results during a poster competition at the CANHEIT | HPCS 2016 conference in Edmonton in June.
“We started making greater use of HPC clusters and large distributed clusters starting about 2009, which allowed us to deal with very large-scale problems,” says PhD student Neil Burch, a computer scientist on Dr. Michael Bowling’s poker research team. “And we will continue to depend on Compute Canada resources as we apply these techniques to larger problems, like security.”
Games have been used as a test bed for new ideas in artificial intelligence since the 1950s. But Dr Bowling’s team was tackling a far tougher challenge than programming a computer to beat a human at chess or checkers, where all players have all the relevant information to make their decisions. The outcome of a heads-up limit Texas hold’em poker game, like security threats, is based on what is not known, such as the other player’s cards or, in the case of a security threat, not knowing what moves the attackers have already taken.
This isn’t the first time artificial intelligence has been used in security, but the algorithm developed by the U of A team has proven to produce faster results using five times less computation time.
“Our algorithm (CFR+) can be applied to different problem domains where there is uncertainty in the environment, like airport checkpoints, coast guard patrolling and scheduling of bomb sniffing dogs at airports,” explains Burch. “So the game becomes, what is the best way to place my security resources to thwart an attacker.”
This isn’t the end of the group’s research. Burch says they will continue to rely on Compute Canada/Calcul Québec/WestGrid resources to develop techniques that can solve even larger-scale real-world problems faster.