A Tetris AI built with p5.js.
This AI generates a list of all possible end states of the current piece, and picks the one with the highest fitness score. In case of a tie, the AI picks a state at random.
The list of all possible end states is generated by running a breadth-first-search through all possible control inputs at every possible point in time, attempting to hard-drop at each step along the way.
This brute-force search enables the AI to perform complex maneuvers, like T-spins, tucks, and slides. This also allows the AI to make use of SRS, especially wall kicks, without any additional added code.
Further, the AI also takes into account the next move when deciding the current move; if a sacrifice in fitness score for the current move allows for a much better move for the next piece, it will make the sacrifice. For optimization, only the top 25% of current moves will be looked at when considering the next turn.
The amount of improvement needed is configurable, though it should be noted that the value must be picked with care. Too little required improvement causes the AI to overfit to the next move, always making poor decisions to save the best move for the next turn, while never getting the chance to make the good move. Too much required improvement reduces the strategy to only paying attention to the current move, meaning beneficial sacrifices will never be made (while also wasting computation in looking at the next move).
The AI also takes gravity into account when computing its next move; this means that the AI will only make moves that are possible with the gravity settings. Lock delay is also taken into account, so if the lock delay is sufficiently small, it is not possible to make overly complex spins or slides, and the AI will not attempt them.
To speed up the computations, a few optimizations were made (including smaller hashes for board state in the search, reorganization of cache checks, etc.), which initially brought computation time down from 500ms to 100ms. This was still visually noticeable on a low delay (i.e. AI delay of -1), so as another optimization, the computation is parallelized through parallel.js with worker threads.
Parallization can be toggled on and off via the UI, as it does use a lot of CPU resources. Also note that opening the network tab in the browser devtools can crash the page, as worker requests count as network requests, and the tool buffer fills up very quickly.
The fitness score is determined by several factors:
- Line clears (reward for line clears)
- Gaps (penalty for creating a gap, but less penalty after the first gap is created in the column)
- Height distribution (penalty for a larger average height difference in adjacent columns)
- Piece height placement/board height (penalty when placed higher, increasing with the square of the height)
The weights of each factor were determined manually through testing.
The rest of the Tetris gameplay is quite standard, and built off of the Tetris guidelines.
The pieces are drawn from a bag, meaning all 7 pieces are guaranteed to appear in some order before refilling the bag.
Rotations were implemented based on the SRS (Super Rotation System) guidelines, but no wall kicks or other techniques are implemented yet; there is only functionality for the basic rotations.
Keyboard mappings are standard as well, with the left/right arrow keys moving the pieces left/right, the up arrow
rotating clockwise, the down arrow as a soft drop, and the Z key rotating counterclockwise. Holding a piece is done
with the shift key, and a hard drop is the space.
Delayed auto-shift is also implemented, along with repeated movements upon holding down left, right, or down arrow keys. There is an initial delay, before automatic shifting kicks in at a higher speed.
Lock delay is also implemented---there is a separate timer once the tetromino hits the ground, and once this timer runs out, the piece is locked in. The timer starts immediately when the piece hits the ground, and is reset if the piece moves to a position where it can fall normally again. The drop delay is untouched when this happens (i.e. it is not reset at any point; otherwise, the user can infinitely hold a piece on the board).
The ghost piece is enabled by default (and cannot be disabled at the moment). It should be noted that it is quite similar visually to the display color of the target end state of the AI, and may be changed in future versions.
However, there are a few aspects of the standard game described by the guidelines that are not currently implemented.
There is currently no scoring system, and the only means of scoring is the number of lines cleared. Drop speed is currently static (can be changed in the settings menu) and not variable based on line clears.
The main UI currently has several settings that can be changed on the fly during the game.
-
Enable AI: Starts AI, but will still detect keyboard input
-
AI Delay: Number of frames between AI moves. If this is greater than or equal to 0, the AI will wait until the piece comes on screen before making its first move. If this is equal to -1, the AI will immediately execute its sequence of moves when the piece is generated.
The current target (chosen) end state will be displayed on the board in a light color.
-
Parallelize AI: Whether to utilize parallization to speed up the search for an optimal next step. This takes a considerable
-
Frame Rate: Maximum number of frames per second that p5.js should run at.
-
Drop Frames: Number of frames to wait before gravity drops the current piece down one row.
-
Lock Frames: Upon hitting the ground, number of frames to wait before a tetromino is locked into place.
-
Show Hints: Utilizes the AI to suggest the best possible move to make given the current board state. If there are multiple best moves (i.e. multiple moves with the same fitness score), it will display all of them. Note that this may cause some visual noise when there are a lot of possibilities, as they may overlap.
There are additional configuration options in the configuration file src/config.js, but should not be modified, as
they may mess up the visual appearance of the p5.js canvas.
These advanced settings change how the fitness score is calculated. The defaults were computed through manual experimentation, though a future improvement can be to automatically choose the best settings (perhaps with a genetic algorithm).
-
Line clears weight: Weight given to line clears. This is a positive value added for every line clear the move triggers.
This positive score incentivizes moves that clear lines, which decreases the board height and adds to the score.
-
Holes weight: Weight given to holes. This is a negative value subtracted for every hole in the board after new move. (Other configuration options change how holes are grouped and what value is associated with this weight.)
This negative score prevents moves that create holes in the board, as holes make it a lot harder to clear lines.
-
Board height weight: Weight given to the board height. This is a negative value for the total height of the board, calculated from the height of the tallest filled square, after the new move.
This negative score prevents the AI from staying with a tall board; this means the AI will focus more on clearing lines when the board becomes too tall, and avoids placing more pieces to make the board higher.
-
Placement height weight: Weight given to the placement height of the current piece. This is a negative value for the height of the newly placed piece, calculated from the tallest filled square of the piece.
This negative score prevents the AI from placing pieces at high locations; this means the AI may make sacrifices and holes when the board gets too high, to place pieces lower on the board.
-
Average height difference weight: Weight given to the average height difference. This is a negative value for the average variation in heights across columns. This is calculated by taking the differences between heights in each column, and averaging them all.
This negative score encourages a smoother board, as a board with lots of varying heights makes placing pieces harder.
-
Row flips weight / Column flips weight: Weight given to the number of flips per row/column. This is a negative value for the number of flips between empty and filled squares in each row and column. A flip in a given row/column is when two adjacent cells are of opposite polarity (i.e. one is filled and one is empty).
This negative score encourages more connectivity, which helps with filling in overhangs and making line clears easier.
-
Deepest well weight: Weight given to the depth of the deepest well. This is a negative value for the deepest 1-wide hole in the board. A well is determined by looking at three adjacent columns; if the middle column is of lower height than the adjacent two, the middle column is considered a well. The depth of the well is the difference in height between the lowest adjacent column and the height of the well column.
This negative score discourages deep 1-wide holes, as the only pieces that can fill a hole of depth at least 3 is the
Ipiece. -
Holes scaled / Holes scale exponent: Whether the holes should be scaled, and the exponent if the quantity is scaled. If the holes score is scaled, holes in each column are ground together, and the sum of the holes in each column are raised to this exponent, and these exponentiated values are added together before being multiplied by the weight.
If the exponent is less than 1, more holes in the same column are penalized less with each additional hole; the first hole is penalized the most. If the exponent is greater than 1, more holes in the same column are penalized more with each additional hole.
-
Board height scaled / Board height scale exponent: Whether the board height should be scaled, and the exponent if the quantity is scaled. If the board height is scaled, the board height is raised to this exponent, before being multiplied by the weight.
If the exponent is less than 1, a taller board is penalized less with each added height (which is generally unwanted). If the exponent is greater than 1, a taller board is penalized more with each additional added height.
-
Placement height scaled / Placement height scale exponent: Whether the placement height should be scaled, and the exponent if the quantity is scaled. If the placement height is scaled, the placement height is raised to this exponent, before being multiplied by the weight.
This project is currently under development, but feel free to create an issue for any bugs, or to suggest any improvements or features!