tetrinet bot showdown

11 Jul 2006 I've been working on the tetrinet bot the last couple days. It can now handle practically anything (except a game pause...) and is very modular.

Writing a new AI requires you to write 1 or 2 functions (1 is optional).

The first function is called whenever there is a new block. The current playingfield and block are presented, aswell as the next block. The function needs to return the new playingfield or return an error when it can't place the block (which means the game is over).

The second function is called from time to time and allows the AI to use special blocks. The list of currently gained special blocks is passed to this function. The AI needs to return what it wants to do with the first block in this list. It can do nothing (e.g. to wait for an event before applying a block), delete the first block, apply it to himself or apply it to someone else.

In the process of writing the bot, I wrote a couple AI's.

The very first AI is dubbed Dummy, because it doesn't really do anything. I use it to sit around and be helpless. (In fact, this dummy AI used to show a bouncing smiley, but I removed that since it's so childish ;) Now all it does, is give up when it starts.

All other AI's use a heuristic function to calculate the best position and orientation to drop a block. These AI's are actually useful...

AI1 uses a very simple heuristic function. It just counts the number of "pixels" (1 tetris block is made up of 4 pixels) in each row, and multiplies it with the inverted row number (This means: row 0 at the top has inverted row number 22, which is the highest number possible).
The idea is that more blocks at the bottom, will get the AI a higher heuristic value.
The best solution is the one with higest heuristic value.

Sadly, this AI is not very good. It will create holes in the field all over. That's why I created AI2

AI2 works the same way as AI1, except that the heuristic function is changed a bit. Instead of giving a higher score to better solutions, it gives them a lower score (by not inverted the row number when multiplying by the amount of pixels in each line).
It also adds an amount of points for every hole it finds. It does this by going down each column, and looking for empties that are directly underneath a filled pixel.

AI2 works suprisingly well. I created AI3 and AI4 after this, using the same heuristic function with a few changes, but neither of these could beat AI2 at playing tetris.

None of the Dummy AI, AI1 and AI2 kept track of the special blocks yet. I added that ability after AI2 was done and promptly created AI3.

AI3 is copy of AI2, but it keeps track of all holes underneath the highest non-empty pixel in each column. This makes perfect sense. The less holes you have in total, the better the AI should play the game, right ? Well, not so much. AI3 tries very hard not to introduce any holes and creates long shafts while it does that. Then it has to wait for a long bar (####) to drop down so it can fill those shafts, and those bars don't always come in time.
Anyway, in battles between AI2 and AI3, they both had about the same strength.
That's when I added the special-block-awareness. Instead of just piling up the special blocks gained by playing the game, AI3 actually uses them. (It used to apply all blocks as soon as it got them, but that resulted in storms of special blocks flooding the game, so I added a random delay)
There are basically 3 types of special blocks for AI3. There are the good blocks (c, n and g) which it applies to itself. There are the bad blocks (a, r, b, q and o) which it applies to the player in the worst position (it used its own heuristic function to look at each of the playingfields, and then applies the special block to the worst of those). And finally, there are the ambiguous ones. In specific, the 's' block (which switches playing fields with another player). AI3 looks at all playing fields and choses the one that is both better than itself, and better than any other player. If there is such a field, it switches with it.

AI3 now beats AI2's ass. But I believe this is only because of the way it uses special blocks, not the heuristic function.

I created AI4 in an attempt to improve the AI2 heuristic. AI2 basically tries to drop the given block from every position and every orientation it can (that is 12 columns and maximum 4 orientations, or max 48 combinations), and choses the one with the best outcome. This way of playing is very short-sighted.
So I changed the heuristic to drop both the given block and the next block, and chose the best outcome of all those.
The result was an incredibly slow AI4. (It had to do max 48*48 = 2304 possible scenarios). This has probably to do with the bot being in perl and my computer being a P3 700 :)

Very late yesterday night, I made it possible for the bot to start a game automatically when enough players joined. Then I set up 3 AI players and myself (to watch ;) and let them fight it out.
This morning when I got up, I looked at the game and it was stuck :(. It seems the GUI tetrinet client had timed out, and caused the bot not to start the game because there were not enough players. If the GUI client timed out, that means there must have been one hell of a fight somewhere along the night. It takes almost 15 minutes before the server gives up on a client...