13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The number of set bits in a int can be calculated with Integer.bitCount() Can I ask why performance is an issue, and how you know it is this method? \$\endgroup\$ – spyr03 Feb 13 '15 at 21:19
  • \$\begingroup\$ Performance is an issue because at this point I want to optimize the program as much as possible. I can drop 4500 Tetris pieces per second as of now, and I having a bottleneck bothers me. I precalculate the bitCount values, since I only need 1024 values. Looping through every grid position, and checking every bit three times seems very time consuming, compared to my other methods. This method takes up over 50% of execution time, with my second heaviest method (which has been optimized a lot more) takes up 40%. \$\endgroup\$ – maxb Feb 13 '15 at 22:42
  • \$\begingroup\$ I'm late to the party, but @maxb, I haven't found anything on Google about your setOnes array, can you elaborate on that a bit? \$\endgroup\$ – Sven Jul 12 '15 at 21:50
  • \$\begingroup\$ The setOnes array is precalculated, in order to quickly find the number of set bits in an integer. For example, setOnes[14] = 3, since 14 = 1110b. I ended up using the solution shown above, since other bottlenecks were more dominant. \$\endgroup\$ – maxb Jul 17 '15 at 14:57
  • \$\begingroup\$ @maxb Another question, how did you get that definition of holes? Especially the second "rule". Has this something to do with column/row transitions? Also, did you publish your final version somewhere? \$\endgroup\$ – Sven Aug 27 '15 at 18:17
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Shouldn't it be neighborMask = ((filled << 1) | (filled >> 1)) | underMask; (no |=) and then you can get rid of the first foundHoles += statement. You seem to be counting some holes twice plus you count holes under places that used to be adjacents but may no longer be. \$\endgroup\$ – Brythan Feb 14 '15 at 0:11
  • \$\begingroup\$ @Brythan If you trace through the OP's code, it does exactly what mine does. Once it finds the first filled square in a column, it starts counting all squares in the three columns (left, center, right) of the current column. The OP's code in fact can triple count some holes, which I have edited my code to do as well. \$\endgroup\$ – JS1 Feb 14 '15 at 0:17
  • \$\begingroup\$ Wow, this is really fast. My program went from placing 5200 Tetris pieces per second to 9200 pieces per second. This was exactly what I was thinking (not your actual solution, but being able to remove a for-loop). Great job! Note: Combining your solution with Brythans solution by adding his first while-loop with minY set to 0 to begin with actually makes it about 10% faster \$\endgroup\$ – maxb Feb 14 '15 at 0:49
  • 1
    \$\begingroup\$ And to clarify: the reason why I count some holes twice or thrice is because those holes are "worse", and I want to take this into consideration. \$\endgroup\$ – maxb Feb 14 '15 at 12:50
6
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ I implemented this, and it is really fast. In the first while, should it be grid[minY] instead of grid[y]? Also when adding the lines, you are forgetting about the special case where x = 0. Then we only want to look at the current column and the column to the right. I made it work using foundHoles += setOnes[grid[y]<<1 & 7<<x]; which seems to have about the same performance, and giving a better result. Thank you a lot for your answer, it really helped me! \$\endgroup\$ – maxb Feb 14 '15 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.