Calculating holes on a Tetris grid quickly

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> 1);

foundHoles

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 > 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


StackExchange Code Review Q#80462, answer score: 6