A Решенная игра - это игра, результат которой (победа, поражение или draw ) можно правильно предсказать из любой позиции при условии, что оба игрока играют идеально. Эта концепция обычно применяется к абстрактным стратегическим играм, и особенно к играм с полной информацией и без элемента случайности; для решения такой игры может использоваться комбинаторная теория игр и / или компьютерная помощь.
Содержание
- 1 Обзор
- 2 Perfect play
- 3 Решенные игры
- 4 Частично решенные игры
- 5 См. Также
- 6 Ссылки
- 7 Дополнительная литература
- 8 Внешние ссылки
Обзор
A игра для двух игроков может быть решена на нескольких уровнях:
- Сверхслабая
- Докажите, выиграет ли первый игрок, проиграет или сыграет из исходной позиции, учитывая идеальный ход с обеих сторон. Это может быть неконструктивным доказательством (возможно, включающим аргумент кражи стратегии ), которое на самом деле не обязательно определяет какие-либо ходы идеальной игры.
- Слабое
- Предложите алгоритм, обеспечивающий победу для одного игрока или ничью для любого из них против любых возможных ходов соперника с самого начала игры. То есть создайте хотя бы одну полную идеальную игру (все ходы от начала до конца) с доказательством того, что каждый ход оптимален для игрока, который его делает. Это не обязательно означает, что компьютерная программа, использующая это решение, будет оптимально играть против несовершенного противника.
- Сильный
- Обеспечить алгоритм, который может производить идеальные ходы из любой позиции, даже если ошибки уже были сделаны с одной или обеих сторон.
Несмотря на свое название, многие теоретики игр считают, что «сверхслабые» доказательства являются самыми глубокими, интересными и ценными. «Сверхслабые» доказательства требуют, чтобы ученый рассуждал об абстрактных свойствах игры и показал, как эти свойства приводят к определенным результатам, если реализована идеальная игра.
Напротив, «сильные» доказательства часто основываются на грубая сила - использование компьютера для исчерпывающего поиска в дереве игр, чтобы выяснить, что произойдет, если будет реализована идеальная игра. Полученное доказательство дает оптимальную стратегию для каждой возможной позиции на доске. Однако эти доказательства не так полезны для понимания более глубоких причин, почему некоторые игры решаемы, как ничья, а другие, на первый взгляд очень похожие игры решаемы как выигрыш.
Учитывая правила любой игры для двух человек с конечным числом позиций, всегда можно тривиально построить алгоритм минимакс, который будет исчерпывающим образом пройти по дереву игры. Однако, поскольку для многих нетривиальных игр такой алгоритм потребует недопустимого количества времени для создания хода в данной позиции, игра не считается решенной слабо или сильно, если алгоритм не может быть запущен существующим оборудованием в разумный срок. Многие алгоритмы полагаются на огромную предварительно сгенерированную базу данных и фактически не более чем ничего.
В качестве примера сильного решения игра крестики-нолики может быть решена как ничья для обоих игроков с идеальной игрой (результат даже вручную определяется школьниками). Игры, подобные ним, также допускают строгий анализ с использованием комбинаторной теории игр.
То, решена ли игра, не обязательно совпадает с тем, остается ли она интересной для людей. Даже сильно решенная игра может быть интересной, если ее решение слишком сложное для запоминания; и наоборот, слабо решенная игра может потерять свою привлекательность, если выигрышная стратегия достаточно проста для запоминания (например, Махараджа и сипаи ). Сверхслабое решение (например, Chomp или Hex на достаточно большой доске) обычно не влияет на играбельность.
Более того, даже если игра не решена, вполне возможно, что алгоритм дает хорошее приблизительное решение: например, в статье в Science от января 2015 года утверждается, что их хедз-ап лимит техасский холдем покерный бот Cepheus гарантирует, что человеческая жизнь в игре недостаточна для того, чтобы со статистической достоверностью установить, что его стратегия не является точным решением <. 28>
Идеальная игра
В теории игр, идеальная игра - это поведение или стратегия игрока, которая приводит к наилучшему возможному результату для этого игрока независимо от ответа оппонента. Идеальная игра для игры известна, когда игра решена. Исходя из правил игры, каждая возможная финальная позиция может быть оценена (как выигрыш, проигрыш или ничья). Используя обратное рассуждение, можно рекурсивно оценить незавершенную позицию как идентичную позиции, которая находится на расстоянии одного хода и которая лучше всего ценится для игрока, чей ход идет. Таким образом, переход между позициями никогда не может привести к лучшей оценке движущегося игрока, а идеальный ход в позиции был бы переходом между позициями, которые оцениваются одинаково. Например, идеальный игрок в ничейной позиции всегда получит ничью или победу, но никогда не проиграет. Если есть несколько вариантов с одним и тем же результатом, идеальная игра иногда считается самым быстрым методом, приводящим к хорошему результату, или самым медленным методом, приводящим к плохому результату.
Идеальная игра может быть обобщена на игры с не- полной информацией как стратегия, которая гарантирует наивысший минимальный ожидаемый результат независимо от стратегии оппонента. Например, идеальная стратегия для камень ножницы-бумага - это случайный выбор каждого из вариантов с равной (1/3) вероятностью. Недостатком этого примера является то, что эта стратегия никогда не будет использовать неоптимальные стратегии оппонента, поэтому ожидаемый результат этой стратегии по сравнению с любой стратегией всегда будет равен минимальному ожидаемому результату.
Хотя оптимальная стратегия игры e может (пока) не быть известно, игровой компьютер может по-прежнему извлекать выгоду из решений игры из определенных позиций эндшпиля (в форме баз эндшпиля ), что позволит это, чтобы играть идеально после определенного момента в игре. Компьютерные шахматы хорошо известны тем, что делают это.
Решенные игры
- Awari (игра семейства Mancala )
- Вариант Oware, позволяющий закончить игру "великим". slams »была решительно решена Анри Балом и Джоном Ромейном в Vrije Universiteit в Амстердам, Нидерланды (2002). Любой из игроков может принудить игру к ничьей.
- Палочки для еды
- Второй игрок всегда может добиться победы.
- Соедините четыре
- Решено первым Джеймсом Д. Алленом 1 октября 1988 г. и независимо от Виктор Аллис 16 октября 1988 г. Первый игрок может добиться победы. Решительно решено 8-слойной базой данных Джона Тромпа (4 февраля 1995 г.). Слабо решено для всех размеров досок, где ширина + высота не более 15 (а также 8 × 8 в конце 2015 г.) (18 февраля 2006 г.).
- Английские шашки (шашки)
- Это 8 Вариант × 8 черновиков был слабо решен 29 апреля 2007 г. командой Джонатана Шеффера. Из стандартной стартовой позиции оба игрока могут гарантировать ничью при идеальной игре. Шашки - самая крупная игра, которая была решена на сегодняшний день, с пространством поиска 5 × 10. Было проведено 10 расчетов за 18 лет. В процессе участвовало от 200 настольных компьютеров на пике до 50.
- Фанорона
- Слабо решено Маартеном Шаддом. Игра представляет собой ничью.
- Бесплатно гомоку
- Решает Виктор Аллис (1993). Первый игрок может добиться победы без вступительных правил.
- Призрак
- Решено Аланом Фрэнком с использованием Официального словаря игроков в скрэббл в 1987 году.
- Угадай кто?
- Решительно решено Михаем Ника в 2016 году. У первого игрока есть 63% шанс на победу при оптимальной игре обеих сторон.
- Hex
- A аргумент кражи стратегии (используемый Джоном Нэшем ) показывает, что все размеры квадратной доски не могут быть потеряны первым игроком. В сочетании с доказательством невозможности ничьей это показывает, что игра является сверхслабой, решается как победа первого игрока.
- Решительно решается на нескольких компьютерах для размеров доски до 6 × 6.
- Цзин Ян продемонстрировал выигрышную стратегию (слабое решение) для досок размером 7 × 7, 8 × 8 и 9 × 9.
- Выигрышная стратегия для Hex с заменой известна тем, что доска 7 × 7.
- Решительное решение Hex на доске N × N маловероятно, поскольку было показано, что проблема PSPACE-complete.
- Если Hex играется на N × (N +1), то игрок, который имеет меньшее расстояние для соединения, всегда может выиграть с помощью простой стратегии пар, даже с недостатком игры вторым.
- Известно слабое решение для всех начальных ходов на 8x Доска 8.
- Hexapawn
- Вариант 3x3 решен как победа за черных, также решены несколько других более крупных вариантов.
- Kalah
- Большинство вариантов решено Джеффри Ирвингом, Джероеном Донкерсом и Джосом Уитервейком (2000) кроме Калаха (6/6). Вариант (6/6) был решен Андерсом Карстенсеном (2011). В большинстве случаев было доказано сильное преимущество первого игрока. Марк Роулингс из Гейтерсбурга, штат Мэриленд, количественно оценил величину победы первого игрока в варианте (6/6) (2015 г.). После создания 39 ГБ баз данных финальной стадии, поиска в общей сложности 106 дней процессорного времени и более 55 триллионов узлов было доказано, что при идеальной игре первый игрок выигрывает с 2-мя выигрышами. Обратите внимание, что все эти результаты относятся к Захвату пустой ямы. вариант и поэтому представляют очень ограниченный интерес для стандартной игры. Анализ стандартной игры по правилам теперь опубликован для Калаха (6,4), который является выигрышем 8 для первого игрока, и для Калаха (6,5), который является выигрышем на 10 для первого игрока. Анализ Калаха (6,6) со стандартными правилами продолжается, однако было доказано, что это выигрыш как минимум 4 для первого игрока.
- L игра
- Легко решаемая. Любой из игроков может довести игру до ничьей.
- Проигрыш в шахматы
- Слабо решается как победа для белых, начиная с 1. e3.
- Махараджа и сипаи
- Эта асимметричная игра - победа сипаев игрок с правильной игрой.
- Ним
- Решительно решен.
- Девять мужчин morris
- Решено Ральфом Гассером (1993). Любой из игроков может довести игру до ничьей.
- Порядок и Хаос
- Побеждает Порядок (Первый игрок).
- Охвалху
- Слабо решено людьми, но подтверждено компьютерами. (Дакон, однако, не идентичен Охвалху, игре, которую на самом деле наблюдал де Вугт)
- Пангки
- Решительно решено Джейсоном Дусеттом (2001). Игра вничью. Есть только два уникальных первых хода, если вы отбрасываете зеркальные позиции. Один принуждает к ничьей, а другой дает оппоненту принудительную победу за 15.
- Пентаго
- Решительно решено. Побеждает первый игрок.
- Пентамино
- Слабо решено Х. К. Орманом. Это победа для первого игрока.
- Поддавки («Русские раздаточные шашки»)
- Решено Осиповым и Морозевым в 2011 году. Победа белых.
- Quarto
- Решено Люком Гуссенсом (1998). Два идеальных игрока всегда будут играть вничью.
- Кубич
- Слабое решение: Орен Паташник (1980) и Виктор Аллис. Побеждает первый игрок.
- Рендзю игра без вступительных правил
- Янош Вагнер и Иштван Вираг (2001) объявили ее решенной. Победа первого игрока.
- Сим
- Слабое решение: победа для второго игрока.
- Тико
- Решено Гаем Стилом (1998). В зависимости от варианта либо выигрывает первый игрок, либо ничья.
- Моррис на троих
- Решаемо тривиально. Любой из игроков может довести игру до ничьей.
- Три мушкетера
- Решительно решено Йоханнесом Лайре в 2009 году и слабо решено Али Элабриди в 2017 году. Это победа синих фигур (люди кардинала Ришелье, или,
- Крестики-нолики
- Тривиально сильно разрешима из-за небольшого игрового дерева. Если не было сделано никаких ошибок, игра заканчивается вничью, и ошибка невозможна на первом ходу.
- Тигры и козы
- Слабо решена Ю Джин Лим (2007). Игра представляет собой ничью.
Частично решенные партии
- Шахматы
- Полное решение шахмат остается неуловимым, и предполагается, что сложность игры может помешать ее решению. Благодаря ретроградному компьютерному анализу, таблицы эндшпилей (сильные решения) были найдены для всех трех- и семиэлементных эндшпилей, считая двух королей в виде фигур.
- Решены некоторые варианты шахмат на меньшей доске с уменьшенным количеством фигур. Решены и другие популярные варианты; например, слабое решение для Махараджа и сипаев - это легко запоминающаяся серия ходов, которая гарантирует победу игроку «сипаев».
- Go
- Доска 5 × 5 была слабо решена для всех начальных ходов в 2002 году Доска 7 × 7 была слабо решена в 2015 году. Люди обычно играют на доске 19 × 19, которая на 145 порядков сложнее, чем 7 × 7.
- Международные шашки
- Все эндшпильные позиции с двумя по семь были решены фигуры, а также позиции с фигурами 4 × 4 и 5 × 3, где на каждой стороне был один король или меньше, позиции с пятью людьми против четырех человек, позиции с пятью людьми против трех мужчин и одним королем и позиции с четырьмя людьми и один король против четырех человек. Эндшпильные позиции решил в 2007 году Эд Гилберт из США. Компьютерный анализ показал, что очень вероятно, что оба игрока сыграют безупречно.
- m, n, k-game
- Очевидно, что второй игрок никогда не выиграет; см. аргумент кражи стратегии. Почти все случаи решены слабо для k ≤ 4. Некоторые результаты известны для k = 5. Игры нарисованы для k ≥ 8.
- Реверси (Отелло)
- Слабо решены на Доска 4 × 4 и 6 × 6 в качестве победы второго игрока в июле 1993 года Джоэлем Файнштейном. На доске 8х8 (стандартной) она математически не решена, хотя компьютерный анализ показывает вероятную ничью. Никаких строго предполагаемых оценок, кроме увеличения шансов для начинающего игрока (черный) на досках 10 × 10 и более, не существует.
См. Также
Литература
Дополнительная литература
- Аллис, победив чемпиона мира? Современное состояние компьютерных игр. в «Новые подходы к исследованиям настольных игр».
Внешние ссылки
- Вычислительная сложность игр и головоломок Дэвид Эппштейн.
- GamesCrafters решающие игры для двух человек с точной информацией и без всяких шансов
