Getting the World Record in Hatetris (2022)

I think one of the general takeaways about ML is that barring a few experts, its really challenging to reason about your system. Like, yes, you might expect that a convolutional layer will behave in a specific way under ideal conditions, but the way that behavior manifests is often wildly hard to predict during the early days.

I agree that step 1 for most beginner projects should be to start with something that works and then tweak.

Very good article. I hadn't seen it before. I wonder why it never mentions SAT solvers at all. I can believe that the approach is hopeless, but a few words on the topic would still have been nice.

Lego protection was based on patents. They tried to play the "make a slight variation and extend the patent" game but were slapped down. Now anyone can make Lego-compatible blocks legally, though of course they can't identify it as Lego. (Although based on the various ones I've gotten as presents, Lego never had anything to fear. The knockoffs sucked before the patent expired and they didn't get any better afterwards. It's still a terrible idea to let knockoffs mix with your real sets, and that's 0% Lego "purism" and 100% pragmatics. Maybe there's a good specific knockoff somewhere, but the odds seem poor.)

TTC protection is based around other IP constructs. Here's a good sample link from a source that seems to know what is up, which I link to for the legal analysis rather than the details of a 2009 court case: https://www.gamedeveloper.com/game-platforms/exclusive-i-tet...

From Dave:

Short answer: SAT solvers are hard.

Long answer: I actually discussed it with Tim once, long after part 2 of our blog post and after the whole thing settled down. Tim was making an SAT solver based on a post about a homemade Sudoku program that got out of hand (https://t-dillon.github.io/tdoku/), and HATETRIS has a binary grid representation, so it's a logical thing to attempt. So, how would you answer the question of the longest possible game with SAT? The idea would be that you can start with a set of wells S_0, generate a new set S_1, and continue generating sets of all possible wells until you find some N for which S_N is not satisfiable; N-1 is therefore the longest game.

Suppose S_0 consists of the starting well, W_0. W_0 is a conjunction of 160 different clauses, each of which is initially set to 'not':

W_0 = !x_0_0 && !x_0_1 && ... && !x_15_9

Once you have that, you need some way of getting from W_0 to its possible descendants. There are 2457 possible piece positions in a standard 16x10 HATETRIS well, each of which interacts with at most four squares (fewer for the piece positions within the top four lines), and each of which can be reached at most four ways (from another piece moving down, moving right, moving left, or rotating). This puts a rough estimate of ~39,000 clauses needed for a function which converts W_0 into its children: W_0 -> W_1a || W_1b || W_1c || ... = S_1. Which isn't too bad, as far as SAT solvers go.

The problem is that this is very similar to what our first version of the emulator did and that version was a hundred times slower than our current version. SAT is NP-complete in the worst case, and without some huge simplification from putting it in Boolean form, it didn't seem likely to be worth the additional cost. I think there's still a possibility for some kind of solver to aid searches, e.g. "Given this specific well, you need to clear lines 5 and 6 in order to clear line 4, and you need to clear lines 7, 8, and 9 in order to clear line 6...", and I think certain properties (such as the minimum number of pieces needed to clear a given line) are computable with SAT, maybe even to the point of making a a pruned-but-provably-optimal game tree search feasible.

Putting the raw emulator in SAT form is natural. Putting constraints like these in SAT form requires coming up with a new level of abstraction ourselves. Our only attempt at it was in the Mumble Mumble Graph Theory section; what we learned is that making a new level of abstraction is a lot harder, and we don't know how to do it.

So after reading "Getting the World Record" I was brimming with ideas on how one could improve upon their work, only to be squashed upon reading "Losing the World Record." All parties involved has done an excellent job breaking the game, and aside from the (really) hard questions of understanding game, there's not much left except further exploring the parameter space.

I simmered on the latter overnight, and a few thoughts occurred to me:

- a parameter for fullness (holes + filled blocks that are below the "surface"). It might be its own parameter, or used to augment other parameters to discourage behavior that might lead to a the end game.

- reachable surface height: rather than taking the lowest height of the surface, compute the reachable height of the following piece

- an alternate definition of reachable surface height: the lowest point any of the seven pieces can reach (perhaps augmented by the number of pieces that can reach it)