Calculating holes on a Tetris grid quickly

Question

I have created a Tetris AI which can play Tetris on its own given a set of rules. It places the next piece in every possible way on the board, and calculates which position that gives the fewest "holes" on the playfield.

The playfield is represented by an int[] array, where every bit represents a position in a row, and every int represents a row.

A playfield can look like this:

(0000000000000000000000)1111111111
(0000000000000000000000)1111111111
(0000000000000000000000)1111111111
(0000000000000000000000)1111111111
(0000000000000000000000)0111111111
(0000000000000000000000)0111111111
(0000000000000000000000)0111001111
(0000000000000000000000)0111100111

the zeroes in parentheses are not part of the playfield, and are not used. 1 represents an empty square, 0 represents a filled one. So the example above would be a long piece on the left, and a squiggly piece in the middle.

However, to determine if this playfield is "desirable", I calculate the number of holes on the grid. A hole is defined as follows:

• An empty square under the topmost filled square in a column.
• An empty square in a column next to a column where we have found a filled square, given that the empty square in question is under the topmost filled square in the other column.

I guess it's hard to explain, but I've marked all "holes" here:

(0000000000000000000000)1111111111
(0000000000000000000000)1111111111
(0000000000000000000000)1111111111
(0000000000000000000000)1111111111
(0000000000000000000000)0X11111111
(0000000000000000000000)0X11111111
(0000000000000000000000)0X1X00X111
(0000000000000000000000)0X11D00X11

Every hole is marked with an "X", except for one in the bottom row, since that one is counted twice, because it is under a filled square, and next to a square that is under a filled square.

Right now this is the optimal solution that I've found. It is a combination of JS1's and Brythan's solutions:

private static int EMPTY_ROW = (1<<xsize)-1;

public int calcHolesConverted(int[] grid) {
    //int gridMask      = (1 << xsize) - 1;
    int underMask     = 0;
    int lneighborMask = 0;
    int rneighborMask = 0;
    int foundHoles    = 0;
    int minY = 0;

    while ( minY < ysize && grid[minY] == EMPTY_ROW ) {
        minY++;
    }

    for (int y = minY; y < ysize; y++) {
        int line   = grid[y];
        int filled = ~line & EMPTY_ROW;

        underMask     |= filled;
        lneighborMask |= (filled << 1);
        rneighborMask |= (filled >> 1);

        foundHoles += setOnes[underMask & line];
        foundHoles += setOnes[lneighborMask & line];
        foundHoles += setOnes[rneighborMask & line];
    }
    return foundHoles;
}

This results in over 10000 Tetris pieces per second, compared to the 4800 that I could accomplish before I asked the question.

Answer 1

You can do this faster by doing the whole row at once instead of one bit at a time. All you need to do is to keep a mask of bits that correspond to your firstFound booleans. To match the OP's counting scheme (which can triply count a hole), I keep three masks: an underMask, an lNeighborMask, and an rNeighborMask. underMask is used to count holes underneath the topmost filled square in a column. lNeighborMask is used to count holes to the left of the column. rNeighborMask is used to count holes to the right of the column. (I edited my original answer to account for the triple counting).

The Code

public int calcHolesConverted(int[] grid)
{
    int gridMask      = (1 << xsize) - 1;
    int underMask     = 0;
    int lNeighborMask = 0;
    int rNeighborMask = 0;
    int foundHoles    = 0;

    for (int y = 0; y < ysize; y++) {
        int line   = grid[y];
        int filled = ~line & gridMask;

        underMask     |= filled;
        lNeighborMask |= (filled << 1);
        rNeighborMask |= (filled >> 1);

        foundHoles += setOnes1024[underMask & line] +
                      setOnes1024[lNeighborMask & line] +
                      setOnes1024[rNeighborMask & line];
    }
    return foundHoles;
}

In this code, setOnes1024 is an array of size 1024 which contains the number of 1 bits in the corresponding index. It is analagous to your setOnes array. Also, this code assumes that the bits to the left of the leftmost column will all be 0. If they are not, then you will need to adjust lneighborMask to not contain bits outside the valid columns.

The Timing Test

I ran this timing test by converting both functions to C and running them on the same randomized grid (20000000 iterations each function).

OP's function    : 8.2 seconds
Modified function: 1.4 seconds

Answer 2

• An empty square under the topmost filled square in a column.
• An empty square in a column next to a column where we have found a filled square, given that the empty square in question is under the topmost filled square in the other column.

Note that both of these are limited to squares at or below the top row with a filled square. So you don't have to fully check every row.

Assuming rows are numbered from top to bottom rather than bottom to top:

final private static int EMPTY_ROW = 0x3FF;

public int calcHolesConverted(int[] grid, int minY) {
    int foundHoles = 0;

    while ( grid[minY] == EMPTY_ROW && minY < ysize ) {
        minY++;
    }

    int x = xsize-1;
    while ( x >= 0 ) {
        int bitMask = 1 << x;
        for ( int y = minY; y < ysize; y++ ) {
            if (grid[y] & bitMask == 0) {
                break;
            }
        }

        x--;

        for ( ; y < ysize; y++ ) {
            foundHoles += setOnes[(grid[y] >> x) & 7];
        }
    }

    return foundHoles;
}

Note that you can determine the maximum height for any piece by a simple lookup. Then you just need to know the current depth of the board and subtract the piece height from that. This happens outside the function and you pass this value into the function as minY. This saves the first few iterations of checking the board. I'd write this code, but there is insufficient context in the question.

The function itself then checks the current board arrangement and eliminates the empty rows at the top by comparing the value of an empty row with the current row. It updates minY until a non-empty row is found. I include a check of minY < ysize, but you can skip this if there's always at least one non-empty row in grid.

I removed the firstFound boolean in favor of two loops. This saves checking for the firstFound condition once it has been found. And it saves checking firstFound at all in the second loop.

I moved the x-- so as to save the unnecessary x-1. Note that the compiler may or may not have optimized that out. Once I did that, it seemed unnecessary to continue using a for loop, so I switched to the while. That's entirely stylistic though.

Instead of shifting grid[y] on every iteration, I shift 1 once before starting. There may be a way to do this with setOnes as well, but it looks more complicated. It might use more memory but save time. You don't include the definition of setOnes, so I won't try modifying the code for this purpose.