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 ?
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.
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.
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.
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?
Basically, I wanted to know if any casino currently offers, or ever offered, Vegas Solitaire.
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.
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.
fascinating, thanks
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.
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.
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.
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.)
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
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.
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?
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.
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.
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 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."