Уже очень давно математики знают способ построения оптимальной стратегии в любой игре с дискретным пространством состояний и с полной информацией. Многие его знают как Minimax-алгоритм, логика работы следующая:
1) Построим направленный граф состояний игры.
- Каждое возможное состояние в игре обозначим как вершину графа
- Рёбра между вершинами будем проводить согласно правилам - если из одного состояния в другое игра может перейти в результате хода игрока, проведём это ребро
- Для корректной работы алгоритма требуется отсутствие циклов в графе. Обычно правила игры позволяют такое утверждение доказать
2) Разметим "листья" графа
Вершины без исходящих из них рёбер нужно разметить их соответствующим финальным результатом - ничьей или победой какого-то игрока
3) Рекурсивно разметить все вершины в графе
Эта функция работает для данной вершины
v так:- Вызываем её сначала для всех вершин, в которые из
v есть ребро- В зависимости от того, чей ход в данном состоянии игры, выбираем среди этих вершин результат, наиболее желаемый для него, и присваиваем его вершине
v.- Так как обычно в играх 2 игрока и они ходят по очереди, получается, что выбор результата чередуется: если в вершине
v выбирается "максимальный" результат для игрока 1, то в его детях уже будет выбираться "минимальный" для него результат, т.к. ходит противник. Получается Minimax.С одной стороны, очень простой алгоритм позволяет получить оптимальную стратегию в любой игре. С другой, его сложность по времени и памяти слишком велика для применения в реальных играх, и поэтому не применяется в таком виде, приходится костылить. Но об этом в другой раз.
@knowledge_accumulator