Как выиграть бота в крестики нолики

Искусственный Интеллект. Самообучение играм на победу на примере «Крестики-Нолики»

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

Допускаем, что есть две различающиеся ситуации:

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

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

Примером первой ситуации являются «Крестики-Нолики».

При поле 3X3 и двух типах фишек общее число возможных комбинаций равно 3 в 9 степени, то есть 19683 комбинаций.

При этом есть еще и невозможные комбинации. Например, на поле только 7 крестиков, или ряд крестиков и ряд ноликов и так далее. Фактически корректных комбинаций будет в разы меньше. Мы даже не будем оптимизировать с учетом симметричности, а возьмем все как есть и просто переберем.

Возможно, что, например, в шахматах ситуация другая и комбинаций уже много.Теоретически, это 33 в 64 степени, то есть 1,53 на 10 в 97 степени.

Это довольно много.

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

Пусть робот сыграет много партий случайным выбором и сам определит «лучшие» ходы как те, при которых процент победных партий наибольший.

Обучение

Алгоритм обучения (псевдокод)

повторяем заданное число раз:

фиксация:
цикл по каждой стороне по каждой комбинации из партии:
если такая комбинация есть, то +1 в количество с соответствующим статусом
если такой комбинации нет, то добавляем комбинацию и ставим 1 в количество с соответствующим статусом

Неоптимизированный код на python

Задаем количество партий, и робот играет сам с собой за обе стороны.

Уже со 100 000 партий робот находит 2739 комбинаций для крестиков и это количество не увеличивается с дальнейшим увеличением числа партий. При 1 миллионе партий и при 10 миллионах партий количество комбинаций остается тем же. Будем считать, что это и есть полное число корректных комбинаций. Теоретически, если робот выявил не все уникальные комбинации, то в процессе игры робот столкнется с неизвестной комбинацией и мы это увидим.

Выбор хода

Для выбора хода определяем возможные комбинации и по каждой возможной комбинации смотрим, в скольких процентах случаев достигается победа. Комбинация с наибольшим процентом и будет «лучшим» ходом.

Рассмотрим игру робота за «Крестики».

Первый ход для «Крестиков»:

Ожидаемо, что лучший первый ход за «Крестики» — в самый центр поля.

Дальше смотрим все возможные ходы для «Ноликов» и на каждый из них все возможные ходы для «Крестиков». Ходы для «Ноликов» смотрим все, а за «Крестики» ходим «лучшими» ходами, то есть на каждый возможны ход «Ноликов» ходим «лучшим» ходов «Крестиков».

Возможные ответные ходы за «Нолики» после первого хода «Крестиков» в центр поля:

Перебираем все возможные ходы за «Нолики» и ставим «лучший» за «Крестики».

История после ответного хода за «Крестики» получается такая:

Для последующих ходов все аналогично.

Итог сыгранных партий

В итоге получаем полный перебор сыгранных партии за «Крестики», в которых перебраны все ходы за «Нолики», и на каждый ход «Ноликов» поставлен «лучший» ход «Крестиков»:

Видно, что итог соответствует реальной игре.

Если после первого хода «Крестиков» «Нолик» ставится на боковое поле, то при корректной игре «Крестики» гарантированно выигрывают.

Если после первого хода «Крестиков» «Нолик» ставится в угол, то «Нолики» могут вытянуть самое большее на ничью, но не выиграть.

Как выиграть в крестики нолики

wikiHow работает по принципу вики, а это значит, что многие наши статьи написаны несколькими авторами. При создании этой статьи над ее редактированием и улучшением работали, в том числе анонимно, 134 человек(а).

Количество источников, использованных в этой статье: 7. Вы найдете их список внизу страницы.

Количество просмотров этой статьи: 177 660.

Крестики-нолики — решаемая игра. Это значит, что существует математически доказанная стратегия, с помощью которой можно добиться наилучшего результата в каждой игре. В крестики-нолики два игрока, которые используют правильную стратегию, всегда будут заканчивать партию вничью, то есть без победителя. Против соперника, которому неизвестна эта стратегия, все же можно выиграть, если он допустит ошибку. Как только ваши друзья уловят суть вашей стратегии, попробуйте более сложный вариант правил.

Изучите основные правила, если вы не знаете, как играть в крестики-нолики.

Лайфхаки для азартных людей: как научиться всегда выигрывать в «Крестики-нолики»

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

Поле «три-на-три», два игрока, две фигуры, правила мы все знаем еще с пеленок. Что может быть проще?! Тем не менее, дерево игровых ситуаций, то есть возможных сценариев развития событий, для игры крестики-нолики состоит из 255168 узлов. Это число получается как сумма всех возможных вариантов ходов: 9 вариантов на первом шаге, 8 — для каждого из 9 на втором шаге, 7 — на каждом из 72 вариантов на третьем шаге и так далее, за вычетом ситуаций досрочного окончания игры (выигрыша). Это, конечно, не шахматы, но тоже много. Однако, данные подсчёты позволяют сузить до разумных пределов тактики чтобы выиграть в крестики-нолики.

В XIX веке, наряду с названием «крестики-нолики», также использовались «херики-оники» или вообще «херики» — по старому названию букв русского алфавита «Х» — «хер» (простите великодушно) и «О» — «оно».

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

Прежде чем раскрыть вам все секреты игры в крестики-нолики, давайте разберемся в нашей терминологии:

• Х у нас всегда будет ходить первым, а О соответственно, вторым
• Термин «угол» у нас обозначает все четыре угловых поля
• «Сторона», соответственно, не угловое поле на каждой из четырех сторон
• «Центр» — это центр, если вдруг кто не понял
• Индексы после Х и О показывают раунд, то есть X1 — это первый сыгранный X.

Схема 3х3 в крестиках-ноликах позволяет как выиграть, так и проиграть. Но главное что игра абсолютно симметрична, её можно вращать в любом направлении, и результат будет одинаковым. Например, если вы начнете в правом нижнем углу, принципы игры там будут такими же, как и в левом верхнем углу. Ну, поехали.

Ваш ход первый. Начинаем ходить крестиком с угла

Чтобы не потеряться и всегда быть на связи, читайте нас в Яндекс.Дзене и не забывайте подписаться на нас в Telegram, ВКонтакте и Одноклассниках!

В такой ситуации все достаточно просто. Если вы задумывались о том, как постоянно выигрывать в крестики-нолики, то эта тактика явно придётся вам по душе. Гуру игры при таком раскладе считают оптимальным ходить в любой из четырех углов. Гарантированный выигрыш на рисунке ниже.

Обратите внимание, что независимо от того, где находится O3, крестик выиграет. Красота «углового метода» заключается в том, что при таком раскладе есть семь гарантированных победных схем. Фактически, единственное место, где О мог бы победить — центр, но об этом чуть ниже.

Ваш ход первый. Начинаем ходить крестиком со стороны

Когда вы начинаете атаковать с любой из четырех сторон, количество гарантированных победных схем падает до двух. Однако здесь кроется хитрость, касаемая того, как ходить в крестики-нолики чтобы выиграть на втором ходе. Касаемая в прямом смысле этого слова, — X2 обязательно должен находится рядом с O1.

Чтобы выиграть, ходы в крестики-нолики надо тщательно обдумывать. Но настоящие мастера игры знают, что думать в первую очередь нужно и за своего противника. Если он поставил О не на сторону, а в ближайший к вам угол, разумнее всего разместить Х2 в углу, противоположном от О1.

Наконец, давайте рассмотрим, что произойдет, когда O1 находится в центре. И вот здесь у первого игрока проблемы. Оказывается не всегда можно выиграть в крестики-нолики. В идеале, замрите, может в этот момент ваш противник резко отключиться, тогда вам не надо будет продолжать партию. Если такого не случилось, соберитесь. Есть пара комбинаций, которые помогут заманить противника в ловушку и выиграть в крестики-нолики как ни в чём не бывало:

Всегда выигрывать в крестики-нолики, как показывают схемы выше, вряд ли получится. Просто потому что есть ещё пара других мест, где противник может поставить O2. Скорее всего они приведут к ничьей.

Ваш ход первый. Начинаем ходить крестиком с центра

При таком старте поле 3х3 позволяет выигрывать в крестики-нолики всегда, при желании свести матч к быстрой, но скучной победе. Иногда это полезно, ведь центр всегда отличное место для начала. Тут все просто: если ваш оппонент ставит О1 на одну из сторон, то вы ставите Х2 в любой из углов и празднуете победу:

Если О1 выбирает угловое поле, то вы должны поставить Х2 в противоположный по диагонали угол и дождаться размещения O2. Конечно, при таком раскладе, можно как выиграть в крестики-нолики, так и закончить вничью. Но скорее всего партия будет выглядеть именно так:

Ваш ход второй. Крестик стоит в углу, ваша задача – поставить нолик

А вот для того чтобы выиграть в крестики-нолики второму участнику, нужно действовать хитрее. Как вы заметили, всякий раз, когда O1 находится на стороне, X гарантированно побеждает. Следовательно, никогда не ставьте О1 на стороне! Если вы поставите О1 в угол, это также ничего хорошего нам не принесет. Оптимальный ход — О1 в центре. Таким образом, вы, как минимум, гарантировано получите ничью.

Ваш ход второй. Крестик стоит на стороне

Во многом победа любого игрока – это ещё и череда ошибок его соперника. Если верить этому, то всегда любая схема как выигрывать в крестики-нолики, будет означать для начинающего вторым, прежде всего способность наказать противника за его ошибки, умело воспользоваться ими. В том случае, если Х1 стоит на стороне, наш оптимальный выбор, как уже было сказано выше, — центр поля. Оттуда вы должны попытаться заблокировать все шансы оппонента на победу и гарантировано получите ничью. Но есть и хорошие новости: на самом деле вы можете выиграть, если ходите вторым. В таком случае, как играть в крестики-нолики чтобы выиграть вы уже знаете, ведь этот пример уже у нас был:

Как написать бота, которого будет нельзя обыграть в «крестики-нолики», или Знакомство с правилом «минимакс»

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

Как и профессиональный шахматист, этот алгоритм просчитывает действия соперника на несколько ходов вперёд — до тех пор, пока не достигнет конца партии, будь то победа, поражение или ничья. Попав в это конечное состояние, ИИ начислит себе положительное количество очков (в нашем случае +10) за победу, отрицательное (-10) — за поражение, и нейтральное (0) — за ничью.

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

Попробуйте сыграть вот в такую игру.

See the Pen Минимакс by Ahmad Abdolsaheb (@abdolsa) on CodePen.

Алгоритм «минимакс» проще всего описать в виде рекурсивной функции, которая:

1. возвращает значение, если найдено конечное состояние (+10, 0, -10),
2. проходит по всем пустым клеткам на поле,
3. вызывает минимакс-функцию для каждой из них (рекурсия),
4. оценивает полученные значения
5. и возвращает наилучшее из них.

Если вы не знакомы с рекурсией, то вам стоит посмотреть эту лекцию из гарвардского курса CS50:

Чтобы разобраться в том, как устроен минимакс, давайте напишем его реализацию и смоделируем его поведение. Займёмся этим в двух следующих разделах.

Реализация минимакса

Мы рассмотрим ситуацию, когда игра подходит к концу (смотрите картинку ниже). Поскольку минимакс проходит по всем возможным состояниям игры (а их сотни тысяч), имеет смысл рассматривать эндшпиль — так нам придётся отслеживать меньшее количество рекурсивных вызовов функции (всего 9).

Пусть ИИ играет крестиками, человек — ноликами.

Чтобы упростить работу с полем, объявим его как массив из 9 элементов со значениями, равными содержимому клеток. Заполним его крестиками и ноликами, как на картинке выше, и назовём origBoard .

Затем объявим переменные aiPlayer и huPlayer и присвоим им значения «X» и «O» соответственно.

Кроме того, нам потребуется функция, которая ищет победные комбинации и возвращает истинное значение в случае успешного поиска, и функция, которая хранит индексы доступных клеток.

Итак, давайте определим минимакс-функцию с двумя аргументами: newBoard (новое поле) и player (игрок). Затем найдём индексы свободных клеток на поле и передадим их в переменную availSpots .

Кроме того, нам нужно отслеживать конечные состояния и возвращать соответствующие значения. Если побеждает «нолик», нужно вернуть -10 , если «крестик» — +10 . Если размер массива availSpots равен нулю, значит, свободных клеток нет, игра закончится ничьёй, и нужно вернуть ноль.

После этого нужно собрать очки с каждой из пустых клеток. Для этого создадим массив ходов moves и пройдём в цикле по всем пустым клеткам, помещая индексы и очки каждого хода в объект move .

Затем зададим индекс пустой клетки, который хранился в виде числа в origBoard , равным свойству-индексу объекта move . Потом сходим за текущего игрока на пустую клетку нового поля newBoard и вызовем функцию minimax от другого игрока и получившегося поля newBoard . После этого нужно поместить свойство score объекта, возвращённого функцией minimax , в свойство score объекта move .

Если минимакс не находит конечное состояние, он продолжает рекурсивное углубление в ход игры до тех пор, пока не достигнет терминального состояния. После этого он передаёт очки этого «уровня» рекурсии на один уровень выше.

И наконец, функция сбрасывает изменения newBoard и помещает объект move в массив moves .

Затем минимаксу нужно выбрать наилучший ход move из массива moves . Ему нужен move с наибольшим счётом, если ходит ИИ, и с наименьшим, если это ход человека. Таким образом, если значение player равно aiPlayer , алгоритм инициализирует переменную bestScore очень маленьким числом и идёт циклом по массиву moves : если ход move приносит больше очков score , чем bestScore , алгоритм запоминает этот move . В случае ходов с одинаковыми очками алгоритм запоминает первый из них.

В случае, когда player равен huPlayer , всё аналогично — только теперь bestScore инициализируется большим числом, а минимакс ищет ход move с наименьшим количеством очков.

В итоге минимакс возвращает объект, хранящийся в bestMove .

Вот и вся минимакс-функция. Исходный код реализации алгоритма вы можете найти на GitHub и CodePen.

В следующем разделе мы смоделируем работу нашей программы, чтобы понять, как она работает.

Минимакс в действии

Пользуясь схемой ниже, разберем пошаговую модель алгоритма.

Примечание: На схеме большие числа обозначают порядковый номер вызова функции, а уровни — то, на сколько ходов вперёд прошёл алгоритм.

1. Алгоритму подаются origBoard и aiPlayer . Он составляет список из трёх найденных пустых клеток, проверяет конечность состояния, и проходит циклом по всем пустым клеткам. Затем алгоритм меняет newBoard , помещая aiPlayer в первую пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer и ждёт, пока второй вызов вернёт значение.
2. Пока первый вызов функции всё ещё работает, запускается второй, создавая список из двух пустых клеток, проверяя конечность состояния и проходя циклом по всем пустым клеткам. Затем второй вызов изменяет newBoard , помещая huPlayer в первую пустую клетку. После этого он вызывает сам себя от newBoard и aiPlayer и ждёт, пока третий вызов вернёт значение.
3. Алгоритм составляет список пустых клеток и фиксирует победу игрока после проверки конечности состояния. Поэтому он возвращает объект с полем счёта, равным (-10).

Поскольку второй вызов обнаружил две пустые клетки, минимакс изменяет newBoard , помещая huPlayer во вторую свободную клетку. Затем он вызывает сам себя от newBoard и aiPlayer .

Во втором вызове функции алгоритм получает значения, возвращённые с нижнего уровня третьим и четвёртым вызовами функции. Поскольку ход huPlayer принёс эти два результата, алгоритм выбирает наименьший из них. Так как они одинаковы, алгоритм выбирает первый и передаёт его первому вызову функции.

На этот момент первый вызов функции получил оценку хода aiPlayer в первую пустую клетку. Затем он изменяет newBoard , помещая aiPlayer во вторую пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer .

После этого первый вызов изменяет newBoard , помещая aiPlayer в третью пустую клетку. Затем он вызывает сам себя от newBoard и huPlayer .

Седьмой вызов получил лишь одно, положительное значение от нижних уровней. Поскольку это значение было получено в ход aiPlayer , алгоритм возвращает наибольшее из полученных значений. Поэтому он возвращает положительное значение (+10) на уровень выше, шестому вызову.

Поскольку шестой вызов обнаружил две пустых клетки, минимакс изменяет newBoard , помещая huPlayer во вторую пустую клетку. Затем он вызывает сам себя от newBoard и aiPlayer .

На этом этапе шестой вызов должен выбрать между счётом (+10), который вернул седьмой вызов, и счётом (-10), который вернул девятый вызов. Поскольку ход huPlayer принёс эти два результата, алгоритм выбирает наименьший из них и возвращает его на уровень выше в виде объекта с полями счёта и индекса.

Наконец, все три ветви первого вызова оцениваются (-10, +10, -10). Поскольку ход aiPlayer принёс эти три результата, алгоритм выбирает объект, содержащий наибольшее количество очков (+10) и его индекс (4).

В рассмотренном выше сценарии минимакс решает, что оптимальным выбором будет ход в центральную клетку поля.

Выводы

К этому моменту вы должны были понять, как устроен алгоритм минимакс. Попробуйте написать его реализацию самостоятельно или посмотрите пример на GitHub или CodePen и оптимизируйте его.

Если вас заинтересовала тема ИИ в играх, советуем почитать наши материалы по этой теме: