Checkered Past

Way to go!!
Can't wait for the time chess is solved. That will help us stop playing, leave the game behind as a curious scientific experiment and focus on something more useful :)))

Marion Tinsley's absolute dominance in checkers was truly remarkable, and should be of interest to anyone who studies games and game theory. I've always been fascinated by his ability to innately feel his way to victory, and how his mind instantly processed early patterns to completion. The greatest shame is his second match with Chinook had to be stopped as he felt the first signs of cancer. I wonder how he'd feel about the announcement of the solution for checkers.

As far as poker goes, and something I wrote on this board a long time ago, as long as the match is heads-up Hold'em, computers will be able to apply game theory and find Nash Equilibria for the actions of poker at all stages eventually once they get a large enough database of sample hands for any given opponent. However, simply changing the opponent might necessitate a recalculation of the Nash solution set, though perhaps it would be minor for the majority of opponents. A very close to optimal base-line could probably be developed, giving a mixed strategy at every decision point. The strategy would have to be a mixed solution set because poker is a game of incomplete information (unlike checkers and chess) so it is highly unlikely that a single solution set is possible except *perhaps* at tail end hands (i.e. how to play AA preflop). This would lead to variance in the results, so in that way a computer would never be 'unbeatable', though it can be said that it plays 'optimally' with the highest expected value of any player.

Again, this is for heads-up. No Limit, as opposed to Pot Limit or 'Fixed' Limit, would favor the computer as the ability to move all-in eliminates the need to play every street (flop and post-flop) in poker. It becomes a push-or-fold preflop calculation, which is relatively easy. In fact, short-stacked, heads-up, No Limit has already been practically solved.

The real challenge I see for computers in poker is multiway pots with multiple opponents and a mixing of styles. Here, the factors like whether or not one of the opponents is currently tilting, or vastly adjusting their game to play against one of the weaker opponents also in the hand, or just the combination of players in the pot, and other 'feel' variables are important and hard to program. Add in deep-stacks and the computer will have a long way to go to solve the game.

Thank you, Stern. Excellent comments that I could never have phrased so well.

Even if chess ever IS solved, it would still be playable because no human could ever memorize all of the necessary variations to every opening.

Agreed kgd. People are not going to stop playing checkers now just because it is solved. Some day when they solve chess it will still be popular for the same reason, that is, no-one will be able to memorize all the necessary variations.

For me it would suffice if they can find a solution to the question: Is it a draw?
Because there is a draw zone (in german we say "Remisbreite"),even it may be very small, black should be able to hold - in my opinion.
Besides this I can't believe that they ever will find a solution for chess. Where to write down all the variations? Can anybody tell me how much space you need even to write down the variations? Maybe even for that problem of space there is no solution.

For me it would suffice if they can find a solution to the question: Is it a draw?
Because there is a draw zone (in german we say "Remisbreite"),even it may be very small, black should be able to hold - in my opinion.
Besides this I can't believe that they ever will find a solution for chess. Where to write down all the variations? Can anybody tell me how much space you need even to write down the variations? Maybe even for that problem of space there is no solution.

Anyone know how good Schaeffer is?

Gerhard the number of possible chess positions exceeds the number of atoms in the universe, so yeah, it would be kind of hard.

If chess is ever solved, I for one will lose interest in playing. Knowing the outcome of checkers, I am not interested in ever playing a game of checkers in my life. The mystery of chess right now is that we don't know what is suposed to happen and get seduced by it. If you knew that perfect play by your opponent will end up in a draw, why would you play and try to win - to prove you are smarter than your opponent? There are better and more usefull venues to showcase your intelligence, don't you think?

I was arguing with a friend last night about whether chess would ever be solved. I said no, he said eventually. Can someone who knows about these things give me some idea of the scale of the problem, and speculate as to whether it's even vaguely possible to achieve in practise? One point I was concerned about was whether it would be possible to store all the data associated. 6 man tablebases are a few gig(?). I wonder if our solar system can physically accomodate enough information for a 32 man tablebase. (bonus points for invoking quantum mechanics here)

Playing any game is a social contract between players. Agreeing to follow the rules, taking turns and accepting the result is an activity that mirrors the deepest aspects of human culture and is for most people, something they do for enjoyment. Solving chess or checkers won’t spoil the enjoyment for most people because the most human of activities is play. My car gets me there faster, but I enjoy riding my bicycle more and I still like to write short stories and poems, despite the fact that professional writers do it better then I do. Maybe solving chess will turn off the intellectual snobs who use chess to prove how smart they are, or diminish the status of professional genius, once a machine can do it better then people. But that means that chess will live on as a game of popular entertainment, which it’s been for most of its1500 years because people enjoy it. BTW One Jump Ahead is an excellent book, a modern example of the American myth of John Henry.

CHECKERS & TINSLEY

[] I wonder whether M.Tinsley would have been able to draw against the new Chinook? My guess is yes, at least occasionally.

[] I think Tinsley would cheer the perfection of the new Chinook. Tinsley suffered from the lack of any serious competition during his 40 years of playing. Shortly before Tinsley died of cancer, he played Chinook and won +4,-2,=33 (circa 1992). Tinsley had not lost 2 checkers games since he was in diapers. Tinsley was thrilled!

CHESS IS A THEORETICAL DRAW

[] John Watson wrote that all chess grandmasters believe chess is a draw with perfect play.
I believe chess would also be a theoretical draw from any of the other 959 start positions of chess960 (Fischer Random).

But what if chess is Not a theoretical draw, meaning that Black has no chance to win or draw against perfect White play? That would be grossly unfair and unsporting.
In that case chess could be fixed by using a fair first move rule of the type used in Twixt: White moves, then Black decides whether he wants to switch to playing the White pieces.

POKER AND SOFTWARE BLUFFING

[] Poker is about winning money, not really about winning hands. Bluffing, and making human intuitive guesstimates about the bluffing of others, is something beyond anything that poker playing software has yet touched upon.

GO SOFTWARE IS WEAK

[] A few months ago, on PhysOrg.com, it was reported that software had made modest gains in the game of Go. Apparently Go software is so far not able to challenge human masters, not even close yet. The article did not expect that imbalance to change any time soon.

{
(from August 2003 , http://www.britgo.org/reviews/goplusplus.html)

Go++ is a program for Windows. It plays Go, and plays it as well as any program... It is notoriously difficult to assess the strength of Go-playing programs, because humans soon become accustomed to their weaknesses... Dr. Reiss claims that Go++ is about 7-kyu, and supports this claim by giving its results against some members of North London Go Club. These were, I assume, people who had never played against it before. I tested it myself by giving it nine handicap stones on a full board, with it set to its maximum playing strength, and I beat it comfortably (I am 2-kyu on the European Rating List).
}

What about the question of "understanding"? It was heatedly debated on an earlier thread about computer progress in chess.

By analogy, are there positional principles in checkers? (I'd guess there must be)... and does the now-perfect play of the computer program align with those principles, in a way that makes sense to human masters of checkers? Or, does the perfect fruit of brute-force calculation fall beyond the range of human comprehension -- as seems to be true for chess?

In other words, can strong human checker players learn anything about improving their own play, by observing how the perfect engine does it?

In chess, the consensus here (in my recollection) seemed to be that strong humans can't learn from observing the strongest computers, because the computers "understand" chess at a deeper level that goes beyond any principles-based human level of "understanding."

Being a Ph.D. studnet in Math, the way I look at chess is from a scientific standpoint and I am very interested in how the game eventually turns out to be. The flawed idea some insecure people have trying to prove their "intellectual superiority" by defeating their oppenent in a game of chess is a big turnoff and flat out stupid. The social factor is of secondary importance to me as well. However, I reckon that many people enjoy the chess social environment more than the pursuit for chess perfection. While I and many other people will turn away from chess once it is solved, others will still continue to make the game their every day leisure activity. I for one would prefer to watch TV, go jogging or surf the net for leisure. Nothing wrong either way.

The other question posed in this tread is pretty interesting and not easy to answer. Of course, solving chess completely is unfeasible using today's technology. A breakthrough such as quantum computing or another technology allowing for storing information at the subatomic level might be the key. We'll have to wait and see and admit to ourselves that it probably won't happen in our life times.

... and by the way, that guy Marion Tinsley must've been quite remarkable. I can't imagine he lost only a handful of games his ENTIRE life, two of them to a computer. The fact that virtually no other human was able to beat him even in a single game is hard to comprehend. His brain must've been wired very differently ;)) Do you think he would lose a game to today's perfect-play program? Or would he be able to draw every time when at full strength?
As a (half) joke, he might've been an alien - have you seen his picture in the Chessbase article - he looks like someone straight out of Star Trek.

GeneM, I believe I read once, somewhere, that a GM with considerable Chess960 experience(could it even have been Svidler?) stated that there were starting positions that hugely favoured White.

Yes, and I think he generalized it to say that overall, White's advantage is bigger in Chess960 than in ordinary chess.

.. looking for confirmation of this I found a text written by Gene himself: http://chess960.com/wordpress2/?p=38

"Anyone know how good Schaeffer is?"

He was a master in the 90s when I last saw him play. Very good general knowledge, openings a bit shaky, but extremely prone to time trouble. Basically what you'd expect from a master who didn't play very often.

Charley & acirce,

It is also very likely that some chess960 setups give White LESS of a theoretical advantage than does the traditional chess1 setup.

In fact, the actual game DATA from Mainz Germany so far shows that overall White has less of an advantage (on average) from chess960 than from chess1! (Mainz holds Rapid tourneys in both chess960 & chess1, enabling comparisons.)

This might mean that the theoretical advantage White gets in chess (chess1 or chess960) can be strongly exploited if but only if White has months to study move data collected over centuries for the one setup used in his upcoming game.

We are talking about the philosophy of chess.

This may be a good time to propagate the ancient Scandinavian game of hnefatafl. This game tends to have more legal moves per position than chess, which should mean that (like go) it ought to be more difficult for computers than chess is. I found this link to online play:

http://aagenielsen.dk/hnefatafl_online.html

They didn't solve all of the 3-move openings. This means Chinook can still theoretically lose under normal tournament rules.

Reply to 'ew':

My understanding is that Chinnok did solve all of the 3-move openings in checkers.

The change made to checkers in 1900 (and extended circa 1930) is loosely analogous to chess960 (FRC). However, ...
3-move checkers does not increase the number of POSSIBLE positions, it only increases the number of LIKELY positions (compared to the old/original "Go As You Please" or GAYP rule set).

In contrast, chess960 increases the number of possible positions, and these lead to middle-game formations that fall outside the more familiar patterns repeated in traditional chess.

I can understand why some chess players are against variety in start position, but I wonder whether they are also against more variety in middle-game formations? And if so, why?

kgd,
I know that the possible positions exceed the number of atoms in the universe!
But my question has been: Can we ask something different like "Is black able to stay in the drawzone?". Just define properly what a drawzone should be (ask Kramnik what does it need to win certain positions :-), then maybe we get an answer to the eternal question, whether black is lost or not.
To solve chess as a whole: I don't see any chance for that.

The comments about poker in this thread so far are off base.

You don't have to recalculate a Nash equilibrium if the opponent changes his strategy. For one 2-player zero-sum game, there can't be more than one Nash equilibrium to begin with. If the opponent deviates from optimal strategy, you can deviate to FURTHER exploit him, but his deviation can at worst be break-even (co-optimal) compared to optimal play.

Limit is much easier for computers to handle, and bots have been far more successful at heads-up limit than at heads-up NL. (Exception for very short-stacked (under 10 big blinds) NL noted)

Poker bots bluff and snap off bluffs. It's basic math, not "human-intuitive guesstimates".

Tinsley would draw at least 90% of 3-move games against Chinook, and probably closer to 99% if he were only playing for a draw (since winning is impossible). In a match of 100 GAYP games, I'd take even money that Tinsley could draw every game.

I must correct some of the posters above.

The number of possible chess positions is much smaller than the number of atoms in the universe.
(The previous posters might be thinking of the number of possible chess games.)

The number of chess postions is at most 5×10^52,
which is less than the number of atoms in the sun.

http://en.wikipedia.org/wiki/Shannon_number

TC:"You don't have to recalculate a Nash equilibrium if the opponent changes his strategy."

I didn't say 'opponent changes his *STRATEGY*', I said, if the OPPONENT changes. The very definition of Nash equilibrium means the *same* opponent cannot improve his expectation if he diverts. But this changing of opposition is obviously very common in poker, so a computer would need to compile a database to classify each opponent it faced. Read what I wrote again before jumping down my throat.

tc:"Limit is much easier for computers to handle, and bots have been far more successful at heads-up limit than at heads-up NL. (Exception for very short-stacked (under 10 big blinds) NL noted)"

Heads up is the key more than limit vs no limit. Heads up No limit ~50BB stacks is not difficult for a computer at all. Only deep stack (500x+) is tricky, but not so much that computers aren't already very competitive in deep stack. Again, the key is Heads up, where math dominates.

What evidence do you have that bots are more successful in limit than NL Heads Up? The evidence I've seen is very very scarce, mainly because it is almost impossible to get away with bot play Heads-up in either format for long. I'm betting you're just guessing this is true.

6-max, Bots in NL have been more successful, *perhaps* because it was the more popular game when bots came on the scene and thus targeted first. Yes, I've seen actual data and know a former head of support for one of the biggest online sites in the business.

TC:" Poker bots bluff and snap off bluffs. It's basic math, not "human-intuitive guesstimates"."

I've never said differently, so I hope you aren't addressing this to me. Maybe to Gene M - and I agree, Heads-up bluffing and bluff catching is simply a pot size to bet ratio to determine the optimal % to bluff.

My whole thing I said before was that Heads-up is so much easier for computers than multi-way poker. Put an opponent acting before and one or two after the computer and the calculations can become very complex. The most successful bots aren't great multi-way players, they are just very TIGHT, with infinite patience. Tight was enough 2-3 years ago when there was so many fish around, tight is all you needed.

If the opponent changes? Nonsense. There's no difference between a new opponent with a new strategy and the same opponent with a new strategy. I thought you may have mistakenly written Nash equilibrium where you meant optimal response, but now that you've done it twice, it's obvious you have no idea what a Nash equilibrium is. If the computer plays Nash equilibrium strategy, it DOESN"T MATTER WHAT THE OPPONENT DOES, he can't win. Every "new" strategy (or new opponent) CANNOT win money over the long term if the computer plays that same strategy. The computer can even print out its exact strategy, let you read it during the hand, and YOU STILL CAN'T WIN (long term, obviously anybody can lucksack a few hands). That's game theory 101.

Bots are reported at much higher stakes in limit than NL. I've never seen a report of a bot playing 100+BB no limit (and winning) at 2-4 or above, whereas I've seen plenty of reports in 100-200 limit.

I suppose we should remember that checkers has not been solved... only the 8x8 version. I suppose the more complex 10x10 version (draughts) has not been solved, but would it be a matter of tweaking?

I remember researching a Senegelese Grandmaster named Ndiaga Samb (during his match with a computer named "Buggy") and finding my way onto the International Draughts Federation website. I went through many of the 10x10 puzzles and they were absolutely beautiful! The combinations and the sacrifices were astounding. I went over some of the annotated games and realized that these GMs were able to see very farther than chess players because the piece movements were not varied and thus, more forced variations... hence a higher incidence of draws. Of course we know that seeing far is not what chess is about, but brute calculation is probably more important in checkers/draughts.

Here's an illustrative story told to me in a phone conversation by an expert draught player:

The expert draught player (also a Chess Master)and a FIDE Chess Master were having a chess/checker debate. The draught player was discussing the complexity of draughts. This FM thought he could figure out the variations over the board and challenged him to a game. The FM didn't last very long. The draught player told me, "He wasn't even close." Then he started giving the FM all types of odds. Still no progress. The FM learned a valuable lesson. Checkers is not the game we played at the kitchen table as kids.

Check out this site on 10x10:

See http://www.10x10.dse.nl/index.html

You are interpreting what a "strategy" means under game theory too widely. You are actually *correct* in saying a different opponent, who has a different range of hand selection and post flop strategy, and the same opponent who changes drastically his range of hand selection and his post flop play are one in the same. But it is easier to see what saying a different opponent brings and what a same opponent who suddenly changes means (because you can say that this sudden ability to change has already been recognized by the computer). And guess what, in both cases the Nash IS DIFFERENT.

Look, Nash Equilibrium and the inability to unilaterally change strategy to increase one's given expected value applies to a *given game* with *defined payouts*. Here the term "game" is the traditional one in game theory, and that is very narrow. In typical (simplified) game theory games, where Player A has the row of strategies A, B, C, D to choose from and Player B has the columns E, F, G, H, and each player chooses a strategy letter and you look up in the crosstable what the payoff is for each player, then you can calculate the Nash and neither player can profit from diverting from it, meaning Player A can change from, say, selecting A-25% and B-10% to a new change of A-40% and B-5% and it wouldn't do him any good if Player B sticks to his Nash. That is true and is the very definition. No disagreement so far.

But you are applying how far a Nash Equilibrium reaches way too liberally, because you aren't recognizing what a change of opponent OR the same opponent, who, for instance, goes from a very tight, non-bluffing strategy to a wildman, bluff-too-much one (that the computer does not expect at all from this same opponent) does to the game theory outlook. What this does is change the PAYOUTS for strategies A, B, C, D vs counter-strategies E, F, G, H, and therefore is considered a *whole new game* under "Game Theory 101", with a whole new solution set and Nash. I use the 'new opponent' nomenclature because this makes it easier to distinguish the difference between 'a strategy change within a given game with defined payouts (same opponent)' which the current Nash for that game deals with nicely, and whole new game with different payouts due to the vast change of expected value for strategies ABCD vs EFGH and therefore a whole new Nash calculation.

If you don't see how a different opponent (or again, the same one who can switch widely enough AND the CPU does not have that different style in his database yet), with a different starting hand range, different value betting and raising requirements, and different fold criteria, doesn't fundamentally change the payouts for any counter- strategy to this matchup and therefore is practically a different game with a different solution set and different Nash, then we can't really agree on anything.

Sorry, but I think it is you who does not understand how to apply game theory to poker, because you are taking the "unable to unilaterally change one's strategy" part of Nash and applying it universally (which is downright ridiculous to think that poker could have just one Nash for all hand ranges and all counter actions, just think about it for a second, and if you were right why haven't these "universal Nashes" been published yet?) to every situations, instead of recognizing what a Nash equilibrium calculation gives you (it only applies to a given game with its given payouts) and what a change of poker opponent (strategy) means (changing the payouts and thus changing the very game is question).

In *your* world, once you've figured out the Nash for Opponent X who opens with [AA-JJ, AK-AQ, KQs] you've ALSO figured out the Nash if he changes his requirements to [AA-22, AK-A2, KQ-K2, QJ-Q2, ....43-42, 32] since your are counting this as a "mere" change in Opponent X's strategy. This is just fundamentally wrong, the change in hand ranges that Opponent X is now undertaking defines a WHOLE NEW GAME under game theory and all the calculations it entails. And this doesn't end with just starting hands changes, it also applies to vast play differences in other parts of the game.

You are confusing what 'game' means in game theory and what a poker 'game' is, and treating them as one in the same. If you don't agree with me after this, then we might as well shake hands and go our separate ways since our axioms are not in the same ballpark.

GeneM:

From http://www.nytimes.com/2007/07/20/science/20checkers.html

"The new research proves that Chinook is invincible in traditional checkers. In most tournament play, however, a match now starts with three moves chosen at random. In solving the traditional game, the researchers have also solved 21 of the 156 three-move openings, leaving some hope for humans."

Excellent citation 'ew'. I guess I do not exactly understand how the many start positions of 3-move checkers (or checkers156?) are generated.

Nor do I understand why some sources say 3-move checkers has 174 start positions, while more seems to say 156.

You have no idea what a game, a strategy, a payout matrix, or a Nash equilibrium is- you're just misusing big words repeatedly to try to sound intelligent. Anybody who's actually interested can pick up Mathematics of Poker and see I'm 100% right. You completely fail at the concept of a Nash equilibrium applying to multiple streets, or that multiple streets can be solved as the same game. Go browse Mathematics of Poker in the bookstore, then come back and post your retraction.

Your comment about different payouts is completely retarded. Poker has a gigantic payout matrix (far beyond current computational ability, which is why poker isn't a completely solved game, to answer your question about why this strategy isn't published- umm, duh) with every permutation of legal actions and cards, each with a payout. Changing STRATEGY for how often certain outcomes occur can't change the PAYOUT when they do occur. Just because I call 3 bets (in limit) less frequently doesn't change the value of those 3 bets when i do call. W T F?

Beaver.

That's what else they mount on walls in Alberta.

"...it can't be done for a very long time unless there is a fundamentally new breakthrough." Yeah, thats what they said about computers playing chess back when 2001: A Space Odyssey came out. Then they said they would never beat humans... then never beat Kasparov...I'm going out on a limb and predicting that Chess will be busted by the late 2020's.

>>"...it can't be done for a very long time unless there is a fundamentally new breakthrough." Yeah, thats what they said about computers playing chess back when 2001: A Space Odyssey came out. Then they said they would never beat humans... then never beat Kasparov...I'm going out on a limb and predicting that Chess will be busted by the late 2020's.

True...but wouldn't alpha-beta pruning count as a major breakthrough? So really, they were right.

There is a limit to how small you can make a transistor. Eventually you reach the point where they're too small for electrons to flow through them. Once you get there, you either need a major breakthrough or make the computer larger. Given the depth of chess's complexity, the latter is impractical.

So, I think it's safe to say that it really will take a big breakthrough. When that will come, I have no clue.

So Chinook has solved GAYP but not every opening in tournament checkers? Does this mean it can still lose? Being able to say you beat a tablebase would be something.

This is a funny video about Chess by Mail, check it out.