Probability of a successful game in Prisoner’s Patience

Prisoner’s patience is a simple patience game – with a story! Legends tells that a warden gave a deck of cards to a prisoner serving a life sentence and told them that they are allowed to play a single game each day, and if they play a successful game, they are free to go. The details are a bit hazy, but if I remember correctly, it was said it took the prisoner 27 years to beat the game. That’s just a shy under 10,000 games. This got me thinking: is this a reasonable number of games played? Let’s bust this myth!

Rules of the game

The game is very simple: take a shuffled 52-card deck, and play them on the table one at a time in a single row. If the card’s rank is one smaller or one greater than the rank of the previous card, place the card on top of it. The card can also jump over two cards to check if the card there is one smaller or one greater. Aces are the smallest, kings are the greatest, and aces can be played on top of kings, and vice versa. The aim is to have all cards stacked in a single stack in the end of the game.

To elaborate, let’s take a table of cards like this:

// C, S, H and D are short-hand for clubs, spades, hearts and diamons

C5  D9  C7

Now, let’s say the next card we play is the eight of clubs:

C5  D9  C7  C8

Now, C8 can be moved on top of C7:

// C7 is below C8
C5  D9  C8

Next, we can repeat the moves until no moves can be done. C8 can be moved to D9:

C5  C8  C7

And finally, C7 can be moved to C8:

C5  C7

We end up with C5 being the sole card in the first stack, and the second stack containing C7, C8, and D9.

The moves can be done over two cards as well:

// C2 can hop over the two cards to C1, but H2 cannot hop over D5.
// It's either "the immediate neighbor", or "over two cards".
C1  D5  H2  C2

…and that’s it, rules-wise. A simple game to play, but apparently really difficult to win. Let’s see how an AI fares with it.

Coding the game

The game is rather simple to code. The core loop looks like this:

fun playCard() {
    val card = deck.pop()
    
    val newDeck = Deck()
    newDeck.push(card)
    table.add(newDeck)

    // TODO Check if table decks can be combined
}

We take a card from our hand deck, create a new table deck, and put the picked card on top the (empty) table deck. If we were to do only this, we would always end up with all the 52 cards laid out in a single row. Let’s remedy that by performing all the possible actions after each played card:


fun playCard() {
    val card = deck.pop()
    
    val newDeck = Deck()
    newDeck.push(card)
    table.add(newDeck)

    var keepGoing: Boolean
    do {
        keepGoing = false
    
        // Prune empty decks
        table.removeAll { it.isEmpty() }
        if (table.size == 1) break
    
        for (i in table.size - 1 downTo 1) {
            val current = table[i]
            val previous = table[i - 1]
    
            val rank = current.peek()!!.rank
            if (canPlay(current.peek()!!, previous.peek()!!)) {
                while (!current.isEmpty()) {
                    previous.push(current.pop())
                }
                keepGoing = true
            } else if ((i - 3) >= 0) {
                val wayBack = table[i - 3]
                if (canPlay(current.peek()!!, wayBack.peek()!!)) {
                    while (!current.isEmpty()) {
                        wayBack.push(current.pop())
                    }
                    keepGoing = true
                }
            }
        }
    
    } while (keepGoing)
}

On each iteration, we remove all the empty stacks we have on the table, and bail out early if there’s only one stack left. Next, from the right-most stack, check if can play the card to the previous stack, or to the stack that’s three steps back from the current stack. Repeat this until there’s no possible moves left.

The canPlay() method looks like this, by the way:

fun canPlay(card: Card, target: Card): Boolean {
    if (card.rank == target.rank - 1) return true
    if (card.rank == target.rank + 1) return true
    if (card.rank == 1 && target.rank == 13) return true
    if (card.rank == 13 && target.rank == 1) return true
    return false
}

Now all that’s left is to wrap the whole thing in a loop:

fun play() {
    while (!deck.isEmpty()) playCard()
}

Next, let’s play a few… million games.

Simulating 16 million plays

Since I’m lazy and can’t be bothered to wait while a single core churns through the games, I wrote a little code that lets coroutines play the games, one million games per coroutine:

suspend fun main(args: Array<String>) {
    val victories = AtomicLong(0L)
    val count = 16_000_000

    withContext(Dispatchers.Default) {
        val jobs = mutableListOf<Job>()
        for (j in 0 until 16) {
            val job = launch {
                for (i in 0 until count / 16) {
                    val game = Prisoner(Random.nextLong())
                    game.play()
                    if (game.table.size == 1) victories.incrementAndGet()
                }
            }
            jobs.add(job)
        }
        joinAll(*jobs.toTypedArray())
    }

    val percentage = (victories.toDouble() / count.toDouble()) * 100.0
    println("$victories / $count --> $percentage %")
}

After about 20 seconds, the results were in:

661 / 16000000 --> 0.00413125 %

Huh. 0.004 % chance of winning. That leads to about 24,205 games per successful game. Remember that 10,000 tries from the story? It turns out, that was WAY off. It didn’t take 27 years for the prisoner to get free; it took 66 years!

Conclusion

So, the myth of a prisoner playing a card game for 27 years until getting free was quite optimistic. From 16 million games, only 661 were successful, resulting in 24,205 games played on average per single successful game. I knew the game is ridiculously hard to win, but I didn’t expect it to be this hard.

I hope you enjoyed this little write-up of my little experiment. If you’re interested, my blog has other write-ups of similar experiments – have a look!

1 thought on “Probability of a successful game in Prisoner’s Patience”

  1. Damn, awesome website. I actually came across this on Bing, and I am happy I did. I will definately be coming back here more often. Wish I could add to the posts here and bring a bit more to the table, but am just absorbing as much info as I can at the moment.

Leave a Comment

Your email address will not be published. Required fields are marked *