Month: January 2015

Heads-up limit hold’em poker is solved

Here is a bit more on the poker story Tyler mentioned yesterday.

An important variant of poker, heads-up limit hold’em (HULHE), has been essentially solved–meaning that a computer can now play the game so well that it wouldn’t lose much and might even win against a theoretically perfect player over a lifetime of play. Solving the game required new algorithms and significant computational power.

HULHE has 3.16 × 1017 possible states the game can reach, making it larger than Connect Four and smaller than checkers. However, because HULHE is an imperfect-information game, many of these states cannot be distinguished by the acting player, as they involve information about unseen past events (i.e., private cards dealt to the opponent). As a result, the game has 3.19 × 1014 decision points where a player is required to make a decision….There are two challenges for established CFR variants to handle games at this scale: memory and computation.

The solution supports some conventional strategies but also contains new insights:

Human players have disagreed about whether it may be desirable to “limp” (i.e., call as the very first action rather than raise) with certain hands. Conventional wisdom is that limping forgoes the opportunity to provoke an immediate fold by the opponent, and so raising is preferred. Our solution emphatically agrees (see the absence of blue in Fig. 4A). The strategy limps just 0.06% of the time and with no hand more than 0.5%. In other situations, the strategy gives insights beyond conventional wisdom, indicating areas where humans might improve. The strategy almost never “caps” (i.e., makes the final allowed raise) in the first round as the dealer, whereas some strong human players cap the betting with a wide range of hands. Even when holding the strongest hand—a pair of aces—the strategy caps the betting less than 0.01% of the time, and the hand most likely to cap is a pair of twos, with probability 0.06%. Perhaps more important, the strategy chooses to play (i.e., not fold) a broader range of hands as the nondealer than most human players (see the relatively small amount of red in Fig. 4B). It is also much more likely to re-raise when holding a low-rank pair (such as threes or fours) (44).

Why is this important? The only previous games of any difficulty that have been solved are perfect information games–games where each player knows everything that has previously happened. Tic-tac-toe and chess are perfect information games because everything that has happened is summarized in the state of the board. In imperfect games there is hidden information, such as in card games where the opposing players cards are hidden.

It’s clear that most games in the real world (and that includes “games” of nuclear strategy, bargaining, and detection and monitoring) are imperfect information games. Even though the sample space for HULHE is very large it’s smaller than these real world strategy games (and smaller than other forms of poker). Nevertheless, it’s clear that people are “solving” the real world games not by working through the sample space but by pruning it. A combination of search and heuristic pruning in the perfect information game of chess has already produced computers that are better than any human player. What the solution to this relatively small and somewhat unimportant imperfect information game indicates is that the computers are soon going to be better than you and I at the “human” capabilities of threat, bluff and deception.

Has Los Angeles fixed its gang problem?

That is the new and excellent Sam Quinones article from Pacific Standard, here is one excerpt:

Some of this is a state and national story, as violent crime declined by about 16 percent in both California and the nation from 2008 through 2012. But the decline has been steeper in many gang-plagued cities: 26 percent in Oxnard, 28 percent in Riverside, 30 percent in Compton, 30 percent in Pasadena, 30 percent in Montebello, 50 percent in Bell Gardens, 50 percent in El Monte.

Santa Ana once counted 70-plus homicides a year, many of them gang-related. That’s down to 15 so far in 2014, even as Santa Ana remains one of the densest, youngest, and poorest big cities in California. “Before, they were into turf,” says Detective Jeff Launi, a longtime Santa Ana Police gang investigator. “They’re still doing it, but now they’re more interested in making money.”

No place feels so changed as the city of Los Angeles. In 2014, the Los Angeles Police Department announced that gang crime had dropped by nearly half since 2008.

Obviously this is welcome news, not only for its own sake, but also for those of us who have been arguing that Latino immigration is going to work out.

Thomas C. Schelling on why international terrorism is so rare

From a 1991 essay, “What purposes can “international terrorism” serve?”:

…I want to offer another conjecture on why international terrorism is so rare…whereas individual acts of terrorism may be easily within the capabilities of quite ordinary individuals , a sustained campaign on any scale may require more people and more organization than could be viable in most target countries.  And there may be some negative feedback from the low success rate to the low attempt rate: Resourceful individuals, people with brains or people with money, may find terrorism so unpromising that they do not choose to contribute effort or money.  And any organization that is secret and dangerous risks both defection and infiltration; a group of people large enough to carry on a sustained campaign, perhaps simultaneously in different target areas, may simply be too vulnerable in defection and infiltration.  Even seeking financial help risks being informed on.

That is one of the essays in the book Violence, Terrorism, and Justice, edited by R.G. Frey and Christopher W. Morris.  By the way, Schelling cites the campaign of Palestinian radicals against Palestinian moderates as one of the examples of a successful terrorist plan.

Have game theorists plus computers cracked the game of poker?

A new computer algorithm can play one of the most popular variants of poker essentially perfectly. Its creators say that it is virtually “incapable of losing against any opponent in a fair game”.

…That means that this particular variant of poker, called heads-up limit hold’em (HULHE), can be considered solved. The algorithm is described in a paper in Science1.

The strategy the authors have computed is so close to perfect “as to render pointless further work on this game”, says Eric Jackson, a computer-poker researcher based in Menlo Park, California.

“I think that it will come as a surprise to experts that a game this big has been solved this soon,” Jackson adds.

…Bowling and colleagues designed their algorithm so that it would learn from experience, getting to its champion-level skills required playing more than 1,500 games. At the beginning, it made its decisions randomly, but then it updated itself by attaching a ‘regret’ value to each decision, depending on how poorly it fared.

This procedure, known as counterfactual regret minimization, has been widely adopted in the Annual Computer Poker Competition, which has run since 2006. But Bowling and colleagues have improved it by allowing the algorithm to re-evaluate decisions considered to be poor in earlier training rounds.

The other crucial innovation was the handling of the vast amounts of information that need to be stored to develop and use the strategy, which is of the order of 262 terabytes. This volume of data demands disk storage, which is slow to access. The researchers figured out a data-compression method that reduces the volume to a more manageable 11 terabytes and which adds only 5% to the computation time from the use of disk storage.

“I think the counterfactual regret algorithm is the major advance,” says computer scientist Jonathan Shapiro at the University of Manchester, UK. “But they have done several other very clever things to make this problem computationally feasible.”

The computer does engage in a certain amount of bluffing, full story here, via Vaughan Bell.

In which professions are Americans most likely to be married?

Catherine Rampell reports:

While engineers, mathematicians and scientists today are (unfairly) stereotyped as awkward nerds who don’t know how to interact with the opposite sex, in 1950 they were among the occupations most likely to be married. Today, the most commonly conjugated occupations are instead more often medical professionals with doctorates, starting with dentists (81 percent of whom are hitched)…

The top of the list looks like this:

1) Dentist
2) Chief executive
3) Sales engineer
4) Physician
5) Podiatrist
6) Optometrist
7) Farm product buyer
8) Precision grinder
9) Religious worker
10) Tool and die maker

We also learn this:

Turns out that in 1950, many of the occupations whose members were most likely to end up divorced were creative or artistic ones (artist, writer/director, dancer, designer, writer), which perhaps reflects the communities that were most accepting of divorce at the time. In 2010, the occupations with the highest divorce rates were predominantly in manufacturing or other areas that have been subject to downsizing (drilling machine operator, knitter textile operative, force operator, winding machine operative, postal clerk). This seems to support the idea that economic stability is a good predictor of marital status.

Do read the whole thing.

Assorted Charlie Hebdo links

1. Ross Douthat, on “the blasphemy we need.”

2. “A thorough understanding of the Iconoclast period in Byzantium is complicated by the fact that most of the surviving sources were written by the ultimate victors in the controversy, the iconodules.” That is from Wikipedia on the Iconoclastic debates.

3. Against Daumier (splendid visuals too).

4. Juan Cole on the attacks.  And Will Wilkinson.  And insulting Monty Python (video).

5. And, for something completely different, here is a video of dos niños colombianos.

Quantifying confidence

Angeletos, Collard, and Dellas serve up another important entry (NBER gate) in the growing literature on the importance of the risk premium for macroeconomic fluctuations:

We enrich workhorse macroeconomic models with a mechanism that proxies strategic uncertainty and that manifests itself as waves of optimism and pessimism about the short-term economic outlook. We interpret this mechanism as variation in confidence and show that it helps account for many salient features of the data; it drives a significant fraction of the volatility in estimated models that allow for multiple structural shocks; it captures a type of fluctuations in aggregate demand that does not rest on nominal rigidities; and it calls into question existing interpretations of the observed recessions. We complement these findings with evidence that most of the business cycle in the data is captured by an empirical factor which is unlike certain structural forces that are popular in the literature but similar to the one we formalize here.

There are ungated versions here.  The funny thing is, these theories are in some key regards more true to the spirit of John Maynard Keynes than many theories which are called “Keynesian.”

Robert Tombs, *The English and Their History*

I ordered this book through the UK, as it does yet have a U.S. publication date on Amazon.  It has a fascinating 891 pp. of text (and an excellent annotated bibliography), virtually all of which are worth reading.  In just about any year it is one of the top five non-fiction books of that year.  I found it especially strong on English-French relations, and early modern times, and perhaps a bit weak on post-1970 developments, which are in any case harder to cover.

It is not an easy book to excerpt but here is one short bit on Shakespeare:

…at deeper levels he is astonishingly not the product of his times, which is an evident reason for the continuing power of his work.  Most obviously, he is not dogmatic; he displays a wide variety of cultural and religious influences, but is not defined by the religious conflict that shaped his time — hence continuing modern debate about his personal beliefs.  He pays little respect to social and gender hierarchy.  He writes of a ‘deep England’, beyond London and the court.  Women are always important and often dominant in his plays, and women came in large numbers to see them, scandalizing foreign visitors.  It is often said that he conceals his opinions; it seems rather that the ideas he explores transcend the limits of contemporary polemics.

Definitely recommended, I quickly became addicted to this book.  Do any of you know when it will have a formal release on this side of the Atlantic?

Is the Great Stagnation soon over?

The method, which extracts drugs from bacteria that live in dirt, has yielded a powerful new antibiotic, researchers reported in the journal Nature on Wednesday. The new drug, teixobactin, was tested in mice and easily cured severe infections, with no side effects.

Better still, the researchers said, the drug works in a way that makes it very unlikely that bacteria will become resistant to it. And the method developed to produce the drug has the potential to unlock a trove of natural compounds to fight infections and cancer — molecules that were previously beyond scientists’ reach because the microbes that produce them could not be grown in the laboratory.

Studies on people will start in about two years, the NYT article is here.  Here is the underlying Nature article.

Alternatively, here is a claim that James Harden is the future of basketball.

I thank numerous MR readers for related pointers.

Markets in everything

The tables have turned on zoo-goers in China — where people are paying to be locked in cages while hungry lions and tigers stalk their every move.

The Lehe Ledu Wildlife Zoo in Chongqing city is giving people the hair-raising chance to learn what it’s like to come face to face with an apex predator, Central European News reports.

Visitors are forking over their cash to be caged inside the back of a truck as it makes its way through the animal park. Just to make sure they get the attention of the beasts, huge chunks of raw meat are tied to the bars to lure them as close as possible.

“We wanted to give our visitors the thrill of being stalked and attacked by the big cats but with, of course, none of the risks,” said zoo spokeswoman Chan Liang. “The guests are warned to keep their fingers and hands inside the cage at all times because a hungry tiger wouldn’t know the difference between them and breakfast.”

The chilling, once-in-a-lifetime experience has been a hit with visitors — the trips have been sold out for the next three months, according to CEN.

The link is here, via NinjaEconomics.  Elsewhere, in New York they are banning the tiger selfie, with or without huge chunks of raw meat.  Yet also in New York, Tough Mudder has added tear gas to some of its obstacle routines, via Hugo Lindgren.

Modern Principles, 3rd edition: Videos!

The third edition of Modern Principles of Economics is now available! Modern Principles is the best written and most interesting economics textbook and it has a wonderful new feature which puts it far ahead of its competition.

The third edition features over 30 beautifully produced videos each carefully chosen to integrate perfectly with Modern Principles of Economics. A majority of the videos are newly written and designed by Tyler and myself and all are linked in the text with URLs and QR codes. The videos will also be available in Macmillan-Worth’s learning management system, LaunchPad, along with the e-text, grading system and assessment tools.

The videos integrate perfectly with Modern Principles but they also work great with any textbook, Most importantly, we will be making all of the videos available to anyone in the world completely free of obligation or charge (more on that next week!).

A new chapter in Modern Principles covers asymmetric information so here is our video on adverse selection featuring Groucho Marx and George Akerlof!

The effect of the TseTse fly on African development

Marcella Alsan has a new paper in the American Economic Review:

The TseTse fly is unique to Africa and transmits a parasite harmful to humans and lethal to livestock. This paper tests the hypothesis that the TseTse reduced the ability of Africans to generate an agricultural surplus historically. Ethnic groups inhabiting TseTse-suitable areas were less likely to use domesticated animals and the plow, less likely to be politically centralized, and had a lower population density. These correlations are not found in the tropics outside of Africa, where the fly does not exist. The evidence suggests current economic performance is affected by the TseTse through the channel of precolonial political centralization.

You will find ungated versions here.