- Updated Friday, May 6th 2016 @ 00:47:02
When I was working on my bot I had some ideas that you guys may find interesting. With 2 weeks left maybe you might find some of this useful. I just wanna see if someone can improve their bot and take down the mighty hogeris.
To preface and give some context: My heuristic works like this:
Gather various features about the board and quantify them as a number. Call these x1, x2, x3, ... xN. For example, the number of holes in a board is one of my variables. Another example is the overall smoothness of the board (sum of the absolute value of difference between every adjacent column).
Multiply these variables with some constants c1, c2, ..., cN and add them all up. The score is computed as c1 * x1 + c2 * x2 + c3 * x3 +... + cN * xN. This is your score and the fields with the highest scores are the best. The coefficients ci can be negative or positive. Variables which measure bad things, like holes, get a negative coefficient.
So I had a couple ideas about the variables when I was watching the games.
Measuring the smoothness of the board
So initially I measured the smoothness of a board by summing up the absolute value of the differences in the heights between every pair of adjacent column. But I noticed that you might have more success if you sum the square roots of these differences instead. So for example, if the absolute value of the differences between all your columns are d1, d2, d3,... dN, take the sum of sqrt(d1) + sqrt(d2) + ... sqrt(dN) instead. Then you minimize this number instead.
I noticed that this produced more "comboing" behavior. I think this is for the following reason: So this smoothness number is something you want to minimize (smoother fields are presumably better). If you minimize the sum of a bunch of square roots, it produces the effect that you penalize large columns in the field less and punish small jaggedness in the board more. Or to put in math terms: Suppose the difference between height of adjacent columns is stored as: <d1, d2, d3, ... , d9> Then minimizing the square root of the sum of the differences has the effect of favoring "sparse" vectors as opposed to bigger ones. <3, 0, 0, 3> would have a smaller smoothness score than <1, 1, 1, 1>. Because sqrt(3) + sqrt(3) < sqrt(1) + sqrt(1) + sqrt(1) + sqrt(1).
In some way, minimizing smoothness is like minimizing the norm of the vector that contains all of your differences between columns. So this is like changing up the norm function you choose.
So we all know holes are bad. I define a hole as a empty square surrounded by four full squares on each edge. But another thing is that you probably don't wanna place pieces on top of holes either. If you already have a hole, you probably want to avoid placing pieces on top of that hole since it makes downstacking harder. So there are two factors to holes: Holes are bad, and making holes deeper from the surface of your stack is also bad.
I had an idea to model this in the following way. Every hole counts as 1. For each hole, its depth also contributes a small term to its count. So for example, let's say I had a hole that was 3 levels deep. Then the hole's contribution to the "hole Score" could be 1 + sqrt(3) (sqrt(3) for a depth of 3). OR, you could model it like a geometric series, so it's hole score could be 1 + 0.5 + 0.5 * 0.5 +0.5 * 0.5 *0.5. For a depth of 3, you add the first 3 terms of a geometric series for a value of your choice. With all things being equal, this has the effect that your bot prefers positions where holes are less deep. Also, you make sure that this small term shrinks for each depth, so that your bot doesn't care about placing pieces on top of the holes that are too deep. If you follow the geometric series model, then this this is naturally accounted for since the terms in a geometric series shrink super fast.
Using these principles, you can construct a "hole score" variable that you minimize.
Measuring opportunity cost
I think in the early game, it is bad to clear lines for low points. You wanna go for the tspin doubles and whatnot. I found some success in adding a variable which measures the opportunity cost of clearing lines. You could arbitrarily say that you want 3 points per line that is cleared in the early game. The opportunity cost would then be the amount of potential points you lost per line cleared. This opportunity cost factor could be a negative term in the total score. And then as the height of the board grows up, you could have the term go to zero.
- Created Friday, May 6th 2016 @ 12:06:46
Hm, interesting) Adding your type of smoothness prevents t-spin preparing) I have this criteria for smoothness: if two adjacent columns have heights difference more than 2 - penalize it by every extra step.
- Updated Friday, May 6th 2016 @ 22:23:04
Interesting, yeah I see what you're saying.
So for example, let's say the our board is just 5 columns wide. If the height of our columns is [1, 1, 0, 1, 1] that has a worse smoothness than [0, 0, 0, 0, 0] or [0, 0, 0, 0, 2]. And one might argue it is better since it offers t-spin opportunities.
I'd say that this might be okay because the smoothness score is only supposed to measure smoothness and not something. Ideally you would have other variables which would counterbalance this. But ya good point, i'm gonna further tinkering and play around the variables some more.
- Created Saturday, May 7th 2016 @ 04:05:14
I used fast learn, maybe search gone to local minimum area where big smoothness is good thing - so t-spins are impaired. Last time i remove all redundant factors, making eval simple and orthogonal. And i can win someone > 2300 elo, but not someone who close to me. I have few wins against your bot) Strange thing.
[0,0,0,0,0] is not bad - it allow O placing and stacking will be low with L, J, T. But this position need at least one hill for S,Z.
Ideally we need to exclude t-spin preparing place from scoring surface, holes. But it is hard to make clear.
- Updated Saturday, May 7th 2016 @ 22:48:48
I am hoping to make some final improvements this weekend so this has been very insightful. My bot tends to work in the same way by analyzing a set of heuristics and multiplying them by a set of coefficients.
Analyzing Bumpiness I actually tended to take the opposite approach to cowzow and square the heights before multiplying them by a coefficient. Although similarly to neurocore I ignore a height separation of 1 and I actually reward a height separation of 0. This results in my bot often ending up with a bumpy map of small height separations, although, as neurocore mentioned it is good for creating t-spin opportunities. This does, however, stop my bot from creating very deep "valleys" as I call them. It will instead choose to create a hole if it has too rather than create deep valleys.
Holes When measuring holes I classified a hole as any empty cell that has a filled cell above it. Then I penalized based on a linear coefficient between the distance from the hole to the top of the stack. I tried only classifying holes based on being fully surrounded by filled cells but I found my bot would make really weird decisions so I reverted back.
Looking ahead at uncertain pieces This was the most difficult area for me conceptually, I am still not entirely sure what the best thing is for me to do with the information I get about uncertain pieces. How much weight should I put onto the possible pieces? Do I consider the best-case scenario, worst case scenario, the average case? Ultimately I ended up looking at the best case scenario putting about .5 of the weight of the first two moves on the 3rd move then .5 of that on the fourth move. The result of this is that my bot tends to be very polarized in it's game play. When the best pieces show up it wins games very quickly, even managing to take a game off of hogeris while still ranked worse than 20th place.
Speeding up my bot After getting my analysis function to a place where I was fairly happy with it I began pushing my bots time bank to the limit to see how far I could look ahead. After reading a post in one of earlier discussion I decided to transition from a  array to storing the board state inside the bits of integers. This gave me a speed up to approximately 4X and was able to get my bot looking at depth 4 but not to a full breadth.
This competition has been an awesome experience and I am really hoping there will be more open discussions like this once the bots are locked down and we can all reveal our entire strategies.
Good luck to everybody!
-Marty & DawgBlockerson
- Created Saturday, May 7th 2016 @ 18:53:23
I predict that hogeris will not win, unless he comes with an update (it seems that his version 35 was stronger than version 36). My data suggests an other winner (too bad, it will not be me, although I hope to make it to the final 8).
- Created Sunday, May 8th 2016 @ 06:27:18
About uncertain pieces.
My bot searches 4 full moves in Alpha-Beta-like framework. It means that i have in mind worst case. My logic was that mechanism choosing next piece is my opponent and he tryes to improve his position.
But, actually he doesn't my opponent. He acts randomly. So we can make decision relyed both on worst case and average case with some percent. Just idea, glad it found realization in DawgBlockerson code)
I also tryed use theory of probabilities for predict which pieces are preferable to appear (Bernulli formula). But bot starts to play very bad.
- Created Tuesday, May 10th 2016 @ 01:46:35
I can promise a full story about my bot. After the competition :)
- Created Tuesday, May 10th 2016 @ 04:30:18
Awesome, TaroKong! I am really looking forward to hear about everyone's bots as I am sure everyone has spent a huge amount of time on them. This has been a great learning experience for me and I hope to learn even more after the competition closes. With a little luck my bot will make the top 24!
- Updated Tuesday, May 10th 2016 @ 16:19:53
I am also looking forward to hearing about everyone's ideas after the competition. I learned a lot about coding (and Tetris). Good luck everyone!
- Created Saturday, May 14th 2016 @ 11:57:33
I'll also will write some blog about my bot, and publish it's code. (Make my Git repo public)