🎮 Every Programmer Should Write Tetris! 🚀
ML, JavaScript, and Beam Search w/ AI
Alex Avdiushenko
December, 2025
ML is built using the tools of mathematical statistics, numerical methods, mathematical analysis, optimization methods, probability theory, and various techniques for working with data in digital form.
What is it?
\[\begin{cases} \frac{\partial \rho}{\partial t} + \frac{\partial(\rho u_{i})}{\partial x_{i}} = 0 \\ \\ \frac{\partial (\rho u_{i})}{\partial t} + \frac{\partial[\rho u_{i}u_{j}]}{\partial x_{j}} = -\frac{\partial p}{\partial x_{i}} + \frac{\partial \tau_{ij}}{\partial x_{j}} + \rho f_{i} \end{cases} \]In machine learning, there is no pre-set model with equations...
Types of Machine Learning
- Supervised Learning: The algorithm is provided with labeled training data, and the goal is to learn a general rule that maps inputs to outputs
- Unsupervised Learning: The algorithm is provided with unlabeled data and must find the underlying structure in the data, like clustering or dimensionality reduction
- Reinforcement Learning: The algorithm learns by interacting with an environment and receiving feedback in the form of rewards or penalties
Data matrix (objects and features as rows and columns):
$F = ||f_j(x_i)||_{\ell\times n} = \left[ {\begin{array}{ccc}
f_1(x_1) & \dots & f_n(x_1) \\
\vdots & \ddots & \vdots \\
f_1(x_\ell) & \dots & f_n(x_\ell)
\end{array} } \right]$
Types of tasks
Classification
- $Y = \{-1, +1\}$ — binary classification
- $Y = \{1, \dots, M\}$ — multiclass classification
- $Y = \{0, 1\}^M$ — multiclass with overlapping classes
Regression
$Y = \mathbb{R}\ $ or $\ Y = \mathbb{R}^m$
Ranking
$Y$ — finite ordered setPredictive Model
A model (predictive model) — a parametric family of functions
$A = \{g(x, \theta) | \theta \in \Theta\}$,
where $g: X \times \Theta \to Y$ — a fixed function, $\Theta$ — a set of allowable values of parameter $\theta$
Example
Linear model with vector of parameters $\theta = (\theta_1, \dots, \theta_n), \Theta = \mathbb{R}^n$:
$g(x, \theta) = \sum\limits_{j=1}^n \theta_jf_j(x)$ — for regression and ranking, $Y = \mathbb{R}$
$g(x, \theta) = \mathrm{sign}\left(\sum\limits_{j=1}^n \theta_jf_j(x)\right)$ — for classification, $Y = \{-1, +1\}$
Tetris, step 1: Look for some implementation of Tetris on the Inrenet
Source: Javascript Tetris, how it works
Features for Heuristic Agent
Heuristic Agent
Combine features into a heuristic score:
(-0.51 * aggHeight + 0.76 * completeLines - 0.36 * holes - 0.18 * bumpiness) $\to\max$
The first result
Fixed bug in Possible Moves
Fixed Height calculation, including null-bug
Heuristic Agent Results
(-0.51 * aggHeight + 0.76 * completeLines - 0.36 * holes - 0.18 * bumpiness) $\to\max$
| Case | Rows | Score |
|---|---|---|
| Heuristic with bugs | 0 | 222 |
| Fixed Possible Moves | 5 | 1 036 |
| Fixed Heigh calculation | 612 | 78 268 |
Ok, looks good, but what about Beam Search?
What is Beam Search?
- An approximate search algorithm commonly used in Natural Language Processing (NLP) tasks like machine translation and speech recognition
- It is a variation of greedy search that explores multiple paths simultaneously, keeping track of the $k$ most promising paths at each step
- Beam search striking a compromise between the efficiency of greedy search and the optimality of exhaustive search
Full Search based on the next piece
Heuristic Agent Results
(-0.51 * aggHeight + 0.76 * completeLines - 0.36 * holes - 0.18 * bumpiness) $\to\max$
| Case | Rows | Score |
|---|---|---|
| Heuristic with bugs | 0 | 222 |
| Fixed Possible Moves | 5 | 1 036 |
| Fixed Heigh calculation | 612 | 78 268 |
| Full Search w\ Next Piece | 44 301 | 5 623 130 |
Time to rewrite it in Python!
Trust Junie to do the hard work:
Prompt 1: Look at the javascript tetris project and come up with the plan of rewriting it in Python. Write all the details in the `python-tetris/plan.md` file.
Prompt 2: Implement the tetris in Python according to the `python-tetris/plan.md`, but replace the `texture.jpg` background to the simple gray grid.
Prompt 3 (fixing bug): The game in Python works, but there is no AI mode, only flag for it.
It took about 30 min to get
Possible Future Steps
- Fix Python implementation!
- Join our programs at NUP or CUB 😎
- Rewrite Tetris in C++ or Kotlin
- Implement true Beam Search or MCTS
- Switch to other game 🙂