Archive for May, 2016

Kubisme BlockBattle AI

Sunday, May 29th, 2016

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 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:

  1. I have enough space to rotate my block before dropping it
  2. I have a (potentially reachable) hole I can get a block in
  3. 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.


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.


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.


Kubisme has at least 3 weaknesses, that I tried to solve but failed on.

  1. If the frequency of T-blocks is (way) lower than expected, it handles positions  worse than most competitors.
  2. 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.
  3. Sometimes it blocked the access to accessible free cells, adding some holes. This leaded to bigger chunks of attaches unreachable holes.


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).


For those who like to see the actual code:

Exact TechTalks 2016

Thursday, May 19th, 2016

Machine learning is hot. If my colleague Ad and where not aware before we decided to do our Exact TechTalks 2016 about  applying this on the Exact Online (EOL) domain, we would have been afterwards. Half the board entered our talk, including the CEO at the first session. Zillions of questions by the attendees, and full-house 5 times in row.


It might be wise to point out what these Exact TechTalks where about in the first place. It was an internal event where the different development teams could give 20 minute presentations on a subject they are currently working on. Ad and I represented the EOL System team (responsible for the core libraries and framework of EOL).

So what is Machine Learning?

Specially since AlphaGo beat a human Go player, machine learning and AI became both hot and mythical. So, our main goal was to demystify it, and show with an simple example that it can be easily applied, if you have (good) data.

Machine Learning:

Writing a program to perform a task
With more information, the program performs the task better
Without having to change the code

That’s all. Yes, you can apply it by building complex neural networks, and dedicated server parks, but in most cases, you don’t have to go down that road. A consequence of this is also that without proper data, you will not be able to learn your machine anything.

Allocating bank statements

We showed some functionality that can take up a lot of time while bookkeeping: allocating bank statements. By comparing new imported statements with historical data that was already assigned to a GL-account and an account, in a lot of cases new statements can be matched automatically. A developer has to build some specific matching algorithm to determine which historical record is the closed match. This is called statistical classification.

User experience

Speed is important in this scenario, as a user does not like to wait. In our test set-up we where able to test a new entry against 450 historical records within 0.29 milliseconds, so 1.5 million matches per second. But even more important is how to present the findings of the algorithm to the user. Does a user like to be bothered with poor and potential wrong matches? Or with (almost) identical matches? Not per se. And which options should there be to show the user what was allocated automatically?

Food for thought

Ad and I split our talk in two parts: 10 minutes of talking/presenting, 10 minutes of discussion. Although stated clearly during the talk, still quite some people thought it hard to believe that machine learning could be that simple. Some of them where searching for the silver bullet to solve all issues at once. Spoiler alert: such a bullet does not exist in this case. But most questions and remarks where about the potential issues of matching automatically and by that making mistakes. And that is good! Because how brilliant your algorithm might be, there will be inconsistencies, exceptions, on previous decisions. If you don’t understand the data and/or the domain, you will not be able to come up with a solution.

What’s next?

As members of the EOL System team, this part is not our responsibility. The functional team that is responsible is, guided by us, now working on shipping it. Besides that, a lot of awareness is raised throughout Exact. You should not be surprised if the customer will benefit from that in the near future.