Тетрис на битбордах: старые песни на новый лад
Битборды (Bitboard) — специальные битовые структуры, позволяющие эффективно рассчитывать ходы в настольных играх. На хабре писали про применение битбордов к шахматам и даже к шашкам. Сегодня мы применим технику битбордов к несколько неожиданной, но всем знакомой игре — к тетрису. Результатом наших изысканий будет консольная игра, а также автоматический поиск лучших ходов (при заданной последовательности фигур), скорость которого как раз и обеспечивается эффектиностью битовых манипуляций. Заодно мы поддержим проигрывание найденных ходов в автоматическом режиме, чтобы в полной мере насладиться компьютерным интеллектом. В конце статьи дана ссылка на гитхаб с кодом игры на C#, а также коротенькое видео игры из 114 ходов, найденной компьютером поиском в глубину за пятнадцать минут.
Обычно битборд — это машинное слово, состоящее из нескольких байт, каждый бит которого соответствует одной клетке поля в игре. Так, в шахматах всего 64 клетки, что соответствует 8-байтному слову (ulong в C#), а в шашках — 32 (uint в C#). Любители тетриса наверняка помнят, что размер поля в стандартном тетрисе — 10 на 20 клеток, то есть, 200 бит, что не влезает ни в один числовой тип. Конечно, можно разбить поле на четыре части и использовать четыре восьмибайтных слова, или можно не мелочиться и использовать массив из двадцати двухбайтных слов, по одному слову на каждую линию поля; все реализации тетриса на битбордах, которые я нашел (в количестве одной штуки), так и делают. Но мы пойдем другим путем…
Векторы
Мы воспользуемся специальным набором инструкций Advanced Vector Extensions 2, которым мы уже пользовались в прошлый раз для ускорения вычислений. Они оперируют 256-битными значениями (в отличие от обычных инструкций, работающих с 64-битными значениями):
// Обычные регистры, 8 байт
ulong
x = 0,
y = 0,
z = x & y; // z[i] = x[i] & y[i], i = 0..7
// SIMD-регистры, 32 байта
Vector256
X = Vector256.Zero,
Y = Vector256.Zero,
Z = Avx2.And(X, Y); // Z[i] = X[i] & Y[i], i = 0..31
Надо сказать, что писать каждый раз вызовы статических методов вместо арифметических операций не очень удобно; к тому же не все операции имеют прямые аналоги в AVX2, поэтому мы воспользуемся изолентой мощью c# и напишем специальную структуру, инкапсулирующую 256-битное слово, чтобы писать код в таком стиле:
V256 X = 0, Y = 0, Z = X & Y;
Чтобы предыдущий код имел смысл, определим V256 как структуру, хранящую внутри 256-битный вектор данных и имеющую неявные конструкторы и перегрузку операторов:
readonly unsafe struct V256
{
private readonly Vector256 _data;
public V256(Vector256 data) { _data = data; }
// невявное приведение от Vector<256>:
// вместо V256 x = new V256(data) можно писать просто V256 x = data
public static implicit operator V256(Vector256 data) => new V256(data);
// Перегрузка оператора позволяет писать x & y
public static V256 operator &(V256 x, V256 y) => Avx2.And(x._data, y._data);
// невявное приведение от байта: теперь можно писать V256 x = 42;
public static implicit operator V256(byte b) => Avx2.BroadcastScalarToVector256(&b);
...
}
Добавим к этой структуре остальные методы и операторы, которыми мы будем пользоваться в дальнейшем. Посольку этот класс — самый важный в нашей программе,
// помечаем readonly, чтобы позволить JIT-компилятору больше оптимизаций
readonly unsafe struct V256
{
// желательно проверять, что мы поддерживаем AVX2
static V256() { if (!Avx2.IsSupported) throw new NotSupportedException("AVX2"); }
// здесь мы воспользовались неявным приведением байта к нашему типу, см. ниже
public static readonly V256 ZERO = 0;
// собственно данные. JIT-оптимизатор может их вообще в памяти не хранить,
// а только держать в одном из шестнадцати специальных 256-битных
// регистров процессора YMM0 - YMM15
private readonly Vector256 _data;
// можно загрузить 32 байта напрямую из памяти
public V256(byte* b) { _data = Avx2.LoadVector256(b); }
// или задать от одного до 32 байт в конструкторе
public V256(params byte[] buffer)
{
if (buffer.Length < 32) Array.Resize(ref buffer, 32);
fixed (byte* p = buffer) _data = Avx2.LoadVector256(p);
}
// А можно загрузить массив произвольного типа. Обратите внимание
// на ключевое слово unmanaged, которое позволяет обращаться с типом T
// как с массивом байт. Все целочисленные типы (int, uint, long, ulong,
// и т.д.) удовлетворяют этому условию
public static V256 Load(params T[] buffer) where T : unmanaged
{
fixed (T* p = buffer) return new V256((byte*)p);
}
public void Store(T[] buffer) where T : unmanaged
{
fixed (T* p = buffer) Avx2.Store((byte*)p, _data);
}
public T[] ToArray() where T : unmanaged
{
T[] array = new T[32 / sizeof(T)];
fixed (T* ptr = array) Avx2.Store((byte*)ptr, _data);
return array;
}
// Специальная инструкуция broadcast повторяет параметр необходимое число раз
// то есть, результатом будет 32 одинаковых байта b
public static V256 FromByte(byte b) =>
Avx2.BroadcastScalarToVector256(&b);
// или 16 одинаковых short-а s
public static V256 FromShort(short s) =>
Avx2.BroadcastScalarToVector256(&s).AsByte();
// также можно поступать с любыми типами
public static V256 FromULong(ulong ul) =>
Avx2.BroadcastScalarToVector256(&ul).AsByte();
// невявное приведение от байта: теперь можно писать V256 x = 42;
public static implicit operator V256(byte b) => FromByte(b);
// Особые возможности AVX2
// берется минимум по каждому байту, аналогично result[i] =
// Math.Min(this[i], other[i]), i=0..31, только в 100 раз быстрее
public V256 Min(V256 other) => Avx2.Min(_data, other._data);
// аналог table lookup: result[i] = this[data[i]], i = 0..31
public V256 Shuffle(V256 mask) => Avx2.Shuffle(_data, mask._data);
// аналог result[i] = this[i] == other[i] ? 0xFF : 0x00;
public V256 CompareEqual(V256 other) => Avx2.CompareEqual(_data, other._data);
// Перегрузка операторов позволяет писать x & y, x | y и т.п.
public static V256 operator &(V256 x, V256 y) => Avx2.And(x._data, y._data);
public static V256 operator |(V256 x, V256 y) => Avx2.Or(x._data, y._data);
public static V256 operator +(V256 x, V256 y) => Avx2.Add(x._data, y._data);
public static V256 operator -(V256 x, V256 y) => Avx2.Subtract(x._data, y._data);
public static V256 operator -(V256 x) => Avx2.Subtract(ZERO._data, x._data);
// а сравнить просто так два 256-битных числа не получится.
// Рано или поздно на замену AVX2 придет AVX512, где будет специальная
// инструкция для этого, но пока только так:
public static bool operator ==(V256 x, V256 y) =>
-1 == Avx2.MoveMask(Avx2.CompareEqual(x._data, y._data));
// Но самое хитрое - это сдвиг. К сожалению, невозможно сдвинуть значение как
// одно 256-битное число (а вот в AVX512, по слухам, будет можно!), поэтому
// извращаемся:
public static V256 operator >>(V256 x, int count)
{
// сдвинем данные, как 4 независимых 8-байтных слова
Vector256 data = Avx2.ShiftRightLogical(
x._data.AsUInt64(), (byte)count);
// а эти биты мы потеряли в предыдущем сдвиге
Vector256 carry = Avx2.ShiftLeftLogical(
x._data.AsUInt64(), (byte)(64 - count));
// взболтать...
carry = Avx2.Permute4x64(carry, 0x39);
// но не смешивать!
carry = Avx2.Blend(ZERO._data.AsUInt32(), carry.AsUInt32(), 0x3F).AsUInt64();
data = Avx2.Or(data, carry);
return data.AsByte();
}
// Распечатываем значение вектора, в том числе, для дебага.
// обратите внимание на аллокацию массива на стеке: в данном методе
// это не обязательно, так как производительность не критична,
// но иногда это может спасти нас.
public override string ToString()
{
byte* buffer = stackalloc byte[32];
Avx2.Store(buffer, _data);
return string.Join(" ", Enumerable.Range(0, 32).Select(i => buffer[i].ToString("X2")));
}
}
полная версия: V256.cs.
Мы почти готовы начать-таки писать тетрис, но перед этим мы должны написать юнит тесты!
[TestClass]
public class V256Tests
{
[TestMethod]
public void V256_ToString()
{
Assert.AreEqual(
"05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 " +
"05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05",
((V256)5).ToString());
}
[TestMethod] public void V256_And() =>
Assert.AreEqual((V256)4, (V256)5 & (V256)6);
[TestMethod]
public void V256_ShiftRight()
{
V256 y = new V256(
0xF1, 0x18, 0x80, 0x01, 0x18, 0x80, 0x01, 0x18,
0x80, 0x01, 0x18, 0x80, 0x01, 0x18, 0x80, 0x01,
0x18, 0x80, 0x01, 0x18, 0x80, 0x01, 0x18, 0x80,
0x01, 0x18, 0x80, 0x01, 0x18, 0x80, 0xFF, 0x0F);
Assert.AreEqual(
"01 18 80 01 18 80 01 18 80 01 18 80 01 18 80 01 " +
"18 80 01 18 80 01 18 80 01 18 80 01 F8 FF 00 00",
(y >> 12).ToString());
}
Тетрис
Ну, теперь-то мы практически готовы начать писать тетрис! И игровое поле, и фигуры будут представляться структурой V256. Когда фигуры падают вниз, соответствующие биты поля будут устанавливаться в значение 1. Так как нам надо всего 10×20=200 бит, а в V256 их 256, оставшиеся 56 бит мы можем пропить использовать на благое дело. Сначала добавим по одной клетке слева и справа к каждой линии, которые всегда будут заполненными. Это позволит нам не писать отдельный код для проверки выхода фигуры за границу поля слева и справа. Аналогично добавим двадцать первую линию, полностью заполненную, чтобы избавиться от проверок выхода за границу поля снизу. Так что у нас получается 21 линия по 12 бит, что дает 252 бита, оставляя 4 бита на непредвиденные расходы:
Вот битборд для пустого поля; младшие байты (идут первыми, ибо little endian) соответствуют верхним линиям; старшие — нижним; четырехбитный хвост не используется:
V256 board = new V256(
1, 24, 128, 1, 24, 128, 1, 24,
128, 1, 24, 128, 1, 24, 128, 1,
24, 128, 1, 24, 128, 1, 24, 128,
1, 24, 128, 1, 24, 128, 255, 15);
А вот T-фигура во всех четырех вариантах, по одному для каждого поворота:
// possible pieces with rotations
V256[][] PIECES = new V256[][] { ...,
new[] { // T-shape
new V256(224, 0, 2),
new V256(96, 0, 4, 64),
new V256(64, 0, 7),
new V256(32, 0, 2, 96),
}, ...
};
Падающую фигурку мы будем представлять как массив всех ее вращений, плюс индекс, указывающий, какой вариант в данный момент выбран:
// Все варианты поворота фигурки одновременно падают вниз.
// Когда игрок поворачивает фигурку,
// меняем индекс текущего вращения, если получившаяся фигурка
// не пересекается с содержимым поля.
V256[] fallingPiece = new V256[4];
// от 1 до 4
int rotationsCount;
// текущий индекс поворота. Изначально равен нулю
int fallingPieceRotation;
// текущий вариант поворота текущей фигурки
V256 FallingPiece => fallingPiece[fallingPieceRotation % rotationsCount];
// Последовательность выпадения фигурок случайна, но всегда одинакова ;-)
Random rand = new Random(12345);
// новая случайная фигурка появляется сверху!
void SelectNextPiece() => SelectPiece(rand.Next(0, PIECES.Length));
// копируем все повороты этой фигурки из базы фигурок
void SelectPiece(int index)
{
fallingPieceRotation = 0;
rotationsCount = PIECES[index].Length;
Array.Copy(PIECES[index], fallingPiece, rotationsCount);
}
// крутим и вертим
void RotateLeft() => Rotate(1);
void RotateRight() => Rotate(-1);
bool MoveDown() => ShiftLeft(width);
bool MoveRight() => ShiftLeft(1);
bool MoveLeft() => ShiftRight(-1);
bool Rotate(int count)
{
// поворачиваем в нужную сторону, выбирая нужный
// вариант из массива
fallingPieceRotation += count;
// скоро узнаем, как это делается
if (!Intersects(bord, FallingPiece)) return true;
// не удалось повернуть, поворачиваем обратно!
fallingPieceRotation -= count;
return false;
}
bool ShiftLeft(int count)
{
// сначала проверим, не мешает ли нам чего
if (Intersects(board, ShiftLeft(FallingPiece, count)) return false;
// все варианты поворота сдвигаются одновременно!
for (int i = 0; i < rotationsCount; i++)
fallingPiece[i] = ShiftLeft(fallingPiece[i], count);
}
}
Ну, а теперь размахнись рука, раззудись плечо аккуратно манипулируем битами!
Во-первых, нам потребуется определять пересечение заполненных клеток поля и фигуры, что делается в одну логическую операцию:
bool Intersects(V256 board, V256 piece) => (piece & board) != 0;
Сдвиг фигурки вниз, влево или вправо будет просто логическим сдвигом на соответствующее количество бит (заметим, что сдвиг фигуры вправо является сдвигом ее битов в сторону увеличения, что соответствует логическому сдвигу битов вектора влево):
const int width = 12; // ширина поля в битах
V256 MoveDown(V256 piece) => piece <<= width;
V256 MoveRight(V256 piece) => piece <<= 1;
V256 MoveLeft(V256 piece) => piece >>= 1;
// чтобы сбросить фигурку в самый низ,
// сдвигаем ее, пока не натыкаемся на препятствие
V256 Drop(V256 piece)
{
while(!Intersects(board, MoveDown(piece)) piece = MoveDown(piece);
return piece;
}
Далее, поскольку игра у нас консольная, надо распечатать поле и падающую фигурку:
void DisplayField()
{
V256 field = board | FallingPiece; // печатаем и поле, и фигурку сразу
while (field != 0) // печатаем в цикле линии поля, начиная с верхней
{
Console.WriteLine(GetLine(field));
field >>= width; // простым сдвигом переходим к следующей линии
}
}
// применяя AVX2-магию, преобразуем биты в байты,
// соответствующие пустым и заполненным клеткам
V256 tile = new V256(' ' & 255, '*' & 255);
V256 lineToStringShuffler = new V256(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1);
V256 lineToStringMask = new V256(1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8);
// почему это работает, оставляем в качестве упражнения читателю
string GetLine(V256 field)
{
V256 line = field.Shuffle(lineToStringShuffler) & lineToStringMask;
line = line.Min(V256.ONE);
line = tile.Shuffle(line);
return Encoding.ASCII.GetString(line.ToArray(), 0, width);
}
Наконец, самая сложная часть — определить заполненные линии и удалить их. Тут без цикла не обойтись (по крайней мере, мне не удалось), поэтому будем сканировать поле по линиям снизу вверх, и битовыми операциями проверять, что линия заполнена. Чтобы убрать заполненную линию из поля, битовыми операциями обнулим соответствующую линию в поле, и сдвинем верхнюю часть к нижней:
while (lineMask != 0)
{
V256 boardLine = board & lineMask;
V256 boardUnderLine = board & underLineMask;
V256 boardOverLine =
board & ~underLineMask & ~lineMask;
if(boardLine == lineMask)
// вырезаем заполненную линию
//из поля и склеиваем остаток
board = boardUnderLine |
(boardOverLine << width) |
emptyLine;
// сдвигаем маску на одну линию вверх
underLineMask |= lineMask;
lineMask >>= width;
}
V256 fullLine = new V256(0, 0, 0, ..., 0, 0, 255, 15);
V256 emptyLine = new V256(1, 8);
void RemoveFullLines(ref V256 board)
{
// начинаем маску с нижней линии
V256 lineMask = fullLine >> width;
// маска части поля под этой линией
V256 underLineMask = fullLine;
while (lineMask != 0)
{
// это проверка, что линия заполнена
while ((board & lineMask) == lineMask)
{
// вырезаем заполненную линию из поля и склеиваем остаток
board = (board & underLineMask) |
((board & ~underLineMask & ~lineMask) << width) |
emptyLine;
}
// сдвигаем маску на одну линию вверх
underLineMask |= lineMask;
lineMask >>= width;
}
}
Собственно, это все, что нам надо. Теперь код самой игры выглядит тривиально, никакого намека на происходящие внутри битовые перипетии:
void PlayGame()
{
SelectNextPiece();
while (!Intersects(FallingPiece))
{
DisplayField();
for (int i = 0; i < 10; i++)
{
Control();
Thread.Sleep(100);
}
if (!MoveDown())
{
AddPieceToBoard();
RemoveFullLines();
SelectNextPiece();
continue;
}
}
DisplayField();
}
void Control()
{
if (Console.KeyAvailable)
{
ConsoleKeyInfo key = Console.ReadKey(false);
if (key.Key == ConsoleKey.UpArrow) RotateLeft();
else if (key.Key == ConsoleKey.DownArrow) RotateRight();
else if (key.Key == ConsoleKey.LeftArrow) MoveLeft();
else if (key.Key == ConsoleKey.RightArrow) MoveRight();
else if (key.Key == ConsoleKey.Spacebar) while (MoveDown()) ;
while (Console.KeyAvailable) Console.ReadKey();
DisplayField();
}
}
А вот полный код класса: Tetris.cs
Поиск оптимальной стратегии
Собственно, ради самой игры городить эти битовые трюки не имело бы особого смысла. Зато для поиска оптимальной стратегии — самое то! Сделаем самый простой вариант поиска — рекурсивный поиск вглубь полным перебором: так как последовательность выпадения фигурок фиксирована, то для каждой фигурки перебираем все возможные варианты ее вращений и горизонтальных сдвигов. Параллельно храним последовательность действий, чтобы можно было воспроизвести найденные варианты. Упрощенный код достаточно прямолинеен:
void Solve() => Solve(Tetris.board, 0, 0);
// ищем оптимальное решение перебором на шаге step
void Solve(V256 board, int step, int score)
{
// выбираем следующую фигурку
int pieceIndex = pieceOrder[step];
V256[] currentPieceRotations = Tetris.PIECES[pieceIndex];
// проверяем все вращения
foreach (V256 piece in currentPieceRotations)
{
// проверяем все сдвиги (в реальном коде больше проверок)
Solve(board, piece, step, score);
for(int i = 1; i <= 5; i++)
{
Solve(board, piece << i, step, score);
Solve(board, piece >> i, step, score);
}
}
}
void Solve(V256 board, V256 piece, int step, int score)
{
if ((piece & board) != 0) return; // фигурка не влезла!
// бросаем фигурку вниз
while ((board & (piece << Tetris.width)) == 0) piece <<= Tetris.width;
board |= piece; // добавляем фигурку на поле!
Tetris.RemoveFullLines(ref board, ref score); // удаляем заполненные линии
if(score > maxScore) {...} // новый рекорд!
// рекурсивно вызываем поиск для следующего шага
Solve(board, step + 1, score);
}
Полный код: TetrisSolver.cs
Результат
Поиск перебором, на самом деле, не самая эффективная вещь, поскольку количество вариантов растет экспоненциально с каждым шагом. Однако получившаяся скорость поиска около 15 миллионов шагов в секунду позволяет находить достаточно интересные сценарии (компьютер сам себе создает проблемы, которые потом сам же героически решает). Примерно так он работает:
C:\Tetris\bin\Release\netcoreapp3.1>tetris -solve 1000
...
Processed 12,000,000,000 moves at 00:12:51 (15.56 M moves/second)
new max score=57 at depth 114 after processing 12,475,091,815 moves at 00:13:22
0:0 0:0 0:0 ... 0:4 0:3 0:-2 0:2 0:-2 3:-4
new max score=58 at depth 114 after processing 12,475,143,842 moves at 00:13:22
0:0 0:0 0:0 ... 1:-2 0:-2 0:-3 1:3 1:4 1:2 3:0
Processed 13,000,000,000 moves at 00:13:57 (15.53 M moves/second)
А вот видео найденного сценария:
dotnet run -c Release -p Tetriss -replay "0:0 0:0 0:0 0:0 0:0 0:0 0:0 0:0 0:0 0:-3 0:3 0:-3 0:-2 0:3 0:-4 0:4 0:3 0:3 0:0 0:3 0:1 0:-3 0:3 0:-2 2:-3 0:-1 3:-4 2:-2 1:4 0:1 0:2 0:-4 1:4 0:2 0:-2 0:0 0:-3 0:-3 1:0 1:4 3:-4 1:4 1:2 0:0 0:-2 0:1 1:-4 0:0 0:-2 0:-4 0:4 1:2 1:4 1:4 1:-5 0:0 0:4 1:-4 0:-2 0:1 1:4 0:1 0:-1 1:3 2:2 0:0 1:-4 3:-1 2:4 1:-2 0:1 3:3 0:-3 1:1 3:-4 3:0 1:4 1:2 1:1 1:-4 1:-4 0:-2 0:1 1:4 3:-1 0:2 1:3 1:-5 1:4 0:1 1:-4 0:-2 1:4 1:2 0:2 1:4 1:0 0:-2 0:2 0:1 1:-4 0:1 0:1 1:4 1:-2 1:-2 0:-2 0:-3 1:3 1:4 1:2 3:0"
Код выложен на гитхаб.
