Law Of Diminishing Returns

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  😉

5 thoughts on “Law Of Diminishing Returns

  1. I can give a few thoughts as a guy who’s halfway decent at Spider and who has done a bunch of programming, including fairly complicated problems like how to create a rule-based system to translate English into Japanese. I’ve gotten most of the answers to “Advent of Code” the past few years. (And I’ve had a bit of fun looking at Wordle strategies and curiosities recently.) But I’ve never done AI learning stuff.

    In an ordinary Spider game, I have some tendency to think about spaces as “money in the bank”. If you were thinking of placing card A on card B, and you lose that play by making a space, you can look at the situation with the space and evaluate “card A onto B” as one of many possibilities, and if it’s still the best, simply take that card you put on A or B into the space and then do the play you were going to do.

    Some version of the “law of diminishing returns” is obvious, but how to incorporate it suitably into an overall AI strategy is not at all.

    You have to do something with the spaces, and it seems there ought to be a way to incorporate something like this into the source code. One AI framework is to have competing “experts” giving their opinion on evaluating a position according to various criteria, and if so just reduce the weight of the “more spaces” expert when you get 2 of them and reduce it even more when you get 3.

    Another take on thinking about LODR is a version of the “local maximum” problem. A simple and often effective way to get to the top of a hill is to keep going higher, but sometimes you will end up at the top of a “false peak”, and the actual way to the top involves deliberately going downhill for a while.

    Tidbit: I concluded some years ago that the length of a suit-broken sequence you can move from one spot to another is 2^n, where n is the number of spaces you have. You can move one card without a space, but with three, you can move an 8-piece sequence from spot to spot. If someone thinks that’s wrong, I’d love to know it.

    Like

  2. This isn’t directly about the LODR, but it is a thought about the “Z key”. If you had a “guest post” category this might be a candidate.

    The other day I played my first game where I made liberal and unashamed use of the Z key. I could immediately see why it was appealing. Instead of reaching a dead end, you can go back and try a different path and keep going. And a way to at least “keep going” when you were going to lose has immediate appeal. From the marketer’s point of view, the program is keeping your attention for longer than it would without the Z key.

    But some games are more fun when you have less information.

    First assertion: Any game that is winnable with the Z key is winnable by just knowing the identities of all the cards in advance (all the unturned cards in each pile, in order, and the five deals) without a Z key, and vice versa.

    So consider a variant of Spider in which you knew the identities of all the cards in advance. I suspect it would be not at all popular, because very few people could see in advance everything they need to do to win, and they would be reminded of their mental shortcomings. The Z key is more fun because you can make plans based on what you can see and your ordinary human intellect, and then modify them to get you a “local maximum” again, something that looks good to you given what you see right then, and then build from there.

    Among those who use the Z key, I wonder if there is a tendency to try to minimize its use — is it psychologically a “last resort”? In contrast, you can get half the unknown information by immediately dealing five times and undoing the five deals. Do people do that?

    But surely there would typically be much shorter paths to victory if you knew the identities of all cards in advance. One interesting area of inquiry would be maximizing “garden path” situations… for what winnable hands would a good/perfect player have the highest ratio of moves required to win via the Z key versus wins required to win by simply knowing all cards in advance?

    It also poses the question of whether anyone who deals with AI solutions is more interested in the version limited to Z-key information, or in simply knowing all cards in advance.

    Like

    1. Esteemed Scholar Bart before I came here to 4SSS-SansZKey I played Two Suit for about four years. I was using the “Win 7 Games for Win 10” version. My lady friend must have accidentally downloaded onto my computer.

      My method was to play first without ZKey and if unsuccessful at winning, return as necessary with the ZKey. Sometimes I needed to go back only a few moves to chose a different pile to attack, sometimes I had to go back to the beginning ……… sometimes to the beginning again and again. To save a game that I did not have time to finish, I would go back to the deal position, make one move and save the game. I never mapped out where the cards were. I call this the Play-Til-You-Puke-No-Map-Mode. I had one game that took over two thousand moves to win!!!

      Data was lost due to The Blue Screen of Death but I was approaching 1500 games in a row won, with the filter that if there was not a move on the last draw the game was unsolvable and I did not count it. I now realize that I was selling things short as a different placement of cards preceding the last draw could possible (probably?) give a move and an eventual win.

      I think my win on the first try rate was about 33%. (I wish I had not typed that, now I have an idea of going back and seeing if I can do better…………hopefully that idea will join the other seven hundred sixty two ideas I have forgotten today.)

      I found this to be a very enjoyable and challenging way to play Spider.

      Then this character with Edifying Thoughts comes along, ups my Excedrin bill by seven fold and here I is.

      This is the great thing about SS…you can play at whatever level you enjoy. Playing Two Suit hands over and over until I got it right certainly prepped me for here. I learnt a lot about moving cards around.

      You can map out card locations, or trust to memory. Even now I find that sometimes I need to count outstanding cards towards the endgame and keeping thirteen things straight in my mind is a distraction from the game, so I write them down.

      I am not sure that 4SSS-With-ZKey-Play-Til-You-Puke-No-Map-Mode would be any less a challenge then SansZKey, just different. Your win rate should approach or equal 100%, but some games would stretch into next week.

      So everyone who enjoys Card Solitaire Games should be able to find a SS level and mode that works for them.

      Like

      1. Hi IM Bug, this is a great comment – the fact you can play Spider at whatever level you enjoy is probably worthy of a blog post in itself!

        It’s hard to think of another card game with the same “choose-your-difficulty” aspect. For instance, playing Freecell with only two suits is not a thing AFAIK and undo is theoretically pointless when all cards are face-up anyway.

        Like

    2. Hi Bart,

      Z-Key is an interesting topic, and probably worthy of a blog post in itself. You’ve already raised most of the relevant points, but I should mention that I have seen one Spider version that halves your score and turns the screen red if you submit to the one thing Oscar Wilde can’t resist.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s