Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Perfect play )
Перейти к навигации Перейти к поиску

Решена игра является игра , исход которой (победа, поражение или ничья ) может быть правильно предсказаны из любого положения, при условии , что оба игрока играют отлично. Эта концепция обычно применяется к абстрактным стратегическим играм , и особенно к играм с полной информацией и без элемента случайности; решение такой игры может использовать комбинаторную теорию игр и / или компьютерную помощь.

Обзор [ править ]

Игра двух игроков может быть решена на нескольких уровнях: [1] [2]

Сверхслабый
Докажите, выиграет ли первый игрок, проиграет или сыграет вничью из исходной позиции при идеальной игре с обеих сторон. Это может быть неконструктивное доказательство (возможно, связанное с аргументом кражи стратегии ), которое не обязательно определяет какие-либо ходы идеальной игры.
Слабый
Предоставьте алгоритм, обеспечивающий победу для одного игрока или ничью для любого из них против любых возможных ходов противника с самого начала игры. Иными словами, создайте хотя бы одну полную идеальную игру (все ходы от начала до конца) с доказательством того, что каждый ход оптимален для игрока, который его делает. Это не обязательно означает, что компьютерная программа, использующая это решение, будет оптимально играть против несовершенного противника.
Сильный
Предложите алгоритм, который может производить идеальные ходы из любой позиции, даже если ошибки уже были сделаны с одной или обеих сторон.

Несмотря на свое название, многие теоретики игр считают «сверхслабые» доказательства самыми глубокими, интересными и ценными. «Сверхслабые» доказательства требуют, чтобы ученый рассуждал об абстрактных свойствах игры и показал, как эти свойства приводят к определенным результатам, если реализована идеальная игра. [ необходима цитата ]

Напротив, «сильные» доказательства часто основываются на грубой силе - использовании компьютера для исчерпывающего поиска в дереве игр, чтобы выяснить, что произойдет, если будет реализована идеальная игра. Полученное доказательство дает оптимальную стратегию для каждой возможной позиции на доске. Однако эти доказательства не так полезны для понимания более глубоких причин, почему одни игры решаемы, как ничья, а другие, на первый взгляд очень похожие игры решаемы как выигрыш.

Зная правила любой игры для двух человек с конечным числом позиций, всегда можно тривиально построить минимаксный алгоритм, который будет исчерпывающим образом пройти по дереву игры . Однако, поскольку для многих нетривиальных игр такой алгоритм потребует недопустимого количества времени для создания хода в данной позиции, игра не считается решенной слабо или сильно, если алгоритм не может быть запущен существующим оборудованием в разумный срок. Многие алгоритмы полагаются на огромную заранее сгенерированную базу данных и фактически не более чем ничего.

В качестве примера сильного решения игра в крестики-нолики решается как ничья для обоих игроков с идеальной игрой (результат даже школьники могут определить вручную). Такие игры, как nim, также допускают строгий анализ с использованием комбинаторной теории игр .

Будет ли игра решена, не обязательно то же самое, что будет интересно играть людям. Даже сильно решенная игра может быть интересной, если ее решение слишком сложное для запоминания; и наоборот, слабо решенная игра может потерять свою привлекательность, если выигрышная стратегия достаточно проста для запоминания (например, Махараджа и сипаи ). Сверхслабое решение (например, Chomp или Hex на достаточно большой доске) обычно не влияет на играбельность.

Более того, даже если игра не решена, возможно, что алгоритм даст хорошее приблизительное решение: например, статья в Science за январь 2015 года утверждает, что их хедз-ап лимит техасского покерного бота Cepheus гарантирует, что человеческая жизнь игры недостаточно, чтобы со статистической значимостью установить, что его стратегия не является точным решением. [3] [4] [5]

Идеальная игра [ править ]

В теории игр , совершенная игра является поведением или стратегии игрока , который приводит к наилучшему исходу для этого игрока , независимо от ответа со стороны соперника. Идеальная игра для игры известна, когда игра решена. [1] Исходя из правил игры, каждая возможная финальная позиция может быть оценена (как выигрыш, проигрыш или ничья). По обратному рассуждению, можно рекурсивно оценить незавершенную позицию как идентичную позиции, которая находится на расстоянии одного хода и которая лучше всего оценивается игроком, чей ход идет. Таким образом, переход между позициями никогда не может привести к лучшей оценке движущегося игрока, а идеальный ход в позиции был бы переходом между позициями, которые оцениваются одинаково. Например, идеальный игрок в ничейной позиции всегда получит ничью или победу, но никогда не проиграет. Если есть несколько вариантов с одним и тем же результатом, идеальная игра иногда считается самым быстрым методом, приводящим к хорошему результату, или самым медленным методом, ведущим к плохому результату.

Идеальная игра может быть обобщена на игры с несовершенной информацией как стратегию, которая гарантирует наивысший минимальный ожидаемый результат независимо от стратегии противника. Например, идеальная стратегия для каменных ножниц - это случайный выбор каждого из вариантов с равной (1/3) вероятностью. Недостатком этого примера является то, что эта стратегия никогда не будет использовать неоптимальные стратегии оппонента, поэтому ожидаемый результат этой стратегии по сравнению с любой стратегией всегда будет равен минимальному ожидаемому результату.

Хотя оптимальная стратегия игры может (пока) не быть известна, игровой компьютер может по-прежнему извлекать выгоду из решений игры с определенных позиций эндшпиля (в виде базовых таблиц эндшпиля ), что позволит ему играть идеально после некоторого точка в игре. Компьютерные шахматные программы хорошо известны тем, что делают это.

Решенные игры [ править ]

Авари (игра семьи Манкала )
Вариант Oware, допускающий окончание игры «Большого шлема», был решительно решен Анри Балом и Джоном Ромейном в Университете Врие в Амстердаме , Нидерланды (2002). Любой из игроков может довести игру до ничьей.
Палочки для еды
Второй игрок всегда может добиться победы. [ необходима цитата ]
Подключите четыре
Решено сначала Джеймсом Д. Алленом 1 октября 1988 г. и независимо Виктором Аллисом 16 октября 1988 г. [6] Первый игрок может добиться победы. Сильно решено 8-слойной базой данных Джона Тромпа [7] (4 февраля 1995 г.). Слабо решено для всех размеров досок, где ширина + высота не превышает 15 (а также 8 × 8 в конце 2015 г.) [6] (18 февраля 2006 г.).
Английские шашки (шашки)
Этот вариант шашек 8 × 8 был слабо решен 29 апреля 2007 года командой Джонатана Шеффера . Из стандартной стартовой позиции оба игрока могут гарантировать ничью при идеальной игре. [8] Шашки - это самая крупная игра, которая была решена на сегодняшний день, с пространством поиска 5 × 10 20 . [9] Количество вычислений составило 10 14 , которые были выполнены за 18 лет. В процессе участвовало от 200 настольных компьютеров на пике до 50. [10]
Fanorona
Слабо решает Маартен Шадд. Игра вничью. [ необходима цитата ]
Бесплатный гомоку
Решено Виктором Аллисом (1993). Первый игрок может форсировать победу без вступительных правил.
Призрак
Решаемые Alan Frank , используя Официальный Scrabble игроков словарь в 1987 году [ править ]
Угадай кто?
Решительно решено Михаем Ницей в 2016 году. [11] У первого игрока есть 63% шанс на победу при оптимальной игре обеих сторон.
Hex
  • Заимствование стратегии (как используется John Nash ) показывает , что все квадратные размеры доски не могут быть потеряны первым игроком. В сочетании с доказательством невозможности ничьей это показывает, что игра является сверхслабой, решается как победа первого игрока.
  • Сильно решается несколькими компьютерами для размеров плат до 6 × 6.
  • Цзин Ян продемонстрировал выигрышную стратегию (слабое решение) для досок размером 7 × 7, 8 × 8 и 9 × 9.
  • Выигрышная стратегия Hex со свопингом известна для доски 7 × 7.
  • Сильное решение Hex на доске N × N маловероятно, так как было показано, что проблема является полной для PSPACE .
  • Если Hex разыгрывается на доске размером N × ( N +1), то игрок, который имеет меньшее расстояние для соединения, всегда может выиграть с помощью простой стратегии пар, даже с недостатком игры вторым.
  • Известно слабое решение для всех ходов на доске 8 × 8. [12]
Hexapawn
Вариант 3 × 3 решен как победа за черных, также решены несколько других более крупных вариантов. [13]
Калах
Большинство вариантов решено Джеффри Ирвингом, Йеруном Донкерсом и Джосом Уитервейком (2000), за исключением Калаха (6/6). Вариант (6/6) был решен Андерсом Карстенсеном (2011). В большинстве случаев было доказано сильное преимущество первого игрока. [14] [15] Марк Роулингс из Гейтерсбурга, штат Мэриленд, количественно оценил величину победы первого игрока в варианте (6/6) (2015 г.). После создания 39 ГБ баз данных финальной стадии, поиска в общей сложности 106 дней процессорного времени и более 55 триллионов узлов было доказано, что при идеальной игре первый игрок выигрывает с 2-мя выигрышами. Обратите внимание, что все эти результаты относятся к Захвату пустой ямы. вариант и поэтому представляют очень ограниченный интерес для стандартной игры. Анализ стандартной игры по правилам теперь опубликован для Калаха (6,4), который является выигрышем 8 для первого игрока, и для Калаха (6,5), который является выигрышем на 10 для первого игрока. Анализ Калаха (6,6) со стандартными правилами продолжается, однако было доказано, что это выигрыш как минимум 4 для первого игрока.
L игра
Легко решаемая. Любой из игроков может довести игру до ничьей.
Проигрыш в шахматы
Слабо решается победой белых, начиная с 1. e3. [16]
Махараджа и сипаи
Эта асимметричная игра - победа для сипаев при правильной игре.
Ним
Решительно решено.
Девять мужчин моррис
Решено Ральфом Гассером (1993). Любой из игроков может довести игру до ничьей. [17]
Порядок и хаос
Орден (Первый игрок) побеждает. [18]
Охвалху
Слабо решается людьми, но доказано компьютерами. (Дакон, однако, не идентичен Охвалху, игре, которую фактически наблюдал де Вугт)
Пангки
Решительно решена Джейсоном Дусеттом (2001). [19] Игра завершилась вничью. Есть только два уникальных первых хода, если вы отбрасываете зеркальные позиции. Один форсирует ничью, а другой дает сопернику форсированный выигрыш за 15.
Пентаго
Решительно решено. [20] Побеждает первый игрок.
Пентамино
Слабо решено HK Orman. [21] Это победа для первого игрока.
Поддавки ("Русские розыгрыши шашек")
Решили Осипов и Морозев в 2011 году. Победа белых. [ необходима цитата ]
Кварто
Решено Люком Гуссенсом (1998). Два идеальных игрока всегда будут рисовать.
Кубич
Слабо решена Ореном Паташником (1980) и Виктором Аллисом . Побеждает первый игрок.
Рендзю- подобная игра без вступительных правил
Янош Вагнер и Иштван Вираг заявили о своем решении. Победа первого игрока.
Сим
Слабо решаемая: победа для второго игрока.
Тико
Решил Гай Стил (1998). В зависимости от варианта либо выигрыш первого игрока, либо ничья. [22]
Трое мужчин моррис
Тривиально разрешимо. Любой из игроков может довести игру до ничьей.
Три мушкетера
Решительно решено Йоханнесом Лайре в 2009 году и слабо решено Али Элабриди в 2017 году. [23] Это победа синих фигур (людей кардинала Ришелье, или врага). [24]
Крестики-нолики
Тривиально сильно разрешимо из-за небольшого дерева игр. [25] Игра считается ничьей, если не было сделано никаких ошибок, без ошибок на первом ходу.
Тигры и козы
Слабо решено Ю Джин Лим (2007). Игра вничью. [26]
Игра Wythoff
Решительно решено.

Частично решенные игры [ править ]

Шахматы
Основная статья: Решение шахмат
Полное решение шахмат остается труднодостижимым, и предполагается, что сложность игры может помешать ее решению. Через ретроградной компьютерного анализа , эндшпильные tablebases (сильные решения) были найдены для всех трех до семи штучных эндшпилей , считая двух царей , как куски.
Решены некоторые варианты шахмат на меньшей доске с уменьшенным количеством фигур . Решены и другие популярные варианты; например, слабое решение для « Махараджа и сипаев» - это легко запоминающаяся серия ходов, гарантирующая победу игроку «сипаев».
Идти
Доска 5 × 5 была слабо решена для всех начальных ходов в 2002 году. [27] Доска 7 × 7 была слабо решена в 2015 году. [28] Люди обычно играют на доске 19 × 19, которая более чем на 145 порядков сложнее чем 7 × 7. [29]
Международные шашки
Были решены все позиции в эндшпиле с фигурами от двух до семи, а также позиции с фигурами 4 × 4 и 5 × 3, где на каждой стороне был один король или меньше, позиции с пятью людьми против четырех, позиции с пятью людьми против трех мужчин и одним король и позиции с четырьмя мужчинами и одним королем против четырех человек. Эндшпильные позиции решил в 2007 году Эд Гилберт из США. Компьютерный анализ показал, что при безупречной игре обоих игроков велика вероятность ничьей. [30] [ нужен лучший источник ]
м, н, к-игра
Легко показать, что второй игрок никогда не выиграет; см. аргумент о краже стратегии . Почти все случаи решены слабо для k ≤ 4. Некоторые результаты известны для k = 5. Игры проводятся вничью для k ≥ 8.
Реверси (Отелло)
Слабо решена на доске 4 × 4 и 6 × 6 как вторая победа игрока в июле 1993 года Джоэлем Файнштейном. [31] На доске 8 × 8 (стандартной) она математически не решена, хотя компьютерный анализ показывает вероятную ничью. Никаких строго предполагаемых оценок, кроме увеличения шансов для стартового игрока (черных) на досках 10 × 10 и более, не существует.

См. Также [ править ]

  • Компьютерные шахматы
  • Компьютер идти
  • Компьютер Отелло
  • Сложность игры
  • Алгоритм Бога
  • Теорема Цермело (теория игр)

Ссылки [ править ]

  1. ^ a b Виктор Аллис (1994). «Кандидатская диссертация: поиск решений в играх и искусственный интеллект» (PDF) . Департамент компьютерных наук . Лимбургский университет . Проверено 14 июля 2012 .
  2. ^ Х. Яап ван ден Херик , Йос У. М. Уитервейк, Джек ван Рейсвейк, Решенные игры: сейчас и в будущем , Искусственный интеллект 134 (2002) 277–311.
  3. ^ Боулинг, М .; Burch, N .; Johanson, M .; Таммелин, О. (янв 2015). "Хедз-ап лимитный холдем решен" (PDF) . Наука . 347 (6218): 145–9. CiteSeerX 10.1.1.697.72 . DOI : 10.1126 / science.1259433 . PMID 25574016 . S2CID 3796371 .    
  4. ^ Филип Болл (2015-01-08). "Теоретики игр взламывают покер" . Природа . Природа. DOI : 10.1038 / nature.2015.16683 . S2CID 155710390 . Проверено 13 января 2015 . 
  5. ^ Роберт Ли Хотц (2015-01-08). «Компьютер побеждает Техасский холдем, говорят исследователи» . Wall Street Journal .
  6. ^ a b «Игровая площадка John's Connect Four» . tromp.github.io .
  7. ^ «Репозиторий машинного обучения UCI: набор данных Connect-4» . archive.ics.uci.edu .
  8. ↑ Шеффер, Джонатан (19 июля 2007 г.). «Шашки решены» . Наука . 317 (5844): 1518–22. DOI : 10.1126 / science.1144079 . PMID 17641166 . S2CID 10274228 . Проверено 20 июля 2007 .  
  9. ^ "Проект - Чинук - Чемпион мира по шашкам человек-машина" . Проверено 19 июля 2007 .
  10. Перейти ↑ Mullins, Justin (19 июля 2007). «Шашки« решены »после многих лет перебора чисел» . Новостной сервис NewScientist.com . Проверено 6 декабря 2020 .
  11. ^ Оптимальная стратегия в «Угадай, кто?»: Помимо двоичного поиска , Михай Ника.
  12. ^ П. Хендерсон, Б. Арнесон и Р. Хейворд [webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf, Решение 8 × 8 Hex], Proc. IJCAI-09505-510 (2009) Проверено 29 июня 2010 г.
  13. ^ Цена, Роберт. «Шестигранник» . www.chessvariants.com .
  14. ^ Решение Kalah Джеффри Ирвингом, Джеруном Донкерсом и Джосом Уйервейком.
  15. ^ Решение (6,6) -Калаха Андерсом Карстенсеном.
  16. ^ Уоткинс, Марк. «Проигрыш в шахматы: 1. e3 побеждает белых» (PDF) . Проверено 17 января 2017 года .
  17. ↑ Девять мужчин Моррис - рисунок Ральфа Гассера
  18. ^ "Решено: Порядок побеждает - Порядок и Хаос" .
  19. ^ Pangki решительно решена как ничья Джейсоном Дусеттом
  20. ^ Джеффри Ирвинг: «Пентаго - победа первого игрока» http://perfect-pentago.net/details.html
  21. ^ Хилари К. Орман: пентомин: A Первого игрока Win в играх не случайно , MSRI Публикация - Том 29, 1996, стр 339-344. Онлайн: pdf .
  22. ^ Teeko , Е. Weisstein
  23. ^ Elabridi Али. «Слабое решение игры« Три мушкетера »с использованием искусственного интеллекта и теории игр» (PDF) .
  24. ↑ Три мушкетера , Ж. Лемера
  25. ↑ Крестики-нолики , Р. Манро
  26. ^ Ю Джин Лим. О прямом сокращении в поиске по дереву игр . Кандидат наук. Диссертация, Национальный университет Сингапура , 2007 г.
  27. ^ 5 × 5 Go решает Эрик ван дер Верф
  28. ^ "首期 喆 理 围棋 沙龙 举行 李 喆 7 路 盘 最优 解 具有 里程碑 意义 _ 下棋 想赢 怕输 _ ​​新浪 博客" . blog.sina.com.cn . (где говорится, что решение 7x7 решено слабо и все еще исследуется, 1. правильный коми - 9 (4,5 камня); 2. есть несколько оптимальных деревьев - первые 3 хода уникальны - но в пределах первых 7 ходов есть 5 оптимальных деревьев; 3. Есть много способов игры, которые не влияют на результат)
  29. ↑ Подсчет юридических должностей в Go. Архивировано 30 сентября 2007 г.в Wayback Machine , Tromp and Farnebäck, просмотрено 24 августа 2007 г.
  30. ^ Некоторые из девяти частей tablebase эндшпиле Эд Гилберт
  31. ^ «6 × 6 Отелло решено слабо» . Архивировано из оригинала на 2009-11-01.

Дальнейшее чтение [ править ]

  • Аллис, победив чемпиона мира? Современное состояние компьютерных игр. в новых подходах к исследованию настольных игр.

Внешние ссылки [ править ]

  • Вычислительная сложность игр и головоломок Дэвида Эпштейна.
  • Мастера, решающие игры для двух человек с точной информацией и без всяких шансов