Sandholm, Tuomas

professor at CMU; co-creator of Libratus, the first AI to beat top human professionals at heads-up no-limit Texas Hold'em

Tuomas Sandholm: Poker and Game Theory

Lex Fridman Podcast · Dec 28, 2018

• Tuomas Sandholm
• Libratus
• heads-up no-limit Texas Hold'em
• imperfect-information games
• Nash equilibrium
• computational game theory
• mechanism design
• depth-limited search
• AI value alignment
• nuclear risk game theory

Core ideas

Sandholm frames heads-up no-limit Texas Hold'em as the AI community's central benchmark for imperfect-information game solving — a genuinely two-player, zero-sum, sequential game where, unlike chess or Go, each player holds private information the other lacks. He recounts the 2017 "Brains vs. AI" event where Libratus played four top-10 heads-up specialists at a Pittsburgh casino for 20 days and 120,000 hands (needed for statistical significance given the game's high variance), with players compensated based on individual performance against the AI rather than a flat fee to preserve competitive incentive; Libratus wound up roughly $1.8-2 million ahead in chip value despite no real money changing hands (Pennsylvania's Gaming Board had denied an earlier request to play for actual stakes). He notes that international betting markets favored the humans 4-to-1 or 5-to-1 even though his team's internal assessment was closer to a coin flip, given that an earlier system (Claudico) had lost to top humans just 18 months prior — illustrating, in his view, a broader pattern where people are overconfident in skilled humans relative to AI until they've directly witnessed an AI outperform them.

Addressing the popular belief that human "tells" (facial expressions, body language) are central to poker mastery, Sandholm argues this romanticized notion largely evaporates at the elite level: top professionals are already so skilled at concealing tells that investing effort in reading opponents' tells yields little marginal benefit among peers, even though tells matter enormously in casual games. He explains that the raw game tree for heads-up no-limit hold'em (roughly 10^161 states) is far too large to solve directly, requiring abstraction — distinguishing "information abstraction" (grouping similar hands, done via automated potential-aware clustering and integer programming that considers not just a hand's current strength but how it might evolve) from "action abstraction" (grouping similar bet sizes, partly informed by historical human and AI play, with an early, provably-convergent but not fully scalable automated method used for the first couple of betting rounds).

On architecture, Sandholm clarifies Libratus did not use deep learning, unlike DeepStack (a contemporary poker AI), and explains why naive evaluation-function learning (as in AlphaGo-style perfect-information games) doesn't transfer to imperfect-information settings: a game state's value depends not just on the cards but on both players' beliefs about the situation (a weak hand is more valuable if the opponent believes it's strong, and vice versa), so post-Libratus follow-up work instead allows the search algorithm to consider that an opponent might switch to different "continuation strategies" at the leaves of a depth-limited search tree, preventing overly optimistic local search — a technique enabling sound depth-limited lookahead search that differs fundamentally from DeepStack's approach of generating random situations, treating each as the start of a new sub-game, and using deep learning to learn the resulting (belief-inclusive) state values.

He explains how Nash equilibrium (introduced by John Nash in 1950) does double duty in these systems: beyond defining a pair of mutually-non-deviating strategies, it derives, via Bayes' rule, an implied probability distribution over which underlying game states an agent is likely facing at each information set — illustrated with rock-paper-scissors, where equilibrium play (1/3 each) directly implies the correct belief distribution for the opponent. Crucially, this approach requires no opponent-specific data or history — it is a purely rational, "data-free, opponent-free" property of the game's structure itself, not a model of any particular human or AI's tendencies (Libratus deliberately did not enable opponent-exploitation techniques the team had developed, since Sandholm judged the elite pros too skilled at counter-exploitation for the added risk to be worthwhile), though he notes separate research on hybrid approaches that gradually shift toward exploiting weaker opponents in observed regions of the game tree while remaining close enough to the game-theoretic strategy to avoid becoming exploitable in turn.

Sandholm surveys the hierarchy of game classes from simplest to most general — repeated matrix games, stochastic games, and finally extensive-form (tree-structured) games, of which poker is a canonical example — and explains why two-player zero-sum games are both conceptually and computationally easier than general-sum or three-or-more-player games: in two-player zero-sum settings, any equilibrium strategy is a best response to any other equilibrium strategy, so which specific equilibrium each player independently selects doesn't matter for correctness, a guarantee that collapses even in two-player general-sum games (where joint benefits can be left on the table by picking mismatched equilibria) and especially in three-or-more-player zero-sum games (which introduce new problems like collusion between two players against a third). He cites his own recent work developing new game representations specifically for modeling collusion/cooperation (e.g., bridge, where partners share payoffs but cannot communicate mid-hand and must pre-coordinate legal signaling conventions), contrasting this with domains like auctions, negotiations, or poker where cooperation isn't built into the rules but can still emerge and complicate solving.

Discussing real-world applications beyond poker, Sandholm describes two startups — Strategic Machine (applying game-solving to business, sports, gaming, finance, and electricity markets) and Strategy Robot (targeting military, cybersecurity, and intelligence applications) — plus separate work in optimized combinatorial markets (distinct, non-game-theoretic optimization technology). Asked about applying game theory to model ambiguous human interactions (using the host's example of pedestrian-vehicle "trust" dynamics in jaywalking), Sandholm proposes a more tractable related application: pre-negotiating standardized merging/right-of-way conventions between different autonomous vehicle fleets (e.g., Waymo vs. Uber) via automated multi-issue negotiation, allowing full-speed merging in situations that would otherwise require slow, ad hoc negotiation — while noting that whether such situations are best modeled as perfect or imperfect information is itself a nontrivial modeling choice, and that imperfect-information games are strictly harder to solve when the underlying reality genuinely is imperfect-information.

Reflecting on lessons from a decade-plus of the Annual Computer Poker Competition and the broader AI-benchmark tradition (comparing Libratus's 2017 milestone to Deep Blue and AlphaGo), Sandholm emphasizes that computational game theory has repeatedly shown a gap between theoretical convergence guarantees and real-world performance — some algorithms with superior theoretical convergence rates (compared to CFR-based methods) perform worse in practice, meaning large-scale empirical testing, not theory alone, is necessary to determine which techniques actually work. He recounts becoming, in his words, "the most hated person in the world of poker" after the first Brains vs. AI event, facing near-death-threat-level hostility from players fearing the game's viability once AI surpassed humans — a fear he argues (drawing a parallel to chess, where humans continued enjoying the game post-Deep-Blue) proved unfounded, since top human players have since incorporated Libratus's genuinely novel, "Martian" strategic insights into their own play, enriching rather than destroying the game.

On mechanism design (designing game rules to produce desired outcomes), Sandholm distinguishes formal impossibility results (like the 1983 Myerson-Satterthwaite theorem, which proves no mechanism can achieve efficient trade under imperfect information for an entire class of settings) from the practical value of automated mechanism design, which — rather than seeking a universal solution for a whole class — can identify specific "islands of possibility" within a provably-impossible general class by tailoring designs to particular settings. He's candid that manual mechanism design has had limited real-world success even when designed by top economists, citing FCC spectrum auctions (involving tens of billions of dollars) as a case where truthful bidding still isn't the optimal strategy and no one has identified a single known-optimal bidding strategy, despite expert design.

Sandholm expresses considerably more optimism than concern about AI's societal impact, citing concrete personal examples: a nationwide kidney exchange system he built that has kept hundreds of people alive while also creating employment (surgeons, nurses, coordinators), and roughly 800 large-scale combinatorial sourcing auctions run through an earlier startup (CombineNet, 2001-2010) that improved supply-chain efficiency on $60 billion of spend by 12.6% (over $6 billion in efficiency gains, including reduced empty trucking miles and associated emissions). Addressing AI value-alignment concerns (raised by figures like Max Tegmark and Stuart Russell), Sandholm calls the worry largely theoretical based on his own extensive applied experience, illustrating with an anecdote from the late 1980s about a colleague suggesting "maximize truck utilization" as an optimization objective — which Sandholm immediately recognized would produce trucks driving in useless circles at 100% utilization while delivering nothing — arguing that while poorly specified objectives are a real and long-understood risk, he has never actually seen this materialize as a real-world problem in decades of applied optimization work. On existential risk more broadly, he names climate change and nuclear war as his two primary societal worries (having twice explored, without success, building pollution-credit market mechanisms, concluding the actual bottleneck was political will rather than market design), and regarding nuclear risk specifically, argues that Cold War-era mutually-assured-destruction game theory (a simple, low-dimensional analysis valid for a small number of superpowers) is a poor fit for today's more fragmented landscape of smaller nuclear-armed states and potential non-state actors with lower initiation thresholds, leaving him more, not less, worried about nuclear risk than in the past.

Closing on future directions, Sandholm identifies scaling game-solving to settings with hidden player actions (unlike poker, where only chance's actions—the cards—are hidden while betting actions are public), multiplayer games, collusion and opponent exploitation, and — most ambitiously — modeling genuinely infinite, non-repeating extensive-form games (such as open-ended business or military strategy "from here to eternity," where there's no natural endpoint to define success) as his primary open research interests, alongside developing more scalable integer programming techniques and (citing a recent paper) the first algorithm-configuration method with formal generalization guarantees — ensuring that configuration choices tuned on training examples will provably perform well on an unseen real-world distribution, a theoretical gap that had persisted despite roughly 17 years of applied algorithm-configuration research.

Excerpts