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 variouslyshaped 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:
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 steadystate 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 worstcase 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 lowlevel 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 128bit integer type, I really used two 64bit integers. Some of the above operations may be implemented very efficiently with bit fields:
 move a piece on the grid:
 check that a piece fits in the grid:
 place a piece on the grid:
 check full row or column in the grid:
 empty some cells from the grid:
 count bits: many algorithms (lookup table, Hamming weight) and a nice builtin
implemented as one
POPCNT
instruction on some processors.
 count aligned cells in a row or column:
 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 dataparallel 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 pvalue 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 pvalue 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 steadystate (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?