Cyborg Earthworm»Blog
Anton Swifton
I'm going to stop working on this project for an unclear amount of time. The main reason is that the project is too large given that I'm trying to get a PhD and do a bunch of other things at the same time. Another reason is that there are legal issues that I don't want to deal with.

If anyone was planning to play when the game is finished, I apologize. However, there will be similar games, because I'm interested in the idea of giving the player an intuitive graphical interface for making a bot playing a game (and exploring this idea doesn't have to involve Tetris).

In the near future I'm planning to go back to making games that run in a browser, and the main motivation for my technical decisions will be the desire to try my ideas as fast as possible and let people play my games with the minimal effort. Thus, the only handmade thing about my programming will be the fact that I like doing things from scratch. I might look into webassembly at some point, though, so if people are interested in reading about my experiments with it, I will submit a project to the network.


Anton Swifton
After making a pretty good progress in May, I thought that I should get more serious about this project. This would involve:

1. Sorting out legal issues. The Tetris Company has been suing people for copyright infringement very actively, and I have to find out a way to avoid a lawsuit.
2. Putting the prototype online and posting a note to a couple of appropriate subreddits and maybe Hacker News to find out whether people find this game interesting (I still don't know whether they will, frankly).
3. Thinking about doing some PR and eventually making the PC version commercial, if there is enough interest. Ideally, getting a licence from TTC to be able to use the word "Tetris" in the description would increase discoverability greatly (I think).

Basically, TTC copyrighted everything they could and a couple of things they couldn't. "Tetriminoes" is a trademark, which is ok, I guess, since they are not tetrominoes. Shapes of blocks are copyrighted, which is pretty confusing: does it mean that the square is copyrighted? Or does it mean that the shapes of the tetrominoes are copyrighted? Both options are pretty surreal, so I hope it only means that the sprites are copyrighted, but with TTC it could be anything. In 2012 they won a lawsuit where they claimed that an author of a clone infringed on their copyright by copying the playfield dimensions (10x20).

I asked New Media Rights for an advice on this issue. They were very vague and didn't really say anything that I didn't know (other that they would have to do a formal review before they can say anything specific). Asking for a formal review would be probably helpful, but even if I don't infringe on anything, it doesn't mean TTC can't sue me, and if they do, I won't have any money to hire a lawyer.

I also asked TTC for a permission to use the word "Tetris" in the description, but they said that they aren't interested in exploring this possibility.

All of this makes me think about how to proceed with the project. I can use the name "The Game of Falling Tetrominoes" instead of "Tetris" with the (hopefully easy to remember) acronym GoFT, but this won't solve the problem of having a violently litigious company hovering around. I could hope that they will never bother to sue me because my game is not a clone or because I'm too small for them, but trying to become an independent game designer is difficult enough and I don't want to have legal issues at the very beginning of it. Frankly speaking, I'm thinking about deferring the project until the day when I have enough resources to fight off lawsuits. I have a lot of game ideas and exploring one or another doesn't make a big difference.

As usual, any advice is appreciated.
Anton Swifton
Here is how I measure the speed of my program: I run the game for 1 000 000 randomly picked tetrominoes and measure how much time it takes. In the js prototype it takes 40 seconds.

Here is what I have done in May.

1. Implemented the matching algorithm in C. Running time was 44 seconds, slightly worse than the js version. Compiling with /O2 gave a 2x speedup, bringing it down to around 23 seconds.

2. Made it possible to test a program by loading a pre-generated sequence of tetrominoes and turning on deterministic mode (it was randomized in several ways). Now the game runs identically between launches. After making a change I can make sure that the game runs the program the same way it ran it before by just comparing two files that store results of the run.

3. Improved efficiency of the matching algorithm. Instead of trying to match the pattern to every region of the field, now the game only tries to match it to the regions on the surface. Here is what I mean by that. Let's assume that a tile of the pattern is full and all tiles above it are guaranteed to be empty. Then if that pattern ever matches a region of the field, this tile will be matched to the highest full tile in one of the columns of the field.



Therefore, you can calculate the surface of the field (one tile in each column, such that all tiles above that tile are empty) and only match the surface of the pattern to the surface of the field. Yellow tiles on the following picture are the surface of the field.



I take the tiles under the intended position of the tetromino as the surface of a pattern, because the matching algorithm guarantees that all tiles above the tetromino are empty (otherwise the tetromino won't always land where the player expects it to land).



All columns that don't contain the tetromino aren't guaranteed to be empty, regardless of the structure of the pattern. Here is a simple example.



Because of that, it's impossible to apply this optimization to floorless patterns, because they don't have any surface.



The surface function sets the surface to the tiles right below the tetromino, but it also recognizes that it is outside of the pattern, and the matching algorithm uses the old way (trying to match everywhere). Nevertheless, this improvement yielded more that 2x speedup, bringing the runtime down to about 10 seconds. Floorless patterns get hit two times less frequently than floored patterns and take about twice longer (combined) to get matched. Therefore, if you rewrite the program so that it doesn't use floorless patterns, I expect it to give another 2x speedup (although, the program will become worse).

4. Changed the format of data. The field was previously a 2D array of integers, where 0 means that the tile is empty, and numbers 1 - 8 mean different colors. Now it is a 1D array of uint32, where each number is a row, and each bit of that number is a tile in that row. 0 means empty, 1 means full, no colors.



With this format, matching two rows means taking a bitwise "xor" of them. If the result is 0, then the rows are the same. There is a little caveat with patterns, though. Patterns contain tiles that are full, tiles that are empty and tiles that can be either (in the js prototype they are marked by question marks). The pattern will match a region regardless of whether the corresponding tiles of the field are empty.



To make the new pattern representation reflect that fact, I keep two sets of tiles for each pattern: mask tiles and data tiles. Mask tiles are zero if the original tile is a question mark and one otherwise. Data tiles are one if the original tile is full and zero otherwise. For the following pattern



the data tiles will be



and the mask tiles will be



Matching a row of the field and a row of the pattern, then, consists of two steps. First, taking a bitwise "and" of the field row and the mask row. Second, taking a bitwise "xor" of the result of the first step and the data row. If the result of the second step is zero, then the rows match. This brought the runtime down to exactly 2 seconds (before this step I used a regular stopwatch to measure the time, so the result wasn't very precise).

5. Measured how much time every part of the algorithm takes. As expected, out of these 2 seconds looking for matches takes 1.8 seconds, 1.7 of which is spent in the function that matches a pattern to a specific region of the field.

6. Converted the matching function to SIMD. Now that the function operates on rows of the field and rows of the pattern, I can match 4 rows at once. This brought the runtime down to 1670 ms, which is almost 24x speedup compared to the prototype.

Here is what I haven't done.

1. I haven't tried to make the computation parallel. Since most of the time you need to try several patterns before you find one that matches anything, you can just as well try to match several patterns in parallel. However, I don't really know much about parallel computations, so I will explore this direction later.

2. I haven't optimized the function that calculates the surface of the field. It takes 120 ms per million tetrominoes, so it might help a little bit.

70 hours, 1500 lines. The core game mechanic is finished, the plan for June is to start implementing the UI.
Anton Swifton
The semester is over, though, so May should be more fertile.
Anton Swifton
When you test your pattern-based program, Tile Machine simulates the Game of Falling Tetrominoes and uses your program to decide where exactly each tetromino will fall. This process consists of the following steps.

1. Pick a tetromino randomly.
2. Consider the patterns that handle this tetromino. Each pattern in the game can handle only one tetromino (*1). I use the word "column" to denote the set of patterns that handle the same tetromino (*2).
3. Patterns in any column are ordered. Take the first pattern.
4. Run the matching algorithm.
5. If the pattern matches a region of the playing field, put the tetromino into the place specified by this pattern and let it fall according to the rules of the Game of Falling Tetrominoes.
6. If the pattern doesn't match any region, take the next pattern and go to step 4.


The matching algorithm consists of four steps.
1. Find all regions that match the pattern (*3).
2. Remove all regions that are obscured by tiles above them.
3. If there are more than one region left, pick the lowest regions.
4. If there are more than one of them, pick one randomly.

It is important which region you pick, because the desired position of a tetromino is specified in the local coordinate system of the pattern, so where the tetromino ends up being placed depends on where on the field the region is.

To assess the quality of a player's program I use the average game length. The length of an individual game is the number of lines completed (and thus removed) during that game. Any game starts with an empty playing field and ends when there is no place for new tetrominoes. I run the game many times and average lengths of all games in that run. The quality of the program is the limit of that average when the number of games goes to infinity (*4). We can't calculate the limit precisely, but we can approximate it by running the game many times. The more games are run, the more precise the estimate is. Usually I drop 50 000 tetrominoes, however many games this constitutes. On my desktop this takes a couple of seconds.

The problem is, when the average game length is 150, this is already not enough, because, empirically, the result can differ between runs by 10, which makes the measurements useless. Therefore, I need to either invent different ways to test the program (which I will definitely do later just because it is an interesting direction to explore), or to increase the number of tetrominoes in one run. For now, I will go with the latter. And since nobody wants to wait for half a minute to get the stats, the game needs to run faster.

Generally, this month hasn't been particularly productive, I got swamped at school, and the next month is likely to be unproductive as well, because the semester is not over. However, I did a simple profiling of the prototype.

I drop 10 000 tetrominoes and measure how long it takes to process them. Looking for a match currently takes 115 ms, and removing matches takes 86 ms. Dropping the tetromino takes the currently negligible 10 ms.

The most interesting part is that a trivial change from

1
2
for (var i = command.walls?0:1; i < fieldWid - command.patternWid + command.walls?1:0; i++) {
    for (var j = 0; j < fieldHeit + 1 -command.patternHeit + 1; j++) { 


to

1
2
3
4
var upperLimitI = fieldWid - command.patternWid + command.walls?1:0;
var upperLimitJ = fieldHeit + 1 -command.patternHeit + 1;
for (var i = command.walls?0:1; i < upperLimitI; i++) {
    for (var j = 0; j < upperLimitJ; j++) { 


made a huge difference. It reduced the total matching time from 380 ms to 246 ms. Apparently, a lot of time was spent just calculating these upper limits multiple times. This made me think that I could actually optimize the prototype before rewriting it in C to be able to distinguish between improving efficiency, which, I think, can be done in javascript, and improving performance.

There are two more things that I plan to do. I recently realized that I shouldn't make people download my prototype that runs in a browser from github, when I can just put it online. Also, I'm trying to figure out a way to explain how to play the game without making people read the tutorial.


*1 This is the decision I made at the very beginning after mistakenly trying to make each pattern specify the desired position for every tetromino.
*2 This is not necessarily the word that I want to use in the future, but for now I don't have a better alternative.
*3 This is currently done by trying to match the pattern to every possible region of the same size. I will optimize it later.
*4 This limit, according to my intuition, always exists, although I didn't try to prove its existence.