“Face-up” Solitaire Algorithm

Question

I'm designing a program to solve solitaire games in the highest-scoring way possible. The game is scored on the following point system:

10 points for moving Aces to top
9 points for moving 2s to top
8 points for moving 3s to top
7 points for moving 4s to top
6 points for moving 5s to top
5 points for moving 6s to top
4 points for moving 7s to top
3 points for moving 8s to top
2 points for moving 9s to top
1 points for moving 10s or face-cards to top
2 points for freeing a "downcard" (face-down card on the table)
2 points for moving a card from the deck to the table
-2 points deducted for moving a card from the top to the table
-20 points deducted for flipping over the deck
Putting a card back to the top after moving it from the top to the table does not give double points.

Cards from the deck are flipped over one at a time, and players are allowed to flip over the deck an unlimited number of times (however, the -20 point deduction still applies).

I have found various strategy guides, like Klondike Strategy Guide for Windows Solitaire Game, but these guides are for real games of solitaire where the table cards are not known.

I am looking to create an algorithm for solving what I call "face-up" solitaire games where I have knowledge of the deck before it is dealt. Edit: from the papers given in the answers below, it seems that this game has been called "thoughtful solitaire."

So far, my ideas have been: some sort of brute forcing, where all possible moves are tried and scored; a simple algorithm that looks at each column individually and tries the "best" move it can; and finally some sort of algorithm similar to pathfinding, where each move is scored and the best "path" is found.

The problem with brute forcing is that it would take forever (literally) as you can repeat moves infinitely. With a simple algorithm, I couldn't do tricky things like rearranging two columns to put all the hearts and clubs (for example) to free a lone 8 of hearts. From what I can see, pathfinding will work, but I am lost in how that sort of implementation would work.

Answer 1

You might find the following papers helpfull (it seems this has already been done by a research team.)

Searching Solitaire in RealTime:

• http://web.engr.oregonstate.edu/~afern/papers/solitaire.pdf

Solitaire: Man vs. Machine

• https://web.stanford.edu/~bvr/pubs/solitaire.pdf

Answer 2

The first thing I'd try is a naive fixed-step lookahead algorithm, where at each step, I'd analyse all the possible n steps ahead and I'd choose the one that leads to the highest overall score.

Play around with different values of n on the same series of pseudorandom packs and see how (if at all) scores improve by increasing it.

If this brings reasonable success, the next step is to assign points to certain positions that you can use during the evaluation process. (For example, the distance of 'downcard' aces from the top of their pile can be substracted.)

The next step could be an adaptive search, where you look ahead a fixed number of steps first, then expand only the promising leaves of the move tree even further. (Pruning, basically.)

And so on, there's a lot you can try and it sounds like great fun, so enjoy it.

But if all else fails, organise a coding competition. :)