- Updated Monday, May 30th 2016 @ 15:18:48
Hello everyone. I'd like to share with you a story of my bot.
My name is Nikita Glashenko. I live in Samara, Russia. I am software developer, ACM ICPC 2013 finalist, 2nd place in Russian AI Cup 2012, 3rd in RAIC 2013. I like programming competitions.
It seems my bot is quite good, but it isn't something special. I've read about ideas of other players, and I don't think my bot has anything original. You won't find some super cool ideas here. Instead, I focused on my experience during development of the bot.
The bot story starts with site tetrisfriends.com.This site allows you to play Tetris in various modes. One of them, Battle 2P, has similar rules to rules of our competition. When I first discovered it, I was amused by the idea of PvP tetris. Before, I played Tetris only in late 90's, on Brick Game device.
And even then I considered Tetris quite boring game. But PvP version turned out to be completely different and super fun for me. So I've spent a lot of time playing it.
After some time I decided to create a bot for Battle 2P. There isn't any API, so interaction should be done by image recognition (maybe it's possible to parse traffic of flash app, but I didn't think over it).
About 80% of time was spent on implementing image recognition and key pressing.
Suddenly, it was super hard to tell the app "I wanna press some key ONCE". If you hold it for long, it could be counted as 2 moves. If you hold it quickly, move could be not counted at all. And if you hold it average time, you can get BOTH possible wrong interpretations.
Reading game state was fun as well. When you score, fancy animations appear on the board and disturb an image. In the middle of the match, background color changes and board content shifts 1 pixel up and left for some weird reason. If tetrimino has just appeared, you can't see it completely, so you need to recognize it by COLOR of it's bottom. Pieces in queue are located inconsistently and have different sizes...
But, one way or another, all these problems were solved, so I could implement some logic finally. I ended up with quite simple strategy which created hole on the right side and spammed tetrises (4 row clears). And it was enough for reaching highest level in Battle 2P. Final version doesn't lose any matches. Maybe there are some players who can still beat it, but I didn't meet them.
So I recorded video of final version and published source code.
Bot starts with new account of rank 1, and reaches rank 20: http://www.youtube.com/watch?v=Xr2vmu7dRgA
I didn't want to pollute TetrisFriends with dozens of cheaters using my bot. So it was intentionally left non-easy to use. Just kidding, actually I'm just lazy.
After beating Battle 2P I wasn't satisfied. It was too easy. Bot performed well against people because it was fast, not because it was smart. It didn't use T-spins, or complex rotations. I had bunch of ideas how to improve, but I had no motivation to implement them. How can I track progress of bot if it has highest possible level? Ah, if only there was Tetris bot competition somewhere in the Internet...
AI Block Challenge
After a while I stumbled upon AI Block Challenge here. OMG, I was sooo happy - that was just what I wanted! PvP Tetris competition with proper API, strong participants, some money prizes... Oh yeah!
First of all, I integrated my Battle2P bot code into the given sample bot. Then I challenged a few bots from the middle of the leaderboard. Oh, that was so pathetic. I've lost every match. Game rules were too different. Without ability to stash pieces, my strategy of stacking and waiting for 'I' piece had no sense. I needed to rework evaluation function completely.
So, I removed stacking code and just tried to teach the bot how to stay alive. Implemented combo and score calculation.
Next feature. First, a little definition: I call a cell bad if it's empty and there is a block above it. Of course, evaluation function already knew about them and tried to minimize amount of them. But how to get rid of them more efficiently? I tried to get rid of the topmost bad cell first. So bot started to find the topmost bad cell and try to minimize number of blocks above it. Defined this way, this parameter has some caveats, I'll describe them later.
By this time, bot could make only simple sequensces of moves. Rotate, move to the left or to the right, drop. I had to teach it more complex moves, so it could stick pieces to some holes under blocks. I implemented simple BFS over <row, column, orientation> of piece. After submission, it turned out something was wrong with rotations of I, S and Z tetriminoes. They worked not the way I expected! After some research I found information about SRS-rotations. It was a little bit mindblowing for me. The whole my life I thought there are only 2 orientations of I, S, and Z. And it turns out there are 4 of them! After taking it into account all worked fine and the bot became significantly stronger.
As bot climbed higher in the leaderboard, it became obvious that just staying alive is not enough anymore. We can't just sit and wait until opponent fills our board with garbage. We need to be aggressive. The first thing that came to my mind was to forbid clearing lines if it gives little score and it's beginning of the match now. It was implemented through some weird buggy conditions and was reworked many times later.
Next, I implemented calculating scores for T-Spin. Never dealt with it before, fun technique. Just who invented the idea to give scores for such a weird thing?
I noticed that not all bad cells are equally bad. What's so scary in bad cell, which can be easily filled, for example, with L piece from the side? I called such cells semibad and made them a little less important than truly bad cells.
Rework of evaluation function
Time to tell about my evaluation function at that moment. It was somewhat unusual. It returned not evaluation of state in a classic sense, as number. Instead, it returned some tricky mix between full game state and classic evaluation. I call it EvaluationState. It is set of parameters of full state which affects evaluation. And it's comparable. So when I evaluate game state, I actually just extract needed parameters from it. And only when two EvaluationStates are compared, real evaluation occurs.
Look at code of two involved classes (it's snapshot of considered period).
Look how comparison of EvaluationState is implemented. It's super obvious which parameters are more important.
Why I used it? I see two advantages.
* It's debug-friendly. When I debug bot with classic evaluation function: "Well, this move was evaluated as 5.323. And that move - as 13.013. But what exactly does it mean? I expected that move to be worse. Hmmm...". When EvaluationState is used, I can look at summary of evaluations, and see right now, why exactly bot thinks that state is better than this state.
* Complex conditions can be used in comparison function. For example: "if (a.badCells == 0 && b.badCells == 0) compare this way; else compare another way". Of course, with classic evaluation it can be achieved as well, but it will look less natural. When using complex comparison, you need to be cautious to avoid breaking properties of total order relation.
And of course there are disadvantages:
* It's convenient when you rely on statements like "parameter A is infinitely more important than parameter B". But what if A has 2/3 of importance of B? Then classic evaluation with linear combination of parameters is better.
* It seems it's impossible to use in expectimax search, since you can't find "average" of two EvaluationStates. And again, classic evaluation works fine here.
So, what did I do next with this nice evaluation concept? I got rid of it and switched to classic evaluation.
For me, advantages mentioned above are important at the early stages of development. When I debug a lot, when I prefer to use human-like language and logic during state comparisons.
Later, classic evaluation becomes preferable.
Problems started with determining importance of height. I define height simply as height of the highest column on the board. Evaluation of height just doesn't fit into EvaluationState concept naturally.
I think, height change is less important when height is small, and super important, when height is, well... high. And this importance rises gradually.
That's why I calculated height contribution as A*height^B. As it's exponent, it's derivative rises.
So I reworked evaluation to weighted sum of state parameters. All parameters had simple linear contribution, except height, which has linear multiplier parameter and nonlinear exponent part.
After I manually chose some more or less reasonable weights for my parameters, the bot became significantly stronger.
Next step is obvious: develop some method of automated weights optimisation. Actually, I'm not very proud about this part of my story...
I decided to use some sort of genetic algorithm for optimisation. Because... because it sounds cool.
I implemented the first thing that came to my mind:
Create 50 vectors of parameters (either random, or clones of best known vector).
In endless loop:
Take 2 random vectors
Let them battle in best of X match
Kill the loser
Create child of winner. To create child, take random parameter of parent and add random.nextGaussian() to it.
Everyone remembers his number of wins. The one with highest number of wins is considered as current best. From time to time, pick up current best and battle it to globally best one in Bo100 or Bo1000 match.
It's quite weird algorithm. I was going to research some literature, do some math, and implement something really good. But I didn't. This algorithm was used till the end.
At that time game rules were updated and SKIP move was added. When I first saw it's announcement, I was hoping it would be something like STASH action in Battle 2P. But it was just plain skip. Skipped tetrimino was simply destroyed. Much less cool than stash, but still better than nothing.
T-spins occured very rarely in my bot's games, only when needed conditions emerged randomly. So I've taught it to recognise two patterns:
* When board is ready to T-spin, you only need to wait for T piece - T-spin pattern
* When board is almost ready (formal description isn't very interesting) - semi-T-spin pattern
The bot often made suicidal moves, when it was obvious that opponent is going to send a huge pile of garbage. I started to calculate how many garbage can opponent send on this move. For that, I run calculation for his best move, supposing he maximizes score and ignores all other parameters.
And finally, the last major improvement.
Before, I searched two moves ahead. One more move required processing all seven possible tetriminoes, not just one. I tried it in straightforward manner and it worked way too slow. So I first evaluated moves with depth 2, sorted them, and run expectimax search with depth 3 for the best 5 moves.
It was implemented in Decempber. Since then I didn't make any significant changes, only minor constants tweaks. The final version was submitted February 5.
Then I got tired and couldn't make myself to code any more.
Lockdown start date was May 15. I still had some ideas for improvement. Maybe some of them combined could make my bot stronger, possibly even make it top1 again. I just needed some coding in last couple of days, but... There was a video game, the release of which I have been waiting for a long time. And it was released May 13. My hopes on winning were Doomed...
Repository with final source code:
- Created Sunday, May 29th 2016 @ 20:32:53
Your enthousiasm for TheAIGames.com sounds familiar to me. I had the same feeling when the first Warlight competition was anounced. I had made two or three different bots for Risk (or Warlight) before that, but having a bot competition for it is so much more fun. And it results in a much more sophisticated bot as well.
- Created Sunday, May 29th 2016 @ 20:51:58
Good job and a good write up. We already know that majority of top bots have very similar evaluation. So all they are similar in a sense.
- Created Sunday, May 29th 2016 @ 21:04:22
Thanks for sharing this. Congrats on #2.
- Updated Sunday, May 29th 2016 @ 21:14:42
Wow nice, thanks for the writeup. Yeah I also wonder what would have emerged if the mechanic was stash instead of skip. I've played TetrisFriends a lot too; I played the Arena mode a lot and that contributed to my excitement for this competition haha.
- Created Sunday, May 29th 2016 @ 23:09:03
Thanks for sharing. It was fun to read. :)
- Created Monday, May 30th 2016 @ 14:31:30
Great work, Hohol! Congrats with second place! Would you like to publish this article in russian?) Maybe on habrahabr? Many people interested in programming and in IT would be appreciated.
- Created Monday, May 30th 2016 @ 21:33:51
Thanks for sharing your thoughts, it is truly awesome.