03 Идеи по улучшению алгоритмов

Анализ алгоритмов и идеи по улучшению

В ходе разработки бота на базе Monte Carlo Tree Search (MCTS) и его сравнения с базовым Monte-Carlo ботом, был проведён глубокий анализ текущих алгоритмов. Ниже представлены ключевые наблюдения и архитектурные идеи, которые могут значительно повысить силу игры ботов и эффективность использования процессорного времени.

1. MCTS: Предварительная сортировка и прунинг ходов (Candidate Pruning)

Текущая проблема: В функции расширения узлов MctsSearch генерируются все легальные пути (комбинации из 3-х микро-ходов). В Dice Chess таких путей на одном ходу может быть от 50 до 300+. В условиях ограниченного времени (TimeBudgetedSearch) бот случайным образом разворачивает эти ходы. Это приводит к тому, что львиная доля драгоценных итераций MCTS (вычислительного времени) тратится на заведомо плохие ходы (например, подставы ферзя, бессмысленные движения пешек и т.д.), прежде чем алгоритм успевает оценить действительно сильные продолжения с помощью UCT.

Предлагаемое решение: Вместо перемешивания untriedPaths случайным образом:

1. Предварительная оценка (Pre-scoring): Использовать Evaluator.evaluateMaterial для быстрой оценки всех сгенерированных путей.
2. Сортировка / Усечение (Truncation): Сортировать untriedPaths по материальной оценке и брать только Топ-N лучших путей (например, MaxCandidates = 16, как это уже сделано в MonteCarloSearch).
3. Progressive Widening: Альтернативно, можно открывать новые ветки постепенно, но сначала всегда пробовать самые перспективные с точки зрения материала.

Это позволит UCT-дереву фокусироваться на тактически осмысленных ветках с первых миллисекунд.

2. MCTS: Безопасный выбор корневого действия

Текущая проблема: После завершения времени на поиск MctsSearch выбирает потомка с максимальным количеством посещений (maxBy(_.visits)). Однако, если из-за высокого фактора ветвления мы успели раскрыть лишь малую часть узлов (например, 5 узлов из 100), у всех них будет по 1 посещению. В этом случае выбор становится произвольным, и бот может сделать случайный плохой ход вместо лучшего из доступных материальных ходов.

Предлагаемое решение: Применять эвристику “безопасного отступления” (Fallback). На корневом узле, при выборе финального хода, если максимальное количество посещений слишком мало (например, <= 2), следует отказаться от выбора на основе MCTS и выбрать ход с наилучшей оценкой Evaluator.evaluateMaterial. Это предотвратит случайные “зевки” при сильном недостатке времени (цейтноте).

3. Обработка случайных узлов (Chance Nodes)

Текущая проблема: В MctsSearch случайные узлы обрабатываются путём реального случайного броска 3-х кубиков (List(random.nextInt(6)+1, ...)). При малом количестве итераций мы можем неравномерно исследовать вероятностное пространство. Более того, существует 56 уникальных отсортированных комбинаций бросков 3 кубиков.

Предлагаемое решение: Использовать формулу математического ожидания или взвешенного MCTS для Chance Nodes. Вместо генерации новых дочерних узлов броском кубика случайным образом (Open-Loop MCTS), можно использовать подмножество наиболее частых бросков или делать небольшое дерево, где каждый бросок сразу имеет свой вес (вероятность выпадения). Это сложнее в реализации, но даёт более точную сходимость.

4. Оптимизация Rollout-фазы (Simulation)

Текущая проблема: Фаза simulate делает один плейаут до самого конца игры. В Dice Chess случайные плейауты часто бывают очень длинными и “шумными” (много случайных ходов, пока кто-то не захватит короля). Из-за этого оценка получается с большой дисперсией.

Предлагаемое решение: Внедрить Early Cutoff (Раннее отсечение). Делать плейаут не до победы/поражения, а на фиксированную глубину (например, 10-15 полуходов). По достижении этой глубины останавливать симуляцию и возвращать результат Evaluator.evaluateMaterial, нормализованный в диапазон [0, 1]. Это:

• Радикально увеличит скорость симуляции (больше итераций MCTS в секунду).
• Снизит дисперсию, так как статический эвалюатор часто надежнее чисто случайных длинных бросков.

Резюме

Бот MCTS уже обладает мощным фундаментом за счет баланса “исследование / эксплуатация”. Однако в играх с большим фактором ветвления (коим является Dice Chess) “чистый” MCTS без эвристик сильно проигрывает. Интеграция статического эвалюатора (evaluateMaterial) в фазы расширения (для прунинга) и симуляции (для обрыва) превратит MCTS в алгоритм, на порядок превосходящий текущую MonteCarlo реализацию.