#StackBounty: #code-challenge #ai-player #tetris Tetris strategy

Bounty: 500

Your task is to implement a Tetris strategy balanced in terms of score vs code size.

In this version of the game tetrominoes are rotated and dropped from above into a grid of 20 rows and 10 columns. While falling, they cannot be rotated or moved horizontally. As usual, a dropped piece stops when it reaches the bottom of the grid or when further downwards motion would cause collision with an already occupied square.

When n horizontal lines get filled completely, they collapse simultaneously, the grid is replenished with n empty lines at the top, and the score is incremented by 2n-1 points. For n=1,2,3,4 that’s 1,3,7,15 points respectively. After the lines disappear, some blocks may remain floating in the air (there’s no “gravity chain reaction“).

When no room is available for the current piece to appear where desired, the grid is cleared, the current piece ignored, and the game continues with the next piece as current. There’s no penalty for that.

You should read a stream of piece types and decide how to rotate them and where to drop them. Look-ahead for the next piece (just one) is allowed: you can look at piece i+1 before responding to i, but you must have decided the fate of i before looking at i+2. No look-ahead is available beyond the last piece of the input.

Tetromino types and their rotations are encoded per the following table:

        type 0    1    2    3    4    5    6
             O    I    Z    J    L    S    T
            ┌────┬────┬────┬────┬────┬────┬────┐
 rotation 0 │##  │#   │##  │ #  │#   │ ## │### │
            │##  │#   │ ## │ #  │#   │##  │ #  │
            │    │#   │    │##  │##  │    │    │
            │    │#   │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          1 │##  │####│ #  │### │  # │#   │#   │
            │##  │    │##  │  # │### │##  │##  │
            │    │    │#   │    │    │ #  │#   │
            │    │    │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          2 │##  │#   │##  │##  │##  │ ## │ #  │
            │##  │#   │ ## │#   │ #  │##  │### │
            │    │#   │    │#   │ #  │    │    │
            │    │#   │    │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┤
          3 │##  │####│ #  │#   │### │#   │ #  │
            │##  │    │##  │### │#   │##  │##  │
            │    │    │#   │    │    │ #  │ #  │
            │    │    │    │    │    │    │    │
            └────┴────┴────┴────┴────┴────┴────┘

Input is binary – a sequence of bytes whose remainders when divided by 7 should be interpreted as the OIZJLST tetrominoes. They will occur with roughly the same probability (except that the first few types may appear slightly more often due to 256 not being a multiple of 7, but that should be negligible). Input can be from stdin or from a file named “i” or passed as an argument. You can read all of the input at once, provided you make sure to abide by the look-ahead restriction.

Output is binary too – a sequence of bytes of the same length as the input. It can be stdout or a file named “o” or the result from a function. Each byte encodes r*16 + x, where r is the desired rotation and x is the 0-based index of the column where the leftmost square of the rotated tetromino should go. Those r and x must be valid, i.e. 0 ≤ r ≤ 3 and 0 ≤ x ≤ 10-w, where w is the width of the corresponding piece.

You program must be deterministic – given the same input, it has to produce exactly the same output. Using a PRNG is ok as long as it’s const-seeded.

The total score is the score from the game minus the size of your code in bytes. Please use the following file (64kiB of pseudo-random noise) as input:
https://gist.github.com/ngn/857bf2c99bfafc649b8eaa1e489e75e4/raw/880f29bd790638aa17f51229c105e726bce60235/i

The following python2/python3 script reads files “i” and “o” from the current directory, replays the game and prints the score (please remember to subtract your code size from the score):

a = [0] * 23 # grid (1square=1bit, 1row=1int, LSB is left, 3 empty rows on top)
#      O     I         Z       J       L       S       T        tetrominoes
t = [[[3,3],[1,1,1,1],[3,6],  [2,2,3],[1,1,3],[6,3],  [7,2]  ],
     [[3,3],[15],     [2,3,1],[7,4],  [4,7],  [1,3,2],[1,3,1]],
     [[3,3],[1,1,1,1],[3,6],  [3,1,1],[3,2,2],[6,3],  [2,7]  ],
     [[3,3],[15],     [2,3,1],[1,7],  [7,1],  [1,3,2],[2,3,2]]]
tw = [[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2]] # widths
th = [[2,4,2,3,3,2,2],[2,1,3,2,2,3,3],[2,4,2,3,3,2,2],[2,1,3,2,2,3,3]] # heights
score = 0
for p, rx in zip(bytearray(open('i', 'rb').read()),
                 bytearray(open('o', 'rb').read())):
    p %= 7; r = rx >> 4; x = rx & 15  # p:piece type, r:rotation, x:offset
    b = [u << x for u in t[r][p]]     # as a bit-matrix (list of ints)
    bw = tw[r][p]; bh = th[r][p]      # width and height
    y = 0                             # drop it
    while y <= 23 - bh and all((a[y + i] & b[i]) == 0 for i in range(bh)):
        y += 1
    y -= 1
    if y < 3:                         # no room?
        a = [0] * len(a)              # clear the grid and carry on
    else:
        for i in range(bh):           # add the piece to the grid
            a[y + i] |= b[i]
        n = 0
        for i in reversed(range(bh)): # collapse full lines
            if a[y + i] == (1 << 10) - 1:
                n += 1; del a[y + i]; a = [0] + a
        score += (1 << n) - 1
print(score)

So does the following much faster C program but it’s guaranteed to work only on Linux:

#include<stdio.h>
#include<fcntl.h>
#include<sys/mman.h>
#include<sys/stat.h>
#define F(i,n,b...)for(i=0;i<n;i++){b;}
typedef int I;typedef char C;
I a[23],t[]={
51,4369,99,802,785,54,39,51,15,306,71,116,561,305,
51,4369,99,275,547,54,114,51,15,306,113,23,561,562};
C*th="2423322213223324233222132233";
I main(){
 struct stat h;stat("i",&h);I i,j,k,l=h.st_size,z=0;
 C*mi=mmap(0,l,1,1,open("i",0,0),0),*mo=mmap(0,l,1,1,open("o",0,0),0);
 F(k,l,
  I p=(mi[k]&255)%7,r=3&mo[k]>>4,q=r*7+p,x=mo[k]&15,y=0,h=th[q]-'0',b[4];
  F(i,h,b[i]=(t[q]>>(4*i)&15)<<x)
  while(y<=23-h){I u=0;F(i,h,u|=a[y+i]&b[i])if(u)break;y++;}
  if(--y<3){F(i,23,a[i]=0)continue;}
  F(i,h,a[y+i]|=b[i])
  I n=0;F(i,23,n+=a[i]==1023)
  if(n){j=23;F(i,20,a[j]=a[22-i];j-=a[j]!=1023)F(i,j,a[i]=0);z+=(1<<n)-1;})
 printf("%dn",z);return 0;}

The highest total score wins. Standard loopholes are forbidden.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!