1010! Analysis

1010! is a simple puzzle game by Gram Games, originating from Turkey in August 2014. It feels like Tetris but without the time constraint and with more choices. It is available on Android and iOS.

Advices are available online on how to get a high score. I’m more interested in devising a decision strategy, automate it efficiently and optimize it through simulations… which also results in advices on how to get a high score, but more substanciated.

Teaser: below, learn how to get a score over 1 million every 8 games…

Game Presentation

1010! consists of a 10 by 10 grid on which variously-shaped pieces can be placed. When a row or column is full it is removed from the grid. At each round, 3 pieces are presented which must be fit on the grid, in any order. The game stops when no more pieces can be placed.

Points are attributed when putting a piece (the number of cells of the piece) and when rows or columns are removed (if \(r\) rows or columns are removed, add \(5 r (r+1)\) to the score).

There are 19 possible pieces ranging from 1 to 9 cells, with different drawing probabilities. There is talk about a special 5x5 square piece but I have never encountered it. Pieces are given a one character name for convenience:

  .: ■      -: ■ ■    i: ■        _: ■ ■ ■    I: ■      r: ■ ■    l: ■
                         ■                       ■         ■         ■ ■
  j:   ■    t: ■ ■                 O: ■ ■ ■      ■
     ■ ■         ■    h: ■ ■ ■ ■      ■ ■ ■          H: ■ ■ ■ ■ ■   V: ■
                                      ■ ■ ■   v: ■                     ■
  J:     ■   T: ■ ■ ■    R: ■ ■ ■                ■      L: ■           ■
         ■          ■       ■      o: ■ ■        ■         ■           ■
     ■ ■ ■          ■       ■         ■ ■        ■         ■ ■ ■       ■

The relative weighted drawing probabilities, as infered from manually collected statistics, seems to be:

W	Pieces
1	`R T J L`
2	`. r t j l h v H V O`
3	`i - I _`
6	`o`

The total weight is 42. Piece o is drawn \(6/42 = 1/7\). There seems to be a bias on j which does not come out as often as it should in my iOS version. Also it would be nicer if O had the lowest probability.

Given these drawing probabilities, the 3 pieces on each round weight on average 11 cells:

\[ 3 . (1 . 5 . 4 + 2 . (1 + 3 . 4 + 4 . 2 + 5 . 2 + 9) + 3 . (2 . 2 + 3 . 2) + 6 . 4) / 42 = 11 \]

The probability of the OOO event is \((2/42)^3\), i.e. 1 every 9,261 rounds.

Game Strategy

The metrics I’m going to optimize is the number of rounds successfully completed, without taking into account the actual score. They are quite correlated anyway, as for steady-state the player must put and remove 11 cells per round on average, getting at least 22 points per round. Moreover, if this strategy succeeds in avoiding the end of the game, it should result in higher scores as well. However, it will not seek multi row/column removals to get bonus points at the price of taking any risks.

Decision Criteria

I’ve considered 5 criteria:

Maximize free space in the grid
The rational is that the more free space the easier to fit the next pieces. However keeping only this criteria is highly ineffective because it does not consider the geometry of the grid being filled. The next four criteria aim at taking this into account.
Large fake piece can be placed
Try to keep space for an artificial 5x5 square piece used as a proxy for the various large real pieces.
Large real pieces can be placed
Same as above for 3 real large pieces: HOV.
Alignment maximization
The idea is to try to have filled cells in the grid aligned as much as possible so that by filling a few holes a row or column can be removed. A measure of alignments is to count for every row and column the number of filled cells, then to sum these numbers squared, so as to emphasize the longest alignments, and finally to normalize.
Surface minimization
The idea is to favor compact lumps of cells, preferably accumulating in corners and on borders, so as to let as much space elsewhere as possible, where large pieces may be put if necessary. A measure of compaction is the surface, which can be derived by counting the number of neighboring empty and filled cells, and then by normalizing. For instance, a lone cell on the inside has surface 4, but the same in a corner counts 2.

On top of this criteria it is possible to add a low priority preference to better scoring by adding the expected score increment with a very light weight, so that everything else being equal, a better scoring option is chosen. The effect on the score seems to be between 1 and 2 percent.

Complexity

When analyzing complexity, \(n = 10\) is the grid size, \(g = 3\) is the number of pieces at each round, \(p = 19\) is the number of distinct pieces.

The number of possible grid layouts is about \(2^{n^2}\). For each layout the number of unordered combination of pieces is about \(p^g/g!\), minus a few combinations with repeated pieces. In order to evaluate the best choices for a round, one must first compute the possible final grid layout from the starting layout and the given pieces:

consider every piece order: \(g! = 6\) (or less if a piece is duplicated in the round)
consider every possible position of the first piece: \(n^2\)
look for fulfilled rows and columns: \(2n \, n\)
consider every possible position of the second piece: \(n^2\)
look for fulfilled rows and columns: \(2n \, n\)
consider every possible position of the third piece: \(n^2\)
look for fulfilled rows and columns: \(2n \, n\)

Then on each final grid, evaluate the different criteria, which may involve:

count free cells: \(n^2\)
check whether a large fake piece fits: worst case \(n^2\)
check whether 3 large real pieces fit: worst case \(3 n^2\)
count aligned cells on each row and column: \(2n \, n\)
count distinct adjacent empty/filled cells: \(n^2\)

The overall worst-case complexity is in \(g! \left(n^2\right)^g n^2\) per round, and this is reached sometimes when the grid is quite empty. However on average number of evaluations performed for each round is around 550,000, instead of \(g! \left(n^2 \right)^g = 6,000,000\). Taking into account the next round would append a \(p^g \left(n^2 \right)^g n^2\) factor, quite unpractical.

Simulations are going to help find which combination of these criteria is the most effective.

Efficient Implementation

As the complexity is quite bad, the simulation is written in low-level C based on bit field tricks for efficiency, and is parallelized with threads.

Bit fields

In order to reduce the practical complexity, bit fields can be used to represent the grid, so that some \(n\) or even \(n^2\) operators can be performed with single bit instructions. Note that as there does not seem to be a standard 128-bit integer type, I really used two 64-bit integers. Some of the above operations may be implemented very efficiently with bit fields:

move a piece on the grid:

// r rows & c columns
piece >>> (10*r+c)

check that a piece fits in the grid:

// intersection is empty
(grid & piece) == 0

place a piece on the grid:

// just keep both
grid | piece

check full row or column in the grid:

// to be evaluated for all 2n alignments
(grid & alignment) == alignment

empty some cells from the grid:

// keep every other
grid & ~toempty

count bits: many algorithms (lookup table, Hamming weight) and a nice builtin implemented as one POPCNT instruction on some processors.

// call compiler builtin
__builtin_popcount(grid)

count aligned cells in a row or column:

// to be evaluated for all 2n alignments
count(grid & alignment)

compute surface requires to deal correctly with borders:

// LEFT is first column, TOP is first row
// shift & xor to detect differing neighbors
count((((grid >> 1) & ~LEFT) | (grid & LEFT)) ^ grid) +
count((((grid >> 10) & ~TOP) | (grid & TOP)) ^ grid))

In order to take best advantage of these tricks, special compiler options for the target hardware must be selected.

Parallelization

Exploring all orders and placements of three pieces at a round is highly parallel: all combinations must be checked and evaluated if legal.

However the operations are not very regular, as for one test the placement may fail at one level while for another it may fail at another level, so there is some irregularity which does not make it very suitable to GPGPU’s data-parallel SIMD model.

The implementation parallelize the exploration with the pthread library, first at the order level (6 combinations) and then the placement of the first piece can be further split. Each independent recursion evaluates its best ply and the final aggregation between threads is performed at the end, so as to avoid any interference between threads. Note that this parallelization is not very effective because each thread has not that much to do and the cost of creating and joining the threads must be amortized.

Experimental Results

Given these optimizations and enough cores, a simulation may proceed at a pace of more than 50 rounds per second. Different combined criteria have been evaluated on a set of 500 distinct random seeds for the number generator used to choose the pieces at each round with the weighted probabilities outlined above.

Each combined criteria is presented below by the weight given to each five criteria under the strategy column. Then statistics about the number of rounds are displayed, and finally the percentage of games which achieved a score over 1 million on those seeds.

strategy	average	std dev	min	Q1	median	Q3	max	score>1M
10025	22,226.6	23,720.7	49	5,679	15,139	30,126	155,059	13.8%
10013	21,082.5	20,707.2	43	6,390	14,653	28,491	145,983	12.2%
10012	20,670.5	19,902.8	49	5,568	13,905	29,676	117,613	12.8%
10023	20,235.3	20,243.1	64	5,396	13,788	28,483	118,320	11.2%
10001	17,890.2	17,972.0	43	4,867	12,744	24,381	97,862	9.2%
00001	492.1	499.3	6	138	315	653	2,923	0.0%
10000	62.4	42.2	0	34	51	77	340	0.0%
00100	21.4	9.7	6	14	20	26	61	0.0%
00000	17.9	7.0	5	13	17	22	52	0.0%
00010	16.0	8.1	4	10	14	19	66	0.0%

The figures are pretty consistent, and show that the 10025 criteria is the best among those tested. However, the first 4 best strategies do not pass a χ² test, that is they cannot be statistically distinguished. Further testing with 10025 suggest that they are indeed equivalent and that the long term average is probably rather around 21,000. The p-value on 500 seeds with the fifth (10001) is 2.26%, which is not so great a distinction. However further testing showed that the difference is indeed significant, with a p-value under 1/10,000 for a few thousand tests.

Overall, the best strategy consist in considering the number of free cells (between 0 and 100), and then to distinguish equal results with the best lumpiest group of cells which display the more alignments, somehow.

Given the nature of a (long) run, which iterates around a steady-state (at each round on average as many cells are placed as are removed through full alignments), one would expect a geometrical/exponential distribution of the number of rounds, where the iterations can stop with a constant (although pretty small) probability all along the run. Indeed, the above figures are consistent with this view: standard deviation is roughly equal to mean, median over mean is about \(\ln 2\)…

Conclusion

The best run on the tests presented above achieved a 3,548,228 score in 155,059 rounds (3 pieces placed per round) for random seed 4128567858 and weights 10025. The average number of filled cells is quite low 18.66 (standard deviation 6.24). The run came 11 times back to an empty grid.

Further random tests yielded a 4,851,264 score in 213,214 rounds for random seed 323067730 and weights 10025.

The overall best run seen during the various tests with a slightly altered decision function with weights 10025 but also with a small contribution for maximizing the score gave a 7,674,915 score in 332,674 rounds on a randomly generated sequence.

My personnal best by hand is 15,676 in probaby around 700 rounds… which took quite a long time.

If anyone wishes to tinker with the simulation, feel free to use the code available on GitHub (license is GPLv3+). The documentation is the source code. The program can be used as an adviser by giving the pieces submitted, but playing like that takes a long time, and it is cheating, so what’s the point?