Loops in HATETRIS @ Things Of Interest

Things Of Interest

-->

Things Of Interest

Code

Loops in HATETRIS

2022-12-06 by<br>qntm

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:

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.

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