Program to play Klondike
Sebald
REGISTERED
Dear Fellow Felters,
I have written a program to play Klondike, to try to better understand the principles of play. Let me say at the start that the exercise has been a little disappointing. I have implemented the general advice about how to play that you find on the web ("try to uncover the hidden cards", etc.,), and have arrived at a 39% solution rate for random games. One source cited in the Klondike Wikipedia article says that the solution rate for a player playing a game for the first time (and who consequently does not know the hidden cards) is 43%; so the general advice seems to achieve most of what is possible. The disappointment comes in when I realize that there is no obvious way to close the 4% gap, or at least no way that does not involve enormously more calculation. I have the sinking feeling that there is less to be gained from seeking deeper ideas about strategy than from empirically fine-tuning the "evalmove" parameters in the strategy section of the program. I must conclude from this that Klondike is only a moderately interesting game, and I am putting the project aside.
The program is in Haskell. I tried to attach the code to this message, but the site will not allow it (it is probably specifically screening against programs); also, I could not include the code as part of the message, as then the message length was too long. If there is a way for me to put the code at the disposal of other users I would like to do so.
Yours,
Sebald
.
Comments
I'd love to see your Haskell Klondike solver. I'm not sure why the attach isn't working. Oh, I see—it's got an extension whitelist and .hs isn't in there. Do you have a github account? That's arguably a better way to get your code out there anyway. If you don't want to fiddle with git and make a whole repo, just make a gist and paste your code in there. It'll come out all fancy and syntax highlighted. Then post the link to it here.
I also went ahead and added .hs to the list of allowed extensions to upload, though I think it won't be as readable as a github gist.
Thanks for enabling the attachment. To see it play one game, execute "makeGame 0". To see it play 1000 games and report the results, execute "play1000".
Sebald
Nice! I made a gist here so I could read it better (no haskell-mode in my Emacs right now). If you don't want that, let me know and I'll remove it.
I was getting errors compiling with ghc 7.10.1 (Could not find module ‘System.Random’), but it worked with 7.0.4 which I luckily had lying around.
So it looks like you don't have any backtracking right now. I like the priority system you have—it matches up with my brain's prioritization when I play. But I suspect it gets hung up on the same type of games that make me undo a lot: the ones where the obvious move is wrong (because it ends up blocking a move much later in the game in way that isn't predictable).
That 44% number from Wikipedia is interesting. I did some digging through our database and chose the 50 most played Klondike games on 2015-07-01. They all had over 600 plays (the top was the game of the day which had 6100 plays). Of all of them, only 8 had no winning plays. That's means roughly 84% of the games were beatable. That's interesting because it means that roughly half the winnable games of Klondike are not beaten on the first try.
Luckily Green Felt supports "undo". :-)
There is a feint at backtracking (playOutGame). It uses a list to simulate nondeterminism. Given a list of games it removes the first one, and replaces it with all the games that can be derived from it by one move, then repeats. I have not tested it seriously except to determine that it does solve some games, adn that the length of the list does not explode.
As Klondike is not a game of perfect information, "undo" and backtracking, like playing the same game twice, convert it into a chess-like game. No problem with that, but imagine poker with "undo".