Perfect Memory Game – Python

The other day, I had a peer of mine send me a message asking me “What programming language should I use for [x]?” After inquiring further, it turned out that this student was analyzing the mathematics behind the classic “memory game”.

For those unfamiliar with this game, essentially it follows that there are a number of unknown objects (generally some type of card like below) placed in-front of two (or more) players. The players then alternate terms trying to match the unknown objects. They can flip over two cards in one term, and if they match, they take those two cards and score a point. They then take another turn as a reward for getting the pair. This continues until all of the cards are matched with each other. The player with the most points wins. If the players have the same number of points, it is a tie.

Figure 1: Example of memory game with images of different objects
Image result for memory game

My friend essentially wanted to calculate the probability of each player winning based off of whether they went first or not. However, in order to validate his findings, he wanted to create a program that simulated the game a number of times in order to find some empirical probabilities.

He was having trouble, so I offered to design the program for him and then he could mess around with it and use it to conduct further research.

For the purpose of my simulation, I created a game where all 52 cards of a normal face card deck were being used. When a player flips over two cards with the same number and same color, then this counts as a match (e.g. 9 of clubs and 9 of spades). However, what made this task more interesting was the concept of perfect memory. My peer wanted each player to have a perfect memory of every card that has been flipped over so that they could always make the “perfect move”, which maximizes the possibility of them winning.

This meant two things:

  1. If Player 1 flips over a picture of an apple and another apple picture had been turned over previously, Player 1 will then select this other picture and get the pair
  2. (Slightly more complicated) If Player 1 selects two cards that don’t match, but then the second card they flipped over matches a card that has been flipped over before, then Player 2 will select those two cards during their next turn.

In order to accomplish this, I basically used two main arrays which consisted of “revealed cards” and the rest of the “game deck” which consisted of the non-matched, non-revealed cards.

After ironing out a few bugs with my implementation, I started collecting data to establish the probability of each entity winning. After running one million simulations of the game I found the following results:

Player 1 Winning: 46.61%

Player 2 Winning: 46.81%

Ties: 6.59%

This does seem to make sense based off of my experience with the game. One phenomenon that you experience after playing this game for awhile is that it is advantageous to have turns towards the end of the game. As the “revealed” cards add up, playing late in the game creates the potential for a “streak” to be created where you get four or more matches in a row due to the ever increasing number of un-flipped cards (and your perfect memory). Since the probability of Player 1 getting a match on the first turn is pretty low (1.96% to be exact), Player 2 has a very slight (and by very slight it seems to be about 0.2%) advantage since the play after Player 1. Of course, the first match could theoretically occur up to the 13th total turn in the game, so that reduces the impact that this advantage has.

Anyway, this was a fun short-term project to embark on. My peer sent me a message about the issue at about 11:30 pm on a Friday night, and then I stayed up until about 1:30 am working on the code and then spent about an hour the next day debugging it and checking for realistic results.

I have uploaded the code onto my GitHub account here if you want to check it out. The program creates potential for you to use a different composition of deck (e.g. half of a full deck), however it does assume that every card in the deck has a match.

This is another example of a project that I’ve done in Python, and I think it’s solidifying my preference to use Python for projects like “Hmmm… I have a problem, let’s write some code to fix it…”. The other two languages that I use/know—Swift and Java—don’t really work as appropriately for this type of project. Swift is only for iOS and macOS and doesn’t have easy ways to read standard input or output, and Java is just a pain to use for pretty much any type of project due to the overhead.

Thanks for reading!

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s