Битборды (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<byte> X = Vector256<byte>.Zero, Y = Vector256<byte>.Zero, Z = Avx2.And(X, Y); // Z[i] = X[i] & Y[i], i = 0..31Надо сказать, что писать каждый раз вызовы статических методов вместо арифметических операций не очень удобно; к тому же не все операции имеют прямые аналоги в AVX2, поэтому мы воспользуемся
V256 X = 0, Y = 0, Z = X & Y;Чтобы предыдущий код имел смысл, определим V256 как структуру, хранящую внутри 256-битный вектор данных и имеющую неявные конструкторы и перегрузку операторов:
readonly unsafe struct V256{ private readonly Vector256<byte> _data; public V256(Vector256<byte> data) { _data = data; } // невявное приведение от Vector<256>: // вместо V256 x = new V256(data) можно писать просто V256 x = data public static implicit operator V256(Vector256<byte> 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); ...}Добавим к этой структуре остальные методы и операторы, которыми мы будем пользоваться в дальнейшем. Посольку этот класс самый важный в нашей программе,
спрячем его под спойлер
полная версия: V256.cs.// помечаем 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<byte> _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<T>(params T[] buffer) where T : unmanaged { fixed (T* p = buffer) return new V256((byte*)p); } public void Store<T>(T[] buffer) where T : unmanaged { fixed (T* p = buffer) Avx2.Store((byte*)p, _data); } public T[] ToArray<T>() 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<ulong> data = Avx2.ShiftRightLogical( x._data.AsUInt64(), (byte)count); // а эти биты мы потеряли в предыдущем сдвиге Vector256<ulong> 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"))); }}Мы почти готовы начать-таки писать тетрис, но перед этим мы должны написать юнит тесты!
Без них ничего не заработает, а мы даже не поймем,
почему
[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. Так как нам надо всего 10x20=200 байт, а в V256 их 256, оставшиеся 56 байт мы можем
Вот битборд для пустого поля; младшие байты (идут первыми, ибо 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 rotationsV256[][] 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<byte>(), 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); // ищем оптимальное решение перебором на шаге stepvoid 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:-4new 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:0Processed 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"Код выложен на гитхаб.
