6
\$\begingroup\$

Imagine a standard Tetris board (10x20) using the standard set of 7 tetrominoes.

Given a Tetris game state and a target position, how can I find the optimal sequence of moves that will get the currently active tetromino into that position?


A really basic example:

example path to position

Clearly, the optimal path is to move to the leftmost column and not rotate the piece. I'd like the algorithm to handle more complex positions too.

\$\endgroup\$
  • \$\begingroup\$ Is it possible for the AI to move the tetronimo once it "landed"? Eg, shift it into a position that's usually not reachable by just dropping it from the top? \$\endgroup\$ – bummzack Jan 5 '15 at 15:15
  • 1
    \$\begingroup\$ Are you just wanting to handle the current move only or do you want to be planning for future moves as well? Current move only, I'd suggest just brute forcing it as the resources required should be quite minimal. \$\endgroup\$ – Mythics Jan 5 '15 at 17:21
  • 1
    \$\begingroup\$ Current move only. Probably bruteforcing should be enough, but a "nicer" algorithm would be better. \$\endgroup\$ – Gabriele D'Antona Jan 5 '15 at 17:57
  • 1
    \$\begingroup\$ Original rotation system. DAS should not matter, should it? Let's say our algorithm can perform "n" shifts and rotations for each row. \$\endgroup\$ – Gabriele D'Antona Jan 5 '15 at 19:16
  • 1
    \$\begingroup\$ I think DAS would matter, because it means a speed gain. Movement speed will influence the reachable destinations. Imagine a board that's almost filled up and a fast falling speed of the tetronimo. This will result in some positions being unreachable, simply by not being able to navigate to that position in time. \$\endgroup\$ – bummzack Jan 5 '15 at 20:59
5
\$\begingroup\$

I added another answer for an alternative explanation of the problem. You can think of this problem as Motion Planning in the Configuration Space of the tetris piece.

The Configuration Space

Define the configuration of a Tetris piece to be an (x, y) location and a rotation (t). The configuration of a Tetris piece is therefore three dimensional. We can define a 3D space that the Tetris piece lives in called its configuration space.

Now, configurations are either possible or impossible. A possible configuration has the Tetris piece completely inside empty parts of the tetris board. Impossible configurations either have the Tetris piece off of the board or colliding with occupied parts of the board.

Configuration Space Planning

The goal is to find a sequence of configurations S =(c_0, ..., c_N), where c_0 is the start configuration of the piece, and c_N is the goal configuration, where S is of minimum length, and all of the configurations in S are possible.

Actions

Define an action as a function that takes one configuration and turns it into another. In Tetris, the actions are Turn (which only modifies t), Move Left, Move Right and Do Nothing. Depending on the way "gravity" is implemented, every action may also move the Tetris piece down as well.

If an action would result in an impossible configuration, that action is itself impossible.

Planning

The problem can be solved using AStar. In this case, the nodes in Astar are 3D configurations of the piece (x, y, t). The links are actions which change from one configuration to another such that the resulting configuration is possible. The distance metric and heuristic is a simple 2D euclidean measure on the position of the piece, and a simple comparison on t. All of the actions have weight 1.

AStar is guaranteed to find the optimal set of actions needed to put the piece in the correct place.

\$\endgroup\$
  • \$\begingroup\$ If the computer is playing fair, then some of the actions are pre-determined. Ie. the algorithm may "want" to move 5 spaces directly right, and all of those configurations are "possible," but (depending on fall speed) gravity will pull the tetramino down one or more spaces somewhere in that span. For complete fairness (which may or may not be the goal), the number of free-choice actions the algorithm can take between prescribed fall actions should be matched to what a perfectly-timed button presses could achieve. I think this is what @bummzack is getting at in the comments above about DAS. \$\endgroup\$ – DMGregory Jan 6 '15 at 16:22
  • \$\begingroup\$ If that's the case all you need to do is append "fall" to every action you take. The problem is the same, still motion planning in the configuration space -- but the action set is a little different. \$\endgroup\$ – mklingen Jan 6 '15 at 16:56
  • \$\begingroup\$ Modified my answer to include this, though including DAS might be slightly more complicated. \$\endgroup\$ – mklingen Jan 6 '15 at 17:01
  • \$\begingroup\$ Turn can also modify x & y in systems with wall & floor kicks (though OP's rotation system does not include these - just mentioning here for others). But you're right, the method works great, these are just implementation details that will depend on the use case. I wonder, would there be any speed gain in doing the pathfinding backwards, since the "landed" state probably has more constraints in its neighbourhood than the initial drop? (Leading to a more tightly-pruned search tree) Rejection of unreachable destinations should be faster, because A* is walled-in and can't explore the whole grid. \$\endgroup\$ – DMGregory Jan 6 '15 at 17:45
2
\$\begingroup\$

I am assuming that your problem is:

Assume the placement location is known. How do I find the optimal sequence of moves to put the piece in the correct location?

One answer to this question is to interpret the problem as an Action Planning problem. The simplest algorithm to solve it is probably STRIPS. There is another algorithm that is a more efficient version of STRIPS called GOAP which is used in the game industry. Basically, you can think of STRIPS and GOAP as an AStar path planning problem where the nodes are states, and the links between nodes are actions.

Here's how it works:

  • You have a set of states, which we shall call S. In your case, the set of states is the set of all possible board positions. It can be represented efficiently as a binary matrix of 1's and 0's, where the 1's represent cells that are filled, and the 0's represent cells that are empty. You will also need to represent the current state of the piece being controlled by the player in your state.

  • You also have a set of actions that can be taken at a particular state, called A(S). In your case, the set of inputs the player can select to move the given piece.

  • An action a performed on a state s leads to a new state s'. In your case, an action will move the current piece so that different parts of the grid become 1's and others become 0's. Given a state, there are at most 4 actions (rotate left, rotate right, move down, and do nothing). Some of these actions will be impossible.

  • There is a goal state g in S that you want to reach, and a start state s_0. In your case, it will be a specific board configuration and position/orientation of the target piece.

  • Assume we have a distance metric d(s_1, s_2) which tells us how similar two states are. In your case, the distance metric can simply iterate through all the grid cells into the two states, and add 1 whenever the cells differ. You can also do this more simply by measuring the distance between the position/rotation of the target piece in s_1 and s_2.

We can interpret this as a graph planning problem. A node is simply a state. A link between nodes is simply an action that takes you from one state to another. The goal is to plan a sequence of actions from the start state to the goal state which has minimum length. To solve this problem, you simply use AStar on the graph, with d as the heuristic. Sometimes, it will be impossible to solve the problem, but Astar will always give you the optimal set of moves to take to get you to the goal.

Here's some simple pseudocode:

// Returns all the reachable neighbors of a given state.
List<State> GetNeighbors(State state):
    List<State> neighbors = new List<State>();
    // Iterate through all possible actions (turn left, turn right, move down, do nothing).
    foreach(Action action in Actions):
        // Some actions will not be possible given a state.
        if (action.IsPossible(state)) :
            // Apply the action to the state, yielding a new state.
            neighbors.Add(action.Apply(state));

    return neighbors;

// Gets the difference between two states. 
float StateDistance(State state1, State state2):
    float dist = 0;
    // States differ if their cells differ
    for (int x = 0; x < NUM_X; x++):
        for (int y = 0; y < NUM_Y; y++):
           if (state1.occupancy[x][y] != state2.occupancy[x][y])
               dist += 1;

    // They also differ based on the position and orientation of the active piece.
    dist += state1.activePiece.position.distance(state2.activePiece.position);
    dist += abs(state1.activePiece.orientation - state2.activePiece.orientation);

    return dist;

// Gets an optimal path of actions from the start state to the goal state.
ActionPath GetActionPlan(State startState, State goalState):
    // Simply run Astar to find a path from the start to the goal with 
    // GetNeighbors as the way of finding connections between states, and
    // StateDistance as a heuristic.
    return AStar(startState, goalState, GetNeighbors, StateDistance);
\$\endgroup\$
  • \$\begingroup\$ Thanks for the detailed answer. I wonder if 8bit systems with Tetris implemented pathfinding this way :) \$\endgroup\$ – Gabriele D'Antona Jan 5 '15 at 21:51
0
\$\begingroup\$

If you know the shape of the piece, and you know where you want to place it, I would assume you have determined the orientation of the piece already. If this is the case then I think the solution is fairly straight forward. You have a default orientation for each piece, and depending on the piece 0-3 possible alternate orientations. The number of rotations left or right are "pre-computed" to match the target orientation. After figuring out how many rotation moves, determine how many spaces to the left or the right you need to move the piece. You can calculate this by using the left-most tile on the piece and the left-most space of the desired location. Finally, the same can be done for the height. From the target orientation, in the starting position, what is the space difference between the lowest tile of the piece and the lowest open space of the desired position.

I say "pre-compute", because in my opinion there are too few possible orientations to make a complicated algorithm, and a waste of cycles trying to compute this. If you haven't done it already, it would probably take about 2 minutes to map out each piece and each possible orientation of each piece. For example, the 2x2 block has only one orientation, while the 1x4 bar, and the "s", and "z" shapes all have 2 possible orientations. And the rest of them, the "L", the backwards "L", and the broken plus sign, all have 4 possible orientations. (I think I got them all).

\$\endgroup\$

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.