5. Просчёт хода компьютера

Цель

Заменить заглушку «случайный допустимый ход» на осмысленную стратегию, которая остаётся дешёвой по времени на мобильном устройстве и опирается только на уже существующую модель BoardState, не переписывая правила партии и интерфейс.

Описание выполненной работы

На шаге 4 искусственный интеллект уже умел соблюдать те же законы, что и человек: брать допустимую пару индексов, выполнять перемещение, снимать линии и копить очки до тех пор, пока очередной ход не перестаёт что‑либо удалять. Единственным «слабым звеном» оставался способ выбора самой пары — равновероятный среди тысяч комбинаций. Такой противник создаёт хаос, но почти никогда не наказывает ошибки игрока и редко строит собственные длинные серии.

Шаг плана формулируется коротко — «просчёт хода» — и в инженерном смысле это может означать что угодно от жадного перебора до минимакса с заглядыванием на несколько полуходов вперёд. Для казуальной игры на сетке 8×16 при сохранении простоты кода разумным компромиссом стала жадная эвристика по немедленному выигрышу: мы не предсказываем всю будущую цепочку до конца хода противника, но на каждом конкретном полуходе ИИ знает, сколько очков принесёт именно это перемещение, если немедленно применить правила совпадений. Такой подход хорошо стыкуется с архитектурой из поста 4: вся тяжёлая работа уже сосредоточена в BoardState.collect_matches(), а сцене остаётся лишь синхронизация видимых ячеек и счётчиков.

Зачем клонировать состояние доски

Прямой вызов apply_move по текущему _board внутри цикла перебора испортил бы реальную партию до того, как мы успеем сравнить альтернативы. Поэтому в класс BoardState добавлен компактный метод duplicate_state, который создаёт новый экземпляр BoardState и копирует массив cells через встроенный PackedInt32Array.duplicate(). Семантика копии совпадает с оригиналом: пустые клетки по‑прежнему кодируются значением −1, цвета — неотрицательными индексами палитры.

В Godot 4 RefCounted подклассы вроде нашего состояния не требуют ручного free, что упрощает использование временных симуляций в tight loop: после выхода из области видимости локальная переменная sim перестаёт иметь ссылок, и подсчётчик ссылок освобождает память. Для начинающего разработчика важный момент в том, что копия должна быть полной именно на уровне данных, которые влияют на правила. Сейчас это только cells; очередь появления новых шаров и счёт партии живут в game_board.gd и при оценке одного полухода ИИ сознательно не трогаются — нам нужен только ответ вопроса «какой будет score и сколько клеток попадёт в to_remove, если бы на этой доске сделали ход X».

Алгоритм pick_greedy_move

Метод принимает готовый список Array[Vector2i], где компонента x — индекс исходной клетки с шаром, y — индекс пустой цели, и генератор RandomNumberGenerator для разрешения ничьих. Алгоритм:

1. Инициализируем «лучшие» значения best_score = -1 и best_clear = -1. Отрицательный старт по очкам гарантирует, что любой реальный результат неотрицательных очков из collect_matches сразу станет новым рекордом; ноль очков означает отсутствие линий и тоже будет корректно сравниваться между ходами.
2. Для каждого вектора m строим sim := duplicate_state(), вызываем sim.apply_move(m.x, m.y) и затем data := sim.collect_matches(). Ключ score словаря приводится к целому и сравнивается с текущим максимумом. Вторичный критерий — размер множества to_remove: при равных очках выгоднее ход, который очищает больше клеток за один проход, потому что это обычно соответствует более широкому совпадению или пересечению линий и меняет позицию сильнее.
3. Все ходы, попадающие на текущую пару (best_score, best_clear), складываются в массив candidates. Когда находится строго лучший результат по очкам или по числу удалений при тех же очках, массив кандидатов обнуляется и заполняется заново одним элементом.
4. Итог — candidates[rng.randi() % candidates.size()]. Так мы сохраняем предсказуемое качество игры без абсолютной детерминированности: среди множества равносильных ходов профиль партии меняется от сеанса к сеансу.

Сложность одного полухода ИИ оценивается как произведение числа допустимых ходов на стоимость симуляции. Перебор пар в худшем случае масштабируется как произведение числа занятых и пустых клеток с фильтром достижимости; для нашего размера поля это остаётся комфортным даже без профилировщика. Если когда‑нибудь понадобится ускорение, первым шагом станет кеширование списков линий или частичное обновление совпадений вместо полного прохода по всем диагоналям — но это уже выходит за рамки текущего шага.

Связка со сценой game_board.gd

Изменение пользовательского кода минимально: внутри _ai_play_sequence заменена строка с индексированием случайного элемента moves на вызов _board.pick_greedy_move(moves, _rng). Остальная машина состояний — таймер паузы, проверка any_legal_move, начисление очков ИИ, очистка клеток и _sync_cells — перенесена без правок. Так мы выполнили обещание архитектуры из поста 4: стратегия сидит рядом с моделью доски или внутри неё, а представление не знает деталей перебора.

Для человека поведение противника становится заметно агрессивнее в тех позициях, где на доске есть короткая линия в два шара рядом с третьим подходящим цветом: компьютер предпочтёт добить линию с немедленными очками, а не ходить «в никуда». В то же время жадность не гарантирует глобально оптимальную серию из нескольких полуходов подряд — иногда человек может спланировать порядок так, чтобы выиграть больше за свой полный ход. Это осознанный уровень сложности для мобильной казуальной игры без режима «турбо‑шахматы».

Контрольные сценарии для ручной проверки

После сборки полезно быстро пройти несколько партий и обратить внимание на следующее:

1. ИИ не делает заведомо невозможных перемещений — источник по-прежнему ограничен списком list_legal_moves, который уже проверяет путь по пустым клеткам.
2. На очевидном поле с двумя альтернативными ходами, из которых один даёт три очка, а второй ноль, компьютер стабильно выбирает выгодный (если только нет другого хода с тем же немедленным счётом и большим числом удаляемых клеток — тогда возможен другой выбор среди лучших).
3. При полном отсутствии линий после любого хода поведение эквивалентно случайному среди всех допустимых пар: все симуляции вернут нулевой счёт и нулевое удаление, список кандидатов совпадёт со всем списком ходов.
4. Нагрузка на кадры не заметна глазу при стандартной паузе 0.42 секунды между полуходами ИИ — если заметны редкие лаги на очень слабом устройстве, имеет смысл замерить один цикл перебора профилировщиком редактора и при необходимости сократить число ходов эвристическим отбором.

Возможное развитие

Если позже понадобится усложнить ИИ без полного дерева перебора, естественная эволюция — добавить один или два полухода lookahead с альфа‑бета отсечением только для верхних ходов по эвристической оценке, либо смешать жадность с лёгким шумом в оценке (epsilon‑greedy), чтобы противник иногда жертвал немедленными очками ради случайной ловушки. Все эти техники продолжают использовать тот же каркас duplicate_state и collect_matches, так что текущий шаг закладывает устойчивый фундамент без привязки сцены к конкретному алгоритму.

Ссылка на проект: Third Planet

Ссылка на игру: Google Play Rustore