Embedded Files
Research
Tetris is a game that has been played and mastered for ages! So I did my fair well of research and to no one’s surprise I found plenty of strategies, and heuristics. My Heuristic Ai is a combination of everything I saw into a ONE. So it would have not been possible without the following resources:
Max Column Height Heuristic
Alan's Heuristic was a great starting point, so the first thing I did was implement his code, into code that would be useful to me. With that in mind onto testing!
Score: 37 (on a 10x10)!
This is important since it will be the standard by which we judge other heuristics in a 10x10 board
Completeness
AKA Lines Cleared. From Greg’s Heuristics, he made a heuristic of lines cleared. This caught my eye, since he mentions a heuristic for clearing a line, and a heuristic for clearing 4 lines. Therefore I implemented my Hueirstic by squaring the number of lines cleared. This way it will have exponentially higher influence on the total heuristic the more lines are cleared. This is the only heuristic where the higher the value of the heuristic function the better.
Score: N/A (or Deniable)
This are basically the results of the Max Column Height Heuristic and comparing them to last page it clear that the value added from this heuristic is deniable.
Yet it is part of my final heuristic calculation, with a low weight, since it can have some value, even if its low.
This Heuristic does not work on its own for obvious reasons: Most moves do not clear lines. Additionally, there are other heuristics that account for this indirectly. Also 1 line is not always good! It can make holes, bumps, etc!
Holiness Heuristic
AKA The Hole Heuristic :P. Almost everyone uses this heuristic in some shape or form, but my favorite is Max Bergmark method! This is because his way of doing it not only relies on the number of holes, but their height and their type!
HEIGHT: The higher the hole, the worse it is. This is because the higher the hole, the more dangerous it is. Plus it also allows for some sacrificial holes at the bottom if it means less holes at the top.
TYPE: There are 3 Types, I call them Caves and Holes. A hole is any empty cell with a filled cell above. And a Cave is an empty cell to the left or the right of a column “which the topmost cell is at the same height or above the empty cell in question.” These are not mutually exclusive and indeed add stack in the heuristic.
TOGETHER: For every cave to the left of add (cell.y +1)^2 to the heuristic, for every cave to the right do the same, and for every empty cell anywhere under a filled cell add (cell.y +1)^3
Important reminder: this is a 10x10 board meaning it is exponentially better the higher the height of the board!
This is also the most influential heuristic in my game. To the point that I do not even normalize this heuristic, and I normalize every other heuristic.
Important reminder: this is a 10x10 board meaning it is exponentially better the higher the height of the board!
This is also the most influential heuristic in my game. To the point that I do not even normalize this heuristic, and I normalize every other heuristic.
Aggregate Height Heuristic
From Yiyuan Lee Heuristics, Aggregate Height is very simple… Simply add the height of all columns together! The higher the worse. As I mentioned before, this indirectly influences lines cleared with the added value of not increasing height for clearing a line.
Score: 32 (Aggregate Height)
However, this performed worse than the Aggregate Height Heuristic, which is not what we want since it is our base
Aggregate Height + Max Collumn Height:
But by combining the two and weighting proportional to their average score, we can get the best from both worlds:
A heuristic that prioritizes moves that do not increase the height of the highest column + the benefits of keeping all columns low
Score: 61 (Aggregate Height + Max Column Height)
Even though these are different ways of clearing height, the max column height heuristic informs the Aggregate Height Heuristic that the biggest collum has a great inpact on its aggregate height. (Additionally it inderictly also solves for bumpiness)D
Bumpiness Heuristic
Another Heuristic from Yiyuan Lee Heuristics, Bumpiness describes the variation of height between columns. The higher the difference between columns the higher the value of the heuristic function.
Although it scored much lower than our base heuristic, when added to other heuristics it might add some value
Although it scored much lower than our base heuristic, when added to other heuristics it might add some value
From Yiyuan Lee’s Article, you can find how she calculates this, and therefore how I programmed mine: in simple terms she finds the difference in height between every column and their neighboring column. The absolute value of all differences are added together into one heuristic value for the function.
If n is the height of the first column an n + 1 is the next column, then do:
| n - (n+1) | + | (n+1) - (n+2)| + | (n+2) - (n+3)| + | (n+3) - (n+4)| ….
Position Heuristic
Although it seems obvious, I again did not come up with heuristic, since I saw it Code Bullets video. But it is a very simple heuristic, the lower the position of the move is (so the lower move.Position.y) the better.
However, in my implementation, the higher the move the worse. And similar to my other heuristics, the higher it is the exponentially worse it is… Lower positions on the board will be much less punishable than higher positions
At first I was adding +1 to the height since in this Tetris row 0 is the lowest, but at second look, this damages the algorithm since we want remove any punishment for placing a spot at position 0. On its own it makes no difference, but when adding heuristics together, it helps the AI.
Score: 35
Honestly, for the simplicity of the algorithm which is literally one line of code, it perfomed great in comparison to our base!
Normalization Max: boards height squared
Edges Heuristic
In Greg’s Heuristic he mentioned that the higher the number of edges the Tetromino shares with other Tetrominoes bricks the better.
How:
I Implemented mine by checking the number of empty spaces surrounding the tetromino, the more empty spaces the less edges so the worse it is.
Alan provides an API which spits a row and column matrix of the area of a Tetromino. With this we can go into a nested for loop, where one index will be offsetX and the other offsetY. For every cell of our matrix (shape[offsetX, offsetY]) that is true, we will enter another for loop for every direction essentially grabbing our offset and adding our direction. For every empty sell, add 1 to our heuristic value. Edges of the map count as edges too!
Score: 18
Not the best heuristic, but it works! Can definitely add some value!
Normalization Max: The max number of edges a tetromino can have is that of an I tetromino, which is 10!
Combining Yiyuan’s Heuristics
Once I had all heuristics, I started adding them together, and giving them weights. Without knowing where to start I started with Yiyuan’s Weights (which she got by running an Evolutionary Algorithm):
Combined Height: -0.510066
Completeness Weight: 0.760666
Hole Weight: -0.35663
Hole Weight: -0.184483
It is important to note that
1. My individual heuristic functions are completely different to their heuristic functions!
2. She did not have all the heuristics I did so of course I excluded mine
3. I have not normalized
All these differences matter a lot since me using her numbers is basically me using random numbers
Score: 213
A score of 213 is higher than that of my best score so far (200) so I will use this a base for combining heuristics
Combining 4 Heuristics
Since using Yiyuans Heuristic was basically guessing, I decided I would try to make an estimated guess using my own heuristic.
My calculations were based on the scores my individual heuristics have gotten (excluding Edge and Position) added all together. So each weight was their contribution to that total. Dividing score/total score:
233 (Holes) + 22 (Bumpiness) + 62 (Aggregate Height + Max Column Heuristic)
= 317
Height Weight = 62 / 317 = -0.1956
Completeness Weight = 0 / 317 = .1 (I am adding a minimum of .1)
Hole Weight = 233 / 317 = -0.7350
Bump Weight = 22 / 317 = -0.0694 = -0.1000 (I am adding a minimum of .1)
So if you have not realized, I got 233 median score for my hole heuristic in on of the test… after running it more times to make sure, it is 200. Meaning that at the moment I thought this was a bad result but it was not at all! Indeed I ran lots of tests getting lower scores and thought they were performing worse than my Hole heuristic.
Again: I HAVE NOT NORMALIZED ANYTHING! Another lucky guess!
Score: 229
Combining All Heuristics
As mentioned before, my Hole median score was an outlier! So it negatively influenced my decisions plus added a bias to my tests! But I still calculator the weight of my heuristics using the same method: adding all individual scores into a total them dividing a score by that total.
Score: 214
Although not bad, it is lower than our highest score so far: 226
Again, no normalization yet, or actual true calculations… these are basically guesses (But I did not know it heheh)
Normalizing Heuristics!
Once I realized that the Hole median score was wrong this whole time I recalculated the weights properly one last time. Even if It is still an educated guess.But I also realized I had not normalized after running several tests that scored around 100, which was so much lower than my highest score. I thought that adding weights was in a way normalizing the heuristics, but then It would be very hard to find the real weights of stuff
But after I remembered one of Alan’s lectures I realized I needed a maximum value for all heuristics in order to normalize them. So here they are:
Holiness: NO HEURISTIC (Since it is the highest scoring, it will serve as the WORLD VIEW of the AI. This way I can weight every other heuristic more equally without over inflating this one’s weight)
NOTE*: normalizing and weighting this heuristic worsened scores
Aggregate Height: Board Aerea (if all columns are their max height that means they take the whole area of the board)
MaxColumn Height: state.Height (the max a column can be)
Completeness: 4^2 = 16 (4 lines can be cleared at once, and I square it)
Bumpiness: Board Area / 2 (Worst case scenario halve of the columns are topped, and halve are emptied)
Position: state.Height^2 (Position is squared)
Edge: 10 (The max number of edges a tetromino can have is that of an I tetromino)
Future Prediction
Now that we have a Heuristic function that works relatively well in a 10x10 context and normalized heuristics, it means we can now manipulate what we pass into the function. So of course, we can now run the heuristic function on future moves!
For all the moves available right now, we will look into all valid moves available in the future. We will not calculate the heuristic of the current moves, rather we will just calculate the score of all the future moves possible. For all those future moves, we will know the index of the current move that gets us so that future move. Therefore, everytime we find a new future move with the highest score, we will update the best move index to that which allowed the future move.
Essentially, unless it is an edge case, we will ignore the score of the current move and only look for the highest score from all future moves. This is key to my strategy since the AI will always be thinking ahead and not be blinded by the current move. For instance, -30 (in the diagram above) could have been chosen if the we included the score of the current move and it was weighted higher.
Future Prediction Results
For this test I had to lower the size of the grid since I just wanted a simple test to see how good it works, and it performed really well assuming that scores will double for every added height
With this test I was convinced that I had reached a solution which yielded much more than the minimum score I was aiming for!
With this test I was convinced that I had reached a solution which yielded much more than the minimum score I was aiming for!
Score: 148 (10x6 Grid)
Score: 21145 (10x10 Grid)
Results:
After a while of running the test I realized it was taking too long. So I made a calculation:
The score would increase 1 million every 3 hours.
I only completed 1 simulation, so which means I had to stop it before I reached 5 simulations which was my gole!
Score: More than 2,000,000
(10x20 Grid)
Conclusion
There were a couple things I had in mind:
I wanted the AI to look 1 level deeper into the future (so it does not explode my PC)
I wanted to run an evolution algorithm on all my weights so that I could find the best way to weight my heuristics, without me having to manually do it. This would have been easy since I the initial idea of adding weights was evolution
However, at this point adding and testing the AI would be useless since it already untestable levels. But in the future I might add these features.
Finally, all resources online I found and cited at the beginning are the foundation of my attempt! Without them my AI would be much worse. That being said, I tried adding a twist to all implementation. Maybe in the future I can twist them further! :P
Page updated
Google Sites
Report abuse