# Meet Hyperborean, the Poker-Playing AI

## What strategies help a computer program win at Texas Hold ’Em?

Image: Rubén Hidalgo / iStockphoto

Image: Rubén Hidalgo / iStockphoto

This is the second in a short series of posts about the Annual Computer Poker Competition (ACPC) taking place at the AAAI conference in Toronto July 22-26, 2012. My name is Richard Gibson and I’m a member of the Computer Poker Research Group (CPRG) at the University of Alberta. In my previous post, I discussed the history and present state of the competition, as well as the six events currently being played. Here, I will talk about our programs from previous years and explain our new programs for this year’s competition.

The CPRG’s poker programs, named “Hyperborean” in the ACPC, are constructed quite differently compared to programs for “perfect information games” such as chess. For example, the chess program Deep Blue was based on a technique called alpha-beta search, which compares sequences of moves until one sequence is found to be superior. On Deep Blue’s turn to move, search was performed on-line from the current game state for up to several minutes before the best estimated move was taken. In contrast, during a match, our poker programs play instantaneously. All computation for decision-making is performed off-line for several days before the competition and a final strategy profile is written to disk. Then, during an actual match, actions are chosen simply through table lookups in the precomputed profile.

For the heads-up (two-player) instant-runoff events, the CPRG’s approach, as well as the approach taken by several other teams, has been to compute an approximate Nash equilibrium strategy profile. One can think of a Nash equilibrium as a perfect defensive strategy; that is, in a fair 2-player game, the best an opponent can do in the long run against an equilibrium strategy is tie. Since the most losing player is sequentially eliminated in the instant-runoff divisions of the ACPC, playing a Nash equilibrium strategy here would be optimal. However, designing a program that can play Texas Hold’ Em at an exact equilibrium is currently infeasible due to the game’s massive size. The smallest game played at the ACPC, heads-up limit (fixed bet sizes) Texas Hold ’Em, has approximately 1018 game states.

To compute approximate Nash equilibria, the CPRG uses Counterfactual Regret Minimization [PDF], a state-of-the-art iterative algorithm that closely resembles a self-play procedure. As CFR’s memory requirements are linear in the size of the game, we cannot apply CFR to full Texas Hold ’Em. Instead, we run CFR on a smaller, abstract game that we construct by merging similar card dealings into “buckets.” This makes hands that fall into the same bucket indistinguishable to the program [PDF]. For example, a pair of aces and a pair of kings are both strong hands and one might want to play them similarly, and so the two hands might be combined into a single bucket.

In no-limit games, actions must also be abstracted. Rather than being able to raise any number of chips, only a few bet sizes, such as “pot” (a raise equal to the number of chips in the pot) or “all-in” (bet all remaining chips), are allowed by our programs to keep the game size manageable. An abstract game equilibrium can then be computed with CFR and used to play the real game. Unfortunately, even in limit games, abstraction provides no guarantee [PDF] for how far the generated profile is from equilibrium in the real game. In practice, however, well-designed abstractions with many buckets tend to yield the programs closest to a real equilibrium [PDF].

We also use a modified version of CFR for the two-player games where the winner is determined by “total bankroll.” Modifications tend to change from year to year in an attempt to improve our program’s chances of taking more money from weaker players. In addition, our 3-player entries are also built using CFR, even though CFR no longer guarantees an approximate Nash equilibrium with the addition of a third player.

While there are a number of other teams that also use CFR or other equilibrium-finding algorithms, some teams have used different techniques to succeed in the competition. For example, the programs named “Sartre” from the University of Auckland use case-based reasoning [PDF] derived from hand history data of ACPC results from previous years. At each turn to act, Sartre searches for scenarios similar to its current situation and picks an action that was most successful in the previous scenarios.

For the 2012 competition, we incorporated some exciting new techniques from our recent research into our programs. While our instant-runoff entry for heads-up limit is a traditional approximate equilibrium computed with CFR, our total bankroll program for heads-up limit is quite different. Rather than using a single strategy profile, we instead dynamically generate a strategy profile on each hand by mixing a small collection or “portfolio” of profiles. Estimates of the expected reward for each of the portfolio’s profiles are used to generate the mixture.

For the no-limit and 3-player games, we are submitting just one program per game to play in both the instant-runoff and total bankroll divisions. In no-limit, we used a new algorithm to allow a different bet size [PDF] at every decision point in conjunction with the fold, call, and all-in actions. Many no-limit poker programs only properly understand a small number of traditional bet sizes, such as “pot,” but our new program frequently uses non-standard bets. Because of this, we found that the new program, at least when played against our previous no-limit entries, won a lot of chips by pushing its opponent “off-tree.”

In the last blog of this series, I will discuss the outcome of this year's computer poker competition and report on the Poker Symposium that was introduced at AAAI this year.

The Conversation (0)

## Will AI Steal Submarines’ Stealth?

### Better detection will make the oceans transparent—and perhaps doom mutually assured destruction

The Virginia-class fast attack submarine USS Virginia cruises through the Mediterranean in 2010. Back then, it could effectively disappear just by diving.

U.S. Navy

Submarines are valued primarily for their ability to hide. The assurance that submarines would likely survive the first missile strike in a nuclear war and thus be able to respond by launching missiles in a second strike is key to the strategy of deterrence known as mutually assured destruction. Any new technology that might render the oceans effectively transparent, making it trivial to spot lurking submarines, could thus undermine the peace of the world. For nearly a century, naval engineers have striven to develop ever-faster, ever-quieter submarines. But they have worked just as hard at advancing a wide array of radar, sonar, and other technologies designed to detect, target, and eliminate enemy submarines.

The balance seemed to turn with the emergence of nuclear-powered submarines in the early 1960s. In a 2015 study for the Center for Strategic and Budgetary Assessment, Bryan Clark, a naval specialist now at the Hudson Institute, noted that the ability of these boats to remain submerged for long periods of time made them “nearly impossible to find with radar and active sonar.” But even these stealthy submarines produce subtle, very-low-frequency noises that can be picked up from far away by networks of acoustic hydrophone arrays mounted to the seafloor.

And now the game of submarine hide-and-seek may be approaching the point at which submarines can no longer elude detection and simply disappear. It may come as early as 2050, according to a recent study by the National Security College of the Australian National University, in Canberra. This timing is particularly significant because the enormous costs required to design and build a submarine are meant to be spread out over at least 60 years. A submarine that goes into service today should still be in service in 2082. Nuclear-powered submarines, such as the Virginia-class fast-attack submarine, each cost roughly US \$2.8 billion, according to the U.S. Congressional Budget Office. And that’s just the purchase price; the total life cycle cost for the new Columbia-class ballistic-missile submarine is estimated to exceed \$395 billion.

The twin problems of detecting submarines of rival countries and protecting one’s own submarines from detection are enormous, and the technical details are closely guarded secrets. Many naval experts are speculating about sensing technologies that could be used in concert with modern AI methodologies to neutralize a submarine’s stealth. Rose Gottemoeller, former deputy secretary general of NATO, warns that “the stealth of submarines will be difficult to sustain, as sensing of all kinds, in multiple spectra, in and out of the water becomes more ubiquitous.” And the ongoing contest between stealth and detection is becoming increasingly volatile as these new technologies threaten to overturn the balance.

## We have new ways to find submarines

Today’s sensing technologies for detecting submarines are moving beyond merely hearing submarines to pinpointing their position through a variety of non-acoustic techniques. Submarines can now be detected by the tiny amounts of radiation and chemicals they emit, by slight disturbances in the Earth’s magnetic fields, and by reflected light from laser or LED pulses. All these methods seek to detect anomalies in the natural environment, as represented in sophisticated models of baseline conditions that have been developed within the last decade, thanks in part to Moore’s Law advances in computing power.

Airborne laser-based sensors can detect submarines lurking near the surface.IEEE Spectrum

According to experts at the Center for Strategic and International Studies, in Washington, D.C., two methods offer particular promise. Lidar sensors transmit laser pulses through the water to produce highly accurate 3D scans of objects. Magnetic anomaly detection (MAD) instruments monitor the Earth’s magnetic fields and can detect subtle disturbances caused by the metal hull of a submerged submarine.

Both sensors have drawbacks. MAD works only at low altitudes or underwater. It is often not sensitive enough to pick out the disturbances caused by submarines from among the many other subtle shifts in electromagnetic fields under the ocean.

Lidar has better range and resolution and can be installed on satellites, but it consumes a lot of power—a standard automotive unit with a range of several hundred meters can burn 25 watts. Lidar is also prohibitively expensive, especially when operated in space. In 2018, NASA launched a satellite with laser imaging technology to monitor changes in Earth’s surface—notably changes in the patterns on the ocean’s surface; the satellite cost more than \$1 billion.

Indeed, where you place the sensors is crucial. Underwater sensor arrays won’t put an end to submarine stealth by themselves. Retired Rear Adm. John Gower, former submarine commander for the Royal Navy of the United Kingdom, notes that sensors “need to be placed somewhere free from being trolled or fished, free from seismic activity, and close to locations from which they can be monitored and to which they can transmit collected data. That severely limits the options available.”

One way to get around the need for precise placement is to make the sensors mobile. Underwater drone swarms can do just that, which is why some experts have proposed them as the ultimate antisubmarine capability.

Clark, for instance, notes that such drones now have enhanced computing power and batteries that can last for two weeks between charges. The U.S. Navy is working on a drone that could run for 90 days. Drones are also now equipped with the chemical, optical, and geomagnetic sensors mentioned earlier. Networked underwater drones, perhaps working in conjunction with airborne drones, may be useful for not only detecting submarines but also destroying them, which is why several militaries are investing heavily in them.

A U.S. Navy P-8 Poseidon aircraft, equipped to detect submarines, awaits refueling in Okinawa, Japan, in 2020. U.S.Navy

For example, the Chinese Navy has invested in a fishlike undersea drone known as Robo-Shark, which was designed specifically for hunting submarines. Meanwhile, the U.S. Navy is developing the Low-Cost Unmanned Aerial Vehicle Swarming Technology, for conducting surveillance missions. Each Locust drone weighs about 6 kilograms, costs \$15,000, and can be outfitted with MAD sensors; it can skim low over the ocean’s surface to detect signals under the water. Militaries study the drone option because it might work. Then again, it very well might not.

Robo-Shark, a 2.2-meter-long submersible made by Boya Gongdao Robot Technology, of Beijing, is said to be capable of underwater surveillance and unspecified antisubmarine operations. The company says that the robot moves at up to 5 meters per second (10 knots) by using a three-joint structure to wave the caudal fin, making less noise than a standard propeller would. robosea.org

Gower considers underwater drones to be “the least likely innovation to make a difference in the decline of submarine stealth.” A navy would need a lot of drones, data rates are exceedingly slow, and a drone’s transmission range is short. Drones are also noisy and extremely easy to detect. “Not to mention that controlling thousands of underwater drones far exceeds current technological capabilities,” he adds.

Gower says it could be possible “to use drones and sonar networks together in choke points to detect submarine patrols.” Among the strategically important submarine patrol choke points are the exit routes on either side of Ireland, for U.K. submarines; those around the islands of Hainan and Taiwan, for Chinese submarines; in the Barents or Kuril Island chain, for Russian submarines; and the Straits of Juan de Fuca, for U.S. Pacific submarines. On the other hand, he notes, “They could be monitored and removed since they would be close to sovereign territories. As such, the challenges would likely outweigh the gains.”

Gower believes a more powerful means of submarine detection lies in the “persistent coverage of the Earth’s surface by commercial satellites,” which he says “represents the most substantial shift in our detection capabilities compared to the past.” More than 2,800 of these satellites are already in orbit. Governments once dominated space because the cost of building and launching satellites was so great. These days, much cheaper satellite technology is available, and private companies are launching constellations of tens to thousands of satellites that can work together to image every bit of the Earth’s surface. They are outfitted with a wide range of sensing technologies, including synthetic aperture radar (SAR), which scans a scene down below while moving over a great distance, providing results like those you’d get from an extremely long antenna. Since these satellite constellations view the same locations multiple times per day, they can capture small changes in activity.

Experts have known for decades about the possibility of detecting submarines with SAR based on the wake patterns they form as they move through the ocean. To detect such patterns, known as Bernoulli humps and Kelvin wakes, the U.S. Navy has invested in the AN/APS-154 Advanced Airborne Sensor, developed by Raytheon. The aircraft-mounted radar is designed to operate at low altitudes and appears to be equipped with high-resolution SAR and lidar sensors.

Commercial satellites equipped with SAR and other imaging instruments are now reaching resolutions that can compete with those of government satellites and offer access to customers at extremely affordable rates. In other words, there’s lots of relevant, unclassified data available for tracking submarines, and the volume is growing exponentially.

One day this trend will matter. But not just yet.

Jeffrey Lewis, director of the East Asia Nonproliferation Program at the James Martin Center for Nonproliferation Studies, regularly uses satellite imagery in his work to track nuclear developments. But tracking submarines is a different matter. “Even though this is a commercially available technology, we still don’t see submarines in real time today,” Lewis says.

The day when commercial satellite imagery reduces the stealth of submarines may well come, says Gower, but “we’re not there yet. Even if you locate a submarine in real time, 10 minutes later, it’s very hard to find again.”

## Artificial intelligence coordinates other sub-detecting tech

Though these new sensing methods have the potential to make submarines more visible, no one of them can do the job on its own. What might make them work together is the master technology of our time: artificial intelligence.

“When we see today’s potential of ubiquitous sensing capabilities combined with the power of big-data analysis,” Gottemoeller says, “it’s only natural to ask the question: Is it now finally possible?” She began her career in the 1970s, when the U.S. Navy was already worried about Soviet submarine-detection technology.

Submarines can now be detected by the tiny amounts of radiation and chemicals they emit, by slight disturbances in the Earth’s magnetic fields, and by reflected light from laser or LED pulses.

Unlike traditional software, which must be programmed in advance, the machine-learning strategy used here, called deep learning, can find patterns in data without outside help. Just this past year, DeepMind’s AlphaFold program achieved a breakthrough in predicting how amino acids fold into proteins, making it possible for scientists to identify the structure of 98.5 percent of human proteins. Earlier work in games, notably Go and chess, showed that deep learning could outdo the best of the old software techniques, even when running on hardware that was no faster.

For AI to work in submarine detection, several technical challenges must be overcome. The first challenge is to train the algorithm, which involves acquiring massive volumes and varieties of sensor data from persistent satellite coverage of the ocean’s surface as well as regular underwater collection in strategic locations. Using such data, the AI can establish a detailed model of baseline conditions, then feed new data into the model to find subtle anomalies. Such automated sleuthing is what’s likeliest to detect the presence of a submarine anywhere in the ocean and predict locations based on past transit patterns.

The second challenge is collecting, transmitting, and processing the masses of data in real time. That task would require a lot more computing power than we now have, both in fixed and on mobile collection platforms. But even today’s technology can start to put the various pieces of the technical puzzle together.

## Nuclear deterrence depends on the ability of submarines to hide

For some years to come, the vastness of the ocean will continue to protect the stealth of submarines. But the very prospect of greater ocean transparency has implications for global security. Concealed submarines bearing ballistic missiles provide the threat of retaliation against a first nuclear strike. What if that changes?

“We take for granted the degree to which we rely upon having a significant portion of our forces exist in an essentially invulnerable position,” Lewis says. Even if new developments did not reduce submarine stealth by much, the mere perception of such a reduction could undermine strategic stability.

A Northrop Grumman MQ-8C, an uncrewed helicopter, has recently been deployed by the U.S. Navy in the Indo-Pacific area for use in surveillance. In the future, it will also be used for antisubmarine operations. Northrop Grumman

Gottemoeller warns that “any perception that nuclear-armed submarines have become more targetable will lead to questions about the survivability of second-strike forces. Consequently, countries are going to do everything they can to counter any such vulnerability.”

Experts disagree on the irreversibility of ocean transparency. Because any technological breakthroughs will not be implemented overnight, “nations should have ample time to develop countermeasures [that] cancel out any improved detection capabilities,” says Matt Korda, senior research associate at the Federation of American Scientists, in Washington, D.C. However, Roger Bradbury and eight colleagues at the National Security College of the Australian National University disagree, claiming that any technical ability to counter detection technologies will start to decline by 2050.

Korda also points out that ocean transparency, to the extent that it occurs, “will not affect countries equally. And that raises some interesting questions.” For example, U.S. nuclear-powered submarines are “the quietest on the planet. They are virtually undetectable. Even if submarines become more visible in general, this may have zero meaningful effect on U.S. submarines’ survivability.”

Sylvia Mishra, a new-tech nuclear officer at the European Leadership Network, a London-based think tank, says she is “more concerned about the overall problem of ambiguity under the sea.” Until recently, she says, movement under the oceans was the purview of governments. Now, though, there’s a growing industry presence under the sea. For example, companies are laying many underwater fiber-optic communication cables, Mishra says, “which may lead to greater congestion of underwater inspection vehicles, and the possibility for confusion.”

A Snakehead, a large underwater drone designed to be launched and recovered by U.S. Navy nuclear-powered submarines, is shown at its christening ceremony in Narragansett Bay in Newport, R.I.U.S. Navy

Confusion might come from the fact that drones, unlike surface ships, do not bear a country flag, and therefore their ownership may be unclear. This uncertainty, coupled with the possibility that the drones could also carry lethal payloads, increases the risk that a naval force might view an innocuous commercial drone as hostile. “Any actions that hold the strategic assets of adversaries at risk may produce new touch points for conflict and exacerbate the risk of war,” says Mishra.

Given the strategic importance of submarine stealth, Gower asks, “Why would any country want to detect and track submarines? It’s only something you’d do if you want to make a nuclear-armed power nervous.” Even in the Cold War, when the United States and the U.K. routinely tracked Soviet ballistic-missile submarines, they did so only because they knew their activities would go undetected—that is, without risking escalation. Gower postulates that this was dangerously arrogant: “To actively track second-strike nuclear forces is about as escalatory as you might imagine.”

“All nuclear-armed states place a great value on their second-strike forces,” Gottemoeller says. If greater ocean transparency produces new risks to their survivability, real or perceived, she says, countries may respond in two ways: build up their nuclear forces further and take new measures to protect and defend them, producing a new arms race; or else keep the number of nuclear weapons limited and find other ways to bolster their viability.

Ultimately, such considerations have not dampened the enthusiasm of certain governments for acquiring submarines. In September 2021 the Australian government announced an enhanced trilateral partnership with the United States and the United Kingdom. The new deal, known as AUKUS, will provide Australia with up to eight nuclear-powered submarines with the most coveted propulsion technology in the world. However, it could be at least 20 years before the Royal Australian Navy can deploy the first of its new subs.

The Boeing Orca, the largest underwater drone in the U.S. Navy’s inventory, was christened in April, in Huntington Beach, Calif. The craft is designed, among other things, for use in antisubmarine warfare. The Boeing Company

As part of its plans for nuclear modernization, the United States has started replacing its entire fleet of 14 Ohio-class ballistic-missile submarines with new Columbia-class boats. The replacement program is projected to cost more than \$128 billion for acquisition and \$267 billion over their full life cycles. U.S. government officials and experts justify the steep cost of these submarines with their critical role in bolstering nuclear deterrence through their perceived invulnerability.

To protect the stealth of submarines, Mishra says, “There is a need for creative thinking. One possibility is exploring a code of conduct for the employment of emerging technologies for surveillance missions.”

There are precedents for such cooperation. During the Cold War, the United States and the Soviet Union set up a secure communications system—a hotline—to help prevent a misunderstanding from snowballing into a disaster. The two countries also developed a body of rules and procedures, such as never to launch a missile along a potentially threatening trajectory. Nuclear powers could agree to exercise similar restraint in the detection of submarines. The stealthy submarine isn’t gone; it still has years of life left. That gives us ample time to find new ways to keep the peace.