Yet Another Digression: DJDJDDJKDK is the new COVFEFE

So here I am, innocently literature-reviewing something that is work-related. Spider Solitaire is the last thing on my mind. Someone has written an interesting Ph. D., titled “An Analytical Framework for Soft and Hard Data Fusion: A Dempster-Shafer Belief Theoretic Approach”. I’ve been there many years ago, so anyone who has something to show after three years of solid research has my respect. The author successfully navigates the first hurdle by not spelling Dempster with a ‘u’ (GIYF). After 16 pages it’s all looking good and the dude seems to know what he’s talking ab– rot13(JUNG GUR NPGHNY SYLVAT SHPX) JUST HAPPENED?!?!?!?

“Decision-level fusion: Here, each sensor makes a preliminary estimation of an entity’s identity in terms location, attributes, or any other DJDJDDJKDK.”

Yes, you read that right.

D-J-D-J-D-D-J-K-D-K.

All capitals.

Ten consonants in a row.

Don’t bother looking it up in Scrabble. Even if it happened to be legit, there are not enough D’s J’s K’s and blanks in the bag to spell that word without violating the laws of physics.

I mean, this word beats “covfefe” hands down. At least the latter has only seven letters and some of them are vowels. I could understand ASDFASDSDF if somebody was too lazy to type “Lorem Ipsum” as place-holder text. But D and J/K are separated by three letters on a standard keyboard last time I checked, so button-mashing doesn’t seem a very plausible explanation of DJDJDDJKDK.

I did what any self-respecting research scientist would do: I googled the thing. Nothing, zilch, nada, zippo, duck’s egg. Buckleys plus Buckleys squared. Worse-than-Anton-Smirnov-getting-smashed-with-the-white-pieces-against-Duda-in-26-moves. With nothing to go on, it looks like I have to invent my own definition.

Let us say that a DJDJDDJKDK is a special cheevo that occurs whenever you deal ten cards from the stock, such that the first card is any diamond, the second card is any Jack, followed by another Diamond, another Jack and so on. That’s a total of five diamonds, three Jacks and two Kings. Probably a lousy deal unless some of the diamonds happen to be Queens or Tens, or you have strong chances of completing a suit of Diamonds.

Assuming cards are drawn with replacement it’s easy to compute the probability of a DJDJDDJKDK. Every diamond occurs with probability 1/4 and every Jack or King occurs with probability 1/13. The overall probability is obtained by multiplying (1/4)^5 * (1/13)^5. Of course, the cards are not drawn with replacement but it’s a reasonable approximation to say the chances of achieving DJDJDDJKDK are not exactly great. We can improve our chances a bit by allowing any permutation of DJDJDDJKDK. Also, the Jack (King) of diamonds can count as a J(K) or a D. But If I were the author of a Ph. D. mentioning the words “decision-level fusion” I wouldn’t be betting my Ph. D. to a brick on the elusive DJDJDDJKDK given those odds. The above image is a randomly generated 4-suit hand, and clearly, we are not even close to a DJDJDDJKDK. We only need one “bad card” i.e. not a Jack, King or Diamond to disprove a set of ten cards achieves DJDJDDJKDK. But if it ever does happen in my Spider Solitaire career, I would definitely let the whole world know 😊

Well, that’s enough digression for today. How would you explain someone choosing DJDJDDJKDK as a Ph. D topic? And more importantly, how would you define DJDJDDJKDK?

The Freecell Project

In this post I wanna talk about the Freecell Project. I beg pardon of the reader if he is familiar with it, but I thought it provides me a good starting point to discuss a similar project with plspider.

Freecell is one of the best-known variants of Solitaire, and distinguished by the fact it is almost always won with best play. Moreover, Microsoft has included a FreeCell computer game with every release of the Windows Operating system since 1995 including the dreaded 4112141 41111 that probably originated in the Ninth Circle of Hell and dare not speak its name (Letters replaced with point-values in Scrabble)

But we digress. ☹

The original Freecell has 32,000 deals corresponding to seed numbers in the range 1-32,000. That means if you input the same seed number you always get the same hand. This allows players to verify the results of others.

In case you’re already bored by me waxing eloquent about things you already know, here’s a little-known fun fact. Many years ago, I used Microsoft Freecell at work by pretending it was a password management system. For instance, if I agreed beforehand that passwords are obtained by reading letters and numbers of the left-most column then a seed number of 11982 will generate A3KJ6JK. If I needed to update my password then I can compute the string of letters and numbers corresponding to a seed number 11983 etc. Obviously A3KJ6JK is a terrible password by today’s standards but you get the gist. Time has moved on and my workplace, rightly or wrongly, no longer has Microsoft Solitaire (or other games) installed.

Oops … I digressed again ☹

If you wanted to play a number of pseudo-random Freecell hands you could start with a seed number such as 27. After completing each game, you take the seed number and call it N. If N is odd then the next seed number is 3N+1. If N is even then the next seed is N/2. You keep going until you reach 1 or exceed 32,000. If you reach an infinite loop other than 1-4-2-1-4-2-1 then too bad! Whenever you solve a hand, you can add the solution to a shared repository and other players can verify that you indeed succeeded.

But if you’re part of a large team dedicated to testing every deal from 1 – 32,000 then you probably wanna do things a bit more systematically. If you had a team of 320 players then it is probably wise to assign each player a run of 100 consecutive hands rather than mucking about with the Collatz conjecture – and the observant reader has noticed that I digressed again. Oops! ☹

In the nineties, Dave Ring did exactly that. He started the Freecell Project to solve as many deals as possible using human solvers. If you’re thinking the number 11982 from my previous digression was familiar then you’re probably right. The project was finished in 1995 and only game 11,982 is (probably) unsolvable.

I say probably because I am not aware of any proof that it really is unsolvable. Google searching shows many have tried and failed, including both carbon-based and silicon-based entities. Some have even posted incorrect solutions. But that is no guarantee that a Ninja Monkey making random moves would not stumble upon a solution tomorrow.

Modern versions of Freecell have many more than 32,000 deals and it is estimated that 99.999% of deals are solvable.

The plspider project is similar. Only 32,000 hands were generated. This is not a coincidence – the logic for defining the permutation of cards is based on the same logic for Freecell. Obviously it can’t be the exact same hands since Spider has twice as many cards as Freecell, but the algorithm is similar. As an analogy you can think of applying SHA-256 cryptographic function once, twice, or thrice to obtain different strings. They look completely different even though they are based on the same algorithm.

In any case, it was found that (at least) 31998 games are solvable assuming unlimited undo/restart privileges. Converting to a percentage yields a win rate of 99.994%. That’s the same as Donald Bradman’s batting average but with an extra 9 added.

Oops, I digressed again ☹

One difference is that certain hands can be proven unwinnable. For instance, one hand did not allow the player to reveal any Sixes in the tableau or stock. I have yet to come across this phenomenon in actual play – even my most disgusting losses allowed me to verify the two decks contained least one occurrence of every rank.

Note that with plspider, I am unable to test the program on “custom hands” because that was not relevant to the original goal of the plspider project. And I assume the Freecell project is similar.

Final Thoughts

The plspider program succeeded in what it set out to do: estimate a win rate of randomly generated Spider Solitaire hands, assuming the player has unlimited undo/restart privileges. It was not designed to determine if a particular Spider Solitaire server is biased (e.g. dealing progressively harder hands without informing a strong human player).

Previous discussion with the author of plspider suggested I might have inspired Alex to add the feature of testing custom hands. The real problem is probably something to do with Past Alex rather than Present Alex … and Present Alex has warned me the source code is truly atrocious.

Awesomeness has been achieved!

I have finally achieved awesomeness! My Spider Solitaire Sudoku puzzle has been featured on Cracking the Cryptic.

For those who are interested in the puzzle only, here is the grid: if you’ve played any Spider Solitaire the rules should be guessable – and if you get a unique solution then you know you’ve guessed correctly 😊 But if you’re interested in the back-story then please read on.

If you follow this blog regularly, you are probably aware of a paper I published some time in 2019. I showed that a particular Spider Solitaire server was biased: if you win too many games then future games will have the cards stacked against you – and one could “prove” this using Statistics.

I use quote marks because the nature of Statistical testing always implies some degree of uncertainty. For instance if you are 95% confident of a hypothesis, then there is a 5% chance you made an error. But it is commonly accepted practice. If your experiment is sound and you get a sufficiently small p-value then go ahead and publish it anyway. You may be wrong, but – to put it in Poker terms – your results pretty much force you to call all the way to the river. If you are beat then you are beat.

Of course, getting the results you want is only the first step. We all know the academic publishing model is broken. The peer review model is hopelessly flawed. At best, peer review is based on good intentions and met the demands of research scientists 30 years ago – but certainly not today. It already takes long enough to get accepted into a mediocre journal, or even the dreaded arXiv. If you’re that desperate you might be willing to spell arXiv backwards. And don’t get me started on predatory journals. I won’t describe the ills of academic publishing in all its gory detail. Someone else can probably explain it much better than I can. In my case I ended up publishing into a high school journal. Parabola from UNSW to be exact.

But at the end of the day, publishing is essentially “a way to prove or showcase your research skills”. Once you complete your thesis (or minor thesis, 3-month vacation employment, etc) and may or may not be a major component of your career depending on your employment. (It is true that my Spider Solitaire paper is not relevant to my job, but that has nothing to do with the Fundamental Theorem of Calculus.)

Still, the Parabola publication still wasn’t entirely satisfactory. My paper wasn’t truly a publication. It was a story. I wanted to tell a story about how a certain Spider Solitaire was broken. There is nothing intrinsically wrong with Parabola (with the possible exception of some really lame comics and puns), but try telling that to the average Joe Bloggs with an average job, has little aptitude for mathematical puzzles and swears by Nova FM. In fact, telling this story was the original motivation for me starting this blog in the first place.

Scientists don’t have a way of getting their work recognised. They have no way of “controlling the narrative” if you will. I can publish a paper in some journal. Or I can post something on a blog and have all the scientific evidence to back it up. But how many people are going to read it, let alone believe it?

Enter Cracking the Cryptic.

You may have already guessed I am a fan of CtC (not necessarily because of this blog!). I was vaguely aware of it last year. It seemed to be massive in the UK. I tried one of the harder puzzles. Solving it was beneath my dignity – after all I scored a silver medal in the 1995 International Mathematical Olympiad. Okay I get it. There’s a pandemic going on. People are struggling in the UK. Some viewers have even commented on YouTube how watching episodes of two people solving Sudoku puzzles helped their mental health issues. I’m living in Australia not the UK. Australia really is the lucky country, so who am I to judge?

I then stumbled on this puzzle by Lucy Audrin.

This is a “Sandwich Sudoku with a twist”. Before solving the puzzle Mark briefly mentions Lucy’s website and eventually finishes the puzzle in just over 15 minutes.

You read that right. Lucy wanted to draw attention to her website. All she had to do is submit a half-decent puzzle to CtC and Mark will take care of the rest. To be fair her puzzle is more than half-decent and a good illustration of how one can keep the puzzles fresh by tweaking various rulesets (such as thermometer, anti-Knight, XV, arrows etc). If Simon and Mark only did classic Sudoku every day of the week, CtC would have finished long ago. I should also mention that Lucy can write much better stories than I can!

Great – if Lucy can draw attention to her website then perhaps I can do the exact same thing with Spider Solitaire.

This was much harder than anticipated.

It would surprise nobody if I claimed I could construct a correct Sudoku puzzle with a unique solution and Spider Solitaire theme. There was one obvious hurdle: if I submit my puzzle and it gets rejected – then good luck trying to resubmit the same puzzle a second time. I decided to play it safe by first submitting “test puzzles”.

It was a long process. Essentially I needed to “play the networking game” and gradually build up reputation. I spent a significant amount of time testing puzzles by other setters, joining the Discord server and chatting, signing up for Patreon, creating my own puzzles, etc. I submitted the above Spider Solitaire paper to the Discord a few months ago, but eventually realised that was not the same as submitting directly to CtC (submitting to Discord only means CtC have permission to do it, if it gets nominated). Yes, networking really did make things a lot easier in the long run. If you play nice and do all the right things then eventually people will help you when you need them to. If Sudoku is your thing then I heartily recommend you join the discord server. Great people, great puzzles, great jokes and cultural references. Occasionally somebody may attempt to pull off a rick-roll. What’s not to like? 😊

I emailed CtC my puzzle earlier this week and finally my luck was in.

So there you have it. If you follow my blog regularly, then I hope you enjoyed the journey as much as I did. Until next time, happy Spider Solitairing 😊

Spider Solitaire Cube revisited

In an earlier post I mentioned “Spider Solitaire Cube”, a version of Spider where players can compete for real money by playing against each other. There were a number of negative reviews claiming the game is rigged in various ways. Not surprisingly I was wondering if I can prove the deals are rigged using the Ninja Monkey’s random move algorithm.

One problem is that I had to set up an account just to test the theory. So I came up with a great idea: Spider Solitaire Cube has “practice mode” as well as “real mode”, so instead of trying to prove the deals in real mode were significantly harder than random then maybe I could prove the deals in practice mode were significantly easier than random. This idea might seem surprising at first, but if you can learn to think like an Awesome Person this can hopefully become second-nature. With practice mode I avoid the inconvenience of setting up a PayPal account just for the sake of doing “research” that is not going to advance my actual work career in any way.

Unfortunately there is a more serious problem: games are played with a 5 minute time limit. Thus if I cannot beat a difficult hand within that time period then it is impossible to work out the starting layout, and hence impossible to give the correct input to Monkey’s random move algorithm – hence the whole experiment becomes impossible.

So unless I can take my lateral thinking to the Next Level Of Awesome, it seems I have to reluctantly delete the Spider Solitaire Cube app after downloading it like half an hour ago ☹