Solving Rummikub with computational power
Gulin, Magnus (2019)
Gulin, Magnus
Åbo Akademi
2019
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi-fe2019120245370
https://urn.fi/URN:NBN:fi-fe2019120245370
Tiivistelmä
Rummikub is a popular family board game for 2-4 players. The game is based on
a number of tile manipulation rules which are combined, creating long chains of
thoughts that the player has to remember. During multiple Rummikub sessions,
I have concluded that this should be a good exercise for a computer. This is my
motivation for this thesis, to make the game solvable by a computer.
The game is played in turns. Each player starts with 14 tiles in the rack and tries to
move them all to the table. The tiles on the table should always be in correct sets
called groups and runs. A group consists of three or four tiles with the same number,
all in distinct colors. A run consists of three to thirteen tiles in the same color, which
follows each other numerically. The tiles on the table can be moved around and tiles
from the rack can be added, as long as all sets on the table are valid at the end of
the turn. If a player cannot make a move, he needs to pick up a tile from the pool
to his rack. The main challenge for a player is thus how to combine the tiles on the
table and in the rack so that he can place as many tiles as possible from the rack to
the table in each move.
This thesis examines earlier work related to this game, where multiple algorithms
have been proposed for solving this game. The earliest is based on Integer linear
programming, where a mathematical model for finding a solution to the game is
presented. A later work proposes an algorithm based on heuristic guided state
space search. In “The Complexity of Rummikub Problems”, a polynomial algorithm
is described. Lastly, I have created a recursive algorithm for comparison with the
other algorithms.
Among these algorithms, I have implemented two for practical benchmarks: my
recursive method and the heuristic guided state space search. The former serves as
a baseline for performance testing, as it is a naive brute-force algorithm. The latter
is a novel technique with influences from predatory animals, and felt like a good fit
for this thesis. As expected, the heuristic based function was faster, although the
performance of the algorithms did not differ much for small inputs.
a number of tile manipulation rules which are combined, creating long chains of
thoughts that the player has to remember. During multiple Rummikub sessions,
I have concluded that this should be a good exercise for a computer. This is my
motivation for this thesis, to make the game solvable by a computer.
The game is played in turns. Each player starts with 14 tiles in the rack and tries to
move them all to the table. The tiles on the table should always be in correct sets
called groups and runs. A group consists of three or four tiles with the same number,
all in distinct colors. A run consists of three to thirteen tiles in the same color, which
follows each other numerically. The tiles on the table can be moved around and tiles
from the rack can be added, as long as all sets on the table are valid at the end of
the turn. If a player cannot make a move, he needs to pick up a tile from the pool
to his rack. The main challenge for a player is thus how to combine the tiles on the
table and in the rack so that he can place as many tiles as possible from the rack to
the table in each move.
This thesis examines earlier work related to this game, where multiple algorithms
have been proposed for solving this game. The earliest is based on Integer linear
programming, where a mathematical model for finding a solution to the game is
presented. A later work proposes an algorithm based on heuristic guided state
space search. In “The Complexity of Rummikub Problems”, a polynomial algorithm
is described. Lastly, I have created a recursive algorithm for comparison with the
other algorithms.
Among these algorithms, I have implemented two for practical benchmarks: my
recursive method and the heuristic guided state space search. The former serves as
a baseline for performance testing, as it is a naive brute-force algorithm. The latter
is a novel technique with influences from predatory animals, and felt like a good fit
for this thesis. As expected, the heuristic based function was faster, although the
performance of the algorithms did not differ much for small inputs.