Following an interesting discussion with JM and Alex regarding the plspider program I wanna discuss the Law Of Diminishing Returns (LODR).
When playing with plspider I noticed an interesting phenomenon. The program can often obtain two or three empty columns pretty easily. After all, playing with undo privileges is a massive handicap. But after getting those empty columns the program flounders for a while, not knowing what to do. An expert human player would normally crush a hand once he has three spaces. Plspider will eventually find a winning path, but by that time I have already churned through a number of levels in Toy Blast (I am currently at level 5923).
I think the reason plspider flounders boils down to the LODR: when you have three empty columns the value of further empty columns is very small.
This is based on many years of playing the Royal Game and working out winning strategies, rather than knowledge of the actual code. I should also mention that players are often reminded that getting empty columns is essential strategy (more superficial advice on the internet, hooray!) so it’s not hard to guess why many spider solitaire solvers emphasize the possession of empty columns. The problem is nobody discusses what to do once you get empty columns.
At first sight, the LODR sounds like madness: after all the win condition for Spider Solitaire can be described as “getting ten empty columns”. But suppose that we always declare victory as soon as the game is mathematically won, i.e. there exists a strategy that removes all cards to the foundations regardless of the permutation of unseen cards. Then it is impossible to obtain 10 empty columns, because the game is prematurely terminated. A little-known but useful analogy would be Dead Reckoning in chess composition.
Some examples of mathematically won game states are:
- Every card face-up in the tableau, 10 cards in the stock, the player has chosen to deal the last row, and a winning move sequence exists for every possible permutation of cards.
- 7 out of 8 suits moved to the foundations
- Two spaces and eight runs from Ace to King with mixed suits. Some cards may be face-down.
I haven’t performed any detailed calculations or statistical analyses but my intuition says an expert will typically declare victory with 3 or 4 empty columns. If he has more than 4 spaces then chances are the expert can’t be bothered working out if the game is mathematically won after every turnover.
To illustrate the law of diminishing returns, consider the following game state, which may be familiar to regular readers 😊. While the game is almost certainly won at this point, it is adequate for didactic purposes.
Assuming we merge the three left-most columns into a single run, we have three empty columns. Now, borrowing a phrase from Cracking The Cryptic, let us ask a facetious question: is there any game state that (1) has three empty columns, (2) is reachable if we (temporarily) use at least one empty column, and (3) not reachable if we don’t use any empty columns?
Clearly the answer is yes since the supermove “fe” fits the bill.
Now let us ask the same facetious question, but this time we want a game state that is only reachable with the use of TWO spaces BUT NOT ONE.
That’s not so hard. We could for instance swap the 8-7-6-5-4 of Spades in column 1 with 8-7-6-5-4 in column 5. That breaks an in-suit build for no good reason but at least we answered the question 😊
Now we ask what happens with three empty columns. One can show that it’s possible to shift the J-0-9-e-t-c-e-t-e-r-A of mixed suits in Column 6 onto the Queen of Spades in column 8. For sake of argument, I will pretend this is not possible with only two empty columns (proving or disproving this is left as an exercise for the reader!)
But that leaves not much room for improvement if we have four empty columns. If three spaces are sufficient to achieve the super-move “fh” then it’s hard to imagine a single game state that can be reached with four spaces but not three.
Admittedly this is not a rigorous proof of the LODR, but hopefully you get the idea. When you have three spaces it is probably wrong to aim for a fourth space. You should concentrate on columns with more face-down cards rather than less. At the risk of sounding like a broken record, at least this helps avoid one-hole-no-card problems (all other things being equal). Or you might sacrifice turnovers and spend a space or two to remove a suit – or even an “almost suit” of 12 cards instead of 13. Obviously, the correct course of action depends on circumstances, but the underlying theme is you never play for Yet Another Empty Column without thinking.
In summary, I believe extracting maximum value from empty columns is the heart of winning play at Spider Solitaire. If the Spider Solitaire Body Of Knowledge was a thing, then the Law Of Diminishing Returns should be part of it.
Improving the plspider algorithm
The plspider program achieves a very high win rate (with undo!), but takes far too long to find a winning sequence of moves. If I had to improve plspider’s performance I would modify the code to start focusing on complete suits instead of spaces once it has accumulated three spaces. Of course, this is easier said than done if you pardon the terrible cliché, especially considering that I do not have the source code of plspider.
While we’re here I may as well mention that 3 is not a magic number. In some given game states, the LODR kicks in after 2 empty columns. On a really good day, most builds are in-suit after 20 moves and the LODR applies with only 1 empty column. In other games, an expert player might find a good reason to chase 4 spaces. That should be rare, but might depend on which version of Spider Solitaire you are playing 😉