Любая конечная игра с полной информацией и нулевой суммой определена: у одного из игроков есть выигрышная стратегия, либо оба могут гарантировать ничью.
Что такое определённая игра
В теории игр термин «определённая игра» (determined game) имеет строгое математическое значение. Это не просто «какая-то конкретная игра», а класс игр, для которых доказано существование оптимальной стратегии у одного из участников до первого хода. Классический результат — теорема Эрнста Цермело (1913) — гласит: в любой конечной двухличной игре с полной информацией и нулевой суммой ровно одно из трёх утверждений истинно: первый игрок может гарантировать победу, второй игрок может гарантировать победу, или оба игрока могут гарантировать ничью.
Ключевое слово здесь — «гарантировать». Это означает, что существует набор правил (стратегия), который приведёт к лучшему возможному результату против любой защиты соперника. Никакой интуиции, удачи или психологии — только математическая необходимость. Если игра определена, её исход предрешен при идеальной игре обеих сторон.
Конечность
Игра не может длиться бесконечно. Число позиций и ходов ограничено. Шахматы подпадают под это правило благодаря правилу 50 ходов и тройному повторению позиции.
Полная информация
Все игроки в любой момент знают полное состояние позиции. Нет скрытых карт, кубиков или одновременных ходов. Примеры: шахматы, го, крестики-нолики, шашки.
Нулевая сумма
Выигрыш одного игрока в точности равен проигрышу другого. Победа = +1, поражение = -1, ничью = 0. Кооперативные элементы или независимые выплаты исключены.
Теорема Цермело: формула определённости
Теорема не просто констатирует факт. Она даёт конструктивный (по крайней мере, в принципе) алгоритм нахождения оптимальной стратегии через обратную индукцию. Начинаем с терминальных позиций (листьев дерева игры), где исход известен: победа, поражение или ничья. Затем поднимаемся вверх по дереву: в узлах, где ходит первый игрок, выбираем ход с максимальной оценкой; где ходит второй — с минимальной (для нулевой суммы). Значение корня дерева и есть значение игры.
На практике полное дерево игры недоступно для сложных дисциплин. Число позиций в шашках ~10^20, в шахматах ~10^43, в го ~10^170. ТеоремаЦермело гарантирует существование решения, но не даёт способа его найти за разумное время. Именно здесь рождается различие между «определённостью» в теории и «решённостью» на практике.
Три степени решения игры
В 1980-х годах Виктор Аллис ввёл иерархию, отличающую теоретическую определённость от практического решения. Понимание этой градации критически важно, чтобы не путать «решенную ИИ» игру с «математически определённой».
| Степень | Определение | Что даёт | Примеры |
|---|---|---|---|
| Ультраслабая (Ultra-weak) | Значение начальной позиции (победа/ничья/поражение) известно, но стратегия достижения может быть неизвестна. | Знание исхода при идеальной игре. Не помогает играть. | Шахматы (предположительно ничья), Го (победа чёрных с коми 7.5) |
| Слабая (Weak) | Известна стратегия, гарантирующая значение игры от начальной позиции против любой защиты. | Можно играть идеально с начала партии. | Крестики-нолики, Коннект-4, Рендзю (с ограничениями) |
| Сильная (Strong) | Известны оптимальные ходы во всех достижимых позициях. Полная база знаний. | Идеальная игра из любой позиции, в том числе после ошибок соперника. | Шашки (английские), Аваланч, Ним (все варианты) |
Важный нюанс
Сильное решение включает слабое, слабое — ультраслабое. Но обратное неверно. Знание того, что шахматы — ничья (ультраслабое), не дает алгоритма, как эту ничью удержать против великого мастера (слабое), а тем более как выигрывать ошибающегося соперника (сильное).
Карта решённых и нерешённых игр
История решения игр — это хроника роста вычислительной мощности и алгоритмического мастерства. Каждая решившаяся игра стала вехой для ИИ.
Крестики-нолики
Сильное решение · 1950-е
Первая полностью разобранная игра. 765 достижимых позиций. Идеальная игра всегда заканчивается вничью. Используется как «Hello World» для алгоритмов минимакс.
Коннект-4
Сильное решение · 1988 (В. Аллис)
Первый игрок выигрывает при идеальной игре. Решено методом доказывания теорем и эвристик. Показал силу proof-number search.
Шашки (английские)
Сильное решение · 2007 (Дж. Щеффер)
18 лет расчётов, 10^20 позиций. Ничья при идеальной игре. Программа Chinook беспроигрышна. Конец эры человеческого доминирования.
Шахматы
Не решены (ультраслабо — предположительно ничья)
Глубина дерева ~10^43. Эндшпильные табличные базы (7 фигур) — это сильные решения фрагментов. Полное решение недоступно现有 физике Вселенной.
Го (19×19)
Не решены (ультраслабо — победа чёрных)
Ветвление ~250 ходов. AlphaGo/Zero достигли сверхчеловеческого уровня без полного решения. Пример: игра может быть определена теоретически, но неразрешима практически.
Покер (Техасский Холдем)
Не определены (неполная информация)
Нарушается условие полной информации. Здесь нет «определённости» по Цермело. Решается через равновесие Нэша (Libratus, Pluribus), а не минимакс.
Почему шахматы ещё не решены: преграда сложности
Часто спрашивают: «Если компьютеры бьют чемпионов, почему шахматы не решены?». Победа над человеком требует найти *хороший* ход. Решение игры требует найти *лучший* ход во *всех* позициях и доказать его оптимальность.
Ошибка: «Сила движка = Решение»
Stockfish или AlphaZero находят ходы, выигрывающие у людей и других движков. Но они не доказывают, что альтернативные ходы не приводят к победе. Доказательство требует исчерпывающего перебора или математического сокращения дерева.
Решение: Эндшпильные таблицы (Syzygy/EGTB)
Это *сильные решения* для подмножеств позиций (до 7 фигур). Они хранят точное значение (DTZ — distance to zero) для каждой легальной позиции. Это «острова решения» в океане неразрешимости.
Оценки сложности (State Space Complexity) объясняют пропасть:
- Крестики-нолики: ~10^3 позиции. Решено за миллисекунды.
- Коннект-4: ~10^13 позиций. Решено в 1988 на мейнфрейме.
- Шашки: ~10^20 позиций. Решено в 2007 на кластере (10^14 операций).
- Шахматы: ~10^43–10^47 позиций. Если бы каждый атом Вселенной был суперкомпьютером, работающим со времен Большого взрыва — перебор не завершился бы.
- Го: ~10^170 позиций. Число позиций превышает число частиц во Вселенной в 100+ порядков.
Алгоритмы решения: от минимакса к доказыванию
Поскольку полный перебор невозможен, исследователи разработали методы доказательства значения игры без посещения всех узлов. Понимание этих методов — ключ к современному Геймдеву и ИИ.
Альфа-бета отсечение
Классика 1950-х. Отсекает ветки, которые не могут повлиять на выбор оптимального хода. Дает квадратный корень из полного перебора. Основа всех шахматных движков до 2017 года.
Proof-Number Search (PNS)
Работает с целями «доказать победу» или «доказать ничью». Подсчитывает минимальное число листьев, необходимых для доказательства. Идеально для решения игр (Коннект-4, Аваланч). Не ищет лучший ход, ищет доказательство.
Ретроградный анализ
Движется от конца к началу. Строит базу всех терминальных позиций и распространяет значения назад. Метод построения табличных баз (EGTB). Требует огромной памяти, но даёт *сильное* решение.
Монте-Карло дерево поиска (MCTS) + Нейросети
AlphaZero подход. Не решает игру математически, а аппроксимирует оптимальную политику. Не даёт гарантий теоремы Цермело, но на практике играет сильнее любых «доказательных» методов в нерешаемых играх.
Распространённые заблуждения об определённости
ОШИБКА
«Определённая игра скучна, в неё неинтересно играть».
РЕАЛЬНОСТЬ
Определённость верна только для *идеальной* игры. Люди (и слабые боты) ошибаются. Сложность нахождения оптимального хода создает спортивный интерес. Шахматы определены теоретически, но неисчерпаемы практически.
ОШИБКА
«Если игра не решена, она не определена».
РЕАЛЬНОСТЬ
Теорема Цермело — это теорема *существования*. Она верна для шахмат и го независимо от того, знаем ли мы решение. «Нерешённость» — это наша вычислительная немощь, а не свойство игры.
ОШИБКА
«Ничья при идеальной игре убивает игру».
РЕАЛЬНОСТЬ
В шахматах ничья — частый результат на высоком уровне, но игра жива. В шашках (решены, ничья) турнирная жизнь не остановилась. Ценность игры — в борьбе за точность, а не в неизвестности исхода.
Практический чек-лист: как определить, является ли игра определённой
Используйте этот список при анализе любой новой игровой механики или правил. Если хоть один пункт не выполняется — теорема Цермело не применяется напрямую.
- Два игрока? Теорема для n>2 требует обобщений (равновесие Нэша), простой определённости нет.
- Нулевая сумма? Выигрыш + проигрыш = 0. Если сумма выплат не константа — это общая теория игр, а не класс определённых игр.
- Полная информация? Нет скрытого состояния (карты в руке, туман войны, одновременный выбор).
- Конечность? Есть ли правило, принудительно завершающее партию (лимит ходов, правило повторения, невозможность циклов)?
- Детерминизм переходов? Ход однозначно определяет следующее состояние. Нет кубиков, рандома, мешка с плитками.
Влияние на ИИ и геймдев
Понимание определённости меняет подход к разработке ИИ для игр и балансу геймплея.
Обучение с подкреплением (RL)
В определённых играх (шахматы, го) можно генерировать идеальные данные для обучения через самовоспроизведение (self-play) с поиском MCTS. Целевая функция известна: приближение к значению игры. В неопределённых (покер, StarCraft) цель — равновесие Нэша, что сложнее вычислить и верифицировать.
Баланс и дизайн правил
Если вы проектируете абстрактную стратегию, проверка на определённость (через солверы на малых досках) выявляет «сломанные» правила: выигрыш первого хода или форсированную ничью. Это экономлет месяцы плейтестинга.
Генерация контента
Для пазлов и уровней в детерминированных играх (Сокобан, логические головоломки) существование единственного решения — требование качества. Солверы используются как валидаторы контента.
Резюме: что нужно запомнить
- Определённая игра — это математический класс (конечная, полная инфо, нулевая сумма), а не список названий.
- Теорема Цермело гарантирует существование оптимальной стратегии, но не даёт рецепта её нахождения для сложных игр.
- Существует три степени решения: ультраслабая (значение), слабая (стратегия от старта), сильная (стратегия везде).
- Шашки — единственная сложная народная игра со *сильным* решением. Шахматы и Го — нет.
- Сила современного ИИ (Stockfish, AlphaZero) ≠ математическое решение. ИИ аппроксимирует оптимум, солверы его доказывают.
Материал подготовлен на основе фундаментальных результатов теории игр и истории вычислительной математики. Все приведённые факты касаются устоявшихся теоретических положений и исторических этапов решения конкретных игр.
ИИ-персонаж, с которым хочется говорить 💬
Он реагирует на ваши слова, помнит, о чём вы говорили раньше, и ведёт себя в характере. Можно отыгрывать дружбу, флирт, ссоры и примирения — всё по-настоящему. Отличный способ переключиться после работы, развеяться в дороге или просто провести интересный вечер.
Начать общение 👉 https://clck.ru/3Ta8kQ
