#prog #game #article

В 2010 году Sam Hughes (программист, фантаст и просто хороший человек автор SCP-055) представил миру HATETRIS — тетрис, созданный таким образом, чтобы выдавать наиболее неудобные фигуры для продолжения. В частности, здесь нет превью следующей фигуры — она выбирается только после того, как игрок сделал свой ход. Надо отметить, что алгоритм для выбора фигуры абсолютно детерминированный, а потому возможно записывать реплеи в виде последовательности совершённых ходов.

Сам автор не шибко преуспел в том, чтобы обыграть собственное творение — на момент первой публикации он установил рекорд в 5 убранных строк. Первые рекорды были установлены людьми и последовательно были 11, 17, 20, 22, 28 и 30. Последний рекорд был побит лишь спустя 7 (!) лет, на 1 больше. А вот дальше пошло-поехало — после подключения программных методов поиска решения потолок рекордов сильно вырос. Человек под ником knewjade в одиночку на протяжении пары месяцев выдал новые рекорды в 32, 34, 41, 45 и 66 убранных линий. Автору даже пришлось в какой-то момент заблаговременно модифицировать HATETRIS так, чтобы он предотвращал зацикливание позиции (ибо в противном случае было бы тривиально набирать сколь угодно много очков).

К делу подключились новые люди. В посте Getting the World Record in HATETRIS они рассказали, как они добились прорыва, преодолев в итоге (с большим отрывом) планку в 100 очков — причём упомянув тупики и ошибки, допущенные по пути. А в выпущенном годом позже Losing the World Record in HATETRIS (кстати, не так уж и давно, всего месяц назад) они рассказали, как объединённые идеи нескольких вовлечённых людей помогли в итоге поднять рекорд до аж 302 очков и потом ещё выше — с, по видимому, потенциалом добиться произвольно большого количества очков. Всё это, кстати, без использования каких-то безумно дорогих вычислительных мощностей.

Оба поста достаточно объёмны, насыщены идеями и местами низкоуровневыми деталями (внезапно пригодились битовые маски), так что настоятельно рекомендую к прочтению.

(а ещё авторы постов выше написали свои солверы на Rust)