Problem Description

Write a simulation of the solitaire card game, "Roll-Call",  in order to determine the probability of winning.

Background & Techniques

Kevin S. is a long time player of this game but has never beaten it.  In his research on the game, he ran across a statement that the probability of winning had never been calculated.  He was wondering if he had a chance of ever winning, so, not being smart enough to answer the question analytically,  I wrote this simulation.   

Here are rules for the game (from the  problem description  for a recent  ACM  programming competition). 

One very simple type of solitaire game known as “Hit or Miss” (also known as “Frustration,” “Harvest,” “Roll-Call,” “Talkative”, and “Treize”) is played as follows: take a standard deck of 52 playing cards — four sets of cards numbered 1 through 13 (suits do not matter in this game) which have been shuffled — and start counting through the deck 1, 2, 3, . . . , and so on. When your count reaches 13, start over at 1. Each time you count, look at the top card of the deck and do one of two things: if the number you count matches the value of the top card, discard it from the deck; if it does not match it, move that card to the bottom of the deck. You win the game if you are able to remove all cards from the deck (which may take a very long time).

There  are a couple of more restrictive  versions.  Kevin plays the one that allows play until you cycle through the non-matching deck three times in a row without matching any card.  Another version allows only two consecutive non-matching cycles through the deck.   In these versions one would probably play each card turned onto "matched" and "not matched" piles and recycle the "not matched" deck.  

All three versions are simulated by this program.  The program assumes that the "Not-match" pile is built face up, and the turned face down for the next  cycle.  I.E. the cards are processed in the same relative order each time through.  Building  the "not-matched" deck face down and not turning it over for the next cycle  would result in reversing the order that cards are seen for each pass.    I haven't checked whether this would affect the outcome, but it would seem unlikely that the statistical results would change change although results for any particular starting deck probably would.      We'll leave that for "Further Explorations".

The first hundred winning games are saved and can be played back by clicking on the deck arrangement display for any game.  A second window then displays each card turned and the result (matched or not matched) for each pass through  the deck.

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download executable version of the program.

Notes for programmers

The simulation runs in a loop for the number of games selected.  Each game does this: 

The first 100 winning decks are saved in a SaveDeck array.  After the specified number of games have been played and summary stats displayed,  the winning decks are displayed in a separate Tmemo, Memo4.  An OnClick exit for Memo4  determines which  game was clicked and that game is "replayed" with each card turn displayed in Memo3.  Both Memo3 and Memo4 are hidden behind Memo1, which is made invisible (Visible:=false) after each set of games has been run.  

For future reference, the best  technique I've found for scrolling a Tmemo display back to the top is to send an EM_LINESCROLL message  with a negative line count.  Like this sample: with memo3 do Perform(EM_LineScroll,0,-Lines.Count);  

The program uses a module, DFFUtils, which resides in the DFF Library file, a collection of units used in multiple programs.  Recompiling Roll_Call will require a one-time download of DFFLIBV04 or later.      

Addendum January 28, 2008:  Three years after writing this program, Kevin is still playing with it and recently wrote asking if "zero strike" games were possible.   Obviously a deck that has all cards in order would produce a zero-strike win in one pass, but are there other arrangements?   The answer is yes, and Version  2 posted today will find them.   Clearly any zero-strike game cannot be longer than 52 passes through he deck, removing one card each time.  I don't think so, but then the question becomes "What is longest zero-strike game?"   So far the range is 17 to 26 passes.   If you find out, let me  know!  

 Running/Exploring the Program 

Suggestions for Further Explorations

Does the order in which the "not-matched" deck is processed affect results?  As mentioned earlier, the order of processing can easily be reversed for each cycle by  not turning the deck over between passes.    What if the deck could be shuffled between passes?

I have assumed, but not proven,  that if you go through the non -matching deck 13 times without matching a card, you never will.   Prove or disprove this assumption.