Problem Description
Here is a version of the
memory-testing card game,
"Concentration". The objective is to select matching
pairs from an array of face down cards by turning two cards face up,
one after the other, on each turn. When a match is found, the
matching cards are removed and the player gets another turn.
When the two cards do not match, they are returned to their original face down
positions.
As a single player game, the objective is to find
all matching pairs in the fewest moves. In the two-player game, the
player that finds the most pairs is the winner.
Background & Techniques
This program was prompted by a request from a high school student
looking for a class Delphi programming project. By the time I
had developed a graphical demo that would flip or remove cards as a
starting point, he had moved on to something different. So I
decided to complete the logic part and post it.
The game allows one or two players and the number of cards in the array
can be selected by the user.
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.
The U_CardComponent previously
introduced, automates the card image handling. When a new
game is started two decks are created - one with 52 cards and one
with twice the number of pairs specified by the user.
After shuffling the temporary 52 card deck, the first "nbrpairs"
cards are used to set the suit and card values of the first half of the
real deck,. The lower half of the deck has card values and suits set
to match the first half, ensuring pairs. The play deck is
shuffled of course before dealing them into a face down array.
The checking and scoring logic is embedded in an
OnMouseUp exit for each TCard object.
The first card clicked of a turn is saved and when a second card is clicked, its
value and suit are compared to the 1st card. Based on results,
scores are updated, cards made invisible or simply turned back face
down. When all pairs are matched, the winner and score
are displayed
and the game is over.
Expected game lengths
What is the expected length of a game if the player has perfect
memory? That is, once a card has been turned our player will remember exactly where it is
located; it is, in effect,
left face up Since a perfectly lucky game would require N
turns to match N pairs, and a perfectly unlucky game would require 2N-1
turns. Simplistic
reasoning says that the average game should be halfway between the
shortest and longest possible games which slightly less than 1.5
times the number of pairs . My analytical skills bogged down in
trying to calculate a value, so I resorted to writing a "Concentration Study" program to play several thousand
"perfect memory" games and chart the game length
statistics. I looks like the average game is slightly higher
than 1.5 times N. In other words, there seem to be more ways to be be
unlucky than there are to be lucky. I'll wait for a real
mathematician to verify this, or tell me that I have a bug in the
program. In any event the Concentration Study program can
be
downloaded from the links below if you want to play with it.
Addendum April 12, 2009: If the original version of
Concentration was not difficult enough, here is Version 2 which adds the
option of requiring 3 cards to be matched before they are removed from the
board. This version also adds the option of matching on card value and
suit, as in the original version, or , on card value only.
Running/Exploring the Program