Как запрограммировать бота для Block Blast

01Модель игры

Всё начинается с данных. Поле 8×8 — это список списков из нулей и единиц. Фигура — список координат (dr, dc) относительно её левого верхнего угла. Поворотов в Block Blast нет, поэтому каждый шаблон хранится ровно один раз:

# поле: 64 ячейки, 0 = пусто, 1 = занято
board = [[0] * 8 for _ in range(8)]

# фигура "уголок" — 3 ячейки со сдвигами
corner = [(0, 0), (0, 1), (1, 0)]

# рука: 3 фигуры, пополняется когда пустеет
hand = ["corner_nw", "dot3h", "square2"]

Почему это важно: правильная модель делает все остальные функции тривиальными. Проверка хода, очистка линий, оценка позиции — каждая превращается в пару строк над одним и тем же представлением.

02Генерация ходов

Ход — это пара «фигура из руки + позиция». Так как поле маленькое, боту не нужна хитрость: он просто перебирает все фигуры × все 64 клетки и оставляет те, что влезают. Для руки из 3 фигур это максимум ~192 кандидата:

def piece_fits(board, cells, r0, c0):
    for dr, dc in cells:
        r, c = r0 + dr, c0 + dc
        if not (0 <= r < 8 and 0 <= c < 8) or board[r][c]:
            return False
    return True

def legal_moves(board, cells):
    return [(r, c) for r in range(8)
            for c in range(8)
            if piece_fits(board, cells, r, c)]

Если legal_moves пуст для всех трёх фигур — игра окончена. Это единственное правило конца игры в Block Blast.

03Очистка линий

После установки фигуры проверяем каждую строку и каждый столбец на заполненность. Полные — обнуляются, причём строки и столбцы очищаются одновременно (крест из линий за один ход — нормальная ситуация):

b[r][c] = 1                          # ставим фигуру
rows = [r for r in range(8) if all(b[r])]
cols = [c for c in range(8) if all(b[r][c] for r in range(8))]
for r in rows: b[r] = [0] * 8
for c in cols:
    for r in range(8): b[r][c] = 0

04Оценочная функция — «мозг» бота

Перебирать ходы мало: нужно понимать, какая позиция лучше. Для этого пишем функцию evaluate(board), которая выдаёт одно число — чем больше, тем лучше. У нашего бота четыре слагаемых:

return (lines_cleared   * 100   # сносить линии — главная цель
        + near_full_lines *  6    # линии в 1-2 ячейках от готовности
        - holes          * 12     # запертые дырки = смерть
        - regions        *  8)    # дробление пустого пространства

Веса подобраны вручную и проверены на 20 партиях. Это и есть вся «магия» — можно часами крутить коэффициенты и наблюдать, как меняется стиль игры (попробуй в лаборатории стратегии «жадный» против «поиск на 2 хода»).

05Поиск: смотреть на ход вперёд

Жадный бот берёт ход с максимальной оценкой сейчас — и часто закапывается. Решение: для каждого кандидата сделать лучший ответ оставшимися фигурами и оценить позицию после двух установок. Результат на 20 тестовых партиях:

случайный бот:    ~19 ходов,   ~180 очков
жадный (1 ход):   ~39 ходов,   ~479 очков
поиск на 2 хода:  ~80 ходов,  ~1041 очков   # вдвое дольше живёт

Код второго уровня вкладывается в один цикл: перебираем ответные ходы по той же схеме, берём максимум, суммируем со скидкой на будущее s1 + 0.7 * s2. Глубину можно наращивать (3, 4 хода), но дерево растёт как ~192^d — дальше уже нужны отсечения или кэширование.

06Куда расти

Expectimax вместо максимина: следующие три фигуры неизвестны — усредняй оценку по случайной раздаче, а не считай руку фиксированной.

Монте-Карло (MCTS): доигрывай партию случайными ходами 200 раз на каждого кандидата — выбирается ход с лучшим средним исходом. Просто и сильно бьёт ручные веса.

Обучение с подкреплением: те же board → move, но веса не руками, а нейросеть, обученная на собственных партиях (как AlphaZero играл сам с собой). Структура кода не меняется — заменяется только evaluate.