Monte Carlo simulation of the Memory Game

matchGame.jl

#= 
Card matching game simulation

using Revise
Load with: includet("matchGame.jl")

Analysis of Jan De Wilde's Shinkei-Suijaku Memory Game
https://jandw.github.io/memory-puzzle/

=#

using Random

"""
    matchMC(nPairs::Integer,nMC::Integer)

Monte Carlo experiment of the Match Game.
    
# Parameters
    nPairs: Number of pairs of matching cards in the game
    nMC: Number of Monte Carlo iterations
    
# Returns
    expTurns: Expected number of turns required
    
# Example
    matchMC(8,1e6)
    12.515998

"""
function matchMC(nPairs::Integer,nMC::Integer)
    # Count total number of plays
    playCount = 0

    # Card numbers
    cardVec = Vector(1:nPairs)

    # Initialize random number generator
    rng = MersenneTwister(1234)

    # Monte Carlo iterations
    for play = 1:nMC
        # Game vector
        cards = shuffle(rng,[cardVec;cardVec])

        # Add the number of turns to the playCount
        playCount += playGame(cards)

    end

    # Divide playCount by the number of Monte Carlo iterations
    expTurns = playCount / nMC
    return expTurns
    
end

"""
    playGame(cards::Vector)

Simulate play of a single game.
    
# Parameters
    cards: Vector of cards in the game
    
# Returns
    turns: Number of turns required
    
# Example
    cards = [4,  3,  5,  8,  5,  6,  1,  8,  1,  2, 7,  6,  7,  2,  3,  4]
    playGame(cards) = 12

"""
function playGame(cards::Vector)

    # Number of cards
    nCards = length(cards)

    # On the first turn, check the first two cards. Move to the third card
    k = 3
    turns = 1
    while k < nCards - 1
        # Does kth card match one of the previous (k-1) cards? 
        if cards[k] ∈ cards[1:k-1]
            turns += 1
            k += 1
        # Otherwise, compare the kth and (k+1)th cards, taking one turn and jumping ahead two cards
        else
            turns += 1
            # If (k+1)th card matches an earlier card, take another turn
            if cards[k+1] ∈ cards[1:k-1]
                turns += 1
            end
            k += 2
        end
    end
    # Compare last two cards. If they match take one turn, otherwise take two.
    if nCards > 2
        if cards[nCards-1] == cards[nCards]
            turns += 1
        else
            turns += 2
        end
    end

    # Return the number of turns required
    return turns
        
end