Выигрышные и проигрышные позиции

Речь про игры одного узкого класса, зато решаются они полностью:

• играют двое и ходят по очереди;
• набор ходов зависит только от позиции, а не от того, чей ход (такие игры называют беспристрастными);
• случайности нет, оба видят всё;
• игра конечна: бесконечно ходить нельзя;
• проигрывает тот, кто не может сделать ход.

Шахматы сюда не попадают: белые не могут ходить чёрными фигурами. А ним, разрезание пирога, передвижение фишки по графу — попадают.

Два правила

Назовём позицию проигрышной, если проигрывает тот, чей ход, и выигрышной, если он выигрывает. Слова относятся к тому, кто ходит из этой позиции, — это главный источник путаницы.

ситуация	позиция
ходов нет	проигрышная
есть ход в проигрышную	выигрышная
все ходы ведут в выигрышные	проигрышная

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

Как считать

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

bool win(int v) {
    if (computed[v]) return value[v];
    computed[v] = true;
    value[v] = false;
    for (int u : moves[v]) if (!win(u)) value[v] = true;
    return value[v];
}

Обратите внимание: цикл не прерывается на первом успехе — так удобнее, когда попутно нужно собрать ещё что-нибудь (например, все выигрышные ходы). Сложность — $O(V + E)$: каждая позиция считается один раз, каждый ход просматривается один раз.

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

Типичная ошибка

Формулировка «проигрывает тот, кто взял последний камень» — это другая игра. Правила выше про «проигрывает тот, кто не может сходить». Вариант с последним камнем называется мизерным, и ответ в нём другой; см. «Ним».

Проверяйте это первым делом: из-за одной фразы в условии меняется весь ответ.

Смежное

• Ретроанализ и ничьи — если в графе позиций есть циклы;
• Функция Гранди — если позиция распадается на независимые части.