Каждый из нас хотя бы раз в жизни играл в знаменитые крестики-нолики, пытаясь построить в ряд или по диагонали 3 крестика или 3 нолика на девятиклеточном поле.
Материал о том, как побеждать, или, по крайней мере, никогда не програть в крестики-нолики, предлагает со ссылкой на 4brain.ru.
Если вы достаточно тренировались в этой игре, то, наверняка, знаете, что два опытных игрока всегда заканчивают партию вничью, и это делает игру для них неинтересной. В этой статье вы прочитаете о том, как выиграть в крестики-нолики или, по крайней мере, не проиграть, а также узнаете все хитрости и секреты прохождения этой популярной игры.
Немного о правилах. Цель игры выстроить на девятиклеточном поле подряд 3 одинаковых фигуры (3 крестика или 3 нолика) по горизонтали, по вертикали или по диагонали раньше, чем это сделает ваш партнер по игре. Игра в крестики-нолики начинается с хода игрока, который ставит крестик в любой клетке на игровом поле три на три (отметим сразу, что у него гораздо больше шансов выиграть, чем у противника). После этого второй игрок ставит в любой свободной ячейке нолик. Затем снова ходит крестик. Потом опять нолик. И так продолжается до тех пор, пока:
Первый ход крестиков.
Самой выгодной позицией является середина игрового поля, или как отмечено на схеме клетка №5. Именно сюда следует вписывать вашу фигуру, если эта ячейка является свободной, и именно поэтому начинающие крестики всегда имеют преимущество. Через центральную ячейку вы можете построить наибольшее количество возможных вариантов выигрыша: две диагонали, одну горизонталь и одну вертикаль.
Второй ход крестиков. После того как вы сделали первый ход, поставив крестик по центру, вам остается ждать ход противника. В целом, у него есть всего 2 возможных варианта действий: поставить нолик в одной из «угловых» ячеек (№1, №3, №7 и №9) или поместить свою фигуру в ячейки №2, №4, №6 или №8. И следует сразу отметить, что от этого хода уже коренным образом зависит ваша возможность выиграть.
Если игрок выбирает одну из недиагональных ячеек №2, №4, №6 или №8, то у вас появляется беспроигрышная стратегия. Другими словами вы сможете победить с вероятностью 100%, если знаете, как верно действовать. Этот алгоритм описан в схеме ниже. В первую очередь вам нужно поставить крестик своим вторым ходом в угловую клетку, вынудив соперника защищаться. А после этого вы занимаете еще одну свободную угловую клетку, в результате чего вы имеете 2 ряда, где не хватает всего одного крестика (это показано на последнем поле схемы). Куда бы соперник ни поставил свой нолик, вы в любом случае побеждаете, имея запасную стратегию.
Если же ваш соперник своим первым ходом выбирает ячейки №1, №3, №7 и №9, тогда вы не имеете абсолютной выигрышной стратегии, и вам следует уповать лишь на дальнейшую невнимательность второго игрока, что в такой простой игре бывает достаточно редко.
Третий и последующие ходы крестиков. Дальнейшие ходы «крестиков» должны быть направлены на построение в ряд 3-х собственных фигур, а также на пресечение маловероятных, но все-таки возможных попыток «ноликов» поставить подряд 3 фигуры.
Также, «крестики» для того, чтобы выиграть могут начинать не только с центральной клетки, но и с угловой. Подробнее об этом .
Если вам выпало играть ноликами, то в большинстве случаев вам предстоит бороться только за ничью. Однако у вас есть шансы победить, если вы играете с совсем неискушенным игроком.
Первый ход ноликов. Если игрок №1 почему-то не занял центральную клетку - смело ставьте туда нолик и действуйте дальше, опираясь на стратегию крестиков, описанную выше. Но, скорее всего, центральная ячейка к моменту вашего начального хода будет уже занята. В этом случае не совершайте непростительную ошибку и не ставьте нолик в ячейки №2, №4, №6 или №8, а выбирайте только диагональные ячейки №1, №3, №7 и №9.
Второй и последующие ходы. Дальнейшие ходы «ноликов» должны быть направлены на пресечение попыток «крестиков» поставить подряд 3 фигуры, а также при возможности, на построение в ряд 3-х ноликов, что является практически невозможным.
На графике, представленном ниже, который можно найти в Википедии , приведены возможные стратегии побед и ничьих в игре крестики-нолики на поле в 9 клеток.
Существует еще одна менее популярная стратегия, при которой выигрыш менее вероятен, но все-таки возможен.
Начинаем с угловой клетки
Суть этой стратеги заключается в том, что «крестик» осуществляет первый ход не в центральную ячейку, а в угловую. В этом случае, нолик имеет несколько вариантов действий.
Вариант 1. «Нолик» ходит в центр. Этот вариант наиболее вероятен как для умелого, так и для неискушенного игрока по тем причинам, которые описывались в предшествующей статье . В этом случае игроку за крестики предлагается поставить свою фигуру в противоположный от первого хода угол. Теперь происходит второй ход нолика, который будет являться решающим. Если нолик ставит фигуру в неугловую клетку, то крестик вынужден защищаться, и игра, скорее всего, закончится ничьей. А если же нолик занимает угловую ячейку, то в этом случае у «крестиков» появляется беспроигрышная стратегия: возможность сделать «вилку», заняв оставшийся угол. Это алгоритм действий выглядит следующим образом:
Вариант 2. «Нолик» ходит в бок. В этом случае «крестики» уже с первого хода имеют выигрышную стратегию: необходимо сделать ход в центр, заставив «ноликов» защищаться, а затем ход в угол, чтобы получилась «вилка». Эта тактика изображена ниже:
Вариант 3. «Нолик» ходит в смежный угол.
В этом случае ситуация похожа на первый вариант, но «крестики» уже с первого хода имеют выигрышную стратегию: второй ход «крестиков» в противоположный от своего первого хода угол, затем «нолики» защищаются ходом в центр, «крестики» занимают оставшийся угол. И вуаля: «вилка» крестиков на двух прямых. Подобная схема действий описана ниже:
Вариант 4. Нолик ходит в противоположный угол. В этом случае сложно найти выигрышную стратегию, и крестикам остается рассчитывать лишь на ничью.
В том случае, когда «крестики» начинают игру ходом в угол, «ноликам» нельзя совершить роковую ошибку, то есть поставить свою фигуру в бок или в смежный угол. В этом случае проигрыша практически не избежать. Наиболее подходящей стратегией будет ход в противоположный угол или ход в центральную клетку. Однако, в последнем варианте важно вторым ходом занять не угловую, а боковую ячейку, перейдя в атаку.
Знаете ли вы, что с помощью стратегий в игру крестики-нолики можно выигрывать с 80% вероятностью? Рассказываем об этом далее в статье!
Данная статья предназначена для лиц старше 18 лет
А вам уже исполнилось 18?
Игра в крестики-нолики хорошо знакома и взрослому, и малышу. Играя в нее, важно оставить за собой последнее решение. Если крестики или нолики игрока не выстроятся в ряд или по диагонали, то он одержит поражение. Чтобы не попасть в неприятное положение, нужно знать секрет того, как выиграть в крестики-нолики.
Самой популярной является игра на девятиклеточном поле. Поле представляет собой три квадрата по горизонтали и три по вертикали.
Как всегда, сначала рисуют поле и выбирают крестик и нолик. Первый вопрос, который хотелось бы уточнить — это vожно ли выиграть у соперника, если ты крестик? Ответ утвердительный, так как крестик в этой схватке всегда ходит первым.
По правилам соревнования нужно выставить по горизонтали или по диагонали три одинаковых хода. И сделать этj нужно быстрее, чем партнер по игре. Первым в соревновании ходит крестик. Для первого игрока появляется больше шансов на выигрыш. Второй ход будет предназначен для нолика.
Самым выгодным первым шагом является позиция в центре поля. Эта ячейка дает преимущество игроку ходить не только прямо, но и по диагонали. У игрока появляется шанс выстроить три фигуры в ряд по:
После второго шага противника на поле появится первый нолик. В зависимости от того, куда противник его поставил, выстраивается дальнейшая линия обороны.
Теоретически противник имеет два варианта:
Теперь у игрока, ходящего крестиком, появляется большая вероятность победить, а не быть побежденным. Второй шаг — это выстраивание нападения. Нужно поставить крестик в свободную угловую ячейку. Необходимо, чтобы через нее проходила диагональ. Эта позиция побудит соперника выстроить линию защиты.
Третьим ходом крестика станет захват еще одной угловой клетки. Это необходимо для того, чтобы получить как можно большее количество рядов, в которых не хватает по одной фигуре. Таким образом, вы идете на одну позицию впереди соперника. В какую бы точкe нолик не поставил свою фигуру, у крестика всегда будет в запасе еще один вариант.
Если же противник на втором шаге вашего боя поставил фигуру на одну из ячеек под номером 1, 3, 7, 9 — шансы на победу становятся невысокими, хотя и зависят от невнимательности противника.
Стратегия победы заключается в построении линии из трех одинаковых фигур по горизонтали или по вертикали. Как легко увеличить шанс на выигрыш? Нужно поставить первую фигуру в центр или в угол.
Для игроков, сражающихся за победу ноликов, выиграть намного сложнее. Ведь право первого удара в этой игре дорогого стоит. Здесь нужно попытаться выйти на ничью, а в случае невнимательности или неопытности оппонента даже появляется шанс на выигрыш.
Первый шаг нолика (в случае, если оппонент не поставил свою фигуру в центр) — поставить нолик в ячейку номер 5. Дальнейшая тактика будет похожа на ту, которая была предписана крестикам. Если же ячейка номер 5 будет занята крестиком, нужно выбрать диагональные ячейки с номерами 1, 3, 7, 9.
Следующие удары оппонентов должны идти параллельно и не допустить построения ряда из трех фигур.
Узнать, как постоянно выигрывать, можно с помощью изучения схемы.
Если крестик сделал свой первый ход не через центральную, а через угловую клеточку, то у противника появляется два варианта развития стратегии игры.
Как только нолик походит в центр, противнику нужно быстро походить в противоположный от первого хода угол. В этом случае у нолика на выбор будет два шага. Какой из них будет выбран — таким и станет исход сражения. Допустим, нолик поставит фигурку не в угловую клетку. Тогда крестик начнет защищаться, и битва закончится дружбой. Но если позиция противника будет обозначена в угловой ячейке, крестики смогут сделать своего рода «вилку» и занять оставшийся угол.
Как сделать так, чтобы крестик все время выигрывал? Нужно придерживаться следующей тактики:
Существует такая стратегия, когда нолик ставят в угол, а крестики выставляют по прямой. Тогда нолик начинают выстраивать по диагонали, но крестик и тут занимает последний свободный угол. В результате получается вилка.
Эта популярная игра очень полезна для развития логики и мышления, ведь в ее основе лежат азы программирования и математики.
В игре 3 на 3 клеточки главной причиной проигрыша одного из игроков является допущенный промах во время первого хода. Именно он определяет дальнейшую цепочку событий. Чтобы второй игрок имел фору и не проиграл, ему нужно в свой первый ход, который будет сделан после начального удара, поставить свою фигуру в центр поля или в один из углов. Это позволит ему занять стратегически важное место, и в случае необходимости с любой точки блокировать угрозу. В соревновании 3 на 3 самым важным является именно стратегия первого удара.
Интересной разновидностью боя являются трехмерные 3 на 3 на 3. Здесь соревнование ведется в кубе. Выигрыш присваивается тому игроку, который займет верхнее центральное поле. В этой борьбе не может быть ничьей. Победить можно, заняв центральное положение на поле, а также с помощью ходов, диаметрально противоположных друг другу.
Для усложнения соревнования и увеличения выигрыша, для игроков было придумано игровое поле Силвермэна размером 4 на 4 к. В этом бою целью игрока является составление прямой из четырех одинаковых фигур. Стратегия боя для первого игрока заключается в атаке и перекрывании ходов соперника. В этом варианте игры ничьей не бывает. Худшим вариантом для начала соревнования на поле 4 на 4 является противопоставление по диагонали. Но и в этом случае у первого игрока всегда есть шесть вариантов ходов. Как показывает практика и анализ боя, у игроков, сделавших первый ход в этой игре, есть огромные преимущества. Для того чтобы изменить условия и усложнить игру, главные диагонали для победы не считаются. В этом случае для выигрыша первый ход не нужно делать по главной диагонали.
На доске 4 на 4 можно играть в интересный вариант игры — «Безумные крестики-нолики». Здесь фигуры не ставят в привязку к игрокам. Выиграет тот, кто соберет первым ряд из любых четырех фигур.
Игра 5 на 5 интересная, но принцип ее действия такой же, как и в игре на поле из девяти клеточек. Главная тактика соревнования — это составление вилок, которые не дадут противнику возможности построить ряд из 5 фигур. Чтобы игра была длинной и интересной, для первого игрока устанавливают специальные правила. Нельзя строить больше двух вилок, а также запрещено создавать вилки на площадке из клеточек 3 на 3 и 4 на 4. Соблюдение этих условий открывает перед вторым игроком шансы на победу. Примечательно, что в этом варианте соревнования можно пропустить один ход. Но, если и второй игрок пропустит ход, то игра заканчивается ничьей.
Игровые поля 10×10 и 15×15 представляют собой доски, которые называются гомоку. Это увлекательная спортивная игра, которая популярна во всем мире. Основным моментом соревнования является составление ряда из пяти одинаковых фигур. Для расчета ходов существует множество алгоритмов и проведены даже компьютерные расчеты.
Нужно знать, что одна фигура оказывает влияние на другие фигуры в пределах пяти клеточек с каждой стороны от фигуры. Главная цель игроков — не допустить, чтобы противник выставил три фигуры подряд.
Действовать нужно по цепочке, строя сначала цепочку из двух фигур, потом трех, четырех и так до победы. Как и в простом уровне, второй игрок всегда идет на шаг позади первого, поэтому ему необходимо тщательно продумывать каждый свой ход.
Игра пришла к нам из древности. Сегодня известно множество вариантов соревнования: на бумаге, с камнями на компьютере. В Интернете существуют виртуальные игры, в которые играют реальные люди, делают ставки и зарабатывают реальные деньги. Но нужно помнить, что сложность боя возрастает с ростом игрового поля. При онлайн игре нет гарантии, что твой противник не машина, которая на один ход имеет несколько решений и алгоритмов. Именно поэтому онлайн игра требует от человека внимания и сосредоточенности.
Не потеряйте. Подпишитесь и получите ссылку на статью себе на почту.
В предыдущей статье, посвященной немногочисленным выигрышным стратегиям крестиков-ноликов, было рассказано, как выиграть в классической схеме игры, когда первый игрок (за крестики) начинает с хода в центр игрового поля. Однако существует еще одна менее популярная стратегия, при которой выигрыш менее вероятен, но все-таки возможен.
Суть этой стратеги заключается в том, что «крестик» осуществляет первый ход не в центральную ячейку, а в угловую. В этом случае, нолик имеет несколько вариантов действий.
Вариант 1. «Нолик» ходит в центр. Этот вариант наиболее вероятен как для умелого, так и для неискушенного игрока по тем причинам, которые описывались в . В этом случае игроку за крестики предлагается поставить свою фигуру в противоположный от первого хода угол. Теперь происходит второй ход нолика, который будет являться решающим. Если нолик ставит фигуру в неугловую клетку, то крестик вынужден защищаться, и игра, скорее всего, закончится ничьей. А если же нолик занимает угловую ячейку, то в этом случае у «крестиков» появляется беспроигрышная стратегия: возможность сделать «вилку», заняв оставшийся угол. Это алгоритм действий выглядит следующим образом:
Вариант 2. «Нолик» ходит в бок. В этом случае «крестики» уже с первого хода имеют выигрышную стратегию: необходимо сделать ход в центр, заставив «ноликов» защищаться, а затем ход в угол, чтобы получилась «вилка». Эта тактика изображена ниже:
Вариант 3. «Нолик» ходит в смежный угол.
В этом случае ситуация похожа на первый вариант, но «крестики» уже с первого хода имеют выигрышную стратегию: второй ход «крестиков» в противоположный от своего первого хода угол, затем «нолики» защищаются ходом в центр, «крестики» занимают оставшийся угол. И вуаля: «вилка» крестиков на двух прямых. Подобная схема действий описана ниже:
Вариант 4. Нолик ходит в противоположный угол. В этом случае сложно найти выигрышную стратегию, и крестикам остается рассчитывать лишь на ничью.
В том случае, когда «крестики» начинают игру ходом в угол, «ноликам» нельзя совершить роковую ошибку, то есть поставить свою фигуру в бок или в смежный угол. В этом случае проигрыша практически не избежать. Наиболее подходящей стратегией будет ход в противоположный угол или ход в центральную клетку. Однако, в последнем варианте важно вторым ходом занять не угловую, а боковую ячейку, перейдя в атаку.
Если вы не читали нашу предыдущую статью о тактиках в игре крестики-нолики, то вы можете перейти к ней . В этой статье вы сможете найти схему со всеми возможными вариантами действий.
Как написать бота, которого будет нельзя обыграть в «крестики-нолики», или Знакомство с правилом «минимакс»
Вполне возможно, что после сотен партий в «крестики-нолики» вы задумывались: каков же оптимальный алгоритм? Но если вы здесь, то вы наверняка ещё и пробовали написать реализацию этой игры. Мы пойдём дальше и напишем бота, который будет невозможно обыграть в «крестики-нолики». Предугадав ваш вопрос «почему?», ответим: благодаря алгоритму .
Как и профессиональный шахматист, этот алгоритм просчитывает действия соперника на несколько ходов вперёд - до тех пор, пока не достигнет конца партии, будь то победа, поражение или ничья. Попав в это конечное состояние, ИИ начислит себе положительное количество очков (в нашем случае +10) за победу, отрицательное (-10) - за поражение, и нейтральное (0) - за ничью.
В то же время алгоритм проводит аналогичные расчёты для ходов игрока. Он будет выбирать ход с наиболее высоким баллом, если ходит ИИ, и ход с наименьшим, если ходит игрок. Используя такую стратегию, минимакс избегает поражения.
Попробуйте сыграть вот в такую игру.
Алгоритм «минимакс» проще всего описать в виде рекурсивной функции, которая:
Если вы не знакомы с рекурсией, то вам стоит посмотреть эту лекцию из гарвардского курса 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; }
В следующем разделе мы смоделируем работу нашей программы, чтобы понять, как она работает.
Пользуясь схемой ниже, разберем пошаговую модель алгоритма.
Примечание : На схеме большие числа обозначают порядковый номер вызова функции, а уровни - то, на сколько ходов вперёд прошёл алгоритм.
Поскольку второй вызов обнаружил две пустые клетки, минимакс изменяет 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 и оптимизируйте его.
Если вас заинтересовала тема ИИ в играх, советуем почитать наши материалы по этой теме.
В школе я был чемпионом в крестики нолики, играл не зная поражаения. Эта игра была любимым способом скоротать время до перемены на скучных уроках.
Когда не было компьютерных игр и приложений для смартфонов, нам для игры достаточно было тетрадного листка в клетку и карандаша. Зимой в крестики-нолики играли на улице, начертив игровое поле веточкой на снегу.
Сейчас игры детства приобрели "мобильный" характер и доступны онлайн. Но правила игры и стратегия победы остались прежними. Освоив простой алгоритм из этой заметки, вы легко сможете выиграть крестики нолики у зои, победить 5 в ряд в мета школе и никогда не проиграете живому человеку.
Игровое поле представляет собой квадрат размером 3х3 нарисованный на листке бумаги и расчерченный на девять клеток. Две линии проводятся вдоль квадрата, две линии поперек.
Варианты, когда игровое поле имеет размеры от 4 х 4 до бесконечности, рассмотрим ниже, после разбора комбинаций игры в поле 3х3.
Базовые принципы общие, и освоив алгоритм "три в ряд", вы сможете уверенно играть в более сложные и интересные варианты этой древней игры.
Первым ход делает игрок, играющий крестиками. Второй ход за игроком, играющим ноликами. Крестики уже заняли одну клетку, и нолики для хода выбирают пустую, из оставшихся клеток.
Игроки по очереди меняются, кому играть за крестиков и ноликов.
Древние китайцы вместо рисованных символов "Х" и "0" на поле ставили камни, черные и белые. Сейчас дома в качестве поля можно использовать шахматную доску и шашками обозначать клетку, на которую сделан ход.
Побеждает игрок, который первым построил (в пределах игрового поля) линию из трех своих символов: горизонтальную, вертикальную или по диагонали.
Небольшой видео ролик, для тех, кому так проще воспринимать информацию. Кому интереснее читать, листаем дальше.
Возможны два варианта исхода игры:
Вариант "Вы проиграли", мы не рассматриваем, так как тем, кто до конца дочитал эту статью проигрыш не грозит. Все время выигрывать я вас не научу, но расскажу, как можно всегда свести игру к ничьей.
Для удобства рассказа, я каждый квадрат игрового поля обозначил цифрами, от 1 до 9.
(5) - центральная клетка.
(1), (3), (7), (9) - угловые клетки.
(2), (4), (6), (8) - боковые клетки.
Чтоб не растягивать повествование, я для каждого варианта первого хода буду рассматривать по одной комбинации. Если в моем примере нолики сходили в угловую клетку (1), а в вашем случае в угловую клетку (3), (7) или (9), то мысленно разверните поле и продолжайте ходить по изложенному мной алгоритму.
Когда крестики первым ходом занимают центральную клетку (5), ноликам остается ходить в угловую клетку или в боковую.
На этом ходу уже все решается. Сходили нолики в угловую клетку - это ничья. Если нолики сходили в любую боковую клетку - вы победили. Можно начинать новую партию, эта игра дальше не имеет смысла.
В нашем примере нолики сходили в боковую клетку (8).
Крестики ответным ходом занимают любую угловую клетку, для примера клетку (1) и получают линию из двух крестиков (см. рисунок).
Главная премудрость игры и основа всей тактики держится на двух принципах:
Принцип 1. Занимай ту клетку, которая принесет тебе немедленную победу;
Принцип 2. Если такой клетки нет, занимай клетку, которая принесет немедленную победу сопернику.
Нолики сейчас своим ходом выиграть не могут и по второму принципу занимают клетку (9), в свою очередь образуя линию из двух ноликов, см. шаг 4.
Крестики занимая клетку (7) нейтрализуют угрозу со стороны ноликов и одновременно с этим строят две линии из своих фигур. Для победы в следующем ходе крестикам нужно будет занять клетку (3) или (4). См. шаг 5.
Такое построение, когда одним ходом создается две угрозы, называется ВИЛКА.
Нолики в шестом шаге заняв клетку (3) закрывают одну угрозу со стороны крестиков.
Крестики по принципу 1, ходят в клетку (4) и одерживают победу.
Предположим, что теперь вы играете ноликами. Чтоб не проиграть эту встречу, первым ходом нужно занять угловую клетку. Без разницы какую, на ваш вкус (1), (3), (7) или (9). Для примера возьмем (1), см. рисунок ниже, шаг 2.
Крестики, опять же без разницы, куда бы ни сходили, получат линию из двух фигур. см. шаг 3.
Нолики закрывают линию крестиков, и создают свою угрозу - см. шаг 4.
Крестики по принципу 2 ходят в квадрат (4), нолики отвечают в квадрат (6). См. шаг 5 и 6.
Независимо от того, каким был предыдущий ход у крестиков, ноликам следует занимать оставшуюся свободную боковую клетку (2) или (8). Крестики занимают последнюю свободную клетку - игра закончена ничьей.
Вилку крестикам при таком начале игры построить не получится, но и ноликам не дадут. Если по невнимательности, после 6-го шага, нолики сходят в угловую клетку (9) вместо боковой (2) или (8), то крестики одержат победу построив горизонтальную линию (2)-(5)-(8).
Вы снова играете крестиками, теперь для разнообразия сходим в угол, без разницы какая угловая клетка. См. рис. ниже, шаг1.
Ход ноликов, как и в ситуации №1, от этого хода зависит исход игры. Если нолики сходили в боковую клетку, то вы построите вилку и победите.
В случае, если нолики первым ходом займут центр или угловую клетку, то будет ничья. Ноликам останется уповать на вашу невнимательность, которая подарит им победу. Но в нашем примере такой исход событий не предусмотрен.
В случае хода ноликами на боковую клетку, шаг 2, вы занимаете еще одну угловую клетку, образуя угрозу - линию из двух фигур. См. шаг 3.
Центр, клетку (5) умышленно оставим пустой для ноликов. Часто, нолики вместо того, чтоб закрыть вашу угрозу ходом в боковую клетку (2), радостно занимают центр.
Если противник попался на уловку и сходил в клетку (5), мы занимаем клетку (2) и линия построена (1)-(2)-(3)
Не будем недооценивать соперника, и он в шаге 4 закрыл нашу угрозу ходом на боковую клетку (2)
Крестикам ничего не остается, как по первому принципу занять центральную клетку (5) и построить вилку.
Теперь, см. шаг 6, куда бы нолик не ткнулся, у нас останется свободной одна из двух угловых клеток (7) или (9), ход в которую и принесет нам победу.
Ход сам по себе в плане будущей победы не оправдан. Варианты исходов - ничья, или проигрыш по невнимательности.
Комбинацию, когда вы с первого хода ставите себя в тактически невыгодное положение можете рассмотреть самостоятельно, опираясь на указанные выше два принципа игры.
Когда вам стало тесно и скучно в игровом поле 3х3, и играть три в ряд уже не спортивно, переходим на большую игровую площадь.
Рендзю - настояльная логическая игра для двух игроков, была известна еще в древнем Китае и Японии. Спортивный вариант классических крестиков-ноликов.
Игровое поле для рендзю имеет размеры от 15х15 и больше. Вот здесь уже начинается простор для стратегий и тактик. Каждая партия носит уникальный характер.
Побеждает так же игрок, первым построивший линию из пяти фигур своего цвета. Линия может быть в любом направлении - по диагонали, по вертикали, по горизонтали.
Для удобства игры в длинные линии (пять в ряд), крестики и нолики должны отличаться цветом. Иначе, глаз замылится и чужие фишки можно принять за свои, т.к. они одного цвета, хоть и разной формы. В классическом варианте фишки (камни, кружочки) которыми ходят игроки, - имеют черный и беый цвет.
По правилам, первый ход делают черные и им запрещено делать вилки 3х3, 4х4, а так же ряд из 6 и более "камней" своего цвета подряд.
Зато черные могут делать вилки размером 3х4, когда за один ход образуются две перекрещивающиеся линии - одна длиной три камня, вторая из 4 камней. Так что нет повода расслабляться у того, кто играет белыми.
Белые, за то, что ходят вторыми - имеют следующие преимущества:
Игрок, может пропустить ход, если ему в данный момент не выгодно менять расположение своих камней на игровом поле.
Если оба игрока подряд отказались от хода, объявляется ничья.
Закончились все свободные клетки - ничья.
Получается, игрок еще может пропустить ход, потому что ему некуда ходить.
Гомоку имеют более мягкие правила, для удобства игры в обычной жизни. Правила рендзю ориентированы на спортивные состязания.
У всех сервисов для игры онлайн реализованы режимы игры с компьютером, с другим пользователем и вторым игроком, который находится рядом с вами.
Так же почти у всех есть вариант игры рендзю. Ссылки даны ниже, на всех сайтах я лично играл. Обязательная регистрация не требуется.
Реомендую сервис, где ваш соперник живой человек . Есть сервисы, где компьютер очень слабый , есть где сильно играет или нестандартно выглядит игра . Но все компьютеры слабо играют в длинный вариант пять в ряд. Если в крестики нолики была ничья, то в рендзю компьютер проигрывает.
На этой ноте я с вами прощаюсь и до новых встреч на страницах моего дневника. Не забудьте подписаться на обновления - в следующий раз я расскажу как всегда выигрывать в морской бой.
С вами был Александр Утышев
