Connect Four – Bring It On!

Okay, I’ve submitted to temptation and finally downloaded the MobilityWare Spider Solitaire app even though it’s probably rigged – but only because I wanna try the daily challenges.

A daily challenge is a certain starting configuration that is guaranteed winnable. MobilityWare has several games (not just Spider) and solutions can be found by googling. Games include Freecell, Solitaire Draw 1, Solitaire Draw 3, Spider Suite 1, Spider Suite 2, Spider Suite 3, Crown, Tripeaks, Addiction. That’s quite a lot of variety, and I will admit I don’t even know the rules for some of these games. Although I thought the “Suite N” part was weird because it clearly should be “N suits” where N = 1,2,3 … no wait, there’s no solution for N=4?!?!?!?

If a solution is given, it means two players can play the hand corresponding to the same day and same game (e.g. Tripeaks, 5th of February) and they are presumably guaranteed to get the same starting hand. If they didn’t get the same hand and wish to check the solution, at least one player would complain very quickly! However, since I can’t find a solution for any 4-suit Spider hand, it is mathematically possible (though unlikely) that two players can play DIFFERENT 4-suit Spider hands corresponding to the same day and they would be none the wiser unless one of ‘em specifically asks the other if they get matching hands.

NOTE: in some cases only partial solutions are given (because some games take longer than others) and you have to pay some $$$$ to get the full solution. But a partial solution is more than enough to confirm two players indeed get the same hands.

Assuming two different players do get the same 4-suit Spider hands, I can play these hands with reasonable expectations they would not be ridic hard – since I can’t see a game developer with rot13(fznyy qvpx flaqebzr) punishing random novices with insanely difficult hands if my win rate is too high, even if he or she works at Zynga (or an equivalent company).

I think a fun challenge would be Connect-Four. On every day of the month I either win or lose the hand corresponding to that day. Four wins/losses in a row, horizontally vertically or diagonally means I win/lose. For instance, if I remove all eight suits on days 5-13-21-29 then I achieve a winning Connect Four, unless I also achieve a losing Connect Four earlier (such as 9-10-11-12). The downside of playing Connect Four of course is if the game ends after 6 days, then I might have to wait a while before the next month! The screen shot below is for April 2023, coming soon to a place near u.

Ultimately, I am interested in playing all the daily challenges in April 2023. Can I expect to win most hands? Also, do hands get tougher as we approach the end of the month or is it roughly uniform difficulty?

Here are the hands for N-suit Spider Solitaire corresponding to 29 March, for N = 1,2,3,4. I would be interested if readers can confirm they get the same starting hands for N=1,2,3,4.

Of course the result I am really interested in is if you get the same hands for N = 1,2,3 but different hands for N=4. Then I would know something suspicious is going on!

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  😉

PLSPIDER: Potential Signs of Awesomeness

Last week, I received an email from JM(*) about a Spider Solitaire solver from some little-known corner of the universe. I was sort-of-aware of its existence but, to my regret, didn’t take it seriously. I think it has some potential. This solver was created by Tranzoa.com in 2005.

(*) I will not reveal his or her full name without consent.

A Spider Solver is what we expect: we arrange the cards as per normal Spider Solitaire rules and then brute force our way to a solution. In some sense it is therefore similar to my Ninja Monkey algorithm, except Ninja Monkey never plays with rot13(haqb).

I can’t say PLSPIDER does exactly what I want, but that could entirely be due to me being Stupid instead of Awesome after playing around with it for only a couple of days. I’ve figured out how to download and run the executable, but haven’t understood the meaning of every statistic in the first four rows. I also am not aware of any source code for the main executable – I only have source code for two modules called showdeal and webresults, and I can’t even compile that, probably due to me having some incorrect version of Python or some other rot13(fuvg).

The author claims (for example) game # 3168 can be solved in under half a minute, but my time is closer to 8 minutes. Did I fail the requirements for minimum RAM or CPU required? I believe the answer is NO. But given my younger brother is much more computer literate than I am, I’m not willing to bet my Ph. D. thesis on it.

The screen shot below shows a game in progress. PLSPIDER has managed to obtain three empty spaces, but then fumbles around for a bit. It takes around 12 minutes to find a solution.

After some observation, I noticed the above screen-shot is not an aberration. PLSPIDER likes empty columns. OTOH, I could have reached the same conclusion by reading the instructions instead of watching it fight its way through the same hand for ten minutes. Maybe I really am Stupid instead of Awesome.

Normally I would expect to crush the game once I obtain three spaces, yet PLSPIDER struggles to convert three spaces to victory, even with rot13(haqb) privileges. This suggests a serious problem in its search strategy – but I will probably have more to say in a future blog post tagged under “strategy”.

But what I really want from PLSPIDER is a quick means of sussing out dodgy Spider Solitaire servers. Suppose I suspect program XYZ is rigged and stacks the cards against a player who wins too many games. Assuming I can win every game and record the identity of all face-down cards, I can then feed in these initial game states to PLSPIDER and expect to find that the time taken to beat a hand steadily increases. In other words, I expect a graph looking like this:

If I get a steadily increasing line for, say, the first 30 hands then I have reason to believe the program is biased. But if the line is random noise with no discernible pattern then the program is in the clear. Obviously “reason to believe” isn’t the same as “conclusive proof” but it does allow us to state that “more investigation is warranted”.

This leads to the second problem with PLSPIDER. I can only deal 32,000 different hands by specifying a “starting seed number” (similar to seed numbers in MS Windows Freecell). If PLSPIDER could read as input any text file (assuming it is formatted correctly) then that would be ideal. Again this could be me being Stupid instead of Awesome.

Finally, I should mention PLSPIDER allows you to play a hand yourself, although the interface is a bit clunky. I assume this was primarily intended to be of more benefit to the programmer fighting his way through the latter stages of the software development cycle.

If JM (or someone else) could teach me the secret to Being Awesome Instead Of Stupid that would be much appreciated.

A closer look at Leapfroglets’ Spider Solitaire

In an earlier post I described the Spider Solitaire server written by someone else, namely “leapfroglets”. According to the website this is apparently a playground for junior leapfroggers to hone their programming skills. However, it is beyond the scope of this blog post to discuss this startup company in detail.

As you may have guessed, I have no interest whatsoever in creating YASS program that contributes less than two thirds of nada to what other programmers have already done, given the other programmers possess many skills that I lack. But I’m perfectly happy to stick my sans-rot13(haqb) AI in the wild when I am blissfully unaware of anyone else doing the same.

I did not include any screenshots of the game, which is probably a bit remiss of me. Here is a small sample:

Finally, here is the victory screen. I am assuming the programmer can’t beat the Four-Suit level half the time, otherwise the screen-shot would have looked slightly different 😉

Features

Transparency

Since this is GitHub, I am able to examine the source code (examining source code is “free” even for those without an account – you only need an account for downloading files and editing them). Here is the code snippet for shuffling cards. Assuming the reader has basic understanding of math and programming languages, it should be reasonably straightforward to work out what’s going on. Admittedly it’s not the most sophisticated shuffling algorithm but at least it’s transparent. If Joe Bloggs accused Leapfroglets of rigging the number generator than it is the software developer who is justified in complaining about his or her bad luck.

No rot13(haqb), rot13(erfgneg)

There is no rot13(haqb) button. The rot13(erfgneg) button means you deal an entirely new hand, which may be worse than T-2-2-0-8-T-5-4-9-2. We all know this is a Good Thing, as it forces the player to learn good habits. Of course, I’m not exactly sure why the player needs over six minutes to find a decent opening play at the one-suit level 😊

That Other Feature

As alluded in a previous post, I made a minor bug fix and made a pull request. This bug was that the move counter was not updated whenever one or more cards was moved to an empty column. I’ve submitted a pull request and am yet to hear back. Ditto for the proposed lyrics for the victory music. Admittedly this was a trivial nit-pick but at least it gave me the opportunity to practice the ritual of downloading code, editing and submitting a pull request. Unfortunately, judging from the activity profile for 2021, I’m not expecting to hear back soon ☹

All things considered, this is actually a pretty decent piece of software and if the company wants young programmers to hone their skills, then they have succeeded in their objective. Well done to Leapfroglets!