Позиция в игре

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

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

Классификация позиций

Если игрок, которому нужно сделать ход, может при некоторой стратегии гарантировать победу, позицию называют выигрышной. Если же при любых его действиях соперник может добиться победы, позиция проигрышная. Для конечных игр без ничьих каждая позиция относится ровно к одному из этих двух классов.

Здесь \(P\) — текущая позиция, \(Moves(P)\) — множество позиций, достижимых одним ходом, а \(W\) и \(L\) обозначают выигрышность и проигрышность. Терминальная позиция без разрешённых ходов считается проигрышной для игрока, который должен ходить.