Битборды (
Bitboard) — специальные битовые структуры, позволяющие эффективно рассчитывать ходы в настольных играх. На хабре писали про применение битбордов к
шахматам и даже к
шашкам. Сегодня мы применим технику битбордов к несколько неожиданной, но всем знакомой игре – к
тетрису. Результатом наших изысканий будет консольная игра, а также автоматический поиск лучших ходов (при заданной последовательности фигур), скорость которого как раз и обеспечивается эффектиностью битовых манипуляций. Заодно мы поддержим проигрывание найденных ходов в автоматическом режиме, чтобы в полной мере насладиться компьютерным интеллектом. В конце статьи дана ссылка на гитхаб с кодом игры на C#, а также коротенькое видео игры из 114 ходов, найденной компьютером поиском в глубину за пятнадцать минут.
Обычно битборд – это машинное слово, состоящее из нескольких байт, каждый бит которого соответствует одной клетке поля в игре. Так, в шахматах всего 64 клетки, что соответствует 8-байтному слову (ulong в C#), а в шашках – 32 (uint в C#). Любители тетриса наверняка помнят, что размер поля в стандартном тетрисе – 10 на 20 клеток, то есть, 200 бит, что не влезает ни в один числовой тип. Конечно, можно разбить поле на четыре части и использовать четыре восьмибайтных слова, или можно не мелочиться и использовать массив из двадцати двухбайтных слов, по одному слову на каждую линию поля; все реализации тетриса на битбордах, которые я нашел (в количестве одной штуки), так и делают. Но мы пойдем другим путем…