Approach and results

Tetris is technically speaking NP-hard, mathematically proving that it is not easy to make a Tetris bot. However, I began this project naively and was doing it because I really like Tetris. I play a lot of Tetris on jstris.com and I didn't just want a bot to play Tetris. I wanted it to play Tetris on the same playing field as myself. The first step I took in the project was programming Tetris in Python. It was just nested lists storing a 2D board filled with 1's and 0's. However a difficult wrinkle was the turning mechanism. All Tetris games are supposed to have the same rotation scheme so in order for my 2D array Tetris to match with Jstris's version it had to rotate identically to the web version.

After I had a working version of tetris in my terminal I needed a way for the program to see what pieces are were being played on Jstris. This task was done by having a program look at specific pixels and determining which color it was. This was made easier knowing that all Tetris pieces start in the same spot and each piece type has a consistent color.

After creating a helpless program that can only look at the piece and keep track of the game board, I decided to add a control algorithm. Tetris differs from say Tic- Tac- Toe in two ways: measuring success and winning. In Tic- Tac- Toe it is trivial to determine whether a move is good or not (especially since a computer can realistically run through the roughly 300,000 possible game situations). In Tetris it is hard to tell if it is worse to play a high stack or to create holes in the board. Should it clear a line now or wait for a better piece. This is also complicated by the fact that you cannot win tetris. You can only not lose. This is interesting because the heuristic program I wrote doesn't look for the best move, it just looks for the least bad move.

Speaking of the algorithm, after reading others works about similar Tetris programs the common consensus is to balance a linear equation with variables of board roughness, line clears, holes, and stack height. What those variables actually mean doesn't matter, but mathematically we want to find the optimal combination of the linear equation. However some have heavier weights than others, and some are a deterrent and others are an incentive. After some trial and error, I experimentally found workable weights for the linear equation. Now the program can determine what is a better board state given between two different situations.

Finally the program would ennumerate all 40ish possible moves it could play for each piece and determine the optimal place and this worked! However the computer was slower than expected and slower than myself (which says something about both the computer and myself). So optimizations were made such as disregarding terrible moves by putting max values thresholds on variables, or optimizing movement to place a piece. Once all was said and done, the bot was proficent. It could play and play for a non-trivial amount of time, but it was not a menace to jstris.com. If ran on something stronger than my laptop maybe it would play faster, but there are more optimizations that could be made such as playing best combination of the next two moves instead of just the current move. Even with the human-level of playing from the computer, this project helped me realize the importance of optimization (and carefully organizing) code for large programs.