Решенная игра — это игра , исход которой (выигрыш, поражение или ничья ) можно правильно предсказать из любой позиции, при условии, что оба игрока играют идеально.
Это понятие обычно применяется к абстрактным стратегическим играм , особенно к играм с полной информацией и без элемента случайности;
для решения такой игры можно использовать комбинаторную теорию игр и/или компьютерную помощь.
Докажите, выиграет ли первый игрок, проиграет или сыграет вничью из начальной позиции при идеальной игре обеих сторон. Это может быть неконструктивным доказательством (возможно, включающим аргумент о краже стратегии ), которое на самом деле не обязательно определяет какие-либо детали идеальной игры.
Предоставьте алгоритм, который может обеспечить идеальную игру для обоих игроков из любой позиции, даже если несовершенная игра уже произошла с одной или обеих сторон.
Несмотря на свое название, многие теоретики игр считают, что «сверхслабые» доказательства являются самыми глубокими, интересными и ценными. «Сверхслабые» доказательства требуют от ученого рассуждать об абстрактных свойствах игры и показывать, как эти свойства приводят к определенным результатам, если реализована идеальная игра. [ нужна ссылка ]
Напротив, «сильные» доказательства часто основаны на грубой силе — использовании компьютера для исчерпывающего поиска в дереве игры, чтобы выяснить, что произойдет, если будет реализована идеальная игра. Полученное доказательство дает оптимальную стратегию для каждой возможной позиции на доске. Однако эти доказательства не столь полезны для понимания более глубоких причин, по которым некоторые игры можно решить вничью, а другие, на первый взгляд очень похожие игры, можно решить вничью.
Учитывая правила любой игры двух человек с конечным числом позиций, всегда можно тривиально построить минимаксный алгоритм, который будет исчерпывающе обходить дерево игры . Однако, поскольку для многих нетривиальных игр такой алгоритм потребует невероятное количество времени для создания хода в заданной позиции, игра не считается решенной слабо или сильно, если только алгоритм не может быть запущен существующим оборудованием в разумное время. Многие алгоритмы полагаются на огромную заранее сгенерированную базу данных и по сути являются ничем иным.
В качестве простого примера сильного решения можно привести игру в крестики-нолики, которая легко решается как ничья для обоих игроков с идеальной игрой (результат определяется вручную). Такие игры, как nim, также допускают строгий анализ с использованием комбинаторной теории игр .
Решена ли игра, не обязательно означает, остается ли в нее интересно играть людям. Даже хорошо решенная игра может быть интересной, если ее решение слишком сложное, чтобы его можно было запомнить; и наоборот, слабо решенная игра может потерять свою привлекательность, если выигрышная стратегия достаточно проста для запоминания (например, «Махараджа и сипаи »). Сверхслабое решение (например, Chomp или Hex на достаточно большой доске) обычно не влияет на играбельность.
В теории игр идеальная игра — это поведение или стратегия игрока, которая приводит к наилучшему результату для этого игрока независимо от реакции противника. Идеальная игра для игры известна, когда игра решена. [1] В соответствии с правилами игры каждая возможная финальная позиция может быть оценена (как выигрыш, проигрыш или ничья). Путем обратного рассуждения можно рекурсивно оценить нефинальную позицию как идентичную позиции, которая находится на расстоянии одного хода и лучше всего ценится для игрока, чей это ход. Таким образом, переход между позициями никогда не может привести к лучшей оценке движущегося игрока, а идеальным ходом в позиции будет переход между позициями, которые оцениваются одинаково. Например, идеальный игрок в ничейной позиции всегда будет иметь ничью или победу, но никогда не проиграет. Если есть несколько вариантов с одним и тем же результатом, идеальная игра иногда считается самым быстрым методом, ведущим к хорошему результату, или самым медленным методом, ведущим к плохому результату.
Идеальную игру можно обобщить на игры с несовершенной информацией как на стратегию, гарантирующую наивысший минимальный ожидаемый результат независимо от стратегии противника. Например, идеальная стратегия игры «камень-ножницы-бумага» — это случайный выбор каждого из вариантов с равной (1/3) вероятностью. Недостаток этого примера заключается в том, что эта стратегия никогда не будет использовать неоптимальные стратегии противника, поэтому ожидаемый результат этой стратегии по сравнению с любой другой стратегией всегда будет равен минимальному ожидаемому результату.
Хотя оптимальная стратегия игры может быть (пока) неизвестна, игровой компьютер все равно может извлечь выгоду из решений игры из определенных эндшпильных позиций (в виде баз эндшпильных таблиц ), что позволит ему играть идеально через некоторое время. очко в игре. Компьютерные шахматные программы хорошо известны тем, что делают это.
Игра Connect Four решена Впервые решено Джеймсом Д. Алленом 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]
Слабо решено людьми, но доказано компьютерами. [ нужна ссылка ] (Однако Дакон не идентичен Овалху, игре, которую на самом деле наблюдал де Фогт.) [ нужна ссылка ]
Полностью решено Джейсоном Дусеттом (2001). [14] Игра ничья. Если отбросить зеркальные позиции, будет только два уникальных первых хода. Один форсирует ничью, а другой дает сопернику вынужденную победу за 15 ходов.
Сильно решено Йоханнесом Лайром в 2009 году и слабо решено Али Элабриди в 2017 году. [20] Это победа синих фигур (людей кардинала Ришелье, или врага). [21]
Этот вариант шашек 8×8 был слабо решен 29 апреля 2007 года командой Джонатана Шеффера . Из стандартной стартовой позиции оба игрока могут гарантировать ничью при идеальной игре. [24] Шашки имеют пространство поиска 5×10. 20 возможные игровые позиции. [25] Количество вычислений составило 10. 14 , которые были сделаны в течение 18 лет. В процессе задействовано от 200 настольных компьютеров на пике до примерно 50. [26]
Слабо решена в 2023 году Хироки Такизавой, исследователем Preferred Networks . [29] Из стандартной стартовой позиции на доске 8x8 идеальная игра обоих игроков приведет к ничьей. «Отелло» — самая крупная игра, решенная на сегодняшний день, с пространством поиска 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. [ нужна ссылка ]
^ Перейти обратно: а б с Эллис, Луи Виктор (23 сентября 1994 г.). Поиск решений в играх и искусственном интеллекте (кандидатская диссертация). Маастрихт: Рейксуниверситет Лимбурга. ISBN 90-9007488-0 .
^ Гассер, Ральф (1996). «Решение девяти мужских Моррисов». В Новаковски, Ричард (ред.). Игры без шансов (PDF) . Том. 29. Кембридж: Издательство Кембриджского университета. стр. 101–113. ISBN 9780521574112 . Архивировано из оригинала (PDF) 24 июля 2015 г. Проверено 3 января 2022 г.
^ Вагнер, Янош и Вираг, Иштван (март 2001 г.). «Решение рэндзю» (PDF) . Университет Сечени — Университет Дьёра . п. 30. Архивировано (PDF) из оригинала 24 апреля 2024 года . Проверено 24 апреля 2024 г. {{cite web}}: CS1 maint: дата и год ( ссылка )
^ важной вехой. Игра в шахматы, если вы хотите выиграть, но боитесь проиграть. Блог Sina» ) . ( «Был проведен первый Салон Жели Го, и оптимальным решением Ли Чжэ для игры с 7 участниками стало в котором говорится о решении 7x7 решен слабо и все еще находится в стадии исследования: 1. правильное коми - 9 (камень 4,5) 2. существует несколько оптимальных деревьев - первые 3 хода уникальны - но в пределах первых 7 ходов есть 5 оптимальных деревьев 3; . Есть много способов игры, которые не влияют на результат)
^ П. Хендерсон, Б. Арнесон и Р. Хейворд, [webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf Решение шестнадцатеричных чисел 8×8], Proc. IJCAI-09 505-510 (2009). Проверено 29 июня 2010 г.
Arc.Ask3.Ru Номер скриншота №: b5c30ff452831c2d883c62cd5694c055__1719597420 URL1:https://arc.ask3.ru/arc/aa/b5/55/b5c30ff452831c2d883c62cd5694c055.html Заголовок, (Title) документа по адресу, URL1: Solved game - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)
