Теорема Цермело (теория игр)
В теории игр теорема Цермело — это теорема о конечных играх двух лиц с совершенной информацией , в которых игроки ходят поочередно и в которых случайность не влияет на процесс принятия решений. В нем говорится, что если игра не может закончиться вничью, то один из двух игроков должен иметь выигрышную стратегию (т.е. может добиться победы). Альтернативное утверждение состоит в том, что для игры, удовлетворяющей всем этим условиям, за исключением условия, что теперь возможна ничья, тогда либо первый игрок может добиться победы, либо второй игрок может добиться победы, либо оба игрока могут, по крайней мере, форсировать ничью. [ 1 ] Теорема названа в честь Эрнста Цермело , немецкого математика и логика, который доказал теорему на примере игры в шахматы в 1913 году.
Пример
[ редактировать ]Теорему Цермело можно применить ко всем играм для двух игроков с конечным этапом, полной информацией и чередующимися ходами. Игра должна удовлетворять следующим критериям: в игре участвуют два игрока; игра содержит полную информацию; настольная игра конечна; два игрока могут делать ходы поочередно; и здесь нет элемента случайности. Цермело заявил, что игр такого типа существует множество; однако его теорема применялась в основном к игре в шахматы. [ 2 ] [ 3 ]
Применительно к шахматам теорема Цермело гласит: «Либо белые могут добиться победы, либо черные могут добиться победы, либо обе стороны могут добиться хотя бы ничьей». [ 2 ] [ 3 ]
Алгоритм Цермело является краеугольным алгоритмом теории игр; однако его также можно применять и за пределами конечных игр. Помимо шахмат, теорема Цермело применяется во всех областях информатики . В частности, он применяется при проверке моделей и взаимодействии значений . [ 4 ]
Выводы теоремы Цермело.
[ редактировать ]Работа Цермело показывает, что в играх двух человек с нулевой суммой и совершенной информацией, если игрок находится в выигрышной позиции, то он всегда может добиться победы, независимо от того, какую стратегию может использовать другой игрок. Более того, и, как следствие, если игрок находится в выигрышной позиции, ему никогда не потребуется больше ходов, чем имеется позиций в игре (при этом позиция определяется как положение фигур, а также игрока, следующего за ходом). [ 1 ]
История публикаций
[ редактировать ]В 1912 году на Пятом Международном конгрессе математиков в Кембридже Эрнст Цермело выступил с двумя докладами. В первом речь шла об аксиоматических и генетических методах основания математических дисциплин, а второе было посвящено игре в шахматы. Второе выступление побудило Цермело написать статью по теории игр. Будучи заядлым шахматистом, Цермело интересовался применением теории множеств к игре в шахматы. Оригинальная статья Цермело, описывающая теорему, «Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels » была опубликована на немецком языке в 1913 году. Ее можно считать первой известной статьей по теории игр. [ 5 ] Ульрих Швальбе и Пол Уокер перевели статью Цермело на английский язык в 1997 году и опубликовали перевод в приложении к книге « Цермело и ранняя история теории игр» . [ 1 ]
Подробности
[ редактировать ]Цермело рассматривает класс безслучайных игр двух лиц, в которых интересы игроков строго противоположны и где возможно лишь конечное число позиций. Хотя в игре возможно только конечное число позиций, Цермело допускает бесконечные последовательности ходов, поскольку он не учитывает правила остановки. Таким образом, он допускает возможность бесконечных игр. Затем он решает две проблемы:
- Что значит для игрока находиться в «выигрышной» позиции и можно ли это определить объективным математическим способом?
- Если игрок находится в выигрышной позиции, можно ли определить количество ходов, необходимое для победы?
Отвечая на первый вопрос, Цермело утверждает, что необходимым и достаточным условием является непустота некоторого множества, содержащего все возможные последовательности ходов, при которых игрок выигрывает независимо от того, как играет другой игрок. Но если этот набор окажется пустым, лучшее, чего может добиться игрок, — это ничья. Поэтому Цермело определяет другой набор, содержащий все возможные последовательности ходов, такие, что игрок может отложить свой проигрыш на бесконечное количество ходов, что подразумевает ничью. Этот набор также может быть пустым, т. е. игрок может избежать проигрыша только за конечное число ходов, если его противник играет правильно. Но это эквивалентно тому, что противник может добиться победы. Это основа всех современных версий теоремы Цермело.
По поводу второго вопроса Цермело заявил, что ходов никогда не будет больше, чем позиций в игре. Его доказательство представляет собой доказательство от противного : предположим, что игрок может выиграть за количество ходов, превышающее количество позиций. По принципу «ячейки» хотя бы одна выигрышная позиция должна появиться дважды. Таким образом, игрок мог бы сыграть в первый раз так же, как и во второй, и, таким образом, мог бы выиграть за меньшее количество ходов, чем имеется позиций.
В 1927 году венгерский математик Денес Кениг пересмотрел статью Цермело и указал на некоторые пробелы в исходной работе. Прежде всего, Кёниг утверждает, что Цермело не доказал, что игрок, например белые, находящиеся в выигрышной позиции, всегда способен добиться победы, делая ходы меньше, чем количество позиций в игре. Цермело утверждал, что белые могут изменить свое поведение при первой же возможности любой соответствующей выигрышной позиции и выиграть без повторения. Однако Кениг утверждает, что этот аргумент неверен, поскольку недостаточно уменьшить количество ходов в одной игре ниже количества возможных позиций. Таким образом, Цермело утверждал, но не доказал, что игрок-победитель всегда может побеждать без повторений. Второе возражение Кенига заключается в том, что стратегия «при первом появлении позиции делать то же самое, что и при втором, и, таким образом, выиграть за меньшее количество ходов» не может быть реализована, если настала очередь черных делать ход в этой позиции. Однако этот аргумент неверен, поскольку Цермело рассматривал две разные позиции независимо от того, делают ли ход черные или белые. [ 5 ]
Теорема Цермело и обратная индукция
[ редактировать ]Считалось, что Цермело использовал обратную индукцию в качестве метода доказательства. Однако недавнее исследование теоремы Цермело показывает, что обратная индукция не использовалась для объяснения шахматной стратегии. Вопреки распространенному мнению, шахматы не являются конечной игрой без хотя бы одного правила пятидесяти ходов или правила трехкратного повторения . Строго говоря, шахматы — бесконечная игра, поэтому обратная индукция не дает теоремы о минмаксе в этой игре. [ 6 ]
Обратная индукция – это процесс рассуждения назад во времени. Он используется для анализа и решения обширных игр с полной информацией. Этот метод анализирует игру, начиная с конца, а затем работает в обратном направлении, чтобы достичь начала. При этом обратная индукция определяет лучшую стратегию для игрока, сделавшего последний ход. Затем определяется окончательная стратегия для предпоследнего ходящего игрока в игре. Процесс повторяется еще раз, определяя лучшее действие для каждого найденного момента в игре. Следовательно, обратная индукция определяет равновесие Нэша каждой подыгры в исходной игре. [ 4 ]
Существует ряд причин, по которым обратная индукция не присутствует в оригинальной статье Цермело:
Во-первых, недавнее исследование Швальбе и Уокера (2001) продемонстрировало, что статья Цермело содержит основную идею обратной индукции; однако Цермело не сделал формального заявления по поводу теоремы. Оригинальным методом Цермело была идея неповторения. Первое упоминание об обратной индукции было сделано Ласло Кальмаром в 1928 году. Кальмар обобщил работу Цермело и Кенига в своей статье «К теории абстрактных игр». Кальмара волновал вопрос: «Как быстро можно добиться победы, учитывая выигрышную позицию?». Его статья показала, что победа без повторений возможна при условии, что игрок находится в выигрышной позиции. Доказательство Кальмара неповторения было доказательством обратной индукции. В своей статье Кальмар представил концепцию субигры и тактики. Главный аргумент Кальмара заключался в том, что позиция может быть выигрышной только в том случае, если игрок может выиграть за конечное число ходов. Кроме того, выигрышная позиция для игрока А всегда является проигрышной позицией для игрока Б. [ 7 ]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Швальбе, Ульрих; Уокер, Пол. «Цермело и ранняя история теории игр» (PDF) .
- ^ Jump up to: а б МакКуорри, Джон (январь 2005 г.). «Математика и шахматы. Основы» . Архивировано из оригинала 12 января 2017 года.
- ^ Jump up to: а б Ауманн, Р.Дж. (1989). Лекции по теории игр (PDF) . Боулдер, Колорадо: Westview Press. п. 1.
- ^ Jump up to: а б Вулдридж, Майкл (17 марта 2015 г.). «Думая назад с профессором Цермело». Интеллектуальные системы IEEE . 30 (2): 62–67. дои : 10.1109/MIS.2015.36 . S2CID 12397521 .
- ^ Jump up to: а б Эббингауз, Хайнц-Дитер (14 октября 2010 г.). Эрнст Цермело: подход к его жизни и работе (2-е изд.). Берлин: Шпрингер. п. 150. ИСБН 9783642080500 . Проверено 26 апреля 2021 г.
- ^ Эверхарт, Кристиан (май 2002 г.). «Обратная индукция и теоретико-игровой анализ шахмат» (PDF) . Игры и экономическое поведение . 39 (2): 206–214. дои : 10.1006/game.2001.0900 .
- ^ Швальбе, Ульрих; Пол, Уокер (январь 2001 г.). «Цермело и теория игр ранней истории» . Игры и экономическое поведение . 34 (1): 123–137. дои : 10.1006/game.2000.0794 . Проверено 26 апреля 2021 г.
Внешние ссылки
[ редактировать ]- Оригинальная бумага (на немецком языке)
- Ульрих Швальбе, Пол Уокер, Цермело и ранняя история теории игр , Игры и экономическое поведение, том 34, 2001, 123-137, онлайн