Coding should be fun. That’s why I like to participate in coding challenges/competitions. Specially those where you have to code an AI (see also: Truusje).
This time I participated in Block Battle by The AI Games.com. It’s name might have given it away (partly), its a (two player) Tetris like battle. You have to play the game of Tetris, and if you play good your opponent will get lines of garbage (and you if he plays well). When one of the two dies, the other wins. Quite simple. I named it Kubisme, Dutch for Cubism.
You know two blocks in advance, the current block to move, and the next one, and the current position of your opponent (he will get the same blocks). When you both have a lot of playing space, the situation your opponent is in is not really important, but that changes when the fields get crowded.
Approach of Kubisme
I most of these challenges speed is key in being successful. That gives you no other option than to represent the board with a bitboard. In my case an array of Int16’s, one short (integer) per line. This allows not only to store a lot of positions in a search tree, but also enables quick manipulations of positions, and calculating scores based on its characteristics.
Move generator
When you do Minimax search (Alpha–beta pruning) you need also a fast move generator. Here I made a clear distinction:
- I have enough space to rotate my block before dropping it
- I have a (potentially reachable) hole I can get a block in
- I’m running out of space
The vast majority of moves you will find (unless you are running out of space) will come from option 1. The move requested to get this can be pre-generated, you don’t have to find a path, you just scan the board where the block (for every rotation) will stick/fit, and you know upfront how many options there will be. For an O there will be 8, for I, S and Z there will be 17, and for J, L, and T it is 34.
I waited some time before implementing path finding to fill some of those reachable holes. When I did, I implemented as follows: first do a quick scan if there is a (potentially) reachable hole. If there is some path finding to get to that hole (and return that moves before the regular ones as described for option 1). This saves a lot of time, and will have a positive effect on the move generator itself, because it returns this move (what is in most cases an improvement on keeping the hole) before the others.
Search depth
To get good Minimax (with ect…) results you need a branching factor that is not to bad. For the first two ply that is okay because you know which block you have to check. However, I defined per block the number of options I’d tested the child nodes for (an O-block 5 on ply 1 and 4 on ply 2, and for a T-block 14 vs 10 children). For ply 3 I took per node the average of the best response per block, and for ply 4 and higher the average of 3 random blocks. Those random blocks were picked per turn, so that all ply 4 and ply 5 (and sometimes ply 6) nodes tested the same blocks to prevent strange outliers (and because of speed, picking 3 random blocks all the time costs some time). I experimented with skipping the search for reachable holes (just testing the drop blocks only) for ply 4 and deeper. Instead of 350k to 45ok nodes/s it checked up to 750k nodes/s and sometimes reached ply 8, but the the results were (just slightly) better when applying the expensive/extensive search for all nodes, specially after introduction of the T-spin bonus.
Evaluation
As most contesters I experimented with a lot of characteristics of the field and taking them into account. In the version that run during the finals I had basically 15 parameters. Almost all parameters I had were basically a curve on their own:
Score(height) = a * Math.Pow(height, power) + delta
Where a, power and delta were determined in long (local) simulations settings. The parameter that could lead to the biggest addition to the evaluation of its own was the parameter for (double) T-spin potential.
Score(height) = 1.14 * Math.Pow(height, 2.01) + -35
{ -34, -30, -25, -16, -6, 7, 22, 40, 60, 82, 107, 134, 163, 195, 230, 266, 305, 347, 390, 437, 485, 536 }
Where the height in this case was the row where the T-spin potential existed. As you can see, Kubisme gives high values on having a potential (double) T-spin, as long as it is placed low at the field, but at the top, it gives a penalty instead.
To make Kubisme found even more T-spins, the evaluation also valued single T-spin potential, and a bonus for the two row clear by a T-block.
I also made the distinction between reachable and unreachable holes. A hole was marked as reachable when (at least) at one side two (or more) free cells where reachable. Those values ended up being -26 for reachable ones and -38 for unreachable ones.
Opponent
I tried different ways to take the current state of the opponent into account. All failed. The only thing that worked, is checking of the opponent could be kill within 2 ply, or that Kibisme could kill. Other approaches failed all when I searched more than 2 ply.
Tweaking parameters
To get the parameters right, I run zillions of games (2 ply per bot) via some genetic algorithm. Doing this with ‘only’ 2 ply, I could run roughly 25 games per second, while with 3 ply that number dropped to just 0.7 games per second.
Weaknesses
Kubisme has at least 3 weaknesses, that I tried to solve but failed on.
- If the frequency of T-blocks is (way) lower than expected, it handles positions worse than most competitors.
- In some situations holes where created without any logical explanation. Specially when the first filled row was low, and there where plenty of options to avoid this.
- Sometimes it blocked the access to accessible free cells, adding some holes. This leaded to bigger chunks of attaches unreachable holes.
Ouput
To see what Kubisme was doing I tried to make some human readable output:
01/01. +2.55 0.009s ( 0.0kN, 1.8kN/s): {left,left,left,turnleft,left,drop}
01/02. +2.84 0.012s ( 0.1kN, 6.7kN/s): {right,right,right,drop}
01/03. +2.78 0.022s ( 6.1kN, 276.7kN/s): {left,drop}
01/04. +2.88 0.061s ( 31.5kN, 512.0kN/s): {left,drop}
01/05. +3.30 0.243s (127.9kN, 527.3kN/s): {right,drop}
01/06. +3.86 0.990s (562.8kN, 568.6kN/s): {right,drop}
(..)
// cleaning up an hole
10/01. +16.95 0.002s ( 0.0kN, 15.7kN/s): {down,down,down,down,down,down,down,down,down,down,left,left,left,down,turnleft,down,down,turnleft}
10/02. +16.94 0.004s ( 0.6kN, 150.4kN/s): {down,down,down,down,down,down,down,down,down,down,left,left,left,down,turnleft,down,down,turnleft}
10/03. +17.93 0.084s ( 25.5kN, 302.6kN/s): {down,down,down,down,down,down,down,down,down,down,left,left,left,down,turnleft,down,down,turnleft}
10/04. +18.65 0.567s (213.6kN, 376.9kN/s): {down,down,down,down,down,down,down,down,down,down,left,left,left,down,turnleft,down,down,turnleft}
(..)
// Sometimes Kubisme changed his mind more than once
38/01. +31.21 0.000s ( 0.0kN, 70.7kN/s): {turnright,drop}
38/02. +31.31 0.001s ( 0.2kN, 262.9kN/s): {turnright,drop}
38/03. +31.51 0.025s ( 10.7kN, 429.9kN/s): {skip}
38/04. +31.71 0.134s ( 54.5kN, 408.0kN/s): {right,right,right,right,turnright,drop}
38/05. +32.75 0.499s (236.1kN, 473.5kN/s): {right,right,right,right,turnright,drop}
(..)
// Spotted a win in 2
43/01. +27.99 0.002s ( 0.0kN, 12.7kN/s): {down,down,left,turnright,turnright,left}
43/02. +oo 2 0.004s ( 0.4kN, 121.5kN/s): {down,down,left,turnright,turnright,left}
// Spotted a win in 1
44/01. +oo 1 0.001s ( 0.0kN, 41.9kN/s): {down,right,turnleft,down,down,down,turnleft}
Final thoughts
This competition was fun! Special thanks to my friend and colleague Ad (developer of the BBKing bot) for all the nice talks and thoughts shared. It was awesome watching games where Kubisme was totally rocking (like this game against TaroKong where it made an 1.59 point/block average!). When things went bad, because a new version was okay during test runs but failed miserably life, or was just playing crap without any indication why, it could also be some what frustrating.
In the end Kubisme was 6th out of 329 competitors. Just one spot before Ad’s BBKing (main goal anyway ;)) and best Dutch participant. I could have been more lucky in the final, but things could have turned out worse too. Winner artoppod, and hogeris where cleary the two strongest bots. After them, 6 bots had more or less the same level, including Kubisme (and BBKing).
Code
For those who like to see the actual code: https://github.com/Corniel/AIGames.BlockBattle.Kubisme
Company hierarchy: Sociopaths/clueless/losers
