📊 Анализ алгоритмов: Aggressive против Monte-Carlo

Основываясь на исходном коде ботов (AggressiveSearch, MonteCarloSearch, Evaluator, MonteCarloEquity), мы проанализировали их поведение и нашли ключевые архитектурные различия, которые объясняют, почему Monte-Carlo показывает результаты хуже ожидаемых (винрейт 44-50% против более простого бота 5-го уровня сложности).

1. Как работают алгоритмы

Aggressive Bot (Difficulty 5)

Это жадный алгоритм глубины 1 (1-ply), который генерирует все возможные легальные ходы и выбирает тот, который максимизирует функцию evaluateAggressive. Эта функция включает:

• Материальный баланс.
• Штраф за подставление своего короля под бой (-2000).
• Pawn Storm Heuristics: бонус за продвижение пешек вперед.
• King Proximity: бонус за приближение тяжелых и легких фигур к королю противника.
• King Ring Pressure: бонус за атаку полей вокруг вражеского короля.

Бот не смотрит в будущее, но его эвристики заставляют его постоянно нагнетать давление и собирать фигуры вокруг чужого короля, что в Dice Chess является выигрышной тактикой, так как рано или поздно выпадут нужные кубики для мата.

Monte-Carlo Bot (Difficulty 6)

Это алгоритм Flat Monte-Carlo (без построения дерева MCTS, делает роллауты только для корневых ходов). Его логика (при лимите времени):

1. Генерирует все легальные ходы.
2. Сортирует их с помощью чисто материальной оценки (evaluateMaterial).
3. Оставляет топ-16 кандидатов (MaxCandidates = 16).
4. Запускает случайные симуляции (rollouts) до конца игры для каждого из 16 кандидатов, распределяя время поровну.
5. Выбирает ход с максимальной вероятностью победы.

2. Почему Monte-Carlo проигрывает и как его улучшить?

Мы выделили 3 главные проблемы алгоритма Monte-Carlo в текущей реализации и предлагаем способы их решения:

Идея 1: Улучшить пре-селекцию ходов (Критическая уязвимость)

Проблема: В MonteCarloSearch.scala для фильтрации топ-16 кандидатов используется Evaluator.evaluateMaterial. Это значит, что если ход не выигрывает материал (например, просто подтягивает Ферзя к вражескому королю для атаки), он получит оценку 0 и может вообще не попасть в топ-16, если есть другие ходы, съедающие пешку (оценка +100). Бот просто слеп к позиционным и атакующим ходам на этапе отбора кандидатов. Решение: Использовать Evaluator.evaluateAggressive (или гибридную оценку) вместо evaluateMaterial на этапе preScored. Это позволит боту делать роллауты для действительно опасных и атакующих ходов, а не только для жадных захватов.

Идея 2: “Тяжелые” (Эвристические) роллауты вместо случайных

Проблема: В MonteCarloEquity.advance симуляции игры делаются абсолютно случайно (random.nextInt). В шахматах чисто случайная игра быстро ведет к потере материала и подставлению короля. Это делает оценку вероятности победы (win probability) очень “шумной” и малоинформативной для стартовой позиции. Решение: Внедрить ε-жадную стратегию в роллаутах (epsilon-greedy). Например, в 70% случаев выбирать случайный ход, а в 30% — ход, который лучше по оценке evaluateMaterial или evaluateKingSafety. Альтернативно — всегда отбрасывать ходы, которые в один шаг подставляют короля под бой (использовать evaluateKingSafety внутри advance).

Идея 3: MCTS (Построение дерева) вместо Flat Monte-Carlo

Проблема: Сейчас бот распределяет время жестко поровну между топ-16 ходами (или по остаточному принципу). Он не углубляется в наиболее перспективные ветки. Решение: Реализовать полноценный UCT (Upper Confidence bound applied to Trees). Строить дерево, где каждый узел — это состояние игры. Использовать формулу UCB1 для выбора того, какой ход симулировать следующим. Это позволит алгоритму тратить больше времени на обдумывание 2-3 самых лучших кандидатов, вместо того чтобы тратить 1/16 времени на очевидно плохой ход.