Solving Tetris in C

by jerf • 15 years ago

102 17 15 years ago

a3_nm2• 15 years ago

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.

zbanks• 15 years ago

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

Good luck ;-P

a3_nm2• 15 years ago

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. :-)

qntm5• 15 years ago

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!

Xk2• 15 years ago

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

algolicious• 15 years ago

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.

Xk2• 15 years ago

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.

CGamesPlay• 15 years ago

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
  }

qntm5• 15 years ago

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)

T-R2• 15 years ago

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.

Iv• 15 years ago

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"

qntm5• 15 years ago

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.

emillon• 15 years ago

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

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

hammock• 15 years ago

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

Solving Tetris in C

Related Stories