Solitaire Klondike: Math Whizzes, Get Cracking
December 24th, 2010 at 11:21:10 AM
permalink
Standard old Klondike solitaire has been getting my play lately. I have recently gotten into the habit of discarding bad starts since that is so easy to do on the computer, and even with doing that my win percentage still has been around 10% over 106 games tallied. I was wondering how good that was but only seem to find opinions instead of facts searching for that. Anybody know what is really good?
Theoretically, it seems, maybe 2 out of 3 Klondike games have solutions. But at various places like wikipedia found this surprising statement: "... the theoretical odds of winning a standard game of ... Klondike are currently unknown. It has been said that the inability for theoreticians to calculate these odds is 'one of the embarrassments of applied mathematics' " A challenge for the Wizard or someone else in this group ?
Theoretically, it seems, maybe 2 out of 3 Klondike games have solutions. But at various places like wikipedia found this surprising statement: "... the theoretical odds of winning a standard game of ... Klondike are currently unknown. It has been said that the inability for theoreticians to calculate these odds is 'one of the embarrassments of applied mathematics' " A challenge for the Wizard or someone else in this group ?
the next time Dame Fortune toys with your heart, your soul and your wallet, raise your glass and praise her thus: Thanks for nothing, you cold-hearted, evil, damnable, nefarious, low-life, malicious monster from Hell! She is, after all, stone deaf. ... Arnold Snyder
December 24th, 2010 at 11:35:37 AM
permalink
I just read a few of the linked papers. The rollout strategy Yan they used is similar in concept to the strategy used to analyze video poker or Pai Gow. The difference is that in these casino games, after the player's one decision, the game is over. In Klondike, there are dozens of decisions, all of which affect later decisions. So the problem becomes exponentially difficult from a computational standpoint. The Oregon State paper is pretty interesting too.
But divining an optimal strategy in a multi-step strategy game is a terribly difficult task. Just ask the Wizard - he did a game with two player strategy choices, where the first impacted the second, and that took quite a while. And that's just going from 1 choice to 2. Going from 2 to a larger number (like the number of plays in Klondike) is beyond the capabilities of closed-form analysis at this time. You have to use heuristics or you'll never come close to finishing.
But divining an optimal strategy in a multi-step strategy game is a terribly difficult task. Just ask the Wizard - he did a game with two player strategy choices, where the first impacted the second, and that took quite a while. And that's just going from 1 choice to 2. Going from 2 to a larger number (like the number of plays in Klondike) is beyond the capabilities of closed-form analysis at this time. You have to use heuristics or you'll never come close to finishing.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
December 24th, 2010 at 12:34:01 PM
permalink
I read a piece once about a guy, last name started with a C, that offered soliare. $52 bucks a game, $5 for every card peeled off, single draw, one time through. They said the odds couldn't be figured, but he made a fortune. I believe that particular variation is named after him. Anybody know of this, or did I have another dream???
Before you diagnose yourself with depression or low self-esteem, first make sure that you are not, in fact, just surrounded by assholes." ~ William Gibson
December 24th, 2010 at 12:37:44 PM
permalink
I'm pretty sure this is how they offered it in casinos, back in the day. Klondike is one of the statutorially-defined gambling games in Nevada. See NRS 463.0152.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
December 24th, 2010 at 3:27:29 PM
permalink
Quote: avargovI read a piece once about a guy, last name started with a C, that offered soliare. $52 bucks a game, $5 for every card peeled off, single draw, one time through. They said the odds couldn't be figured, but he made a fortune. I believe that particular variation is named after him. Anybody know of this, or did I have another dream???
Canfield. Evil, evil game.
December 24th, 2010 at 3:33:43 PM
permalink
Quote: MathExtremistI'm pretty sure this is how they offered it in casinos, back in the day. Klondike is one of the statutorially-defined gambling games in Nevada. See NRS 463.0152.
I'm pretty sure too. I think it was back in the fifties. Every time I get into a conversation with a real Vegas old timer I ask them about it. Usually they are not old enough to remember it, but sometimes they recall second-hand stories of it. I think they followed the 52 units to play and 5 units per card rule. Same as at Cryptologic Internet casinos.
Agreed, this is one nut on the gambling tree that has never been cracked.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
December 28th, 2010 at 9:32:38 AM
permalink
Quote: Wizardthis is one nut on the gambling tree that has never been cracked.
Regarding the solution, why is it that modern computers don't help? If it is a problem of tediousness of examining all possibilities, could a program written for a computer [a super computer?] get that job done for this problem or other such problems?
the next time Dame Fortune toys with your heart, your soul and your wallet, raise your glass and praise her thus: Thanks for nothing, you cold-hearted, evil, damnable, nefarious, low-life, malicious monster from Hell! She is, after all, stone deaf. ... Arnold Snyder
December 28th, 2010 at 9:52:02 AM
permalink
I asked a related question about a year ago: https://wizardofvegas.com/forum/off-topic/general/530-solitaire-vegas-version/
Basically, I wanted to know if any casino currently offers, or ever offered, Vegas Solitaire.
Basically, I wanted to know if any casino currently offers, or ever offered, Vegas Solitaire.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/
Superstitions are silly, irrational, childish rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
December 28th, 2010 at 10:03:25 AM
permalink
For a variety of reasons.Quote: odiousgambitRegarding the solution, why is it that modern computers don't help? If it is a problem of tediousness of examining all possibilities, could a program written for a computer [a super computer?] get that job done for this problem or other such problems?
First, there is the very large number of starting positions.
Second, there are times when a decision has to be made. I.E. A spot opens up, and you have a choice of two cards/piles to move. Which you move affects the rest of the game. The supercomputer would have to compute the remainder of the game for both possibilities before deciding which way was better. And, in the interrum, additional choices come up. While it's easy to picture the factorial tree being formed, it is also a chaos situation.
It is not just tedious from a multiple options of play point of view, but from a programming standpoint as well.
It quickly gets staggering to the point of being impossible.
Maybe if HAL took a crack at it....
But since HAL is already 14 years behind schedule (or 19 years depending on your point of view), don't hold your breath waiting for the answer.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/
Superstitions are silly, irrational, childish rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
December 28th, 2010 at 10:30:18 AM
permalink
delete
Last edited by: odiousgambit on Mar 13, 2017
the next time Dame Fortune toys with your heart, your soul and your wallet, raise your glass and praise her thus: Thanks for nothing, you cold-hearted, evil, damnable, nefarious, low-life, malicious monster from Hell! She is, after all, stone deaf. ... Arnold Snyder
December 28th, 2010 at 1:23:58 PM
permalink
Quote: odiousgambitRegarding the solution, why is it that modern computers don't help? If it is a problem of tediousness of examining all possibilities, could a program written for a computer [a super computer?] get that job done for this problem or other such problems?
There is actually a large class of problems for which brute-force computational analysis is simply insufficient. Some of them, like this one, grow exponentially in complexity as the number of examinations increases. For example, if you were playing Klondike with 8 cards (just the kings and queens), you might have a reasonably easy go of it. Add in the jacks and it gets harder. Add in the tens and it gets much, much harder than going from queens to jacks. Add in the nines and it gets even harder still. Before long, you reach a problem the complexity of which is beyond the capability of modern computer analysis, even if you ran it as fast as possible. To put things in perspective, work has been done to demonstrate that there are somewhere around
45193640626062205213735739171550309047984050718
different positions in the game of chess. In comparison, the age of the universe is around
432329886000000000000000000
nanoseconds. So even if you had a computer that could perform one evaluation per nanosecond, and that computer magically sprang into being at the beginning of time, it would take over 100000000000000000000 times the age of the universe to "solve" chess.
Klondike isn't as difficult, but it's still harder than can be dealt with directly.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
December 28th, 2010 at 1:48:19 PM
permalink
wow
fascinating, thanks
fascinating, thanks
the next time Dame Fortune toys with your heart, your soul and your wallet, raise your glass and praise her thus: Thanks for nothing, you cold-hearted, evil, damnable, nefarious, low-life, malicious monster from Hell! She is, after all, stone deaf. ... Arnold Snyder
December 28th, 2010 at 1:59:13 PM
permalink
Surely all this N, P, NP, NPhard, Polynomial time, Traveling Salesman Problem stuff has been getting less daunting as chip speeds and capacities increase. What about all these clusters and memristor stuff?Quote: MathExtremistThere is actually a large class of problems for which brute-force computational analysis is simply insufficient. Some of them, like this one, grow exponentially in complexity as the number of examinations increases.
I've never felt good about calling a problem impossible to solve merely because so far its not been solved.
December 28th, 2010 at 4:08:39 PM
permalink
Where is Paul Erdos when you really need him....
Before you diagnose yourself with depression or low self-esteem, first make sure that you are not, in fact, just surrounded by assholes." ~ William Gibson
December 28th, 2010 at 4:17:39 PM
permalink
Quote: MathExtremistTo put things in perspective, work has been done to demonstrate that there are somewhere around
45193640626062205213735739171550309047984050718
different positions in the game of chess.
That number is probably being used as a password for encrypted documents somewhere. If you misplace it, you could probably look it up on the Internet.
Sanitized for Your Protection
December 28th, 2010 at 5:50:20 PM
permalink
Quote: FleaStiffSurely all this N, P, NP, NPhard, Polynomial time, Traveling Salesman Problem stuff has been getting less daunting as chip speeds and capacities increase. What about all these clusters and memristor stuff?
I've never felt good about calling a problem impossible to solve merely because so far its not been solved.
Not impossible, intractable. An exponential-time algorithm for solving a problem makes it "possible" to solve, but not tractable for all N. Regardless of how fast chips get, you're still talking about an insignificant improvement relative to the number of computations in an exponential-time problem. So for the TSP, for example, whether a fast computer can solve for N=1000 or 10000 is irrelevant to the question of whether TSP is computationally complex given the current model of computation.
If someone develops a computer that is not computationally-reducible to a Turing machine, that may change the underlying theory. But until then, the whole premise of complexity theory is still sound and that means "hard" problems are "hard" regardless of whether small examples of them have practical solutions.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
December 29th, 2010 at 6:53:16 AM
permalink
Quote: MathExtremistI'm pretty sure this is how they offered it in casinos, back in the day. Klondike is one of the statutorially-defined gambling games in Nevada. See NRS 463.0152.
Back in the '60s, my grandfather taught me how to play Klondike, and he kept score with matchsticks that way; he called it "the Vegas way". He was a long time gambler, his cousin (my mother's Uncle Joe) supplied cigarette-, candy-, and slot machines to bars in Pittsburgh's East End. I actually had a working old time slot machine for years, I sold it in the early '90s. (It was a Jennings fruit machine, "Big Chief", took quarters, all mechanical. I wish I had it now, or at least a picture of it. Oh, well.)
A falling knife has no handle.
March 13th, 2017 at 3:20:33 AM
permalink
Quote: rxwineThat number is probably being used as a password for encrypted documents somewhere. If you misplace it, you could probably look it up on the Internet.
https://www.google.com/#q=45193640626062205213735739171550309047984050718&*
not sure why that doesn't turn into a hyperlink
the next time Dame Fortune toys with your heart, your soul and your wallet, raise your glass and praise her thus: Thanks for nothing, you cold-hearted, evil, damnable, nefarious, low-life, malicious monster from Hell! She is, after all, stone deaf. ... Arnold Snyder
May 23rd, 2020 at 11:08:34 PM
permalink
I think I'm overdue to create a page about Klondike Solitaire. 5Dimes offers solitaire in their "mini casino."
It's a pretty short page and only covers the 5dimes rules.
I'm not sure what my question is, but I welcome comments on the page and if you've heard of other ways to gamble on solitaire.
It's a pretty short page and only covers the 5dimes rules.
I'm not sure what my question is, but I welcome comments on the page and if you've heard of other ways to gamble on solitaire.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
May 24th, 2020 at 3:30:23 AM
permalink
I thought I just heard from somebody that it may be a myth that any casino actually offered this game back in the day. It's not offered today at all in Vegas, right?
I guess you can play at 5 Dimes
not sure where I heard that it was possibly a myth that it was ever offered, maybe Gambling With an Edge radio?
I guess you can play at 5 Dimes
not sure where I heard that it was possibly a myth that it was ever offered, maybe Gambling With an Edge radio?
Last edited by: odiousgambit on May 24, 2020
the next time Dame Fortune toys with your heart, your soul and your wallet, raise your glass and praise her thus: Thanks for nothing, you cold-hearted, evil, damnable, nefarious, low-life, malicious monster from Hell! She is, after all, stone deaf. ... Arnold Snyder
May 24th, 2020 at 5:14:26 AM
permalink
Quote: odiousgambitI thought I just heard from somebody that it may be a myth that any casino actually offered this game back in the day. It's not offered today at all in Vegas, right?
I guess you can play at 5 Dimes
not sure where I heard that it was possibly a myth that it was ever offered, maybe Gambling With an Edge radio?
My grandfather, who was quite a rake in his time, told us that it was offered. That was in the 1960s.
A falling knife has no handle.
May 24th, 2020 at 5:29:20 AM
permalink
Quote: odiousgambitI thought I just heard from somebody that it may be a myth that any casino actually offered this game back in the day. It's not offered today at all in Vegas, right?
I guess you can play at 5 Dimes
not sure where I heard that it was possibly a myth that it was ever offered, maybe Gambling With an Edge radio?
I've heard that too. Whenever I get a chance to meet someone who was over 21 in the 50's or 60's, I ask him if he could confirm or deny the myth. So far nobody has been able to do either.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
May 24th, 2020 at 7:46:58 AM
permalink
I thought there was a thread on here where someone claimed this game was +EV and they would beat it online.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
May 24th, 2020 at 11:25:51 AM
permalink
I have averaged 21% win rate at (3card) Klondike Solitaire - when it has an undo button.
I have also taken a crack at Soliatire theory using combination theory by analyzing scenarios in which you can't win.
There are some starting configurations that cannot be won. Example:
- both red 5s are atop a stack. Beneath them are both black 6s and two low cards (A-4) of both diamonds and hearts.
(There are many variations on this "blocking scenario" which can, in principle be calculated. ALso, the red 5s need not be on top a stack at the start fo teh game, they may be lower in the stacks as long as they are above the cards needed to remove them from the stack.)
You can also be blocked from winning in the stack from which you flip cards, 3 at a time. Example:
The first flip has a 5 diamonds on top with a 6 club, 6 spade underneath. The next flip of three cards has a 5 hearts on top with an Ace of hearts and 2 of diamonds underneath.
Then there are scenarios in which the first three cards off the main stack plus one of the stacks on the board combine to block you from winning. The principles are the same. You must have two cards of the same rank and color sitting above (at least 4 cards) that prevent you from moving them.
I have also taken a crack at Soliatire theory using combination theory by analyzing scenarios in which you can't win.
There are some starting configurations that cannot be won. Example:
- both red 5s are atop a stack. Beneath them are both black 6s and two low cards (A-4) of both diamonds and hearts.
(There are many variations on this "blocking scenario" which can, in principle be calculated. ALso, the red 5s need not be on top a stack at the start fo teh game, they may be lower in the stacks as long as they are above the cards needed to remove them from the stack.)
You can also be blocked from winning in the stack from which you flip cards, 3 at a time. Example:
The first flip has a 5 diamonds on top with a 6 club, 6 spade underneath. The next flip of three cards has a 5 hearts on top with an Ace of hearts and 2 of diamonds underneath.
Then there are scenarios in which the first three cards off the main stack plus one of the stacks on the board combine to block you from winning. The principles are the same. You must have two cards of the same rank and color sitting above (at least 4 cards) that prevent you from moving them.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
May 24th, 2020 at 11:37:35 AM
permalink
I have also done some work to characterize the worst possible starting positions: Those from which you are unable to move a card even when you flip through the main stack, 3 cards at a time. The odds of this "Zero Points" scenario are much elevated when your starting position has "duplicates" atop the short stacks: say two red queens or two black eights -because it reduces the number of "Outs" you have to move a card.
I feel strongly that when you have a starting position with two sets of duplicates (say, two red queens and two black eights) atop the stacks on the board that your chances of winning are greatly reduced.
Basically, my approach was to model solitaire as a game of "outs" where getting an ace created another (suit) stack which usually gives you another "out."
I feel strongly that when you have a starting position with two sets of duplicates (say, two red queens and two black eights) atop the stacks on the board that your chances of winning are greatly reduced.
Basically, my approach was to model solitaire as a game of "outs" where getting an ace created another (suit) stack which usually gives you another "out."
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
