Donatella Merlini: On Some Tiling Games

This is a joint work with Renzo Sprugnoli.

We study the behaviour of some tiling games by computing the average score a player can obtain, as a function of the probability to make a mistake. The idea originates from the well-known Tetris game and the problem is approached by using a method similar to the one presented in [MSV00], where it is described an algorithm to determine the number of ways a $p \times n$ strip, $p$ fixed and $n \in {\bf N},$ can be tiled with some given set of pieces. In that paper it is proved that the set of possible tilings can be generated by a regular grammar. From the grammar it is routine to find the rational generating function $f(t)=\sum_{n,k \in {\bf N}} f_{n,k}t^nz^k$ counting the number of tilings of a $p \times n$ strip with $k$ pieces. Here we show how similar arguments can be used to study tiling games having rules analogous to Tetris.

Bibliography

MSV00

Donatella Merlini, Renzo Sprugnoli, and M. Cecilia Verri.
Strip tiling and regular grammars.
Theoret. Comput. Sci., 242(1-2):109-124, 2000.

Back to the Index