Теорема Цермело
англ. Zermelo's theorem
В конечной игре двух лиц с полной информацией и без случайности у одного из игроков есть выигрышная стратегия либо обе стороны могут гарантировать ничью.
«В шахматах есть либо выигрышная стратегия у белых, либо у чёрных, либо обе стороны могут форсировать ничью» — так в 1913 году Эрнст Цермело сформулировал утверждение, с которого принято начинать введение в теорию игр. Теорема Цермело: в конечной парной игре с полной информацией и без элемента случайности каждая позиция либо выигрышна для одного из игроков, либо ничейна, и у одного из игроков существует стратегия, гарантирующая ему лучший из доступных исходов. Доказательство — обратная индукция по дереву игры: листьям приписываются платежи, значения поднимаются к корню, и каждый узел получает максимум или минимум по детям в зависимости от того, чей ход. Ни расстановки фигур, ни шахматного опыта теорема не требует — только конечность дерева и полнота информации у обеих сторон.
Для крестиков-ноликов разбор достижим вручную: 9 клеток, у крестиков не более 5 ходов, исходов ровно 3 — победа крестиков, победа ноликов, ничья; обратная индукция показывает, что при точной игре обеих сторон партия заканчивается ничьей, а первый игрок не проигрывает никогда. Для шахмат вывод остаётся чистой теорией: стратегия существует, но дерево игры необъятно, и никакой компьютер не просчитает его целиком — теорема ничего не говорит о том, чья именно стратегия выигрышна и как её найти. Распространённая ошибка — читать теорему как «у белых есть выигрыш»: доказана лишь дизъюнкция трёх исходов, и какой из них реализуется, неизвестно до сих пор. За границей применимости остаются игры со случайностью вроде костей, со скрытой информацией вроде покера и бесконечные игры: там гарантированного значения у позиции нет, и требуются другие результаты.
Частые вопросы
Значит ли теорема Цермело, что в шахматах у белых есть выигрыш?
Нет. Теорема утверждает дизъюнкцию из трёх вариантов: выигрышная стратегия у белых, выигрышная у чёрных или ничья при точной игре — но не говорит, какой из них реализуется. Доказательство существования не предъявляет стратегию, а полный перебор позиций недоступен ни одному компьютеру. Для более простых игр дизъюнкция разрешена вычислением: в крестиках-ноликах это ничья, а в шашках проект Chinook в 2007 году доказал ничью при точной игре обеих сторон. Для шахмат ответ неизвестен до сих пор.
К каким играм теорема Цермело неприменима?
К играм со случайностью: бросок кости делает исход негарантированным — работают ожидания и смешанные стратегии. К играм со скрытой информацией вроде покера: позиция известна не целиком, дерево теряет полноту, неразличимые позиции собираются в информационные множества. К бесконечным играм: у дерева без листьев индукции не за что зацепиться. Наконец, теорема — про двух участников: при трёх и более интересы не сводятся к противоположности, и коалиции ломают минимаксную логику.