Solving Tetris in C | Hacker News Reader

Solving Tetris in C

qntm.org

102 pointsjerf17 comments

It might be a good idea to look at it as an induction problem - one state leads to another, and since a lot of states are effectively the same, it means the tree can be pruned.

Let's say the player has a row that's almost full - say, one spot left to fill all the way on the right. That means the AI needs to not give the player any block that would let him fill it (I,J,L,S,T) - so the player can force the AI to just give him O and Z blocks. If the hole isn't against the wall, the AI can only give O blocks. There are only a few, if any board states where the player cannot create a line using only O and Z blocks - the player just needs to make sure he doesn't loosen the restriction on the AI (such as by covering the hole).

If the hole is 2-wide, depending on the hole's depth, the AI may only be able to give T blocks, if even that, and for most board states, you'll probably find that T blocks can be used to make a line without loosening the restrictions on the AI.

You have 10 columns and you need to consider at least 4 rows, to account for the possibility to make a line. That means 2^40 different possible states, and I think that most of them are reachable with the rules of Tetris. It could still be implemented with a hash_table and yield interesting results, but it is still possible to fill up the memory with such an algorithm.

Before using such an approach, I think it would make sense to find a compressed way of representing a state. I think it would be workable to have ten "heights" describing the enveloppe of the structure and to add 3 bits to describe the presence of "holes" in the 3 bottom lines (the presence of holes in the top line can be inferred in the enveloppe information).

That would give us 2 bits of height per column, plus 3 bits for hole presences. 2^23 : a more manageable state space of 8 millions.

Such a representation is not enough to have a good AI or to even make a completely evil AI but it fills the bill when it comes to solve the problem at hand : "prevent the player from making even a single line"

You're suggesting using 2 bits to store the height of the column, plus 3 bits to store the presence of holes, for a total of 5 bits per column. Exactly how you got from that to a figure of "2^23" I don't know. That's actually (2^5)^10 = 2^50 possible column combinations.

Why not just use 4 bits to represent the whole column? That's (2^4)^10 = 2^40, exactly where we started.

In fact, look at rows instead. With 10 columns and 4 rows there are, to be more precise, (2^10 - 1)^4 possible states.

And the majority of which have "floating" (disconnected) sections which, while reachable with the rules of Tetris, cannot be reached without making at least one line.

In case you didn't read the article, Tetris has been solved for width 10 height 4: the AI wins. The same is true for width 10 height 5. We need to go further.

I don't think he meant for the 3 bits to be per-column, I think he meant 3 bits total - one for each row below the top, meaning "does this row have a hole that is covered? (and as such, cannot be cleared unless a line above it is cleared)". This effectively turns all board states with the same exact topology and potential for clearing lines below the surface into the same state.

I think his overall strategy is similar to a point that I intended to make - that there are large sets of states that are effectively equivalent, and treating them as such reduces the complexity of the problem. Not that dissimilar from alpha-beta pruning or branch-and-bound.

Ooh. That's actually cleverer. It reduces the space of possible wells quite substantially. It does make detecting a horizontal line more difficult, though. I will think about this.

Bastet is an open source Tetris clone that is based on a similar concept :

http://fph.altervista.org/prog/bastet.shtml

In the method pseudocode for player_can_always_force_win, the player has full control over which piece will appear next (i.e. the pseudocode in its current form should be called player_can_possibly_win). I think it should read:

  BOOLEAN player_can_always_force_win(well w) {
    for each piece p {
      BOOLEAN player_will_win = FALSE
      for each landing state of piece p in well w {
        well w2 = result
          if(
              that_makes_a_line(w2)
              or player_can_always_force_win(w2)
            ) {
            player_will_win = TRUE
          }
      }
      if (!player_will_win) {
        // If the AI selects this piece, the AI wins
        return FALSE
      }
    }
    // There is no piece the AI can select that will cause the player to lose
    return TRUE
  }

You are correct. I updated it to this:

    who_wins(well W) {
      for each piece P {
        for each landing state of piece P in well W {
          well W2 = result
          if(that_makes_a_line(W2)) {
            next piece
          }
          if(who_wins(W2) == PLAYERWINS) {
            next piece
          }
        }

        // AI wins every landing state
        return AIWINS
      }

      // Player wins every piece
      return PLAYERWINS
    }

    print who_wins(empty_well)

It would be nice to provide the game tree for the 10x20 case. If it's not too big, then it would be an easy way to check the result of your experiment. Even if it's big, it would probably be fun to navigate.

His current implementation runs out of memory on a board less than half that size.

Good luck ;-P

Ah, right, so the real problem is still open. :-)

I didn't examine the code very carefully, but here are some sensible things that you could do and that I'm not sure you're currently doing:

- Are you doing alpha-beta pruning? http://en.wikipedia.org/wiki/Alpha-beta_pruning

- Instead of either caching everything or nothing, choose a cache size, cache things and flush the least used ones when the cache is full. (More intelligent things are possible there.)

- Explore the player moves in a clever order to avoid getting bogged down in useless branches. You could use an existing tetris AI to pick sensible moves for you and examine them first, or use simple heuristics.

- In the same spirit, since you seem to be using an exact but complicated (and costly) way to compute possible player moves, it might make sense to first explore a subset of moves which is easier to compute. For instance, examine first the moves which are just an horizontal movement, a rotation, and a straight drop. Maybe there is a winning strategy for the player which mostly uses such moves.

- I am not sure of what you cache. There is no point in caching the whole well, just caching the lines with a reachable empty space. Also, hitting any configuration from the cache is deadly (since it means we went higher and went back to an equivalent configuration).

Hopefully this is sensible and isn't stuff you already do. I'd be quite interested to know the definitive answer to this problem. :-)

Alpha-beta pruning sounds like a reasonable route forward. In this case, each "well" is a state in the game and placing a new piece in the well constitutes a move to a new state. Since the "heuristic value" of a move is absolute (player wins or AI wins), I already have stuff in place to exit early from an exhaustive evaluation of all possible landing points if a definitive answer is found. But I don't have anything in place to put those landing points into an optimal order for evaluation purposes. A Tetris-playing AI which can quantify the "goodness" of a move would be useful here, and that's entirely possible.

Intelligent caching is possible but I think it would be difficult for me to implement and I'm not certain that it would yield much benefit.

Actually, the procedure for identifying all the possible player moves is very fast already and I think making it prioritise "easier" moves would slow it down. In particular, ruling out or de-prioritising simple things like "tucking" a piece under another is very counterproductive.

I'm afraid the game tree for W10xH5 is over 2 gigabytes and I'm pretty sure the number of possibilities increases faster than exponentially in H!

For those that care, a few years ago some researchers proved Tetris is NP-complete for many problems.

http://arxiv.org/abs/cs.CC/0210020

The paper tells us that Brzustowski and Burgeil already showed that a loss is forced for alternating S and Z pieces. But it is easy to see that you can get 1 line with S and Z simply by putting the thick part in the middle, and this is all the author wants.

Yeah, I realize that -- I'm just saying, for people who want to read more on the subject of Tetris there is a lot out there.

Interesting that the player starts winning earlier in the smaller width wells as opposed to the larger ones. I wonder why that is.

Reply on news.ycombinator.com