Bigger Deal

The End is Nigh! Or is it?

It all began in 1992 when a thing called Chinook took on a man called Dr. Marion Tinsley. Who he and what it, I expect you’re wondering?

Well, Tinsley was as close to god as you can get in the sleepy world of draughts (checkers). In his World Championship career from 1955 to 1991, or 46 years, he lost precisely 7 games and no matches to all human challengers, a feat not equalled in any game or sport of the past or present. And never will be.

Chinook was and is a computer program that plays draughts. It was developed by Jonathan Schaeffer, a research professor at the University of Alberta, Canada, holding the Canada Research Chair in Artificial Intelligence. He saw the lateral thinking ability of humans playing games as the challenge he needed to understand how computers could develop their own intelligence. So he went after draughts, arguably the easiest game to translate into computer based thinking.

After a year of improving development, Chinook placed second to Tinsley in the 1990 US Championships and earned the controversial right to play Tinsley for the world title. In August 1992 the two went into battle and Tinsley won 4-2 (and 33 draws!), the closest match he’d had in 47 years. Two years later they did battle again but, after 4 draws, Tinsley was taken ill with a hitherto undiagnosed cancer (he died 7 months later). Chinook was declared the winner. Another two years and Chinook defended against the second best human, Don Lafferty, drawing the match 1-1-18, and thus retaining the title. That same year, 1996, it crushed the field in the US Championships and was then taken out of service by Dr. Jonathan Schaeffer.

A year later, on the 11th May 1997, the chess playing computer Deep Blue, created by IBM, defeated Gary Kasparov, the greatest chess player of all time (although he said they cheated). This was a different type of victory, as IBM’s massive budget and development team had spent millions on creating an enormous parallel processing super-computer just for the job. It was all for publicising IBM’s name and it did just that.

All very interesting, I’m sure.

But now Dr. Jonathan Schaeffer is back - and this time it’s personal (correction). To me and to you. Aside from draughts, Schaeffer has headed the University of Alberta Computer Poker Research Group (CPRG), an ongoing concern for about 15 years.

The early years were tougher than they wished and it wasn’t until 2003⁽¹⁾ that serious and usable programs appeared. The first was Sparbot, based on pseudo-optimal player strategy, or changing your playing style and seeing if you do better against a given opponent. Then came Vexbot, a program based on adaptive game theory, or learning what works over a long period of time. These two programs were combined in 2005 and released in the Poker Academy software, a commercially available learning tool for Texas Hold’em.

In July of that year Phil Laak took on a version of the new upstart bot called Poki-X in Las Vegas and won a narrow victory in less than perfect conditions. In 2006 Daniel Negreanu released Stacked, a poker entertainment game containing a version of Poki-X. A month later, in Boston, an updated version of Sparbot won the first and little-known artificial intelligence poker competition without much of a fight.

And so to the present.

July 2007. A big hotel in Vancouver, Canada. Over four sessions of play, in two days, the new challenge to life as we know it stepped up to the plate in a $50,000 match with Phil (’The Unabomber’) Laak and Ali Eslami, a big limit player. The program has been renamed Polaris and the competition that took place was four 500-hand duplicate matches. In each match the same series of cards were dealt in two parallel Man vs. Machine heads-up games, teammates playing the opposite hands in each game. The duplicate idea was to reduce the element of luck in being dealt good cards. The game was $10/20 limit hold’em and the combined stacks of both players would determine the winner of each session. (within 25 small bets of the start stack being declared a draw)

Play was conducted in a big meeting room, one human visible, one human in another room, each with a terminal screen in front of them. An audience of 50 or more people watched on huge display screens and the human present (swapping each session) gave a running commentary on play.

Round 1 was drawn with the humans being down a mere and insignificant $70. Round 2 saw the humans being crushed, Eslami losing $2495 but Laak winning $1570, a total of -$925. The humans looked dispirited, as well they might. Then something strange happened. The CPRG team had chosen the specific style of bot (computer program) to use by modelling 10 different ones against the expected opponents - and used just one to play rounds one and two. For the final rounds they switched to a multi-bot scenario, a master bot switching modes to try and outmanouvre the humans. A storming victory, it seems, was not enough - they wanted blood.

On first sight that would appear to be a mistake. People seem to be reluctant to believe that a consistent line of attack can win and will often outplay themselves, as when up against a super-aggressive player. What the CPRG were up to was trying to stop the humans learning the types of play that would work consistently against their bot. It was intended that the bots would start acting like humans themselves; but Laak put in another fine win, up $1455 whilst Eslami again lost $635. Round 3 total, + $820 but still down $175 overall. Sessions one apiece and one draw.

Then came the final session, with Ali Eslami commentating for the audience. Reading from the tickertape-style blogging of the event it was clear that, although Eslami felt the experience was tortuously tough, he had come to see the weakness in the bot’s play. Quite contrary to the CPRG’s intentions. He turned his early stack loss of $600 into a final victory of $460, and with Laak winning $110 the boys had won. Just. Up $395 in 4000 hands of $10/20 limit hold’em.

Basically, that is a draw in anyone’s book. Ali Eslami admitted as much in his speech, going on to say that if they had been forced into time constraints, they would have lost. The humans pocketed $5000 for each session victory and $2500 for the drawn one (I don’t know why), for a grand total of $12,500 - plus expenses, of course.

Now all this computer-based algorithmic research into uncertain risk strategy may well have a solid goal of improving decisions in politics, finance and even war, but why pick on us? Are we just innocent victims because we play the toughest game on earth, or are the CPRG just out to make a lot of money?

I for one don’t like the look of this, not that I play limit hold’em. And I’m not starting now. But I did decide to download the latest version of the Poker Academy software to see how good it was at no-limit. Bloody hell! Sacre-bleu for the French Canadians. I want to make dam sure that I’m up against real people from now on, even when I’m playing bricks-n-mortar poker!

There may soon come a moment when we have to send a cyborg assassin back in time to bump off Mrs Schaeffer. I see Arnold Schwarzenegger in the part. Whose side will you be on?

[1] It is not quite correct to say that no useable program appeared until 2003.  They had winning bots for multi-player games shortly after the inception of the CPRG in 1997.  They won consistently in games with average to decent human players for tens of millions of hands. However, the weaknesses of those programs showed up most prominently in the two-player game (where tricky play is most important), which is one of the reasons they shifted their focus to the two-player game.     Back

Correction

Although Jonathan was the administrative head of the CPRG, Dr. Darse Billings was the lead architect — all of the research ideas prior to 2005 were his, while several M.Sc. students and programmer-analysts did the actual coding.         Back