3.3.1 Основоположник теории игр Эрнст Цермело: различия между версиями
Новая страница: «<span id="основоположник-теории-игр-эрнст-цермело"></span> Серьёзный разговор о теории игр обычно не обходится без упоминания немецкого математика Эрнста Цермело и его теоремы. Цермело в жизни сопутствовала научная удача: его именем названо сразу две теорем...» |
Admin (обсуждение | вклад) Нет описания правки |
||
| Строка 20: | Строка 20: | ||
Впрочем, первый вопрос представлял лишь незначительный интерес для Цермело. Его гораздо больше интересовал второй — о количестве ходов, необходимом для победы в «выигрышной позиции». Цермело приходит к выводу, что максимально необходимое для победы число ходов не превышает числа возможных позиций в игре. Он использует доказательство от противного: предположим, что число ходов, необходимое белым для победы, превышает число возможных позиций. Тогда как минимум одна выигрышная позиция будет в процессе выполнения этой последовательности ходов возникать на доске дважды. Следовательно, белые могли бы при первом возникновении этой позиции совершить тот же ход, что и во втором случае, и таким образом достичь победы за число ходов, не превышающее количества возможных позиций. | Впрочем, первый вопрос представлял лишь незначительный интерес для Цермело. Его гораздо больше интересовал второй — о количестве ходов, необходимом для победы в «выигрышной позиции». Цермело приходит к выводу, что максимально необходимое для победы число ходов не превышает числа возможных позиций в игре. Он использует доказательство от противного: предположим, что число ходов, необходимое белым для победы, превышает число возможных позиций. Тогда как минимум одна выигрышная позиция будет в процессе выполнения этой последовательности ходов возникать на доске дважды. Следовательно, белые могли бы при первом возникновении этой позиции совершить тот же ход, что и во втором случае, и таким образом достичь победы за число ходов, не превышающее количества возможных позиций. | ||
<comments /> | |||
Версия от 18:38, 8 мая 2025
Серьёзный разговор о теории игр обычно не обходится без упоминания немецкого математика Эрнста Цермело и его теоремы. Цермело в жизни сопутствовала научная удача: его именем названо сразу две теоремы, первая из них — одна из фундаментальных теорем теории множеств — называется также теоремой о полном упорядочении; вторая, доказанная в 1913 г., стала первой формальной теоремой теории игр.
В современной литературе по теории игр даются различные формулировки этой теоремы[1]. Некоторые авторы утверждают, что Цермело доказал, что шахматы являются детерминированной (т. е. лишённой элемента случайности) игрой, например: «В шахматах либо белые могут добиться форсированной победы, либо чёрные могут добиться форсированной победы, либо обе стороны могут форсировать ничью»[2], [3], [4].
Другие делают более общие утверждения, называя их теоремой Цермело, например: «В каждой конечной игре с полной информацией имеется строгое стратегическое равновесие Нэша, которое может быть найдено при помощи обратной индукции. Более того, если ни у одного из игроков нет одинаковых результатов в двух произвольных конечных узлах, то существует уникальное равновесие Нэша, которое может быть найдено таким образом»[5]. Равновесием Нэша называется ситуация, в которой ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют. Авторов не смущает, что Джон Нэш родился спустя 15 лет после доказательства теоремы Цермело.
Некоторые вообще утверждают, что белые не могут проиграть: «…в конечной игре существует стратегия, следуя которой игрок, первым осуществляющий ход… может избежать поражения, но неизвестно, существует ли стратегия, следуя которой он может победить»[6].
Кроме того, многие авторы указывают, что методом доказательства, использованным Цермело, была обратная индукция, например: «Цермело использовал этот метод ещё в 1912 году для анализа шахмат. Он начинает с конца игры и затем движется к её началу. По этой причине данную технику иногда называют обратной индукцией»[7].
Несмотря на большой интерес к теории игр, в англоязычной литературе распространилась путаница в отношении того, в чём именно заключался вклад Цермело, равно как и вклад некоторых других ранних теоретиков. Как это ни странно, проблема возникла, по всей видимости, из-за языкового барьера: многие ранние работы по теории игр были написаны на немецком и не переводились на английский. Например, оригинальная работа Цермело под названием «О применении теории множеств к теории шахмат» (Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels)[8], увидевшая свет в 1913 г., не была переведена на английский вплоть до 1997 г. Также не была своевременно переведена на английский менее известная, но связанная работа Денеша Кёнига, написанная в 1927 г.[9] Вторая статья, связанная с работой Цермело, была написана Ласло Кальмаром в 1928−1929 гг.[10], [11], но на английский язык её перевели только в 1997 г. До работы Швальбе и Уокера «Цермело и ранняя история теории игр» (Zermelo and the Early History of Game Theory)[12], написанной в 1997 г., по всей видимости, существовал только один корректный анализ работы Цермело — в статье Николая Воробьёва «Управляемые процессы и теория игр» (1955). Проблема в том, что эта книга переводилась только на немецкий язык (1975) и была недоступна англоязычному читателю. Со времён книги Воробьёва в русскоязычной литературе бытовало корректное описание вклада Цермело: «Цермело доказал детерминизм игр, подобных шахматам, и то, что рациональные игроки могут, используя полную информацию, разработать оптимальную стратегию игры». Вот как звучит вопрос, задаваемый Цермело в его статье: «Можно ли определить объективную оценку произвольной позиции в игре, а также наилучший возможный ход <…> или по крайней мере определить их математически объективно, без необходимости ссылаться на субъективные психологические понятия, такие как «идеальный игрок» и тому подобное?»
Прежде чем продолжить рассуждения о вкладе Цермело, давайте рассмотрим вопрос о максимальной длине шахматной партии. Хотя сегодня шахматы уже не столь популярны, как в 1980-е, основные правила этой игры знакомы едва ли не каждому — худо-бедно почти все мы в детстве освоили, что конь ходит «буквой Г» и что пешки не ходят назад. Однако в шахматах есть правила, о которых знает не каждый любитель. Например, установленное Международной шахматной федерацией (FIDE, от французского Fédération Internationale des Échecs) правило пятидесяти ходов гласит, что если в течение пятидесяти ходов ни одна пешка не двинулась вперёд и ни одна фигура не была взята, то в партии присуждается ничья по требованию любого из игроков. Также любой из игроков вправе потребовать присуждения ничьей в случае как минимум троекратного повторения одной и той же позиции. Благодаря правилу пятидесяти ходов ни одна из сторон не может вопреки воле другой стороны затянуть шахматную партию до бесконечности — для того чтобы она не завершилась в соответствии с вышеуказанным правилом, каждые пятьдесят ходов должно происходить хотя бы одно взятие фигуры или движение вперёд пешки и, кроме этого, позиции не должны повторяться. Весьма остроумные подсчёты показывают, что при таких условиях партия не может продолжаться больше примерно 6000 ходов[13]. В теории игроки могут отказаться от требования ничьей, несмотря на повторение позиции или превышение границы, установленной правилом пятидесяти ходов. Специально для таких случаев (в общем-то, сугубо теоретических) в 2014 г. FIDE установила специальное правило, в соответствии с которым при достижении порога в 75 ходов без взятий и движений пешек ничья присуждается автоматически. Словом, в современных шахматах есть такие тонкости, которые известны не многим. Цермело же рассматривал версию игры, в которой бесконечные партии были теоретически возможны.
Цермело задаётся двумя вопросами: во-первых, что означает, что игрок находится в «выигрышной» позиции, и можно ли это определить объективным математическим способом? Во-вторых, если он находится в выигрышной позиции, можно ли определить количество ходов, необходимых для форсированного выигрыша, то есть такого выигрыша, которому противник не может воспрепятствовать?
Чтобы дать ответ на первый вопрос, Цермело утверждает, что необходимым и достаточным условием является непустота определённого множества, содержащего все возможные последовательности ходов, такие, что игрок (например, играющий белыми фигурами) выигрывает независимо от того, как играет другой игрок. Но если это множество будет пустым, лучшее, чего сможет достичь игрок, — это ничья. Аналогичным образом Цермело определяет и другое множество, содержащее все возможные последовательности ходов, такие, что игрок может отложить своё поражение на бесконечное количество ходов, что подразумевает ничью. Это множество также может быть пустым, то есть игрок может отсрочить поражение только на конечное число ходов в случае, если его противник действует правильно. Однако последнее равносильно тому, что противник может добиться победы. Возможность того, что оба набора будут пустыми, означает, что белые не могут гарантировать, что они не проиграют.
Впрочем, первый вопрос представлял лишь незначительный интерес для Цермело. Его гораздо больше интересовал второй — о количестве ходов, необходимом для победы в «выигрышной позиции». Цермело приходит к выводу, что максимально необходимое для победы число ходов не превышает числа возможных позиций в игре. Он использует доказательство от противного: предположим, что число ходов, необходимое белым для победы, превышает число возможных позиций. Тогда как минимум одна выигрышная позиция будет в процессе выполнения этой последовательности ходов возникать на доске дважды. Следовательно, белые могли бы при первом возникновении этой позиции совершить тот же ход, что и во втором случае, и таким образом достичь победы за число ходов, не превышающее количества возможных позиций.
- ↑ Schwalbe U., Walker P. (1997, 1999). Zermelo and the Early History of Game Theory // http://abel.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
- ↑ Aumann R. J. (1989). Game Theory / Eatwell J., Milgate M., Newman P. (1989). The New Palgrave: Game Theory, Macmillan Press, London.
- ↑ Eichberger J. (1993). Game Theory for Economists, Academic Press, San Diego.
- ↑ Hart S. (1992). Games in Extensive and Strategic Forms, in Robert J. Aumann and Sergiu Hart (eds.), Handbook of Game Theory, Volume 1, NorthHolland, Amsterdam.
- ↑ Mas-Colell A., Whinston M. D., Green J. R. (1995). Microeconomic Theory, Oxford University Press, New York.
- ↑ Dimand M. A., Dimand R. W. (1996). A History of Game Theory, Volume 1: From the Beginnings to 1945, Routledge, London.
- ↑ Binmore K. (1992). Fun and Games: A Text on Game Theory, D. C. Heath and Company, Lexington
- ↑ Zermelo E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels / Proceedings of the Fifth Congress Mathematicians (Cambridge 1912), pp. 501–504 // https://doi.org/10.1007/978-3-540-79384-7_9
- ↑ Kőnig D. (1927). Uber eine Schlussweise aus dem Endlichen ins Unendliche / Acta Scientiarum Mathematicarum, Vol. 3, pp. 121–130.
- ↑ Kalmár L. (1928, 1929), Zur Theorie der abstrakten Spiele / Acta Scientiarum Mathematicarum, Vol. 4, pp. 65–85.
- ↑ Dimand M. A., Dimand R. W. (1997). The Foundations of Game Theory, Volume I. Edward Elgar, Aldershot.
- ↑ Schwalbe U., Walker P. (1997, 1999). Zermelo and the Early History of Game Theory // http://abel.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf
- ↑ Godden K. (2007). The Longest Possible Chess Game / Blog at Chess.com // https://www.chess.com/blog/kurtgodden/the-longest-possible-chess-game