Решенная игра - Solved game

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

Обзор

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

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

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

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

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

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

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

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

Идеальная игра

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

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

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

Решенные игры

Авари (игра Манкала семья)
Вариант Oware разрешение финала игры "Большого шлема" было решительно решено Анри Бал и Джон Ромейн в Vrije Universiteit в Амстердам, Нидерланды (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). Первый игрок может форсировать победу без вступительных правил.
Призрак
Решено Аланом Франком с помощью Официальный словарь игроков в скрэббл в 1987 г.[нужна цитата ]
Угадай кто?
Решительно решил Михай Ница в 2016 году.[11] Вероятность выигрыша первого игрока составляет 63% при оптимальной игре обеих сторон.
Шестигранник
  • А аргумент о краже стратегии (как используется Джон Нэш ) показывает, что все размеры квадратной доски не могут быть потеряны первым игроком. В сочетании с доказательством невозможности ничьей это показывает, что игра является сверхслабой, решается как победа первого игрока.
  • Сильно решается несколькими компьютерами для размеров плат до 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] Побеждает первый игрок.
Пентамино
Слабо решен Х. К. Орманом.[21] Это победа для первого игрока.
Поддавки ("Русские бесплатные шашки")
Решили Осипов и Морозев в 2011 году. Победа белых.[нужна цитата ]
Кварто
Решено Люком Гуссенсом (1998). Два идеальных игрока всегда будут рисовать.
Кубич
Слабо решается Орен Паташник (1980) и Виктор Аллис. Побеждает первый игрок.
Рэндзю -подобная игра без вступительных правил
Янош Вагнер и Иштван Вираг заявили о своем решении. Победа первого игрока.
Сим
Слабо решаемая: победа для второго игрока.
Тико
Решено Гай Стил (1998). В зависимости от варианта либо выигрыш первого игрока, либо ничья.[22]
Трое мужчин моррис
Тривиально разрешимо. Любой из игроков может довести игру до ничьей.
Три мушкетера
Решительно решено Йоханнесом Лайре в 2009 году и слабо решено Али Элабриди в 2017 году.[23] Это победа для синих фигур (людей кардинала Ришелье или врага).[24]
Крестики-нолики
Тривиально сильно разрешимо из-за небольшого дерева игр.[25] Игра считается ничьей, если не было допущено никаких ошибок, и невозможность ошибки на первом ходу.
Тигры и козы
Слабо решено Ю Джин Лим (2007). Игра вничью.[26]

Частично решенные игры

Шахматы
Основная статья: Решение шахмат
Полное решение шахмат остается труднодостижимым, и предполагается, что сложность игры может помешать ее решению. Через ретроградный компьютерный анализ, финальные столы (сильные решения) были найдены для всех трех - семи частей эндшпиль, считая два короли как кусочки.
Немного варианты шахмат на маленькой доске с уменьшенным количеством фигур были решены. Решены и другие популярные варианты; например слабое решение Махараджа и сипаи - легко запоминающаяся серия ходов, гарантирующая победу «сипаеву».
Идти
Доска 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. ^ а б Виктор Аллис (1994). «Кандидатская диссертация: поиск решений в играх и искусственный интеллект» (PDF). Департамент компьютерных наук. Лимбургский университет. Получено 2012-07-14.
  2. ^ Х. Яап ван ден Херик, Jos W.H.M. Уитервейк, Джек ван Рейсвейк, Решенные игры: сейчас и в будущем, Искусственный интеллект 134 (2002) 277–311.
  3. ^ Боулинг, М .; Burch, N .; Johanson, M .; Таммелин, О. (янв 2015). "Хедз-ап лимитный холдем решен" (PDF). Наука. 347 (6218): 145–9. CiteSeerX  10.1.1.697.72. Дои:10.1126 / science.1259433. PMID  25574016. S2CID  3796371.
  4. ^ Филип Болл (2015-01-08). "Теоретики игр взламывают покер". Природа. Природа. Дои:10.1038 / природа.2015.16683. S2CID  155710390. Получено 2015-01-13.
  5. ^ Роберт Ли Хотц (2015-01-08). "Компьютер завоевывает Техасский Холдем, говорят исследователи". Wall Street Journal.
  6. ^ а б "Игровая площадка John's Connect Four". tromp.github.io.
  7. ^ "Репозиторий машинного обучения UCI: набор данных Connect-4". archive.ics.uci.edu.
  8. ^ Шеффер, Джонатан (19 июля 2007 г.). «Шашки решены». Наука. 317 (5844): 1518–22. Дои:10.1126 / science.1144079. PMID  17641166. S2CID  10274228. Получено 2007-07-20.
  9. ^ «Проект - Чинук - Чемпион мира по человеко-машинным шашкам». Получено 2007-07-19.
  10. ^ Маллинз, Джастин (19 июля 2007 г.). "Шашки" решены "после многих лет перебора чисел". Служба новостей NewScientist.com. Получено 2007-07-20.
  11. ^ Оптимальная стратегия в «Угадай, кто?»: Помимо двоичного поиска пользователя Mihai Nica.
  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. ^ Пангки решается как ничья Джейсон Дусетт
  20. ^ Джеффри Ирвинг: «Пентаго - победа первого игрока» http://perfect-pentago.net/details.html
  21. ^ Хилари К. Орман: Пентамино: победа первого игрока в Игры без шансов, Публикации ИИГС - Том 29, 1996 г., стр. 339-344. Онлайн: pdf.
  22. ^ Тико, Э. Вайсштейн
  23. ^ Елабриди, Али. «Слабое решение игры« Три мушкетера »с использованием искусственного интеллекта и теории игр» (PDF).
  24. ^ Три мушкетера, Ж. Лемера
  25. ^ Крестики-нолики, Р. Манро
  26. ^ Ю Джин Лим. О прямом сокращении при поиске в дереве игр. Кандидат наук. Тезис, Национальный университет Сингапура, 2007.
  27. ^ 5 × 5 Го решено Эрик ван дер Верф
  28. ^ "首期 喆 理 围棋 沙龙 举行 李 喆 7 路 盘 最优 解 具有 里程碑 意义 _ 下棋 想赢 怕输 _ ​​新浪 博客". blog.sina.com.cn. (где говорится, что решение 7x7 решено слабо и все еще исследуется, 1. правильный коми - 9 (4,5 камня); 2. есть несколько оптимальных деревьев - первые 3 хода уникальны - но в пределах первых 7 ходов есть 5 оптимальных деревьев; 3. Есть много способов игры, которые не влияют на результат)
  29. ^ Подсчет юридических позиций в Go В архиве 2007-09-30 на Wayback Machine, Tromp and Farnebäck, по состоянию на 24 августа 2007 г.
  30. ^ Некоторые из девяти частей стола для эндшпиля Эд Гилберт
  31. ^ «6 × 6 Отелло решено слабо». Архивировано из оригинал на 2009-11-01.

дальнейшее чтение

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

внешние ссылки