Many two-player perfect information games, such as tic-tac-toe and connect four, have been ‘solved,’ meaning that at least one player has a dominant strategy and can either win or draw ever game they play. Games such has poker are considered ‘imperfect information’ games because each player does not know the cards the other has. No imperfect information game has ever been solved, but a University of Alberta professor, Dr. Michael Bowling, has come close to solving a simple version of poker called Heads-Up Limit Hold’Em (HULHE).
This version of poker has a comparatively small (13.8 trillion) number of different circumstances that can arise within it. Dr. Bowling has discovered a (mostly) dominant strategy for the game using “200 computers, each sporting 24 processors, working in parallel for more than two months.” Though this seems like an insane effort, even only slightly more complicated version of poker can have 6.38X different circumstances, far more than can be processed by computers.
This information, however, has applications beyond poker. According to the article, problems such as airport security and medical diagnosis can be modelled with a similar algorithm, and can hopefully both benefit from this poker-solving model.
This article was an interesting application of the material we learned in class because it covered a game that had only two players but trillions, rather than our standard four or six, possible combinations of moves. It was also interesting to see that problems that are not ‘games’ can still be modeled as such.