Решенная игра — это игра , исход которой (победа, проигрыш или ничья ) можно правильно предсказать из любой позиции, предполагая, что оба игрока играют идеально. Эта концепция обычно применяется к абстрактным стратегическим играм , и особенно к играм с полной информацией и без элемента случайности; решение такой игры может использовать комбинаторную теорию игр и/или компьютерную помощь.
Обзор
Игру для двух игроков можно решить на нескольких уровнях: [1] [2]
Сверхслабый раствор
Докажите, выиграет ли первый игрок, проиграет или сыграет вничью из начальной позиции, учитывая идеальную игру с обеих сторон ( см. § Идеальная игра ниже ). Это может быть неконструктивное доказательство (возможно, включающее аргумент о краже стратегии ), которое не должно фактически определять какие-либо детали идеальной игры.
Слабый раствор
Предложите алгоритм, который обеспечивает победу одному игроку или ничью любому из них при любой возможной игре противника с самого начала игры.
Сильное решение
Предоставьте алгоритм, который может обеспечить идеальную игру для обоих игроков из любой позиции, даже если неидеальная игра уже имела место с одной или обеих сторон.
Несмотря на свое название, многие специалисты по теории игр считают, что «ультраслабые» доказательства являются самыми глубокими, интересными и ценными. «Ультраслабые» доказательства требуют от ученого рассуждать об абстрактных свойствах игры и показывать, как эти свойства приводят к определенным результатам, если реализуется идеальная игра. [ необходима цитата ]
Напротив, «сильные» доказательства часто исходят из грубой силы — используя компьютер для исчерпывающего поиска по дереву игры , чтобы выяснить, что произойдет, если будет реализована идеальная игра. Полученное доказательство дает оптимальную стратегию для каждой возможной позиции на доске. Однако эти доказательства не так полезны для понимания более глубоких причин, по которым некоторые игры решаются как ничья, а другие, на первый взгляд очень похожие игры решаются как победа.
Учитывая правила любой игры двух человек с конечным числом позиций, всегда можно тривиально построить минимаксный алгоритм, который исчерпывающе обойдет дерево игры. Однако, поскольку для многих нетривиальных игр такой алгоритм потребовал бы невыполнимого количества времени для генерации хода в заданной позиции, игра не считается решенной слабо или сильно, если только алгоритм не может быть запущен существующим оборудованием за разумное время. Многие алгоритмы полагаются на огромную заранее сгенерированную базу данных и фактически не являются ничем иным.
В качестве простого примера сильного решения, игра в крестики-нолики легко решается как ничья для обоих игроков при идеальной игре (результат определяется вручную). Такие игры, как ним, также допускают строгий анализ с использованием комбинаторной теории игр .
То, решена ли игра, не обязательно то же самое, что и то, остается ли она интересной для людей. Даже сильно решенная игра может быть интересной, если ее решение слишком сложно запомнить; и наоборот, слабо решенная игра может потерять свою привлекательность, если выигрышная стратегия достаточно проста для запоминания (например, Махараджа и сипаи ). Сверхслабое решение (например, Chomp или Hex на достаточно большой доске) обычно не влияет на играбельность.
Идеальная игра
В теории игр идеальная игра — это поведение или стратегия игрока, которая приводит к наилучшему возможному результату для этого игрока независимо от ответа противника. Идеальная игра для игры известна, когда игра решена. [1] На основе правил игры каждая возможная конечная позиция может быть оценена (как победа, поражение или ничья). С помощью обратного рассуждения можно рекурсивно оценить нефинальную позицию как идентичную позиции, которая находится на один ход дальше и наиболее ценную для игрока, чей ход это. Таким образом, переход между позициями никогда не может привести к лучшей оценке для перемещающегося игрока, а идеальный ход в позиции будет переходом между позициями, которые оцениваются одинаково. Например, идеальный игрок в ничейной позиции всегда получит ничью или победу, но никогда не проигрыш. Если есть несколько вариантов с одинаковым результатом, идеальная игра иногда считается самым быстрым методом, ведущим к хорошему результату, или самым медленным методом, ведущим к плохому результату.
Идеальная игра может быть обобщена на игры с несовершенной информацией , как стратегия, которая гарантирует наивысший минимальный ожидаемый результат независимо от стратегии противника. Например, идеальной стратегией для игры «камень, ножницы, бумага» будет случайный выбор каждого из вариантов с равной (1/3) вероятностью. Недостатком в этом примере является то, что эта стратегия никогда не будет использовать неоптимальные стратегии противника, поэтому ожидаемый результат этой стратегии по сравнению с любой стратегией всегда будет равен минимальному ожидаемому результату.
Хотя оптимальная стратегия игры может быть (пока) не известна, играющий компьютер все равно может извлечь выгоду из решений игры из определенных позиций эндшпиля (в форме таблиц эндшпиля ), что позволит ему играть идеально после определенного момента в игре. Компьютерные шахматные программы хорошо известны тем, что делают это.
Вариант Оваре, позволяющий игру заканчивать "большими шлемами", был решительно решен Анри Балом и Джоном Ромейном в Vrije Universiteit в Амстердаме , Нидерланды (2002). Любой игрок может свести игру к ничьей.
Игра «Соедини четыре» решенаВпервые решено Джеймсом Д. Алленом 1 октября 1988 года и независимо Виктором Аллисом 16 октября 1988 года . [3] Первый игрок может форсировать победу. Сильно решено 8-слойной базой данных Джона Тромпа [4] (4 февраля 1995 года). Слабо решено для всех размеров доски, где ширина+высота не превышает 15 (а также 8×8 в конце 2015 года) [3] (18 февраля 2006 года). Решено для всех размеров доски, где ширина+высота равна 16, 22 мая 2024 года. [5]
Большинство вариантов решены Джеффри Ирвингом, Йероеном Донкерсом и Йосом Уйтервейком (2000), за исключением Калаха (6/6). Вариант (6/6) был решен Андерсом Карстенсеном (2011). Сильное преимущество первого игрока было доказано в большинстве случаев. [8] [9]
Слабо решена людьми, но доказана компьютерами. [ необходима цитата ] (Dakon, однако, не идентичен Ohvalhu, игре, которую фактически наблюдал де Вугт) [ необходима цитата ]
Решено Джейсоном Дусеттом (2001). [14] Игра заканчивается вничью. Если отбросить зеркальные позиции, то есть только два уникальных первых хода. Один заставляет сделать ничью, а другой дает противнику вынужденную победу за 15 ходов.
Сильно решена Йоханнесом Лэром в 2009 году и слабо решена Али Элабриди в 2017 году. [20] Это победа синих фигур (людей кардинала Ришелье, или противника). [21]
Тривиально решаемая задача из-за небольшого дерева игры. [22] Игра заканчивается вничью, если не допущено ни одной ошибки, при этом на первом ходу ошибка невозможна.
Этот вариант шашек 8×8 был слабо решен 29 апреля 2007 года командой Джонатана Шеффера . Из стандартной начальной позиции оба игрока могут гарантировать ничью при идеальной игре. [24] Шашки имеют пространство поиска 5×10 20 возможных игровых позиций. [25] Количество задействованных вычислений составило 10 14 , которые были выполнены в течение 18 лет. Процесс включал от 200 настольных компьютеров на пике до примерно 50. [26]
Слабо решена в 2023 году Хироки Такизавой, исследователем из Preferred Networks . [29] Из стандартной начальной позиции на доске 8×8 идеальная игра обоих игроков приведет к ничьей. Othello — самая большая игра, решенная на сегодняшний день, с пространством поиска 10 28 возможных игровых позиций.
Доска 5×5 была слабо решена для всех начальных ходов в 2002 году. [32] Доска 7×7 была слабо решена в 2015 году. [33] Люди обычно играют на доске 19×19, которая на 145 порядков сложнее, чем 7×7. [34]
Аргумент кражи стратегии ( использованный Джоном Нэшем ) показывает, что все размеры квадратной доски не могут быть проиграны первым игроком. В сочетании с доказательством невозможности ничьей это показывает, что игра является победой первого игрока (поэтому она решена ультраслабо). [ требуется ссылка ] Для определенных размеров доски известно больше: она сильно решается несколькими компьютерами для размеров доски до 6×6. [ требуется ссылка ] Слабые решения известны для размеров доски 7×7 (с использованием стратегии обмена ), 8×8 и 9×9; [ требуется ссылка ] в случае 8×8 слабое решение известно для всех начальных ходов. [35] Сильное решение Hex на доске N × N маловероятно, поскольку было показано, что задача является PSPACE-полной . [ необходима цитата ] Если Hex играется на доске N × ( N + 1), то игрок, у которого меньше расстояние для соединения, всегда может победить, используя простую стратегию пар, даже с учетом невыгодного положения, поскольку он играет вторым. [ необходима цитата ]
Все позиции эндшпиля с двумя-семью фигурами были решены, а также позиции с фигурами 4×4 и 5×3, где у каждой стороны был один король или меньше, позиции с пятью людьми против четырех людей, позиции с пятью людьми против трех людей и одного короля, и позиции с четырьмя людьми и одним королем против четырех людей. Позиции эндшпиля были решены в 2007 году Эдом Гилбертом из США. Компьютерный анализ показал, что с большой вероятностью игра закончится вничью, если оба игрока будут играть идеально. [36] [ нужен лучший источник ]
Тривиально показать, что второй игрок никогда не может победить; см. аргумент о краже стратегии . Почти все случаи были решены слабо для k ≤ 4. Некоторые результаты известны для k = 5. Игры заканчиваются вничью для k ≥ 8. [ необходима цитата ]
^ abc Эллис, Луи Виктор (23 сентября 1994 г.). Поиск решений в играх и искусственном интеллекте (кандидатская диссертация). Маастрихт: Рейксуниверситет Лимбурга. ISBN 90-9007488-0.
^ Х. Яап ван ден Херик , Йос WHM Уитервейк, Джек ван Рейсвейк, Решенные игры: сейчас и в будущем , Искусственный интеллект 134 (2002) 277–311.
^ ab "Игровая площадка Джона Соедини Четыре". tromp.github.io .
^ «Репозиторий машинного обучения UCI: набор данных Connect-4». archive.ics.uci.edu .
^ "ChristopheSteininger/c4". github.com .
^ Фрэнк, Алан (1987-08-01). "Охотники за привидениями". Word Ways . 20 (4).
^ Решение Калы Джеффри Ирвинга, Йеруна Донкерса и Йоса Уитервейка.
↑ Решение (6,6)-Калахи Андерса Карстенсена.
^ Бутон, CL (1901–1902), «Ним, игра с полной математической теорией », Annals of Mathematics , 3 (14): 35–39, doi :10.2307/1967631, JSTOR 1967631
^ Гассер, Ральф (1996). «Решение Морриса для девяти мужчин». В Nowakowski, Ричард (ред.). Игры без шансов (PDF) . Том 29. Кембридж: Cambridge University Press. С. 101–113. ISBN9780521574112. Архивировано из оригинала (PDF) 2015-07-24 . Получено 2022-01-03 .
^ Девять мужчин Моррис — это ничья Ральф Гассер
^ "решено: Порядок побеждает - Порядок и Хаос".
^ Пангки решительно решен как ничья Джейсоном Дусеттом
^ "Quarto" (PDF) . wouterkoolen.info . Получено 29 февраля 2024 г. .
^ «414298141056 Кварто рисует достаточно!».
^ "Quarto". Архивировано из оригинала 2004-10-12.
^ Вагнер, Янош и Вираг, Иштван (март 2001 г.). «Решение рэндзю» (PDF) . Сечени Эгетем – Университет Дьёра . п. 30. Архивировано (PDF) из оригинала 24 апреля 2024 года . Проверено 24 апреля 2024 г.{{cite web}}: CS1 maint: дата и год ( ссылка )
^ Teeko, Э. Вайсштейн
^ Элабриди, Али. «Слабое решение игры «Три мушкетера» с использованием искусственного интеллекта и теории игр» (PDF) .
↑ Три мушкетера, Ж. Лемэр
^ Крестики-нолики, Р. Манро
^ Витхофф, Вашингтон (1907), «Модификация игры в ним», Nieuw Archief voor Wiskunde , 7 (2): 199–202
^ Шеффер, Джонатан (19 июля 2007 г.). «Checkers Is Solved». Science . 317 (5844): 1518–22. Bibcode :2007Sci...317.1518S. doi : 10.1126/science.1144079 . PMID 17641166. S2CID 10274228.
^ "Проект - Chinook - Чемпион мира по человеко-машинным проверкам" . Получено 19 июля 2007 г.
^ Маллинз, Джастин (19 июля 2007 г.). «Шашки „решены“ после многих лет вычислений». Служба новостей NewScientist.com . Получено 06 декабря 2020 г.
^ MPD Schadd; MHM Winands; JWHM Uiterwijk; HJ van den Herik; MHJ Bergsma (2008). «Лучшая игра в Фанороне приводит к ничьей» (PDF) . New Mathematics and Natural Computation . 4 (3): 369–387. doi :10.1142/S1793005708001124. Архивировано из оригинала (PDF) 2016-03-04 . Получено 2015-04-08 .
^ Уоткинс, Марк. "Проигрыш в шахматах: 1. e3 выигрывает для белых" (PDF) . Получено 17 января 2017 г.
^ "首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客" . blog.sina.com.cn.(где говорится, что решение 7x7 решено лишь слабо и все еще находится в стадии исследования, 1. правильный коми — 9 (4,5 камня); 2. существует несколько оптимальных деревьев — первые 3 хода уникальны, — но в пределах первых 7 ходов существует 5 оптимальных деревьев; 3. существует много способов игры, которые не влияют на результат)
↑ Подсчет законных позиций в Go. Архивировано 30 сентября 2007 г. на Wayback Machine , Tromp and Farnebäck, дата обращения 24 августа 2007 г.
^ P. Henderson, B. Arneson и R. Hayward, [webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf Решение 8×8 Hex], Proc. IJCAI-09 505-510 (2009) Получено 29 июня 2010 г.
^ Некоторые из девятифракционных эндшпильных таблиц Эда Гилберта
Дальнейшее чтение
Эллис, Победить чемпиона мира? Современное искусство в компьютерных играх. в Новые подходы к исследованию настольных игр.
Внешние ссылки
Вычислительная сложность игр и головоломок Дэвида Эппштейна.
GamesCrafters решают игры для двух человек с полной информацией и без шансов
