Horrible News!!

Let me introduce: I reviewed the wishlists of kpat after fixing all bugs reported to bugs.kde.org. Now 112032 - showing if a solution is possible found my interest. Not exactly for freecell (which I master quite well after all these years kpat QA), but it's surely interesting for games less likely to win. When I was at my sister's home she played (middle) Spider@XP in the evening and it stroke me why a game should be so popular where the chances to win was so low (we mastered to win 15% - neither paying it much attention nor having a lot of experience). So my idea when seeing the bug was to write a solver that can solve not just freecell but also spider.

So I looked around for patience game solvers to take ideas (and code) from. kpat 2.2 uses fc-solve by Shlomi Fish to prepare a working demo to freecell games (which will report if the game can't be won), but fc-solve is 15K of C code that were designed for speed (to put it positively :), so I ditched the idea pretty quickly to use it and was tempted to start from scratch. But Shlomi's web page (and the wikipedia article that I guess Shlomi contributed most to too) references Tom Holroyd's patsolve as to have other interesting ideas. So I grabed it and found it to be pleasant 2k. So I played around with it, made it a library and C++ and split out a base class from the Freecell specifics and so on.

Then I continued to solve easy Klondike and after some more interesting problems that weren't ones with freecell (as you don't turn cards in freecell nor do you don't redeal forever) I found out: 753 of the first 1000 deals are solveable. I would have estimated the win rate a bit lower, but still pretty high - there is a reason easy Klondike is so popular.

Now on to my real target: spider. That was easy to implement at first, but it turned out pretty quickly that the game has so many branches (having 104 cards as klondike and freecell have 52) that the "hybrid DFS/BFS/prioritized-queue search" (Tom's words) patsolve does easily exceeds its memory limits. So I played 3 games with my wife always explaining her which move the computer would prefer at a given time and she correcting it. In the end we had an algorithm that would play as she was trying (but with a BFS while human players prefer DFS - you know what I mean if you know what I mean :) and that works out so well, that I can tell my wife would win every spider game if she was a computer. Of course I would have way less fun with her, but you can't have everything... ;)

Did you read that? Right! Every spider (with 2 suits) game is solvable with human players being lucky if they win every 5th. How frustrating is that? Anyway, I made my choices: I won't implement more solvers for the moment.