Игра решена, когда известен результат при безошибочной игре обеих сторон. Это утверждение об игре, а не о программе: после того как решили шашки, никакая будущая программа уже не выиграет у другой безошибочной программы. Каждый пункт списка ниже закрыт вычислением, а большинство — вычислением длиной в годы.
Решённость не делает игру скучной для людей — она делает её скучной для машин. Безошибочному сопернику вы проиграете, но вы проиграли бы и так; разница в том, что теперь это теорема.
| Игра | Решение | Кто и когда | Безошибочная игра кончается |
|---|---|---|---|
| Крестики-нолики 3×3 | сильное | известно давно; перебор тривиален | ничья |
| Ним есть на сайте | сильное | Чарльз Бутон, 1901 | выигрывает тот, кто ходит из позиции с ненулевым XOR |
| Четыре в ряд 7×6 есть на сайте | сильное | Виктор Аллис и Джеймс Аллен, независимо, 1988 | выигрывает первый |
| Мельница есть на сайте | сильное | Ральф Гассер, 1993 | ничья |
| Гомоку 15×15 есть на сайте | слабое | Виктор Аллис, 1993 | выигрывает первый (без ограничивающих правил) |
| Калах 6×4 (манкала) есть на сайте | слабое | Джеффри Ирвинг, Йерун Донкерс и Йос Ойтервейк, 2000 | выигрывает первый |
| Авари (манкала) | сильное | Джон Ромейн и Хенри Бал, 2002 | ничья |
| Покер Куна есть на сайте | сильное | Гарольд Кун, 1950 — решён на бумаге, без компьютера | второй игрок выигрывает 1/18 анте за раздачу; оптимальная стратегия случайна |
| Свинья (кости) есть на сайте | сильное | Тодд Неллер и Клифтон Прессер, 2004 — итерация ценности | известна стратегия, максимизирующая шанс победы; исход партии решают кости |
| Английские шашки 8×8 есть на сайте | слабое | команда Chinook, Джонатан Шеффер, 2007 — восемнадцать лет счёта | ничья |
| Отелло 8×8 есть на сайте | слабое | Хироки Такидзава, 2023 | ничья |
| Chomp (шоколадка) 8×5 есть на сайте | ультраслабое | Дэвид Гейл, 1974 — кража стратегии; малые доски просчитаны перебором | выигрывает первый, но общего рецепта ходов теория не даёт |
| Сим (игра Рамсея) есть на сайте | сильное | предложена Густавусом Симмонсом, 1969; решена полным перебором | выигрывает второй — а ничья невозможна по теореме Рамсея |
| Хекс есть на сайте | ультраслабое | Джон Нэш, 1949 — доказательство кражей стратегии; доски до 9×9 просчитаны | выигрывает первый, но как именно — на больших досках неизвестно |
| Точки и квадраты есть на сайте | частично | Джозеф Баркер и Ричард Корф, 2012 — доски до 4×5 | зависит от доски; общий случай открыт |
| Го | частично | 5×5 — Эрик ван дер Верф, 2002; 19×19 не решено и вряд ли будет | на 5×5 выигрывает первый; на 19×19 неизвестно |
| Шахматы | частично | полностью посчитаны только эндшпили до семи фигур (2012) | неизвестен; ничья считается наиболее вероятной |
| Лимитный холдем один на один | слабое | Cepheus, группа Майкла Боулинга, 2015 | решён практически: отклонение неотличимо за человеческую жизнь |
| Нарды есть на сайте | открыта | не решены: мешают кости | решения в привычном смысле не существует |
| Русские шашки есть на сайте | открыта | не решены | неизвестен — бой обязателен и дамка летает, дерево шире английского |
| Ataxx 7×7 есть на сайте | открыта | не решён | неизвестен |
| Сапёр есть на сайте | открыта | не игра двух лиц; Ричард Кэй, 2000 — задача о безопасном ходе NP-полна | быстрого способа всегда играть безопасно, скорее всего, нет |
Столбцы — это степени десятки: сколько у игры позиций. Каждый шаг вправо в десять раз больше предыдущего, так что расстояние между шашками и шахматами — не тот разрыв, который закрывается более быстрой машиной.
Девять из наших закрыты. Мельница при безошибочной игре — ничья, гомоку на свободных правилах — победа первого, отелло признали ничьёй в 2023 году. «Четыре в ряд» и калах 6×4 — победа того, кто ходит первым. Покер Куна решён на бумаге ещё в 1950-м, «Свинья» — в 2004-м, но решены они по стратегии: отдельную раздачу всё равно решают карты, отдельную партию — кости. Английские шашки тоже ничья — но здесь у нас русские, а они не решены. В Chomp выигрывает первый, в Симе — второй, и обе эти стороны отданы вам. Хекс стоит особняком: наша доска — доказанная победа первого, а какими ходами — не знает никто.
Ничто из этого не делает наших соперников безошибочными. Движки сайта считают на несколько полуходов и остальное угадывают оценочной функцией. Решённая игра означает, что безошибочный игрок существует, а не то, что он сидит по ту сторону экрана.