The Method Behind the Poker AI That Took the Pros for $1.7 Million

‘The Machines are coming!’ was the cry earlier this year when poker-playing Artificial Intelligence (AI) bot Libratus defeated four of the best pros in the game for the best part of $1.76million, and the scientific paper released this week by the brains behind the machine will do little to allay fears that at some point, humans – in poker at least – will become redundant.

Back in January, the team of Jason Les, Dong Kim, Daniel McAuley and Jimmy Chou started out quite optimistic that they would prevail against a newer version of the program which some of them had defeated the previous year – but by the end of the match they were in awe of the AI’s performance, though little in the way of detail as to how Libratus managed to overpower them was released.

That changed when Sciencemag.org released a paper by the machine’s creators - Noam Brown and Tuomas Sandholm of Carnegie Mellon University in Pittsburgh, Pennsylvania – which went into depth as to how they overcame the challenge of programming an AI which could somehow compete with humans in poker – a game of imperfect information.

The duo’s paper starts out by stating: ‘Despite AI successes in perfect-information games, the private information and massive game tree have made no-limit poker difficult to tackle’, the pair referencing perhaps this month’s big news that saw chess, Go and Shogi-lovers all stunned when an AI program took mere hours to basically learn the game from scratch and then massacre the top computer programs.

Poker, for those in the know, is a different matter altogether – so how did Brown and Sandholm solve the problems inherent in a game which just a couple of months ago they described as having ‘10^163 (that’s 10 followed by 163 zeroes!) different game situations’?

‘Our game-theoretic approach features application-independent techniques: an algorithm for computing a blueprint for the overall strategy, an algorithm that fleshes out the details of the strategy for subgames that are reached during play, and a self-improver algorithm that fixes potential weaknesses that opponents have identified in the blueprint strategy,’ write Brown and Sandholm, and if that sound a bit too technical, let’s see if we can break down the three steps to AI victory…

First up, the duo set up a simple version of the game – an ‘abstraction’ – and part of the program then ‘computes game-theoretic strategies’ for this smaller version. This solution becomes the ‘blueprint’ for later stages of the AI development – ‘an approximation for how to play in the more numerous later parts of the game’.

Secondly, Libratus’ 2nd module refines this blueprint strategy and solves it in ‘real-time’ -  a necessary part of competitive play in almost any game, poker of course included. The advantages of their new approach means that ‘Whenever the opponent makes a move that is not in the abstraction’ - the simpler version in part 1 - a ‘subgame is solved with that action included. We call this nested subgame solving.’ Basically refining the process and solution as it goes along.

Part 3 of Libratus’ innovative and now-proven technique is called ‘the self-improver’ by the computer science geniuses and is designed to ‘enhances the blueprint strategy’.

The simpler version could be imagined as having far more intricate ‘branches’ to become the full game, and the self-improver module ‘computes a game-theoretic strategy for those branches’.

Because it would become way too complex to solve all of these possibilities, as seen by the numbers given above in the Match Poker post,  the authors of the paper on Libratus decided to ‘tame this complexity’, by using  ‘the opponents’ actual moves to suggest where in the game tree such filling is worthwhile’. Not every branch is useful in practice, so the AI works on what it faces in reality.

The ground-breaking work done by Brown and Sandholm includes extremely detailed information which only computer science and AI buffs and experts will understand fully, but the basic news that the breakthrough which the match against the top pros appeared to be, is now backed by scientific process - open to peer review and doubtless the beginning of even exciting and fresh approaches to taming the game of poker.

It may or may not happen in our lifetimes – but it would be a brave (or perhaps foolish) person who bets against it!