MdpTetris documentation

1.2

Overview

MdpTetris is a Tetris simulator. The purpose of this project is to develop various Tetris-playing algorithms and compare their performances. This documentation will help you understand how to use the simulator to reproduce our experiments and implement your own algorithms.

To know how to install MdpTetris and use the simulator, first have a look at this page. If you want to implement your own algorithm within the simulator, the API and this page will help you but you should contact us before.

Installation instructions

Requirements

To compile MdpTetris, you need a standard Unix environment with of course a C compiler like gcc and the command make. You also need the GSL library (Gnu Scientific Library). Two libraries have to be installed: libgslcblas and libgsl. To do that, if you are using Ubuntu, you just have to install the package libgsl0-dev:

sudo apt-get install libgsl0-dev

Installation instructions

To install MdpTetris, download the latest tarball release available here and save it into a directory, for example /home/you. Then, uncompress the files and compile the project with the standard Unix procedure:

$ tar xvzf mdptetris-1.2.tar.gz
$ cd mdptetris-1.2
$ ./configure
$ make
# make install

The source files will be uncompressed into /home/you/mdptetris-1.2. The executable binaries will be installed into the default binary directory, usually something like /usr/local/bin.

If you don't have root access, you can install the binaries into your home directory. To do this, type ./configure --prefix=$HOME instead of just ./configure. This will install the MdpTetris binaries into /home/you/bin instead of /usr/local/bin. But make sure /home/you/bin is in your $PATH environment variable.

In both cases, you can uninstall MdpTetris with the command make uninstall.

Programs

If the installation succeeds, several binaries are installed. We can organize them in two kinds of programs: those which play some games of Tetris with an existing strategy (or policy), and those which compute a strategy.

Playing Tetris with an existing policy

Computing a policy

The feature files

A feature file defines a Tetris strategy (or policy) based on a linear sum of features. The features are some basis functions such as the wall height, the number of holes, etc. In a given state, all possible actions are tried and they are evaluated with this liner sum of features. The action with the best evaluation is then played.

Thus, a feature file defines what features are used and the value of their weights.

Let's consider an example of feature file. You will find this file in the features subdirectory of the MdpTetris package. It represents the very good Tetris strategy designed by Pierre Dellacherie in 2003.

0
-1
6
1 -1
2 1
3 -1
4 -1
5 -4
6 -1

The first two lines define some various settings about the policy but you don't really need to take care of them for now:

The important part of a feature file is the remaining lines. The next line (i.e. line 3) is the number of features. Then, each line describes a feature and its weight. On a line, the first number is the id of a feature function and the second one is the corresponding weight. Here, we are using features #1, #2, #3, #4, #5 and #6. See the enumeration FeatureID for their definition. For example, feature #5 corresponds to the number of holes in the wall, i.e. the number of empty cells recovered by a full cell. Any Tetris player know that the holes are really bad and should be avoided. Here, the holes have a big weight (-4) to penalize them strongly.

Your first run!

To make you better understand how MdpTetris works, let's play some games with Dellacherie's policy. To do this, we will use the mdptetris_play_games tool. We could also use mdptetris, then we would have got an interactive menu and more options.

Let's launch the command:

mdptetris_play_games
Usage: mdptetris_play_games feature_file nb_games board_width board_height statistics_file [comments]

Obviously, we missed the parameters. We want to play 10 games with Dellacheries' features (features/dellacherie_initial.dat) on a standard board (10 columns and 20 rows). The statistics_file parameter is the name of a file the command will generate. This file is the output of the command, it will contain the scores of all games and some statistical information about them, such as the mean score and the best score. The scores will be also be displayed on the standard output. The last parameter is optional, it is a comment to add at the beginning of the statistics file. So, here is our completed command line:

mdptetris_play_games features/dellacherie_initial.dat 10 10 20 stats

You will first see a message indicating the seed of the random number generator. Then, a score is displayed each time a game is finished. But you have to be patient because Dellacherie's policy is really good, so the games are quite long. However, we have optimized the simulator, and with Dellacherie's policy it completes about 30 000 rows per second (with an Intel Dual Core 3.2 GHz), against 120 rows per second in the original implementation (with an Athlon 1600+).

If you don't want to wait too long, you can also run Dellacherie's policy on a reduced board, such as 10*15:

mdptetris_play_games features/dellacherie_initial.dat 10 10 15 stats

Generated on Thu Mar 6 10:57:51 2008 for mdptetris by  doxygen 1.5.3