Assignment:
Game playing
by Hendrik Lübben
Introduction
The two games "Rummikub", a version of middle eastern origin of the
more well-known card game "Rummy", and "Ludo", a very old dice-based board
game, have been chosen for this comparison.
Given the three characteristics of being or not being complete,
deterministic and zero-sum, these two games differ in two major
aspects, which gives a broad basis for this discussion.
The decidedly more interesting game "Rummikub" will be regarded in
more detail at the end of this work.
Rummikub (Minni Rummy)
Characterisation
I will first characterize Rummikub (Mini Rummy is the german name.)
with respect to the three given categories:
- Rummikub has incomplete information, since only the cards open on
the table and those in the own hand are accessible, both the stack and
the cards of the other player(s) are hidden.
- If the original stack is regarded as given, the game is
deterministic. It might be a better approach, though, to regard the
game as non-deterministic, since information on the stack is
inaccessible: The current top card only becomes known as soon as
it is taken up by someone.
- Due to the evaluation of the games outcome, Rummikub is clearly
zero-sum. There is one winner, the person who first manages to dispose
of all of his cards, all the others are losers. Each loser receives
the negative amount of the sum of the values of all his cards, the
winner receives the positive sum of all the other players losses.
Terminology and rules
When explaining the terminology of Rummikub, I will stick to the parts
most relevant to this analysis. A
comprehensive explanation
of this game can be found in the net. I will also use the terminology
from this site, which is quite straight forward though and should be
understandable without separate explanation.
Rummikub can be subdivided into separate stages. While going through
these, I will also point out some of the popular variations of the
game.
- In the preparation stage, before the actual start of the game,
each player receives 12 cards.
Rummikub is normally played with small tokens in four
colors, numbered from one to thirteen, but two normal decks of 52
cards each, a(ce) weighing 1, j(ack) 11, q(ueen) 12 and k(ing) 13, do just
as fine, the four colors being replaced by clubs, spades, hearts and
diamonds. Normally, runs of subsequent numbers cannot jump from 13
back to 1, i.e. 12, 13, 1, 2 would not be considered a legal run. When
playing with normal decks of cards, though, sequences like
q, k, a, 2 are often considered to be legal.
Standard Rummikub contains four jokers, this, too, varies, though, and
any number from zero to six jokers might be used. The main influence
of the number of jokers is only, that they reduce the number of plys,
needed on average to complete a game. Since they increase the number
of possible combinations, the also make the game more complex.
- In order to put down ones first meld, one has to have a certain
amount of points. Cards can be put down in runs or sets of at least
three cards. Depending on the variation used, the first meld has to
have a value of 30 or 40 and has to consist only of cards from the
hand of the player. Generally, when requiring 30, each player
starts with 12 or 13 cards, when requiring 40, with 13 or 14. These
first 30 or 40 points sometimes have to be in one single meld,
generally they are calculated as the sum over all melds placed on the
table by that player. Some variations of Rummikub have even stronger
restrictions and always allow only one new meld to be put on the
table per turn.
Since each player at each turn either has to do some modifications on
the melds on the table (which is only allowed, after he has layed down
his initial meld) or take up a card from the stack, in the start stage
of the game, i.e. before any player has layed down any cards, every
player just keeps picking up cards until he can put down his initial
meld.
- During the main part of the game, each player who has already
layed down his first initial meld (otherwise he just has to keep
collecting cards) has to make some modifications on the table. These
include any combination of the following three:
- Putting down new melds or adding cards to preexisting melds.
- Taking up melds or single cards from melds. (Some variations of
the game do not allow this move for melds containing jokers.)
- If playing with jokers: Exchanging jokers for the card for which
they stand.
Since the number of cards that can be taken up is not restricted, this
practically allows each player at each turn to completely reorganize
all the cards on the table and in his hand in order to put down some
more. The only restriction is, that at the end of a move, everything
that is left on the table has to be runs or sets of at least three
cards each.
If a player cannot make a move effectively changing the cards on his
hand, he has to collect a card from the stack.
Description of the game
The states of Rummikub are best defined by a set of sets of queues.
There is one subset for the stack, one for the table and one for each
player. The structure has been chosen such as to support best the way
an experienced player would access the game:
- stack: this set contains just one queue, namely all the cards
still in the stack in their sequence resulting from last mixing
- table: the table contains as many sets as there are runs and sets
of cards on the table
- player n: a hand is subdevided into one queue with those cards
that do not yet form a run or set of cards that could be placed on
the table
Each element of theses queues is a pair (value,color) with value
element of {a(ce), 2, 3, 4, 5, 6, 7, 8, 9, 10, j(ack), q(ueen),
k(ing)} and color elment of {c(lubs), s(pades), h(earts), d(iamonds)}.
The table is accessible (readable) for every player, the stack in
hidden for every player. Apart form that, each player can only read
his own subset.
The operators are:
- pick-from-stack: removes the first element from the stack-queue,
adds it to the first hand-queue of the current player and makes the
next player the current one
- place: places a complete run from the hand of the current player to
the table, i.e. takes the corresponding queue (not the first one) from
the subset for his hand and adds it to the subset for the table.
- put: puts one card from one of the queues of the own hand to one
of the queues on the table
- pick: picks up one card from the table, i.e. takes an element
from one of the queues on the table and adds it to one of the queues
of the own hand
- pass: makes the next player the current one (only possible, if
the table-subset only contains admissable queues)
While these actions can only be performed by the current player (i.e.
by each player only at the time, at which he is the current one), the
following action can be performed at any time (i.e. asynchronously):
- organize: select cards from the first queue of the own hand (subset),
form separate queues out of them and add those to the subset.
Analysis of Rummikub
Judging from long-term playing experience, Rummikub has one inherent
property which very gravely effects possibilities to evaluate states:
As soon as at least two of the players have placed their first melds,
Each single turn can (and frequently does) change the face of the
table completely. It is not at all unusual that in order to get rid of
just one card (or even only exchange it against one of smaller value)
almost all of the runs and sets on the table are (ex-)changed.
When evaluating different possible moves, of course the relations
between cards left on the hand are very important, too. Four and five
of spades {(4,s),(5,s)} are better than two cards far apart from
each other, since the chance of forming a run from them is higher.
They should mainly be evaluated
relative to each other, though, not relative to the cards on the
table, since these will very likely be gone / bound into different
constructions when the current player gets his next turn. This
significantly reduces the computational effort without qualitatively
fallling short of the (under the given circumstances) optimal
solution.
The usual MinMax-approach is completely intractable in this game,
since the net branching factor would be orders of magnitude greater
even than for "go": The entire deck consists of 104 cards (plus
jokers if included). In order to consider a typical situation, let us
for the moment assume three players, two of them with cards on the
table, and no jokers in the deck. A couple of cycles into the main
stage of the game, each of the players with cards on the table will
typically have about five cards on his hand, the third player roughly
twenty, twentyfive cards being on the table leaves another fifty cards
in the stack. The third player has to collect cards, anyway (let us
assume, he does not yet have a sufficiently valuable initial meld).
If player one is to move, a MinMax-approach would mean, that he would
have to determine the best move for each possible set of cards his
opponent (player two) might have. If player two has 5 cards, only
those on the table and those in the hand of player one with certainty
not being among them, this leaves (5 [out of] 74) = 74!/(5!69!) =
16.108.764 possible sets - and these are only the possible hands,
for each of these there are many different possible moves that have
to be evaluated, and as soon as the third player enters the scene,
the variety becomes even larger. Since there are two decks of cards,
it are actually not really 16 million, since quite a few of them are
going to be identical, but just by pure order of magnitude this
branching factor is so huge, that even a very fast computer would
not manage to calculate more than one step ahead. And even if all
the possible different hands for the opponent are calculated and
evaluated, due to the enormous uncertainty, which hand he will
acutally have, the evaluation would be practically worthless.
As pointed out before, luckily, the disadvantage of this is small.
Even though Rummikub is not truely episodical, it is a rather good
approximation to it, meaning, that, due to the fact, that the face
of the table is likely to change dramatically from one turn to the
next, optimizing a good evaluation function based solely on the
current status will as much as possible optimize the global goal,
too. Such a one-step-heuristic is rather easy to formulate, though not
quite as easy to achieve. It is verified by playing experience, too.
At any time, the goal should be to minimize the amount of points on
the hand. Complete runs/sets held on the hand are exempted from this in
the early stages of the game, for the following reason: If a player
has a complete run/set on his hand, but is able to do other changes on
the table, too, i.e. does not have to take a card, anyway, it is better
to keep the run/set and only lay it down in the next cycle, preventing
that he might have to collect a card for being unable to change
anything on the table, then. This does no longer apply later in the
game, because the risk that another player might finish before he
has the chance to lay down that run becomes too great.
There are two possible algorithmic approaches to achieve the goal
of this heuristic:
- Just take up all cards on the table, put all your own cards to them
and then just try all possible combinations. This is the
"brute-force"-approach.
If the search strategy applied is complete, and the best result is the
original situation, this means that no sensible changes are possible
and the player has to take a card.
- The "human-like" approach would be a two-step one. First all the
uncritical moves are made. These include: exchanging jokers where
possible; if applicable (possibly using the gained jokers), lay out
any complete runs/sets; put down any cards that can be added to ends of
runs/sets on the table. Apart from the one possible conflict that a
card might be needed in a row but can also be exchanged as a joker,
which is rather easy to resolve, these different actions do not
interfere with each other.
Once this is done, for each card or run or set of cards left on the
hand, possible ways to dispose of it via modifications on the table
is searched. This is best explained via an example. Assume the hand
contains (7,s); to lay this down, either two elements of {(7,c),
(7,h), (7,d)} or both elements of either of the following are needed:
{(5,s), (6,s)}, {(6,s), (8,s)}, {(8,s), (9,s)}. If any of these cards
are on the table, then
- if they can be taken, leaving the rest of the run/set they have
been taken from in an admissable state, then return this solution,
laying down the (7,s) in this new run/set
- if the left-over rest(s) of the run(s)/set(s) are
illegal, then add these rests to the hand and recursively apply the
algorithm to this hand
This strategy is clearly goal-directed and therefore likely to be
significantly faster. It is very hard to guarantee that it finds
the optimal solution, though, for example in situations, where there
is a joker "hidden" on the table. A hidden joker is one, which
can be made unneccessary by ONLY rearranging the cards on the table.
Especially when there are many cards on the table, this happens rather
frequently. Such rearrangements would not automatically be taken by
this approach, though, but would have to be explicitly built in.
The computational complexity of this is impossible to calculate
without extensive stochastic research, because in both cases the
actual number of possible combinations depends enormously on the
cards that are being checked. For the first approach, the average
number of different combinations in which cards can be disposed off
basically determines the branching factor of the search tree. In
the second approach, the number of potential solution-cards that
are on the table, but leave rests that need to be taken care of plays
the same roll.
Further investigation into this promises to be very interesting but
also very time consuming and requires a corresponding implementation,
if possible of both approaches, to stochastically evaluate their
performance.
Ludo (Mensch Ärgere Dich nicht)
Characterisation
Ludo (Mensch Ärgere Dich nicht in german) is a very old game.
Nonetheless, internet resources on it seem to be extremely small,
neither yahoo nor lycos came up with any usefull sites. Since its
structure is comparably simple, this in uncritical, though. With
respect to the three given categories, Ludo can be classified as
follows:
- Ludo has easily accessible complete information. The positions
of the figures on the board completely characterize the current
situation.
- Since the moves in Ludo are determined by the use of dice, it
is clearly non-deterministic.
- Depending on how it is played, Ludo can be zero-sum but does not
have to be. The game ends, as soon as one player has all of his
figures in the goal. If the game evaluation is simply that of winning
or loosing, Ludo is zero-sum, but if every player receives a number
of points according to the number of figures he managed to get into
the goal by the time the game ended, it is not.
There exist situations, where a player has the choice of either
kicking an oponents figure off the board and in doing so putting his
own figure(s) in the danger of being kicked off in return or avoiding
this situation by moving another figure.
Terminology and rules
Ludo is a game for two to four players. The board shows a way
consisting of 56 steps leading around an inner space in the form of a
plus sign. In each corner there is a starting field, where figures
enter the way, at each far end of the plus there are exits into the
goals. Each of the for corners has a different color, belonging to a
different player. The goals have the same four colors, each being
placed such that the goal is reached shortly before reaching the
entry again, so after almost a complete cycle.
Usually the youngest player begins. Each player plays with four
figures. The game is finished, as soon as the first player has
reached the goal with all his figures.
You need a double six to be allowed to start a figure (i.e. leave
the start field). Unless either the entrance is blocked by one of
your own figures or all your figures are on their way, already, if you
get a double six, you are obliged to use it to start a new figure.
Any throw of doubles, unless used to start a new figure, gives you
the right to roll the dice once again, i.e. make two (or more) moves
in a row. If all your figures are in the starting field, you are
allowed to roll the dice up to three times, trying to reach the
double six.
You can either move one of your figures by the sum of the score of
the two dice, or two figures, each by the score of one of the two
dice. You cannot move a figure into a field which already contains
one of your figures. If you manage to reach a field which contains
a figure of another player, moving into that field throws his figure
off the track and moves it back to its starting field.
Description of the game
Since this game has complete information, its states are best
represented by giving the positions of the four figures of each
player as coordinates on the board. Conditions like "all figures
in start field", "all figures in goal" or "beat" can then easily
be checked then by just comparing coordinates.
There is only one operator needed. Whenever it is a players
turn, the dice are rolled automatically. The player then only
has to "assign" the value of each dice to a figure, causing it
to move. "assign" will automatically check that the result of
the move is legal (e.g. not moving beyond the end of the goal
and not moving onto a field already occupied by the same
player) and otherwise reject the selection.
At the beginning and - rarely - later, when all the figures of
one player are in the start field, there will be quite a few
situations (combinations of dice) with which he cannot make
a move. Also, this occurs near the end of the game, when a
player tries to place his figures in the goal places (because
the scores of the dice must match the distance exactly). Apart
from these easy to handle exceptions, it will always be possible
to make a move.
A heuristic for this game will mainly be based on two criteria:
The distance to the goal (positive) and the danger of being
captured by figures of other players (negative).
The first criterium is calculated by simply counting the steps
to be covered before reaching the goal, the second one is a
little more tricky, but still easily tractable. Since there are
only thirtysix combinations for two dice, it is easy to calculate
the probability of being captured by counting those combinations
which would result in a capture and those which would not.
Since rolling a double gives a player a second go, this becomes
a little more complicated, but since the probability of rolling
several doubles in a row decreases rapidly (1/6, 1/36, 1/196, ...)
with the number of doubles, this is not a real problem: Calculating
if for up to three or four doubles is easily tractable, and more
doubles in a row are so unlikely that these cases do not influence
the resulting probability in any measurable way, anyway.
Hendrik Lübben San Diego, November 5, 1997