The article confuses me. How can checkers be "solved" if only the best-play outcome is only known for pieces involving at most ten pieces? On the other hand, the article says this: * * * It does not matter how the players make it to 10 checkers left because from that point on, the computer cannot lose, Schaeffer said. For two players who never make a mistake, every game would be a draw, he said. * * * This would seem to imply that the best-play outcome of the checkers start position is known to be a draw. Is that right? On 7/19/07, Mike Stay <metaweta@gmail.com> wrote:

Whew! It's just checkers, not chess.

On 7/19/07, Robert Baillie <rjbaillie@frii.com> wrote:

...

"Computer program can't lose at checkers"

http://news.yahoo.com/s/ap/20070719/ap_on_hi_te/solving_checkers;_ylt=AoQVuW...

apparently, they analyzed all games with 10 or fewer remaining pieces.

the correct website (not the one in the yahoo article) is: http://www.cs.ualberta.ca/~chinook/ warning: if you don't have the latest java, parts of the chinook site will hang your firefox browser!

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Thane Plambeck tplambeck@gmail.com http://www.plambeck.org/ehome.htm

From: "Edwin Clark" <eclark@math.usf.edu>

Here's what the paper in Science says (in part):

Meanwhile, Schaeffer is turning his computers to poker. In principle, that game can't be solved--but it can make you a lot of money.

Here are some news about that: http://www.pokernews.com/news/2007/7/man-machine-poker-championship-tomorrow... http://www.cardplayer.com/poker-news/article/9320 Alec Mihailovs http://mihailovs.com/Alec/

From: "Alec Mihailovs" <alec@mihailovs.com>

http://poker.cs.ualberta.ca/man-machine/

And we can see that poker is not solved yet. Alec

the simplest non-trivial poker game i can think of is: 1. the players ante one chip each to the pot. 2. the players are each dealt a card from a deck of three cards: 1, 2, and 3. 3. A has the opportunity to bet one chip (B must call if he wants to continue to play). 4. if A doesn't bet, B can bet one chip (A must call if he wants to continue to play). 5. if both players are still in, best hand wins the pot. there is clearly no incentive to bluff with a 2, but there is with a 1. what are the optimal strategies for this game? if you can manage that, what are the optimal strategies with the cards 1, 2, 3, and 4? erich

I've seen various papers analyzing (extremely restricted) poker-like card games, and have often wondered what the best results along these lines are.

Maybe someone knows a good survey article?

Thu, 26 Jul 2007 11:53:00 -0400 "Andy Latto" <andy.latto@gmail.com> The book you want is The Mathematics of Poker, by Bill Chen and Jerrod Ankenman. A book you probably *don't* want, but may enjoy anyway, is "Poker Strategy: Winning with Game Theory" by Nesmith Ankeny (he was a math professor at MIT when I was an undergrad). It is a book about how to win at poker, but (for better or for worse) written by a mathematician. If I remember correctly, the main concern of the book was when and how to bluff. It is available used from Amazon (published by Basic Books in 1981, ISBN 0-465-05839-6

FYI -- The New York Times July 26, 2007 In Poker Match Against a Machine, Humans Are Better Bluffers By JOHN MARKOFF VANCOUVER, British Columbia, July 25 — For anyone stuck on a casino stool, playing hours of video poker, rest assured: humans can still beat a computer. But computers may soon dominate on the felt-top table, as they have on the chessboard. In a match of wits between man and machine this week, a software program running on an ordinary laptop computer fought a close match, but lost to two well-known professional human poker players. The contest, which was billed as the “First Man-Machine Poker Championship” and which offered prize money totaling $50,000, pitted two professionals, Phil Laak and Ali Eslami, against a program written by a team of artificial intelligence researchers from the University of Alberta. They gave it a name that probably no gambler would ever choose as a nickname, Polaris. Poker is thought to be a more difficult challenge for software designers than games like chess and checkers. Computer scientists have to develop different strategies and algorithms to deal with the uncertainties introduced by the hidden cards held by each player as well as difficult-to-quantify risk-taking behaviors such as bluffing. In the past, research has focused on chess and checkers. In 1997 Deep Blue, a supercomputer-based chess playing software system developed by I.B.M. researchers, beat Gary Kasparov, the world chess champion. The University of Alberta researchers won the world checkers championship in 1994, and earlier this month they reported that they had developed a program that cannot lose, and at best can be tied at checkers. However, Jonathan Schaeffer, chairman of the University of Alberta computer science department and the researcher who initiated the poker playing research effort 16 years ago, said that the advances that are being made in the development of poker-playing software are likely to be more applicable in the real world than chess research. “I contend that poker is harder than chess for computers, and the research results that come out of the work on poker will be much more generally applicable than what came out of the chess research,” he said. Research interest has shifted to games like poker in recent years, in part because chess is no longer of keen interest and in part because rapid progress is being made in developing new algorithms with broad practical applications in areas such as negotiation and commerce, said Tuomas Sandholm, a Carnegie Mellon University computer scientist. The version of poker used in the match Monday and Tuesday at the annual meeting of the Association for the Advancement Artificial Intelligence was a popular game called Texas Hold ’Em heads-up limit poker, a two-player game in which some cards are hidden and others are playable by both sides. Each hand is played in four rounds during which each side can bet or fold. After four rounds of 500 hands each, lasting about four hours, the player with the most money is declared the winner. Unlike chess competitions, which are marked by extreme concentration and long moments of silence, the tournament in a hotel here was festive, with each human competitor offering a running commentary on Polaris’s style of play to an audience of several hundred people. Mr. Laak, who is nicknamed the Unabomber because of his trademark hooded sweatshirt and sunglasses, would frequently gesticulate wildly at the laptop computer screen and repeatedly referred to the computer’s play as “sick” — his way of describing an unexpected or extraordinary action on the part of the machine. His supporters included Jennifer Tilly, an actress who is also a well-known professional poker player. The contest had to be formatted to accommodate the computer. To counter the luck of the draw, a dominating factor in poker, the human players were put in separate rooms. The hand dealt to the human in one room was identical to the hand dealt to the computer in the other room. The format also eliminated one of the crucial aspects of traditional poker called the tell, subtle clues such as facial ticks that may permit other players to make accurate guesses about the hidden cards held by their opponent. Mr. Eslami and Mr. Laak are both well-known figures in the world of poker and are mathematically skilled and familiar with the techniques used by their opponents. Although Mr. Eslami and Mr. Laak are not the best human players in the world, the scientists argued that their knowledge of computing made them more effective opponents than other top-ranked poker players. The human team reached a draw in the first round even though their total winnings were slightly less than that of the computer. The match rules specified that small differences were not considered significant because of statistical variation. On Monday night, the second round went heavily to Polaris, leaving the human players visibly demoralized. “Polaris was beating me like a drum,” Mr. Eslami said after the round. However, during the third round on Tuesday afternoon, the human team rebounded, when the Polaris team’s shift in strategy backfired. They used a version of the program that was supposed to add a level of adaptability and “learning.” Unlike computer chess programs, which require immense amounts of computing power to determine every possible future move, the Polaris poker software is largely precomputed, running for weeks before the match to build a series of agents called “bots” that have differing personalities or styles of play, ranging from aggressive to passive. The Alberta team modeled 10 different bots before the competition and then chose to run a single program in the first two rounds. In the third round, the researchers used a more sophisticated ensemble of programs in which a “coach” program monitored the performance of three bots and then moved them in and out of the lineup like football players. Mr. Laak and Mr. Eslami won the final round handily, but not before Polaris won a $240 pot with a royal flush then beat Mr. Eslami’s three-of-a-kind. The two men said that Polaris had challenged them far more than their human opponents.