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

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

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

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

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

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

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

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

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

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

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

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

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

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

Var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

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

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

/* начальное состояние доски O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // человек var huPlayer = “O”; // ИИ var aiPlayer = “X”; // возвращает список индексов пустых клеток доски function emptyIndices(board){ return board.filter(s => s != "O" && s != "X"); } // победные комбинации с учётом индексов function winning(board, player){ if((board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player)) { return true; } else { return false; } }

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

// основная минимакс-функция function minimax(newBoard, player){ //доступные клетки var availSpots = emptyIndices(newBoard);

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

// проверка на терминальное состояние (победа / поражение / ничья) //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }

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

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

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

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

// массив для хранения всех объектов var moves = ; // цикл по доступным клеткам for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard]; // совершить ход за текущего игрока newBoard] = player; //получить очки, заработанные после вызова минимакса от противника текущего игрока if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // очистить клетку newBoard] = move.index; // положить объект в массив moves.push(move); }

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

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

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

// если это ход ИИ, пройти циклом по ходам и выбрать ход с наибольшим количеством очков var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score > bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // иначе пройти циклом по ходам и выбрать ход с наименьшим количеством очков var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // вернуть выбранный ход (объект) из массива ходов return moves; }

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

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

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

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

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

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

4. Алгоритм составляет список пустых клеток и фиксирует победу игрока после проверки конечности состояния. Поэтому он возвращает объект с полем счёта, равным (-10).
   

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

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

5. В пятом вызове функции алгоритм составляет список пустых клеток и фиксирует победу ИИ после проверки конечности состояния. Поэтому он возвращает объект с полем счёта, равным +10.
   

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

6. Шестой вызов составляет список из двух пустых клеток, проверяет конечность состояния и идёт циклом по всем пустым клеткам. Затем он изменяет newBoard , помещая huPlayer в первую пустую клетку. Потом он вызывает сам себя от newBoard и aiPlayer и ждёт, пока седьмой вызов вернёт значение.
7. Новый вызов составляет список из одной пустой клетки, проверяет конечность состояния и изменяет newBoard , помещая aiPlayer в пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer и ждёт, пока этот вызов вернёт значение.
8. Восьмой вызов составляет пустой список пустых клеток и фиксирует победу aiPlayer после проверки конечности состояния. Поэтому он возвращает объект с полем счёта, равным (+10), на уровень выше, седьмому вызову.
   

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

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

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

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

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

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

Конец!

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

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

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

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

Шаги

Выигрыш или ничья, если вы ходите первым

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

Постарайтесь выиграть, если ваш соперник ставит первый О в центральную клетку. Если соперник ставит свой первый О в центре, вам придется подождать, пока он не ошибется, чтобы вы смогли выиграть. Если он продолжает играть правильно, то можно гарантированно свести результат игры к ничьей. Вот два варианта вашего следующего хода с указаниями, как ходить дальше, если соперник сделает определенный ход (а если нет, то просто продолжайте блокировать его ходы, чтобы свести результат к ничьей):

Вы выиграете автоматически, если ваш соперник поставит свой первый О в любую клетку, кроме центральной. Если ваш соперник поставит свой первый О в любую клетку рядом с центром, вы можете выиграть. В ответ поставьте свой второй Х в любом другом углу так, чтобы между двумя Х была пустая клетка.

Поставьте третий Х так, чтобы получить два возможных победных хода. Скорее всего, ваш соперник увидит, что у вас два Х в ряду и заблокирует вас. (Если нет, то выиграйте, сделав ряд из трех Х). После этого должна быть пустая клетка на одной линии с вашим первым и вторым Х, и никакой вражеский О не блокирует эту линию. Поставьте третий Х в эту клетку.

• Например, нарисуйте на листе бумаги поле для игры в крестики-нолики, у которой в верхней строке будет «X O _», в средней - «O _ _», и в нижней - «X _ _». Если вы поставите третий Х в нижнем правом углу, он будет на одной линии с другими вашими крестиками.

1. Выиграйте, поставив четвертый Х. После вашего третьего Х остаются две клетки, заняв которые вы выиграете игру. Поскольку ваш соперник может сделать только один ход, он сможет заблокировать только одну из этих клеток. Поставьте четвертый Х в незаблокированную клетку и вы выиграете!

   Как не проиграть, когда ходишь вторым

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

      • В этом разделе ваш соперник все еще ходит ноликами, но помните, что он начинает ходить первым.

   2. Добейтесь ничьи, если ваш оппонент начинает ходить с центральной клетки. Когда ваш соперник начинает игру, поставив О в центральной клетке, поставьте первый Х в углу. После этого просто блокируйте ходы соперника и получится ничья. В этой ситуации возможности выиграть нет, если только ваш соперник не перестанет рваться к победе!

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

   Разновидности крестиков-ноликов

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

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

Замечательная игра, которая не требует много подготовки, нашли ручку или карандаш, листик и напарника.

На самом деле, игра простая и, одновременно, сложная. Многие подходят к ней не серьезно, поэтому проигрывают. Скажу честно, я сам не понимал, как можно в нее играть, но затем, проанализировал все возможные ходы и понял, что здесь все упирается в математику.

Почему данная игра, очень простая? Все дело в том, что здесь всего 9 клеток, то есть у вас есть 1 из 9 начальных вариантов, а затем это количество уменьшается на 1. То есть, если вы сделали свой ход, то у вашего противника уже появляется не 9 вариантов, а всего лишь 8, потому, что 1 клетка уже занята.

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

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

Основные понятия, которые нужно знать:

Поле – условное поле 3×3 клетки, где и происходит битва.

Крестики – вот такие значки «х», они ходят первые.

Нолики – вот такие значки «0», они ходят вторые.

Победа – когда игрок собирает подряд 3 крестика или 3 нолика.

Вот пример поля.

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

Вот хотя бы так, чтобы вы понимали, где какое поле.

Стратегия выигрыша в 3×3

Запомните, что если вы играете за нолики, то есть вам нужно делать вторым ход, то против сильного противника вы сделаете лишь ничью. Ноликами сложно выиграть, так как они ходят вторыми и, практически, всегда обороняются от угроз, которые создают крестики (они первые ходят).

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

Начнемс…

Самая лучшая стратегия. Крестики делают ход на 5 клетку, которая находится в середине.

Дальше, ЗАПОМНИТЕ, что если нолики делают свой второй ход не на ДИАГОНАЛЬНУЮ КЛЕТКУ, то они проигрывают. Не важно, на какую клетку, они делают ход: 2, 4, 6, 8, если они поставили нолик на любое из этих полей, то они форсировано проигрывают.

Для примера, вы поставили на 5, они поставили на 2, теперь вы ставите на 1 или 3, угрожая сделать 3 крестика по диагонали. Ну, ок, вы поставили на 1, получается, что если вы поставите на поле 9 крестик, то вы выиграете. Вы вынуждаете поставить нолик на поле 9, но теперь вы изысканно побеждаете, ставя крестик на поле 7.

Получается, что вы угрожаете поставить три крестика по диагонали ходом 3 и по вертикали ходом – 4. Красота, не правда ли?

Лучшая защита за нолики – это, после ходя 5 за крестики, делать ходы: 1, 3, 7, 9, в таком случае, вы, при внимательности, всегда будете делать ничью. Запомните это простое правило и вы никогда не проиграете.

Хитрая стратегия за крестики

Но, ведь игрок, вовсе, не обязан делать первый ход в середину, то есть на клетку – 5. Тут, есть весьма крутая ловушка, вы делаете первый ход на угловое поле.

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

Если, к примеру, крестики делают ход на клетку – 1, то ошибкой будет делать ход – 4 и 9, в этих случаях, форсировано выигрывают крестики.

Давайте разберем эти варианты:

А) Крестики – 1, нолики – 4, крестики – 5, нолики – 9 (вынуждено), крестики – 3 с выигрышем на поля 2 или 7 в зависимости от ответа ноликов.

В) Крестики – 1, нолики – 9, крестики – 3, нолики – 2 (вынуждено), крестики – 7 с выигрышем на поля 4 или 5 в зависимости от ответа ноликов.

Ну, вот и все, друзья, надеюсь, что теперь вы знаете, как выиграть в крестики нолики 3х3. В ней (игре) нет ничего сложного, при правильной защите, здесь всегда будет ничья, но, как видите, за крестики есть интересные варианты, в которые можно словить нолики.

Я желаю вам побед, если я что-то забыл написать, то напомните мне, можно даже в комментарии.

Всем удачи, пока!

С уважением, Юрий Ваценко!

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

Когда первый ход предоставляется вам

Если первым ходить должны вы, то, не мудрствуя лукаво, помещайте свою «фигуру» – пусть это будет крестик – в самом углу. Это способно обеспечить вам победу, если соперник не догадается поставить свой нолик на центральное поле. Если его нолик будет стоять в крайнем, но не угловом поле, то следует поместить второй крестик в другом углу, отстоящем от первого в вертикальном или горизонтальном направлении (но не соприкасающемся с этим ноликом). Сопернику придётся поставить свою фигуру между вашими крестиками, а вы спокойно ставите третий крестик в третьем углу. Тогда образуется сразу два выигрышных направления. Соперник не может поставить два нолика одновременно, следовательно, вы одерживаете победу.

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

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

Если вы играете вторым

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

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

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

Разновидности крестиков-ноликов

Считается, что крестики-нолики дали начало многим другим, более сложным и интересным настольным играм. Но и сама эта игра имеет усложнённые варианты.

К примеру, «объёмные» крестики-нолики. Такая игра присутствовала на старинной игровой приставке Atari 2600. Четыре плоскости размером 4 х 4 клетки располагаются одна под другой. Выигрышная ситуация из четырёх крестиков или ноликов может создаваться не только на одной плоскости, но и на всех четырёх, причём существует множество вариантов: например, каждый крестик или нолик имеет одну и ту же координату на каждой плоскости, и это считается выигрышем.

Гомоку, или рэндзю – японская игра, которая проводится на больших полях. На соревнованиях это поле 15 на 15 или 19 на 19 клеток, но есть варианты и на «бесконечном» поле. Ходы делаются не в клетки, а на пересечения линий; вместо крестиков и ноликов обычно используются шашки чёрного и белого цветов, однако суть игры всё та же. Выигрывает тот, кто поставит пять своих шашек в ряд.