Победа первого и второго игрока
В комбинаторной теории игр для двух игроков с идеальной информацией детерминированная пошаговая игра является победой первого игрока, если при идеальной игре первый игрок, который сделает ход, всегда может добиться победы. Аналогичным образом, игра считается выигрышной для второго игрока, если при идеальной игре второй игрок, который сделает ход, всегда может добиться победы. При идеальной игре, если ни одна из сторон не может добиться победы, игра заканчивается вничью .
в некоторых играх с относительно небольшими игровыми деревьями Было доказано, что выигрывает первый или второй игрок. Например, игра «Ним» с классической стартовой позицией 3–4–5 – это игра, в которой выигрывает первый игрок. Однако Ним со стартовой позицией 1-3-5-7 — это победа второго игрока. в классической игре Connect Four Математически доказано, что выигрывает первый игрок.
При идеальной игре в шашках была определена ничья; ни один из игроков не может добиться победы. [ 1 ] Еще одним примером игры, которая приводит к ничьей при идеальной игре, являются «крестики-нолики» , включая игру с любого первого хода.
Значительная теория была завершена в попытках решить шахматы . Было высказано предположение, что может существовать преимущество первого хода , которое можно обнаружить, когда игра ведется неидеально (например, со всеми людьми и всеми современными шахматными движками ). Однако при идеальной игре остается нерешенным вопрос о том, является ли игра победой первого игрока (белые), победой второго игрока (черные) или вынужденной ничьей. [ 2 ] [ 3 ] [ 4 ]
См. также
[ редактировать ]- Решенная игра
- Аргумент о краже стратегии
- цугцванг
- Определенность
- Комбинаторная теория игр
- Преимущество первого хода в шахматах
Ссылки
[ редактировать ]- ^ Шеффер, Дж.; Берч, Н.; Бьернссон, Ю.; Кишимото, А.; Мюллер, М.; Лейк, Р.; Лу, П.; Сатфен, С. (2007). «Шашки решены» . Наука . 317 (5844): 1518–1522. Бибкод : 2007Sci...317.1518S . дои : 10.1126/science.1144079 . ПМИД 17641166 . S2CID 10274228 .
- ^ JWHM Uiterwijk, HJ ван ден Херик. «Преимущество инициативы ». (август 1999 г.).
- ^ Шеннон, К. (март 1950 г.). «Программирование компьютера для игры в шахматы» (PDF) . Философский журнал . 7. 41 (314). Архивировано из оригинала (PDF) 6 июля 2010 г. Проверено 27 июня 2008 г.
- ^ Виктор Эллис (1994). «Докторская диссертация: Поиск решений в играх и искусственном интеллекте» (PDF) . Кафедра компьютерных наук . Университет Лимбурга . Архивировано из оригинала (PDF) 22 ноября 2020 г. Проверено 14 июля 2012 г.
 | Эта прикладной математике, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее . |