Pytris – A Python Script for Testing Tetris Algorithms

In another post, I explained a probably non exhaustive list of the different types of Choosing Blocks Algorithms that might exist for Tetris.  Here I explain Pytris, a script that has the logging abilities for research into the algorithms.  This is part of my ongoing Master’s Thesis Project.  If you’re interested in the source code, just contact me!  I’m happy to provide it with additional explanation.

Pytris has been implemented in Python under heavy use of the pygame library. This made it possible to account for the desired goal of having test participants create a realistic game environment on their own computer. With pyg.exe even Windows users were enabled to play the game on their operating system.

Game Mechanics

Pytris offers all game mechanics, that can generally be found in any implementation of Tetris. Players are able to translate and rotate pieces coming down. Additionally, they can listen to the original Tetris score while playing, if they desire to do so.

Upon starting the script, Pytris captures the screen in a full-screen mode so that players are not visually distracted on the screens of their computers. Graphically there are also no further distractions from the game itself. It does not show a score or a number of lines made indicating performance directly.

The initial speed of the game is set to 400 ms, which means the tetromino is moved every 400 ms. Speed increases of 5 ms happen whenever a line is removed. If more than one line is removed at the same time, the speed increase is multiplied by the number of lines removed. The minimum speed is set to 75 ms. These parameters can be changed, if needed.

tetris2

For each game the algorithm for choosing pieces is chosen at random without replacement from a bag holding all five basic algorithms described above, each of them twice. This means, each player plays ten games of Tetris, two per algorithm in a random order.

A game ends after five minutes or if a player looses – whichever event comes first. The script pauses upon that point in order to give players time to fill in a questionnaire or have a self paced break between games. However, during these breaks the screen is still captured preventing players to do any other computer based activity, at least at the machine they are playing Pytris on. Due to the time restrictions for each individual game, players play a maximum of 50 minutes during one session.

Data Recording

Pytris has been designed in order to record a lot of data in general, not only for the data analysis required for this research. For each game within a session, a log file is created. After a test session has been concluded, these files can be retrieved in a folder named by the participant ID.

Every entry in a log file has a timestamp. A log file consists foremost of a header for general test data such as the participant ID defined in the player setup, the number of the game (ranging from 1 to 10), which algorithm has been used in this game, whether the player had the original Tetris score activated and finally, when the game started. The initial speed and every speed change are recorded as well.

For each new block, a situational analysis is performed. This consists of a count of lines made so far into the game, the current pile height, the current bumpiness measure, the current number of closed holes and for which type of tetromino there are possible placements on the current contour. Finally, the chosen block and the current grid are recorded as well as every keyboard interaction of the player.

Different Tetris Algorithms

I am currently writing my Master’s thesis and using Tetris as a game of reference.  In a pre-test I needed a quick version of Tetris, that records a lot of the interaction and tests different algorithms for choosing blocks.  Before I present the resulting implementation (Pytris), I want to briefly talk about algorithms that choose blocks in Tetris.  Part of this post is in the draft of my written thesis as well.

But lets get into the heart of Tetris: how to choose blocks! Next to obvious solutions like a random choosing of all available blocks, there have also been propositions of using Tetris games as means of communication by encoding information in how the blocks are chosen. This selection of blocks is then still supposed to appear random or at least semi-random to an unknowing player of such a game (see for an example Ou, 2011).

In this post, the five algorithms implemented are presented with the general idea behind how the blocks are chosen. An exemplary implementation of each algorithm is provided in Python.

Nicetris

In order to offer players an algorithm that helps them learn the game and play it with a minimum amount of challenge, the Nicetris algorithm has been designed specifically for this work, but with the inverted principles of the Bust Head (see below) algorithm. By analysing the situation of the current game board and especially, how the contour looks like.situation[4] in the code example refers to an array containing all shapes, that are fitting the current built-up. If the current built up is really not fitting for any piece (which is theoretically impossible), the choice is made from the set of generally well fitting blocks (O, I, and L-blocks).


nice_bag = []
for element in bag:
  if element in situation[4]:
    nice_bag.append(element)
if len(nice_bag) > 1:
  return choice(nice_bag)()
else:
  return choice([I,O,L])()

This approach was designed to ensure that the player always has an edge-fitting option to place the current tetromino and, hence, enable them to clear rows fast.

Grab Bag

According to the Tetris Wiki, this is the original Tetris algorithm. Essentially, all possible tetrominoes are put in a bag and drawn randomly one after the other without replacement, which means, until the bag is empty. Then, another bag is started for the next seven pieces.


if len(ungrabbed_bag) == 0:
  ungrabbed_bag = [ O, I, S, Z, L, J, T ]
block = choice( ungrabbed_bag )
ungrabbed_bag.remove(block)
return block()

This is assumed to create a fair random game. The properties of this algorithm are, that there are at most 12 pieces between two I tetrominoes and a maximum of four ß pieces can come in a row. Hence, the chances of encountering a run of the same (bad) pieces are eliminated.

True Random

The most basic algorithm for choosing blocks in a game of Tetris is the True Random version.

return choice( O,I,L,J,T,S,Z )()

This algorithm is equal to drawing from an urn of tetrominoes with replacement. Very fortunate and very unfortunate series of blocks are likely in an equal way. However, this algorithm might actually sometimes show stronger patterns than the others.

Skewed Random

In order to increase the likelihood for a kill sequence as described by Burgiel, 1997, Skewed Random assigns a 50% chance to either of the ß (S or Z) pieces instead of the usual likelihood of 2/7 = 28.57%.


if random.randint(0,1) == 0:
  return choice([S,Z])()
else:
  return choice([O,I,L,J,T])()

Mild Skewed Random

A milder version of this algorithm adapts Skewed Random as such, that the likelihood for ß pieces are at about 39%. This version is expected to still be more difficult than the previously described algorithms (Nicetris, Grab Bag and True Random) while being less harsh than the 50% version.

Bust Head

This algorithm is inspired by the Bastet game developed by Frederico Poloni. While his version relies on a well analysis, the version used in this research is based on a contour analysis, but with a similar idea. First, the algorithm checks, which pieces do not fit the contour (fitting pieces are recorded in an array in situation[4] in the code example). Then, a bag of these pieces plus the O piece is used to randomly choose the next tetromino. If every possible tetromino could fit the contour, the undesirable combination of O and ß pieces is used as a bag for the next elements.


tiny_bag = [O]
for element in bag:
  if element not in situation[4]:
    tiny_bag.append(element)
if random.randint(0,2) > 0:
  if len(tiny_bag) == 1:
    return choice([O,S,Z])()
  else:
    return choice(tiny_bag)()
else:
  return choice(bag)()

While Bastet and Bust Head share the same core idea, which is to create a really difficult game of Tetris, their methods of achievement differ. Hence, the algorithm used here is named differently, but phonetically similar in order to keep the roots of the idea in mind.

I hope this helped a bit in understanding that randomness can be achieved in different ways and how the choosing block algorithm in Tetris can be manipulated.  This helps then in understanding the soon to come implementation description for Pytris.

Beach in Langballigau

Last week we spent some time at the Baltic Sea. There is a tragicomic story to tell about how I lost my phone and found it again in the beach two days later although the cover was done in a sandy colour. It still had 50% battery, alas I didn’t have it for the day at Legoland. Enjoy these for now.

Talk ‘Surveil and Calculate’ at XII Conference on Culture and Computer Science

In May I was at the XII Conference on Culture and Computer Science in Berlin and gave this talk when it was accepted as a contribution to the conference by a peer reviewed abstract.  That was also my first conference ever at which I was talking, so I was a little nervous. However it worked out and I have even been asked to put this online for others to share and find, which I do here happily.

Vortrag Digitale Emanzipation – 20. Mai 2014 in Ilmenau

— Disclaimer: Since the talk was requested in German and my slides are also all German, I omitt a translation as long as no one is asking for it —

Letzten Dienstag hat mich die Initiative Solidarische Welt Ilmenau (ISWI e.V.) zu einem Vortrag zu ‘Datenschutz und Bürgerrechte’ eingeladen.  Der Titel war vorgegeben.  Wir ihr an den Folien sehen könnt, bin ich eher der Meinung, dass es sich bei Datenschutz und Privatsphäre um ein Menschenrecht handelt, nicht um ein Bürgerrecht.  Deswegen habe ich den Haupttitel auch auf ‘Digitale Emanzipation’ umgemünzt, denn insbesondere in digital kryptographischen Zusammenhängen ist genau dieses Schlagwort von Bedeutung.

Hier findet ihr die Präsentation.

Liste studentisch relevanter Anträge und Anfragen

Fraktion von BÜNDNIS 90/DIE GRÜNEN in Weimar
Legislatur 2009-2014

  • 09.09.09, DS 346/2009, Antrag: Abhängung Weimars vom Fernverkehr (Studierende nutzen häufig den Zug, um nach Hause zu fahren)
    (beschlossen; Sachstandsbericht am 16.02.2010 in schriftlicher Form an alle Stadträte)
  • 09.09.09, DS 347/2009, Anfrage zum Radweg nach Schöndorf (Studierende fahren auch oft mit dem Rad)
  • 01.09.10, DS 141/2010, Antrag: Veröffentlichung des Flächennutzungsplanes auf den Internetseiten der Stadt (für Studierende bspw. der Urbanistik als Lehrmaterial relevant)
    (in Ausschuss verwiesen und nachfolgend von der Verwaltung übernommen)

  • 01.09.10, DS 142/2010, Anfrage Praktikantinnen und Praktikanten in der Stadtverwaltung (Stadtverwaltung als potentielle Arbeitgeberin von Hochschulabsolvent*innen)

  • 17.11.10, DS 222/2010, Anfrage zu Unterhaltungskosten Schwanseebad (wird durch den Hochschulsport genutzt)

  • 17.11.10, DS 239/2010, Antrag: Abhängung Weimars vom Fernverkehr abwenden
    (in SRS 17.11.2010 von einbringender Fraktion zurückgezogen; Unterschriftenliste mit Proteserklärung gefertigt; anschließend mit Anschreiben OB an Bahn und Ministerien verschickt; Kopie der Schreiben mit der Unter-schriftenliste in alle Fächer der Stadträte am 18.11.2010)

  • 15.12.10, DS 265/2010, Freie Software in Schulen (inspiriert von studentischer Abschlussarbeit im Bereich Mediengestaltung)

  • 26.01.11, DS 015/2012, Anfrage zur Sanierung des Schwanseebades
    (in Stadtratssitzung vom 09.03.11 verschoben und dort beantwortet)
  • 12.10.11, DS 145/2011, Antrag: Übertragung von Stadtratssitzungen im Internet (Studierende können nicht immer persönlich an Stadtratssitzungen teilnehmen, auch wenn sie möchten)
    (in Ausschuss verwiesen und dort knapp angenommen, aber aufgrund der Ankündigung von entsprechenden Änderungen der ThürKO wird die Vorlage bis dahin zurückgestellt)
  • 21.12.11, DS 200/2011, Anfrage: Halt von Regionalbussen an Haltestellen im Stadtgebiet (VMT-Ticket der Studierenden)
    (verschoben in Stadtratssitzung am 25.01.2012 und dort beantwortet)
  • 25.01.12, DS 174/2011, Große Anfrage zur Wohnungspolitik der Stadt Weimar (Günstiger Wohnraum wird auch für Studierende immer knapper)
    (in Stadtratssitzung am 25.01.2012 wurde hierzu gemäß GO eine Debatte geführt)
  • 29.02.12, DS 033/2012, Anfrage: Große Anfrage zur Wohnungspolitik – nachgefragt
  • 29.02.12, DS 034/2012, Antrag: Kulturförderbericht ((fehlende) Förderung studentischer Kultur dokumentieren, um dagegen vorgehen zu können)
    (von Verwaltung übernommen)
  • 29.02.12, DS 035a/2012, Antrag: Änderungsantrag zur DS 035/2012 („Bus ins Zentrum“) (Studentisches Busticket)
    (Änderungsantrag und DS 035/2012 übernommen)
  • 28.03.12, DS 062/2012, Anfrage zur Sanierung des Schwanseebades
  • 28.03.12, DS 065/2012, Große Anfrage zur Wohnungspolitik, nachgefragt
  • 28.03.12, DS 066/2012, Anfrage Einführung der Software “Little Bird” zur besseren Koordination der Betreuungsangebote für Kinder (auch für junge, studentische Eltern ist die Jagd nach einem KiTa-Platz eine Odyssee)
  • 13.06.12, DS 091/2012, Antrag: Freifunk-Router in städtischen Gebäuden (studentische Initiative maschinenraum)
    (in Ausschuss verwiesen und dort von der Verwaltung übernommen)
  • 12.12.12, DS 217/2012, Antrag: Verbesserung des ÖPNV-Angebotes in Weimar
    (in Ausschüsse verwiesen)
  • 13.03.13, DS 037/2013, Anfrage zur Bushaltestelle am Herrenrödchen (Haltestelle am Wohnheim mit maßgeblich internationalen Studierenden wird (nicht nur in den Abendstunden) häufig ignoriert)
  • 03.07.13, DS 110/2013, Antrag: Erarbeitung eines Fahrradstellplatzkonzeptes für Weimar
    (in Ausschuss verwiesen und in diesem sowie in der Stadtratssitzung am 18.09.13 abgelehnt)
  • 03.07.13, DS 112/2013, Anfrage zum Fahrradweg nach Taubach
    (in Stadtratssitzung am 18.09.13 verschoben und dann schriftlich beantwortet)
  • 16.10.13, DS 190/2013, gemeinsame Anfrage mit der CDU: Papierloser Stadtrat (zukünftige (auch studentische) Stadträte sollen die Möglichkeit bekommen, zwischen digitaler und physischer Distribution der Unterlagen zu wählen)
  • 16.10.13, DS 208/2013, Antrag: Einbürgerungen aktiv befördern (Integration internationaler Studierender)
    (kein Befassungsrecht)
  • 29.01.14, DS 019/2014, Anfrage: Veröffentlichung von Bebauungsplänen im Internet (Lehrmaterial insbesondere Fakultäten A+U sowie B)
  • 09.04.14, DS 089/2014, Anfrage: Nutzung des Areals der Jugendarrestanstalt an der Thälmannstraße (kreative Nutzung auch mit studentischem Wohnen denkbar)
  • 09.04.14, DS 091/2014, Anfrage: Papierloser Stadtrat
  • 09.04.14, DS 092/2014, Antrag: Prüfung zur Umsetzung eines Modellprojektes für Krankenversicherten-Chipkarten zur medizinischen Versorgung von Asylbewerber_innen (studentische Initiative für Flüchtlinge)

Zusätzlich: Zu den Beratungen zum Studierendenbeirat hat nur unsere studentische Vertreterin darauf aufmerksam gemacht, dass eine Legislatur von zwei Jahren aus studentischer Sicht schwer zu verwirklichen sein wird.  Dies stellt sich jetzt als wahr heraus.

Flower Power

For campaigning in the Weimar municipal elections following the success of the frog in the mayor elections campaign, we decided to have a pin again. Due to my currently limited time budget I couldn’t crochet something, but rather discovered felting. Now green candidates have a sunflower on their jacket (or wherever they pinned it). After the election (May 25th, incidentally also European elections!) I will publish the pattern here.

Sunflower Bed

Wildpark Ortenburg

There is a nature park in Ortenburg, which is much more fun than any zoo I’ve been to lately.   It is located in lower Bavaria and you should bring about 2 hours of time in order to walk through the hills pleasantly. These photos are mostly for my brother to remind him of the fun, but you might enjoy them as well.

Saizou – the Piggy – Pattern!

A few months ago I had a request for a piggy that should also look a certain way – specifically, this way:

Saizou the pig

Saizou – angry

Initially, I thought I’d work my way through some pig pattern, but then I modified it so heavily, that the new pattern calls for publication.

wool and needle

some tools

I used bulky yarn (GGH Camello in pink (3 skeins) and dark purple (1 skein)) and a 6mm crochet needle.  You will also need some white, some pink and some dark pink felt, some thicker scrap wool in black and an aluminum string.  Little tools you might want to have handy are scissors, glue and a tapestry needle.  Additionally you will need lots and lots of polyfill.  The pig will be so large, you can use it as a cushion.  A combination of thinner yarns and smaller needles is of course possible to resize the piggy.

Abbreviations:

sc – single crochet

incr – sc2 in one

tbl – through back loop

decr – sc1 in two

Pattern:

Pre-Round: make a ring (magic ring or chain 2 and stitch in second from hook)

Round 1: 6 single crochet in ring (6)

Round 2: incr around (12)

Round 3: (incr, sc1) around (18)

Round 4: (incr, sc2) around (24)

Round 5: (incr, sc3) around (30)

Round 6: sc tbl around (30)

Round 7+8: sc around (30)

Round 9: (incr, sc9) around (33)

Round 10: (incr, sc10) around (36)

Round11: (incr, sc5) around (42)

Round 12: (incr, sc2) around (56)

Round 13: (incr, sc7) around (63)

Round 14: (incr, sc8) around (70)

Continue increasing in the fashion of the last two rows until you have a total of 98 stitches.

The piece should look like this:

Work in Progress - Snout and Face

Snout and Face

Then sc around for about 5 rows.

Next four rounds:  Round 1: (decr, sc12) around (91); Round 2-4: sc around

Next three rounds: Round 1: (decr, sc11) around (84); Round 2-3: sc around

Next two rounds: Round 1: (decr, sc10) around (77); Round 2: sc around

Decrease in that fashion five more times (42).

Stuffed body with tail

Stuffed body with tail

During the following rows you should continue decreasing like you did before in every row and stuff continually, so that you have a fit tight enough for shaping but soft enough for cuddling.  When you are down to six stitches per row, crochet 20 times around in sc. Fasten of.  Insert the aluminum tube into the tail and twirl it.

Twirled tail

Twirled tail

Feet (make 4):

With dark purple yarn create a ring (like before).

Round 1: sc6 in ring

Round 2: (incr, sc2) around (8)

Round 3: (incr, sc3) around (10)

Round 4: (incr, sc4) around (12)

switch to pink yarn

Round 5: (incr, sc1) around (24)

Round 6-8: sc around (24)

Fasten off and stuff lightly.

Horns (make 2):

With dark purple yarn create a ring (like before).

Round 1: sc6 in ring

Round 2: (incr, sc2) around (8)

Round 3: sc around (8)

Round 4: (incr, sc3) around (10)

Round 5: sc around (10)

Round 6: (incr, sc4) around (12)

Round 7-9: sc around (12)

Stuff horns and fasten off.

Sew feet/hoofs and horns on the piggy.

Cut out the felt and glue white part of eyes and snout on the piggy.  With black yarn, use tapestry needle to accentuate piggy.

Done!

done piggy

done piggy

1 2 3 5