Getting the World Record in Hatetris (2022)
hallofdreams.org
hallofdreams.org
Losing the World Record in Hatetris (2023) - https://news.ycombinator.com/item?id=36558013 - July 2023 (1 comment)
Getting the World Record in Hatetris - https://news.ycombinator.com/item?id=32495842 - Aug 2022 (1 comment)
Hatetris – Tetris which always gives you the worst piece - https://news.ycombinator.com/item?id=27063894 - May 2021 (245 comments)
Hatetris - https://news.ycombinator.com/item?id=4846607 - Nov 2012 (2 comments)
Hatetris: Tetris That Hates You - https://news.ycombinator.com/item?id=1253492 - April 2010 (19 comments)
Reading the back-and-forth about the Hatetris world record progression has the Summoning Salt music playing in the back of my mind, and I absolutely want to see one of his YouTube expositions on the subject.
That post that got 9 points and 1 comment should have been called "Hatetris has been SOLVED (infinite score)" instead of "Losing the World Record in Hatetris".
And indeed, the original Hatetris has been solved: a loop has been discovered that lets you get any score.
In addition to the impressive technical details, this is some really beautiful writing
Yes! This part and the cloud budget gag were also awesome. He's a great writer!
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)
TTC has such an iron grip on Tetris that even clones which don't use the name or anything similar to it are still at risk of being shut down, it's ridiculous. It's possibly the only example of game mechanics being de-facto copyrighted, in spite of game mechanics ostensibly not being copyrightable, due to some legal sleight of hand where they successfully argued that the look of Tetris is their exclusive trade dress. That look is inextricably tied to the mechanics, there's no way to make a Tetris clone which doesn't look like Tetris.
TTC exists solely to collect rent on Tetris so they're never going to let it slip away if they can help it.
If we lived in a just world, that would make the look uncopyrightable, rather than making the mechanics copyrightable.
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...
"We’re not researchers at all. We’re just two people who became obsessed with a problem and put their meager knowledge to use, beating rocks against rocks in different configurations until something resembling a spearhead came out. ... You, too, can do something like this. Find a problem. Become obsessed with it. Learn everything you can about it. Fall down dead ends. Give up, and then keep thinking about the problem at night. Have Eureka moments that lead you down other dead ends. ... "
(Eureka moments leading you down more deadends is so wel put too.)
I thought I’d work on it further and maybe write some blog or put some dev vlogs on YouTube but never got around to doing it. Might do it some day.
Till then I’ll just post some links to my Github if anyone wants to check out what I was doing:
1. https://github.com/krkartikay/AlphaZero-proto
He recommends trying NNUE on a CPU: https://www.chessprogramming.org/NNUE
Mostly because he hasn't seen anyone try it on the personal computer scale and would be interested to see how it pans out
I agree that step 1 for most beginner projects should be to start with something that works and then tweak.
[1] - https://www.educative.io/answers/xor-problem-in-neural-netwo...
I despise stories that are awesome enough to make me invested, but then make main characters (essentially) lose
I can imagine a common space of inspiration there.
I enjoyed it more than the 3 body problem: the characters are better written, their motivations make more sense despite having much less time for actually developing them.
I was really having fun trying to figure out how to make the best of an impossible to solve situation. And the SCP lore is wonderful.
I would never recommend 3 Body Problem. I found it and its sequel to be irredeemably unpleasant.
Sure, new methods will always replace old methods, just like CNNs replaced SIFT for image processing. However, I feel that beam search is one of those elementary methods that you'd always want to check first, similar to A* and quicksort. Even though there are fancy neural networks for game optimization, pathfinding and sorting, it's easier to get started with elementary methods because they're simple and tractable.
Its horrible, this is what hell will look like.
Forever trapped waiting for a piece that will never come - by design.
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.
I've been doing a fair bit with Monte Carlo search lately to explore different spaces, but mine has been in the context of Llama.cpp and Magic: The Gathering. [1] I'm going to compare and contrast my approaches with the approach used by the authors.
First, I want to ask a question (either to the authors, or to the general audience), about trees vs. DAGs. The author wrote:
> It was only after the initial tree implementation that we considered that there would be a lot of repeated wells: after all, in this game you can reach the same position in a number of different ways. A lot of deliberation and a re-factored codebase later, we opted for a directed acyclic graph (DAG) instead, taking identical positions and merging them into the same entry in a graph, rather than making them distinct entries on a tree. This complicated things significantly, but reduced our memory needs by an order of magnitude, at least. Refactoring from tree searches to DAG searches was more work than we’d expected to put in to the project, but was yielding promising results.
I'm curious about why this was such a large refactor. I've made this change in two different projects now, and in both cases, I was able to change from an exhaustive tree structure to what is essentially a DAG by simply searching for duplicate states and culling any branches that are equivalent. For instance, I implemented this change in Llama.cpp and got a >400% speedup -- and it was essentially a two-line change -- no drastic refactoring needed. [2]
Am I missing something here? How is a culled tree structure fundamentally different from a "true" DAG -- and more importantly -- would I stand to gain even more performance by switching to something else? I don't see what's so complicated about this, but I feel like I must be missing something.
> we discovered that the majority of our time was now spent accessing the hash of positions, since whenever a new positions was explored, we had to check if it already existed. A bit of a further dig and we discovered that most of that time was spent running a hashing algorithm on the positions data for comparison. Which again, made sense…but we knew all our positions were unique among each other. We didn’t need to do any hashing, we could just use the position’s representation as a key directly, if we could find a reasonable way to encode it. So we replaced the hashing algorithm with our own custom version that encoded the position as a binary representation of position, rotation and piece type. This was much faster than having to hash a position, and we knew it guaranteed uniqueness. This doubled the speed of our move finder.
In the case of my Magic: The Gathering searcher, I am using a text summary of the game state (essentially `gameState.toString()`) -- what's on the battlefield, what's in the hand, what's in the graveyard, how much mana is available, etc -- as the key. I sort the cards in each location alphabetically, so that it doesn't matter which order they were put there -- only what's actually there. This GREATLY increased the speed of execution, but again -- it was just a simple change.
That said, the fire graph showing how much time is spent in string processing is eye-opening, and it makes me think that I should probably profile my Python code with a similar tool, because a binary representation might be worth it.
It's also fascinating to me that the author attempted to train an ML model to play the game. My initial thought was that an exhaustive search was the only way to approach this (because it's perhaps the only way to arrive at a max score that is provably correct), but I think I am not truly appreciating the vastness of the search space at play here, and exhaustively searching all possible inputs might just be too unimaginably large.
All that said, this read has kept me on the edge of my seat. Kudos to the developers and authors for writing this up for us -- and CONGRATULATIONS ON CAPTURING THE RECORD!!! Even though it was later surpassed, that should in no way diminish the satisfaction of the accomplishments here.
It's an absolute blast reading this. I've enjoyed it, I've learned a ton, and I'm going to try implementing some of their suggestions in my own projects!! Thank you!! It's articles like this that keep me coming back to Hacker News day after day. :)
I think when we did the math with our best emulator it would take 100 billion years? There are, by our estimation or a game lasting a thousand moves 10^23 possible wells. With current computing, even if we threw all the resources of the planet at it, we'd still be a few orders of magnitude short of finishing in our lifetimes. It is a very very very large search space.
>Searching for duplicate states and culling any branches that are equivalent.
Branch pruning and comparison are both expensive relatively speaking. You want, in a perfect world, to essentially have a hashmap lookup for duplicate nodes, so deciding if its new or not is O(1), rather than having to look at your node and all its children to know if it's duplicated. It doesn't matter unless you're really chasing performance.
Also this was our first serious rust project so implementing it was a bit more daunting than expected. In a sane codebase it's probably not a bad refactor, at the point we did it we had six methods with a bunch of stuff jammed into them and names like `explore_tree` so it was a challenge, made significantly easier by rust types, and more frustrating by the borrow checker.