The HATETRIS algorithm has always been perfectly deterministic, with no "RNG". When I originally created it in April 2010, the way it worked was to examine the current well state only and use this to determine which piece to return. If the well was the same, then the piece returned was the same. This design choice had two major implications:

1. It meant that replays could encode the player input only, omitting the AI's piece choices. This made replays shareable and it made it impossible to "forge" a replay which sidestepped the real AI to gain more lines.
2. It meant that if you ever found a way to return to a previously-seen well state — not necessarily the empty well state — you could repeat that same sequence of inputs forever to gain unlimited lines.

In the earliest years of HATETRIS' existence it seemed highly unlikely that a loop existed. Over the course of April and May 2010 the record score for the game rose steadily from 11 lines by Atypical to 30 by Deasuke, where the record then remained for more than seven years. In June 2017 a new record of 31 was reported by chromeyhex, which remained unchallenged for a further four years. (The full history, with replays for all record runs, can be found here.) All the record replays shared during this period showed a game well which rapidly accumulated entropy. Significantly reducing the height of the stack appeared to be impossible. At this time, I felt that it was probably impossible to catch HATETRIS in a loop, although I also felt that it was probably completely intractable to prove this, due to the inherent difficulty in analysing the game of Tetris.

I don't know exactly how any of the records in this first phase were obtained, and I never directly spoke to most of those who achieved these records. However, my gut feeling is that they were all achieved "manually", with a human being playing the game to the best of their ability.

Loop prevention

In June 2021 a new era of HATETRIS records began. In the space of two weeks, using beam searches, new player knewjade raised the record to 32, 34, 41 and then 45 lines. (Their writeup, in Japanese.) Although I still felt that it was impossible to demonstrate a loop, there was renewed interest in the game, so I took this opportunity to add a long-planned fail-safe to the HATETRIS algorithm.

As of June 2021, the HATETRIS algorithm is still perfectly deterministic, but it now maintains a list of all previously-seen wells. If it detects that any particular piece can even theoretically be placed in such a way as to lead back to a previously-seen well, that piece is deprioritised and a different piece is returned instead. This has several significant effects:

Firstly, the only way to actually see a repeat well, now, is to reach a situation where any of the seven pieces can be placed in the current well in such a way as to produce a previously-seen well. (Not necessarily the same well for each piece.) Only when this happens does the algorithm give up and give you what you need. Finding a loop would have been one thing; finding a "seven-fold loop" and actually forcing a repeat well seems absolutely impossible to me.

Secondly, the HATETRIS algorithm is now almost certainly undefeatable. That is, it is impossible to play forever against it and get unlimited lines. Even if you find a seven-fold loop, and place your piece in such a way as to successfully repeat a well, the AI won't allow you to continue merrily around your loop. It knows about the next well in the loop too, and it'll give you a different piece this time instead. The AI will fight you every step of the way, constantly forcing you to branch out of the existing graph of visited wells, to chart new wells. You, the player, would need to find a strategy where no matter what pieces are provided, you can still make lines — because otherwise, the AI will find a way to break you out of that web of "known space" and force a loss. But this seems like it has to be impossible, because Brzustowski (1992) proved that certain sequences of pieces will force a loss, and Burgiel (1997) went on to prove that even an AI which produces alternating S and Z pieces, with no additional logic, eventually forces a loss. Eventually, I believe HATETRIS would either find one of these provably undefeatable strategies, or (much more likely) a simpler, more hostile unbeatable strategy, and force a loss.

From the players' (attackers'?) perspective, this modification to the HATETRIS algorithm did not change anything. No one up to this point had ever tripped the fail-safe, and no existing replays were invalidated when the algorithm was updated. And, yes, I do have unit tests for this.

The first loops

From 2021 to 2022 a fight for the record ensued, with knewjade and others (David & Felipe, Tim) applying similar beam search techniques and various heuristics to drive HATETRIS records well into three digits. It was very impressive to watch.

In November 2022 knewjade announced two things: a ridiculous new record of 289 lines, and the incredible discovery of the first replay to actually trip the loop-prevention logic. (Their writeup, in Japanese.) This replay executes a particular sequence of moves to gain 95 lines and reach a particular well, then executes a further sequence of moves to drop 25 more pieces, gain 10 more lines, and return to that exact well. At least, that's what would happen, but HATETRIS detects what's happening and averts it by providing a different piece at the last step in the cycle. The following day, Tim announced a shorter replay with a "stem" of 68 lines and a repeating cycle of 16 lines (40 pieces).

I have to admit I was amazed. In response to this, I added a new AI to the HATETRIS game. Called "HATETRIS Mild", this AI is the original HATETRIS algorithm without the loop prevention logic. As demonstrated above, with this AI, it is possible get unlimited lines.

I'm also starting a new records table, this one for the shortest loop using HATETRIS Mild. Loop length is measured by the number of lines required to show a repeat well. You'll find the records at the end of this article.

What next?

It's hard to know what people are working on.

I imagine that research into attacking HATETRIS is continuing. I would not be surprised to see much higher scores. My understanding is that in order to carry out these huge beam searches, attackers reimplement the HATETRIS algorithm in high-performance languages like Rust, which can generate new pieces orders of magnitude faster than the JavaScript-based version which runs in the web browser. I believe that, for performance reasons, none of the attackers implemented the fail-safe logic. This may have to change now... but then again, attackers may proceed without it, and try to intentionally avoid loops somehow.

It would also not surprise me to see shorter loops found in the future.

I am impressed and flattered by the incredible amount of work which has been dedicated to attacking HATETRIS, and amazed by the results. At the time I created it, in 2010, I had no idea just how much attack the AI could withstand. It's really a very simple algorithm. You never know, do you?

Although HATETRIS remains the hardest Tetris AI I'm aware of, it's pretty clear that the world is ready for a new generation of Tetris AIs. I feel that such an AI should be developed using similar machine learning techniques to these recent replays... however, I have no intention of trying to do this myself. If you want to try it, be my guest. All I ask is, please don't call your AI "HATETRIS" or anything derived from it. Make it an original work, with an original name.

Shortest known loops

Be sure to load the HATETRIS Mild AI before inputting these replays.

2022-11-26

knewjade is the first announce a loop, visiting a repeat well after 105 lines: "RRRDDDDDDDDDDDDDDDDDDUURRRDDDDDDDDDDDDDDDDDUULLDDDDDDDDDDDDDDDDDDURRRDDDDDDDDDDDDDDUULLLDDDDDDDDDDDDDDDDDULLLLLDDDDDDDDDDDDDDDULLLLLDDDDDDDDDDDURRRRDDDDDDDDDDDDDDDUUULLLDDDDDDDDDDDDDDDURRRDDDDDDDDDDDDUUULLLLDDDDDDDDURRRRDDDDDDDDDDDLLLLDDDDDUURRRRDDDDDDDDDULDDDDDDDDDDDDDDLDUDDDDDDDDDDDDDDDDDUUURDDDDDDDDDDDDDDDDUDULLDDDDDDDDDDDDLLDURRRRDDDDDDDDULLDDDDDDDDDDDDDLDRRRDDDDDDUURRDDDDDDUUDDDDDDULLLLDDDDDDULLDDDDDDDDDDRRRDDDDUDDDLLDDDDDDDDDLDULLDDDDDDDRDDDDDDDDDUUULLDDDDDDDDDRDDDDDDRRDUDULLDDDDDDDDDRDDDDDDRURRDULLLLLDDDDDDURRRRDDDDDDDRRDDDDDDDDDULLDDDDDDDDDRDDDDRUDDDUUULLDDDDDDDDDDDRDDDULUDULLDDDDDDDDDDDRDDDRRUDDDULLDDDDDDDDDDDDRDDDDURRRRDDDDDDDDUUULLLLDDDDDDDUURRRRDDDDDDUULDDDDDDDDDDDLDDURDRRRUDDURUDULLLLDDDDDUUDDDDDDDDDDDLDDURRRRDDDDUURRDDDDDRDUULDDDDDDDDUDDDDDDRDDDDLLLLDDDUUUDDDDDDDDRUDUUUDDDDDDDDUDUULDDDDDDDDDDDDRRRDDDDDURRRRDDDDDULLLLLDDDDDDDULDDDDDDDDDDDDDRRRRDULDDDDDDDDDDDDDDRRRDLLDDDDDDDDDDDDDRRDDDDUUULLDDDDDDDDDDDDDLDULDDDDDDDDDDDDDDRRDUULDDDDDDDDDDDDRRRRDUUULDDDDDDDDDDDDDDDDUDLLLLDDDDDDUUULDDDDDDDDDDLLDUURRRRDDDDDRDDDDDUUDDDDDUULLDDDDDDDRRDDDDLDDRDDLLLDDDDDDDDRRDDDDLDDUDDLLLDDDDDDDDDDLLLLDDDDDDDULLDDDDDDDRDDDDRURRRDUUULLDDDDDDDDRDDDDDULDUDULLDDDDDDDDRDDDDRUDDDUUULLDDDDDDDDDDRDDDULUDULLDDDDDDDDDDUDURRRDDDDDDDDDDDDDDDDDDDDDDDDDDDULLLLDDDDDDDDDURRRRDDDDDDDDDDDURRRRDDDDDDDDDRRRDDDDDDDLLDDDDDDDDDDLDURDDDDDDDDDDRDURRRRDDDDDUURRRDDDDDDDDULLDDDDDDDDRRDDDDLDDDUULLDDDDDDDRRRDDDDDURRRRDDDDDULLLLLDDDDDDDDDUUULLDDDDDDDDDDDRDDDRRDUDUUULLDDDDDDDDDDDDRDDDRUDULLLLDDDDDDDDUUULLDDDDDDDDDDDDDRDDUDULLDDDDDDDDDDDDRRUDDDLLDDDDDDDDDDDDLDUUULLDDDDDDDDDDDRDDULDUDUUULLDDDDDDDDDDDDRDDRRRDUDULLLLDDDDDDDDDDULLDDDDDDDDDDDDRDRRURDUUULLDDDDDDDDDDDDDRDDDRUDUUULLDDDDDDDDDDDDDDRDDUDURRRRDDDDDDDDDRRDDDDDDDDUUULLDDDDDDDDDDDDDDDRUDURRRDDDDDDURRRRDDDDDDDDUURDDDDDDDULLLLLDDDDDDDDDDULLDDDDDDDDDDDDDDDDLLLLDDDDDDDDLLDDDDDDDDDDDDLDLLDDDDDDDDDDLDUUULLDDDDDDDDDRDDDDDULUDULLDDDDDDDDDRDDDDDDULLDDDDDDDDDDUDUUDDDDDDDDDDDDDRRDDRDDUDDDDDDDDDDDDDDRRRDUUUDDDDDDDDDDDDDDDDRUDUURRDDDDDDDDDDDDDUUULDDDDDDDDDDDDDDDDRUDURRRRDDDDDDDDDDDUURRRRDDDDDDDDDUUULLLLDDDDDDDDDDDDUUULLLLDDDDDDDDDLLLLDDDDDDURRRRDDDDDDLLLLDDDDUURRRRDDDDUURDDDDDDDDDDDRDULDDDDDDDDDDDDDDDDDRRRDDDDUURRDDDDULDDDDDDDDDDDURRRDUUDDDDLLLLDDDDUUULLDDDDDRDDDDDDDDDUDULLDDDDDRDDDDDDDUDDDUUULLDDDDDDDRDDDDDDLULUDULLDDDDDDDRDDDDDDURDDUURRRDDDDDDDULLDDDDDDDDRDDDDLDDDUUULLDDDDDDDDDRDDDDLLDULLDDDDDDDDDDRRRDDDURRDUUULLDDDDDDDDDDRDDDDDRUDUUULLDDDDDDDDDDDRDDDDUDUUULLDDDDDDDDDDDDRUDDLUDULLDDDDDDDDDDDDRDDRRRUDRDURRRRDDDDDDDDDRRRDDDDDDDDUUULLLLDDDDDDDDDDUURRDDDDDDUULDDDDDDDDDRRRRDLLDDDDDDDDDRRRDUULDDDDDDDRRDUUULLDDDDDDDDDDDDDRDDRUDULLLLDDDDDDDDULLDDDDDDDDDUDUUULDDDDDDDDDUDULLDDDDDDDDDDDDDUDULLDDDDDDDDDDDDRDDDDURRRRDDDDDDDDDDURRRDDDDDDDDDDLLDDDDDDDDDDDDURRRRDDDDDDDULLLLLDDDDDDDDDDLLLLDDDDDDDDURRRRDDDDURRDDDDDDDRDUURRDDDDDRDLLDDDDDDDDUDDDDDDRDDDLLLLDDDUUUDDDDDDDDRUDUUUDDDDDDDDDDDLDDDDRRDUDURRRRDDDDUUUDDDDDDDDDDDDURDUUULLLLDDDDDDDDDLLLLDDDDDDLLLLDDDDUUULDDDDDDDLLDUUUDDDDDDDDDUDRRRDDDDUURRDDDDUUDDDDLLLLDDDDUUULLDDDDDRDDDDDDDDDDDRUDUUULLDDDDDDRDDDDDDDDUDUUULLDDDDDDDRDDDDDDLDDDRUDULLDDDDDDDRDDDDDDUDDDULLLLDDDDDULLLLLDDDDDRRRDDDDDDDDUUULLDDDDDDDDDRDDDDULDLDUDUUULLDDDDDDDDDDRDDDDULDUDUUULLDDDDDDDDDDDRDDDDUDUUULLDDDDDDDDDDDDRUDDLUDULLDDDDDDDDDDDDUDUUDDDDDDDDDDDDDDRRRDDUUULLDDDDDDDDDDDDUURRRRDDDDDDDDDDDURRRRDDDDDDDDUURRRRDDDDDDUURDDDDDDDDDRRDRRRDDDDDUUUDDDDDDDDDDDDDDDUDULLDDDDDDDDDDULLDDDDDDDDUUUDDDDDDDDDDDDDDULDUDUDDDDDDDDDDDDUDDDDDDDDDDDDRDDULLLLLDDDDDDDDDDURRRRDDDDDDULLLLDDDDDDDDDDUURRRRDDDDDDDDDDDRRDUURRDDDDLLDDDDDDDRRDULLLLLDDDDDDLLDDDDDDDDUULLLDDDDDUUULDDDDDDULLDUDUUDDDDDDULLDDDDDDUDUULLLDDDDDDUURRRRDDDDDDDUDDDDDDDDDDDDDDUDUUDDDDDDDLDRDDDDDDDDUDDDDDDDDDDDDDDLLLLDDDDDDDDUUULLLLDDDDDDUUURRRRDDDDDDDDURRRRDDDDDDURRDDDDDDDUURRDDDDDUUULDDDDDDDRDDDURRDUUULDDDDDDDDRDDDDDRRDUDURRRDDDDULDDDDDDDDRDDDDDRDDDDUUULDDDDDDDDDDRUDUUULDDDDDDDDDDDDDDRRDUDULDDDDDDDDDDDDUDUUULDDDDDDDDDDDDRDDDUDURRRRDDDDDDDDDUUURRRRDDDDDDDUURDDDDDDDDDDUURRDDDDDDDDULLLLDDDDDDDDDURRRRDDDDDUURRDDDDDDUUULLLLDDDDDDDRRRDDDDUURDDDDDUUULLDDDDDDDDDDDDRRDUDUUULLDDDDDDDDDDDDDRDDUDULLLLDDDDDDULLDDDDDDDUDURRRDDDDULDDDDDDDDDLDDDUDUUULDDDDDDDDDDDDDDUD" (95 lines) followed by any number of repetitions of "UUULDDDDDDDDDDDDDUDDDDDDDDRDLLDDDDDDDDDDDURRRRDDDDDDDDUUULLLLDDDDDDDDDUURRRRDDDDDDUURDDDDDDDUUULLDDDDDDDDDRRDUDUURRRDDDDDDULLDDDDDDDDDDDDDUDULLLLDDDDDDDDULLDDDDDDDDDUDUUULDDDDDDDDDDDDDUDLLDDDDDDDDDDDUUURRRRDDDDDDDDDUURRDDDDDDDDURRRRDDDDDDDRRRDDDDDDUURDDDDDDDUUULLLLDDDDDDDDDUUULLDDDDDDDDDRRDUDULLDDDDDDDDDDDDDUDULLLLDDDDDDDDULLDDDDDDDDDUDURRRDDDDDD" (10 lines per repetition).

2022-11-27

Tim's shorter loop is just 84 lines: "DDDDDDDDDDDDDDDDDRRRDDDDDDDDDDDDDDDDDDLLLDDDDDDDDDDDDDDDDDRRDDDDDDDDDDDDDDDDLLLLDDUDDDDDDDDDDDDDRRRRDDUDDDDDDDDDDRRRRDUDDDDDDDDDDDDDLLLLLDDUUDDDDDDDDDDDDDDRRRDUDDDDDDDDDDDRRRDUUDDDDDDDDDRRRDUUDDDDDDDDDDDDDRRDUUUDDDDDDDDDDDLLLLDUUUDDDDDDDDLLLLDUUUDDDDDDDDDDDDLDDLLDUDDDDDDRRRRDUUUDDDDDDDDDDDDLDDDDRUDUDDDDRRRRDDDDDDDDDDDDRDDDDDDDDDDRRDUDDDDDDLDLDDDDLDDDDDDDLLLLDUUUDDDDDDDLDLDDDRDDDDDUDUUUDDDDDDDDLDLDDDRUDDDLUDUDDDDDDDDLDLDDDRDDDDDDDDDDLLLLDDUDDDDDDLLLDUDDDDDDDDLLDUDDDDDDDRDRRDUUDDDDDDDDDDRRDUDDDDDDDDDUDDLULDDDRDRDRUDDDDDDDDRRRDUDDDDDDDDDDUDDLULDDDRDRUDUUDDDDDDRRRRDUUDDDDDRRDUUDDDDRDUDRRDRDDDUDRRRRDDDUUUDDDLLDDDLLDUDDLLDDDDRDDRDDDUDDLULDDDRUDUDDDLLDLLDUDDDLLDDDUDUDDDDLDDDDDRURDDUDDDRRRRDUDDDDLLLLDUDDDDDLDDDDDDUUUDDDDDDDLDDDRDRUDUUUDDDDDLLLDDDDDDDDLLDDDDDDDDDLUDDRDDUDDLDDUDDDLLLLLDDUDDDRRRRDDDDDDDRRDDDDRRRDDDDLDLLDUUUDDDLDDDRUDDDLUDDUUDRUDDDDRDUDLDDDDDUDDDRRRDDDDLDLDLLDUUUDDDLDDDRUDDDDLUDDUUDDULLDUDUUUDDDDLDDDRUDDDDLUDDDLDDUUUDDDDDLDDDRUDDDDLUDDUDUUUDDDDDDLDDDRUDDDDLUDUDDDDDDLDDDRDDDDDUDDDDDRRRRDDDDDDDRRDUUUDDDDDDDDLDDDRDDRDRUDUUUDDDDDDDDLLLLDUUUDDDDDLLLLDUDDDLLLLDUDDDRRRRDDDUUDDDRRRRDDDDDDDLDLLDUUUDDDDDLLDUDDDDDDDDLDDDRDDRURDDUDDDDDDDDDLDDDRDDDUDDDDDDRDUUUDDDDLDDDRDDDDLDDDRDRUDUDDDDLDDDRDDDUDDDDUDDDDRRRRDUDDDDRRRDDUUUDDDDDDLDDDRDDDULLUDDUDDDDDDLDDDRDDDUDRDDDUUUDDDDDDDDLDDDRDDDULUDUUUDDDDDDDDDLDDDRDDDRUDUDDDDDDDDRRDUDDDDDDDDDLDDDRDDDDDUDDDDDDDDDDLDDDRDDDUUUDDDDDDDDDDDLLLLDUUUDDDDDDDDLLLLDDDDDDDDLLLDUDDDDDDDRRDDUDDDDDRRRDDDUUUDDDDDLLLLDUDDDDRRRRDDDUDDDRRRRDDDDDDRRDUDDDDDDDUDDDDDDDDDDDDLDLLDUDDDDDDDDDDDLLDDDUUUDDDDDDDDDDDDDDDRUDDDDDDDDDDUDDDDDDLLLLDUDDDDDDLDDDUDDDDDRRRRDDDDDDDDDDRDDUDDDDRRRRDDUDDDDDDDRRDUUDDDDDDDDRDDDDDDRRDDDDDDLDDLDDUDDDDDDLLLDDDUUUDDDDDDDLLLLDDUUDDDDDLLLDUUDDDDDRRRRDUUUDDDLLLLDDUDDRRRRDDDDDDDDDLLLDDDDRRDUUUDDDDDDDDDDDDDDDUDDDDDDUDLDLDDDRDRDDDDDUDDDDDUUUDDDLDLDDDRDRDDDDDDULLDLUDUDDDLDLDDDRDRDDDDDDLLDDUUUDDDDDLDLDDDRDRDDDDDDUDUUUDDDDDDLDLDDDRDRDDDUDUDDDDDDLDLDDDRDRURDDLDLDUDUDUUUDDDDDDDDLDLDDDRURDDLDLDUDUUUDDDDDDDDDLDLDDDRURDDLDUDUDDDDDDDDDLDLDDDRDRURDDDUDDDDDDDDDDLDLDDDRDDUUDDDDDDDDDDDDRRRRDDDDDDDDDDDDRRRDDDDDDDDDDDDDLDLDDDDDDDDDDDDDRRRDDDDDDDDDDDRRRDUDDDDDDDRRRRDUDDDDDDDDDDDDLLLLLDDDDDDDDDLDDLLLDUDDDDDDDLLLLDDDDDDDDDRRDDDDDDDLDDDLLDUDDDDDRRRDDUDDDDDDDDDDDDLLLDDDUUUDDDDDDDDDDUDUUUDDDDDDDDDLDDDDDDRDRUDDDDDDDDDRDUUUDDDDDDDLDLLLDDUDDDDDRDUUUDDDRRRDDDRDDDUUUDDDDDLDDDDDDDDUDRRDUDDDLDDDDDDDDDDDLLDUDDRRDRDRDDDDDDLDLDDDDDRDDDDDDLDLDDDLLDUDDDDLDLLLLDUDDDRRDDDDUUUDDDDDLDDDDDULUDDUDDDRRRDRDDUUUDDDDDDLDDDDDDRUDUUUDDDDDDDLDDDDDDDDDRUDUUUDDDDDDDDLDDDDDDDDUDUUUDDDDDDLLLLDUDDDDDRRRRDDUDDDRRRRDDDDDDDDDDLDLLDDDDDDDDDDDDDDRRDUUUDDDDDDDDLDDDDUDUUUDDDDDDDDDLDDLDDDRUDDDDDDDDDDLDLDLDDDRDDDDDDDDDDLDLDDLLDDDDDLDLDDDRRRRRDDDDDLDLDDDDLDUUUDDDDLDLDDDRUDDDDLLUDUDDDDLDLDDDRDDDUDRDDUUUDDDDDDLDLDDDRUDDLDUDDDUUUDDDDDDDLDLDDDRUDDLDUDUDDDDDDDLDLLLLDUDDDDDDDRRRRDDUDDDDDDDRRRDUUUDDDDDDDDLDLDDDRDDRRDRUDUDDDDDDDDLDLDDDRDDDDDDDDDDDDRD" (68 lines) followed by any number of repetitions of "DDDDDDDLDLDDDDDDDDDDDDLDLDLLDUDDDDDDRRRRDDDUUUDDDDDDDDLDDDULLUDDDDDDDDDDDLDDUDDDDDDDDRRRDUDDDDDDDDLLDDDUDUUUDDDDDDDDDDDDDDDDRUDUDDDDDDDRRRDRDDUUDDDDDDDDDDDLLLDUUUDDDDDDDDDLLLLDDUUDDDDDDDDDDDRRDUUUDDDDDDDLLLLDUUUDDDDLLLLDUDDDDDDRRRRDUDDDRRRRDUDDDDDDDDDLDDDDURRRDUDDDDDDDDDLDDDDDDRURDDUDDDDDDDDDDLDDDDDDUDDDDDDDDRRRDDDDRRRDDDDRDDDLDLDDDDDDDDRDDDDLDLDLLDUDDLDDDDDDDDLDDDUDDDLDDDUDDDDDRDRDDDDDDDLDDUDDDDLLLLLDDDDDDDRRDUDDDRRRRDDUDDDRRRDUDDDLDLDDDDDDDDRDDDDDDDLDLDDDDLDUUUDDDDDLDLDDDRUDDDLLDUDUUUDDDDDDLDLDDDRDDDDRDRUDDDDDDRDUDDDLDDDDLDDDRDDDUDRRDDUDDDDLDDDDLDDDRDRRRRDUUUDDDDDLDDDDLDDDRUDDDLUDUDDDDDLDDDDLDDDRDDDD" (16 lines per repetition).