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

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

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

Шаги

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ребята, мы вкладываем душу в сайт. Cпасибо за то,
что открываете эту красоту. Спасибо за вдохновение и мурашки.
Присоединяйтесь к нам в Facebook и ВКонтакте

Мы все играли в детстве в крестики-нолики и завидовали тем, кто умудрялся с легкостью побеждать. Кто бы мог подумать, что есть пара простых приемов, с помощью которых так легко выиграть!

сайт раскрывает секреты успешной стратегии опытных игроков.

Вариант 1

Шаг 1.

Шаг 2. Противник ставит нолик в любой угол.

Шаг 3. Ваш ход. Ставите крестик в любой свободный угол.

Шаг 4. Противник защищается.

Шаг 5. Ваш ход. Ставите крестик в другой свободный угол. Вне зависимости от хода противника вы победитель!

Вариант 2

Шаг 1. Ваш ход. Ставите крестик в любой угол.

Шаг 2. Противник ставит нолик в середину.

Шаг 3. Ваш ход. Ставите новый крестик в угол по диагонали напротив первого.

Шаг 4. Если противник ставит нолик в углу, у вас есть шанс выиграть.

Шаг 5. Вы ставите крестик так, чтобы заблокировать противника. Вне зависимости от следующего хода противника вы снова победитель!

Вариант 3

Шаг 1. Ваш ход. Ставите крестик в середину.

Шаг 2. Если противник ставит нолик наверху в середине, у вас есть шанс выиграть.

Шаг 3. Ваш ход. В правом нижнем углу ставите крестик.

Шаг 4. Противник защищается.

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

Крестики-нолики… в них играли все, я уверен. Игра притягательна своей простотой, особенно когда ты тянешь часы где-нибудь на уроке, паре, а под рукой нет ничего, кроме тетрадного листа и простого карандаша. Уж не знаю, кто первым когда-то догадался рисовать кресты и кружки в 9 квадратах, но с тех пор игра нисколько не потеряла в востребованности, тем более, что народ придумал огромное множество её вариаций.

Эта статья про процесс разработки ИИ на javascript для игры в одну из таких вариаций крестиков-ноликов: получилось довольно много материала, но я разбавил его анимацией и картинками. В любом случае, хотя бы стоит попробовать поиграть в это.
Отличия этого варианта игры от оригинала в следующем:

1. Поле может быть сколь угодно большим (На сколько хватит тетради)
2. Побеждает тот, кто поставит 5 фигур (если их можно так назвать) в ряд.

Перед тем, как начнем

Горячие клавиши и команды:

• D – ИИ сделает ход за вас
• T – посмотреть вес клетки
• Напишите в консоли SHOW_WEIGHTS = true , чтобы просматривать веса всех анализируемых клеток.

Начнем

Итак, игровое поле было готово. Можно устанавливать фигуры в клетки. Но победа кого-либо из игроков никак не фиксировалась.

Сканирование «конца игры»

Это тупой способ, но он работал. Однако, его можно было значительно улучшить, что я и сделал: Большая часть клеток будет оставаться пустой на протяжении всей игры – игровое поле слишком большое, чтоб его можно было заполнить целиком. Поскольку сканировать его нужно было каждый ход, а за один ход ставится только одна фигура - то можно сосредоточиться только на этой фигуре (клетке): просканировать только одну горизонталь, вертикаль и две диагонали клетки, которым принадлежит та самая клетка.

Плюс ко всему, не нужно сканировать все клетки линий. Поскольку конец игры – это 5 фигур в ряд, то фигуры, удаленные друг от друга на 6 клеток нас не интересуют. Достаточно сканировать по пять клеток в каждую из сторон. Не понятно? Смотри анимацию ниже.

Посмотреть код

checkWin(cellX, cellY){ var res = null; var newFig = getFig(cellX,cellY); if(! newFig) return false; var res; res = res || checkLine(cellX, cellY, 1, 0); //horizontal res = res || checkLine(cellX, cellY, 0, 1); //vertical res = res || checkLine(cellX, cellY, 1, 1); //diagonal 45 res = res || checkLine(cellX, cellY, 1, -1); //diagonal 135 return res; function getFig(x, y){ return Model.Field[x] && Model.Field[x][y] ? Model.Field[x][y] : "b"; } function checkLine(x, y, dx, dy){ x = +x; y = +y; var score = 0; while(getFig(x - dx, y - dy) == newFig){ x -= dx; y -= dy; } while(getFig(x, y) == newFig){ x += dx; y += dy; score++; } if(score >= 5) return true; return false; } }

Приступим к самому боту

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

Терминология

На соседних клетках атаки (на концах) могут быть пустые клетки или фигуры противника. Логично думать, что атаку с двумя пустыми клетками на «концах», мы можем развивать в двух направлениях, что делает ее более перспективной. Количество пустых клеток на «концах» атаки будем называть её потенциалом . Потенциал может принимать значения 0, 1 или 2.
Атаки обозначаем так: [ мощность атаки, потенциал ] . Например, атака .

Рис 1. Атака

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

Суть анализа

1. Развить свою атаку, а может быть и не одну, увеличив ее мощность. Может начать новую атаку и т.д.
2. Препятствовать развитию атаки противника или и вовсе заблокировать ее.

Суть анализа в следующем:

1. Бот подставляет в проверяемую клетку фигуры: сначала крестик, потом нолик.
2. Далее он ищет все атаки, которые были получены такими ходами и суммирует их веса.
3. Полученная сумма – это вес клетки.
4. Подобный алгоритм выполняется для всех клеток игрового поля.

По сути, таким алгоритмом мы проверяем, что будет, если мы пойдем так… а что будет если так пойдет оппонент. Мы смотрим на один ход вперед и выбираем наиболее подходящую клетку – с наибольшим весом.

Если какая-то клетка имеет больший вес, нежели другая, значит она приводит к созданию более опасных атак, либо к блокировке сильных атак противника. Все логично… мне кажется.
Если зайти на страницу и написать в консоли SHOW_WEIGHTS = true, можно визуально прочувствовать работу алгоритма (Будут показаны веса клеток).

Веса атак

ATTACK_WEIGHT = [,,,,,]; ATTACK_WEIGHT = 0.1; ATTACK_WEIGHT = 2; ATTACK_WEIGHT = 4; ATTACK_WEIGHT = 6; ATTACK_WEIGHT = 200; ATTACK_WEIGHT = 0.25; ATTACK_WEIGHT = 5; ATTACK_WEIGHT = 7; ATTACK_WEIGHT = 100; ATTACK_WEIGHT = 200; ATTACK_WEIGHT = 200;
Подобрано эмпирически – возможно это не оптимальный вариант.

Я добавил в массив атаки мощностью 5 с запредельно большим весом. Объяснить это можно тем, что бот анализирует игру, смотря на шаг вперед (подставляя фигуру в клетку). Пропуск такой атаки есть ни что иное, как поражение. Ну или победа… смотря для кого.

Атаки с большим потенциалом ценятся выше.

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

Рис 2. Атака

«Рваные» атаки

Рассмотрим такую ситуацию: при подстановке фигуры на удалении нескольких пустых клеток, но не более 5-и, расположена еще одна.

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

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

1. «Рваную» атаку представляем, как несколько обычных
2. Считаем количество пустых клеток между центральной атакой и побочной
3. За каждую пустую клетку, делитель увеличиваем на 1
4. Вес центральной атаки просчитываем как обычно, вес побочных – делим на делитель

Таким образом, «рваные» атаки так же будут учитываться ИИ. На самом деле, это будут обычные атаки, но чем они дальше находятся от сканируемой клетки, тем меньшее влияние на нее оказывают и, соответственно, имеют меньший вес (благодаря делителю).

Алгоритм поиска атак

Class Attack{ constructor(cap = 0, pot = 0, div = 1){ this.capability = cap; //Мощность this.potential = pot; //Потенциал this.divider = div; //Делитель }
И один метод , который будет возвращать вес данной атаки:

CountWeigth(){ return ATTACK_WEIGHT[ this.capability, this.potential ] / this.divider } }
Далее. Поиск всех атак для одной клетки мы разделим на:

1. Поиск на горизонтали
2. Поиск на вертикали
3. Поиск на диагонали 45 градусов
4. Поиск на диагонали 135 градусов

Однако, нам не нужно проверять всю линию целиком. Максимальная мощность атаки, которая нас интересует – 5. Безусловно, создать атаку мощностью, скажем, 6 – возможно. Но для ИИ, который анализирует игровую ситуацию следующего хода, все равно, что 6, что 5. Перспектива получить одну из этих атак говорит о конце игры на следующем ходу. Соответственно, вес анализируемой клетки будет в обоих случаях будет одинаковым.

Атрибуты класса:

Class checkLine{ constructor(){ //Фигура, которую мы подставляем на место сканируемой клетки this.subFig = "×"; //Массив всех атак на данной линии. Атака с индексом «0» - центральная. this.Attacks = ; //Текущая атака this.curAttack = new Attack; //Итератор (нужен для определения расстояния от центральной клетки) this.iter = 1; //Флаг, активирующий проверку шестых клеток this.checkEdge = false;
Здесь надо остановиться, так как может возникнуть вопрос: зачем проверять 6-ую клетку, если максимальная мощность атаки – 5. Ответ – это нужно для определения потенциала удаленной от центра атаки.

Вот пример: атака мощностью 1 на картинке находится на границе сканируемой области. Чтобы узнать потенциал этой атаки нужно «заглянуть за границу».

Рис. 3. Сканирование 6-ых клеток. Если не просканировать 6-ую клетку, можно неправильно определить потенциал атаки.

//Место для атаки this.attackplace = 1; }
Для завершения некоторых атак может просто не хватать места. Посчитав attackplace мы заранее можем понять, какие из атак бесперспективны.

Рис. 4. Место для атаки

Алгоритм следующий:

1) Начнем с центральной клетки. Она должна быть пустой (мы ведь собираемся сделать в нее ход, не так ли? Однако мы не забываем, что наш ИИ должен подставлять фигуры в данную клетку для анализа следующего хода. Фигура, которую мы подставляем – this.subfig – по умолчанию крестик. Поскольку центральная клетка изначально будет содержать в себе какую-либо фигуру после подстановки, то она будет принадлежать какой-то атаке this.curAttack :

• ее мощность будет не меньше 1 (фигура в центральной клетке)
• делитель – 1, т.к. речь идет о центральной атаке (ей принадлежит сканируемая клетка);
• потенциал пока неизвестен – по умолчанию 0;

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

cellX, cellY – координаты проверяемой клетки
subFig – фигура, которую мы подставляем в проверяемую клетку
dx, dy – изменения координат x и y в циклах – так мы задаем направление поиска:

• Горизонталь (dx = 1, dy = 0)
• Вертикаль (dx = 0, dy = 1)
• Диагональ 45 (dx = 1, dy = -1)
• Диагональ 135 (dx = 1, dy = 1)

Код функции:

GetAttacks(cellX, cellY, subFig, dx, dy){ this.substitudeFigure(subFig); //Уменьшаем итераторы – перебираем клетки... for(var x = cellX - dx, y = cellY - dy; Math.abs(x - cellX) <= 5 && Math.abs(y - cellY) <= 5; x -= dx, y -= dy) if(this.checkCell(x, y)) break; //разворачиваемся: //возвращаемся в центральную клетку (позже опишу подробнее) this.turnAround(); //Увеличиваем итераторы - двигаемся в обратном направлении... for(var x = cellX + dx, y = cellY + dy; Math.abs(x - cellX) <= 5 && Math.abs(y - cellY) <= 5; x += dx, y += dy) if(this.checkCell(x, y)) break; return this.Attacks; }
Обратите внимание, что если checkCell() что-то вернет, то выполнение цикла прекращается.

3) Проверяем фигуры данных клеток.
За это отвечает функция checkCell(x, y) :

Для начала запишем фигуру в переменную fig :
Model.Field – наше игровое поле.

CheckCell(x, y){ var fig = Model.Field[x] && Model.Field[x][y] !== undefined ? Model.Field[x][y] : "b";
fig может быть ‘x’, ‘o’, ‘b’ (граница), 0 (пустая клетка).

• Если такая фигура совпадает с фигурой центральной клетки (this.subFig ), тогда продолжаем алгоритм – значит мы продолжаем сканировать атаку, все замечательно, продолжаем в том же духе. Лишняя фигура в атаке – плюс к ее мощности(this.curAttack.capability ) и месту (this.attackplace ).

  (Смотри код в следующем пункте)

• Если это другая фигура, значит атака, что мы сканировали до этого(this.curAttack), заблокирована с этой стороны. Ничего не меняем в параметрах атаки, записываем ее в массив атак и вываливаемся из цикла.

  If(fig == "○" || fig == "×"){ if(this.subFig != fig){ //разные фигуры this.Attacks.push(this.curAttack); //записываем атаку return fig; //завершаем функцию и выходим из цикла } else{ //фигура совпадает с подставленной this.curAttack.capability++; // + к мощности this.attackplace++; // + к месту } }

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

  Else if(fig == "b"){ //граница this.Attacks.push(this.curAttack); return "b"; }

• Если поймали пустую клетку – значит текущая атака закончилась или мы имеем дело с «рваной атакой». Плюс к потенциалу и месту для атаки (ведь атака не заблокирована). Однако мы не выходим из цикла – возможно это «рваная атака» - просто запишем this.curAttack в массив всех атак линии this.Attacks. Создаем новую «текущую» атаку и увеличиваем ее делитель на 1 (это уже побочная атака).

  Else{ //Пустая клетка if(this.curAttack.capability){ this.curAttack.potential++; this.Attacks.push(this.curAttack); this.curAttack = new Attack; this.curAttack.potential++; } this.curAttack.divider++; this.attackplace++; }

4) Если на 5-ой клетке фигура совпадает с центральной клеткой, значит атака «уперлась» в границу и для определения потенциала атаки придется «проверить границу» (this.checkEdge = true ).

If(this.iter == 4 && fig == this.subFig) //Это 5-ая клетка this.checkEdge = true; else if(this.iter == 5){ if(this.checkEdge){ if(fig == this.curFig || fig == 0) this.curAttack.potential++; this.Attacks.push(this.curAttack) } return 0; } this.iter++
Функция checkCell – готова. Однако продолжаем работать над классом checkLine .

5) После выполнения первого цикла, надо «развернуться». Переводим итератор в центр и центральную атаку, с индексом 0, убираем из массива атак и устанавливаем как текущую.

TurnAround(){ this.iter = 1; this.checkEdge = false; this.curAttack = this.Attacks; this.Attacks.splice(0,1) }
6) Далее идем в другую сторону от текущей клетки, увеличивая итератор.
Абсолютно такая же проверка фигур. (Код уже написан – функция getAttacks )

7) Все, мы собрали все атаки, что были на линии в один массив.
На этом с классом checkLine всё… закончили.

Ну а дальше все просто – создаем объект checkLine для каждой из линий (2 диагонали, горизонталь и вертикаль) и вызываем функцию getAttacks . То есть, для каждой линии - свой объект checkLine и, соответственно, свой набор атак.

Пусть за все это отвечает функция getAllAttacks() – уже отдельно от описанных выше классов;

GetAllAttacks(cellX, cellY){ //не забываем, что клетка, //куда мы собираемся пойти должна быть пустой if(Model.Field[ cellX ][ cellY ]) return false var cX = ; var cO = ; //все линии крестиков... cX["0"] = this.getAttacksLine(cellX, cellY, "×", 1, 0); cX["90"] = this.getAttacksLine(cellX, cellY, "×", 0, 1); cX["45"] = this.getAttacksLine(cellX, cellY, "×", 1, -1); cX["135"] = this.getAttacksLine(cellX, cellY, "×", 1, 1); //а теперь нолики... cO["0"] = this.getAttacksLine(cellX, cellY, "○", 1, 0); cO["90"] = this.getAttacksLine(cellX, cellY, "○", 0, 1); cO["45"] = this.getAttacksLine(cellX, cellY, "○", 1, -1); cO["135"] = this.getAttacksLine(cellX, cellY, "○", 1, 1); return { //возвращаем объект со всеми атаками "x": cX, "o": cO } } getAttacksLine(cellX, cellY, subFig, dx, dy){ //тут то мы и создаем объекты var C = new checkLine; C.getAttacks(cellX, cellY, subFig, dx, dy); return this.filterAttacks(C) //про это отдельно }
На выходе имеем объект со всеми атаками для проверяемой клетки

Однако вы, возможно, заметили некую функцию-фильтр. Ее задача – отсеивать «бесперспективные» атаки:

• С нулевой мощностью (мало ли такие попадут в массив)
• Атаки, которым не хватает места (attackplace < 5)
• С нулевым потенциалом.

FilterAttacks(attackLine){ var res = if(attackLine.attackplace >= 5) attackLine.Attacks.forEach((a)=>{ if(a.capability && a.potential || a.capability >= 5) res.push(a) }) attackLine.Attacks = res; return res }

Брейкпоинты

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

Или атака . Один зевок - и игру можно легко завершать.

Рис 5. Брейкпоинт

Тут все ясно и понятно, и тот алгоритм, о котором писалось выше уже способен учитывать брейкпоинты и своевременно их блокировать. Бот смотрит на ход вперед. Он увидит, что на следующем ходу оппонент способен создать атаку , например, вес которой 200 – значит хитрый ботяра пойдет сюда.

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

Рис 6. 2 Брейкпоинта

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

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

Как понять, что атака – брейкпоинт

А далее сложнее – «рваные атаки» .
Мы будем рассматривать только атаки с одной пустой клеткой посередине – не больше. Это объясняется тем, что для завершения атаки с двумя пустыми клетками посередь, нужно потратить минимум 2 хода – это явно не брейкпоинт.

Как мы помним, рваные атаки мы рассматриваем, как несколько обычных: одна центральная атака и побочные. Центральной атаке принадлежит сканируемая клетка, у побочных делитель больше 1 – об этом писалось выше.

Алгоритм нахождения брейкпоинта (можно проще – читай ниже):

1. Введем переменную score
2. Берем центральную атаку, считаем мощность
3. Берем одну из побочных, если ее делитель не больше 2х.
4. Score – сумма мощностей центральной и побочной атак
5. Если потенциалы центральной и побочной атак равны 2, то для блокировки такой атаки нужно потратить на один ход больше. Поэтому, score увеличиваем на 1
6. Если score >= 4, то это брейкпоинт
   На самом деле брейкпоинты можно было просто перечислить, их не так много, но это я понял далеко не сразу.

Да соберем, наконец, все воедино

Во-первых, получим массив всех атак, которым клетка принадлежит. (getAllAttacks(x, y) ). Перебирая все линии, мы считаем количество брейкпоинтов. Если 2 брейкпоинта – вспоминаем, что такая ситуация может решить исход игры, и увеличиваем вес клетки на 100.
Однако все брейкпоинты должны принадлежать одному игроку, поэтому пришлось реализовать проверку в 2 шага: сначала крестики, потом нолики.

Поскольку в массиве весов атак (ATTACK_WEIGHTS ) я не предусмотрел атаки мощностью 6 и больше, мне пришлось заменить их на атаки мощностью 5. Разницы никакой – все они приводят к концу игры.

Ну и суммируем веса атак – к этому все и шло.

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

CountWeight(x, y){ var attacks = this.getAttacks(x, y) if(! attacks) return; var sum = 0; sum += count.call(this, attacks.x, "×"); sum += count.call(this, attacks.o, "○"); return sum function count(atks, curFig){ var weight = 0; var breakPoints = 0; [ "0", "45", "90", "135" ].forEach((p)=>{ if(this.isBreakPoint(atks[p])){ debug("Break point") if(++breakPoints == 2){ weight += 100; debug("Good cell") return; } } atks[p].forEach((a)=>{ if(a.capability > 5) a.capability = 5; if(a.capability == 5 && curFig == Model.whoPlays.char) weight += 100; weight += a.getWeight(); }); }) return weight } }
Теперь при вызове этой функции для конкретной клетки мы получим ее вес. Проводим эту операцию для всех клеток и выбираем наилучшую (с наибольшим весом). Туда и ходим)

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

Мое мнение о полученном результате

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

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

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

Спасибо, если ты дочитал до конца.

Теги: Добавить метки

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

Как и профессиональный шахматист, этот алгоритм просчитывает действия соперника на несколько ходов вперёд - до тех пор, пока не достигнет конца партии, будь то победа, поражение или ничья. Попав в это конечное состояние, ИИ начислит себе положительное количество очков (в нашем случае +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).

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

Игры крестики-нолики

Интернет-симуляторы – «Крестик против нолика»!

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

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

Выбор соперника

Если вы считаете, что flash игры крестики-нолики для вас слишком просты, то мы предлагаем вам усложнить задачу. Сыграйте на трех 3D-полях одновременно! Принцип тот же: нужно первым заполнить ряд клеток своими фигурами. Победить может и тот, кто поставит «Х» или «О» в одинаковых ячейках, но в разных измерениях. Следите за каждым шагом вашего виртуального противника!

Смеем заметить, что играть в крестики-нолики с компьютером порой надоедает. Несмотря на множество вариаций, чаще всего он действует по одному шаблону. Из-за предсказуемости теряется интерес. Потому подключайте к этому развлечению своего друга, выбирая опцию «Two players». Человеку свойственно ошибаться. Используйте невнимательность оппонента и выигрывайте! Но будьте готовы, что он отплатит вам той же монетой. Старайтесь играть на опережение, занимая выгодные вам зоны.

Мы предлагаем вам игры «Крестики-нолики онлайн» бесплатно и без регистрации. Вас ждут флеш симуляторы на любое количество полей и клеток. Эта забава больше не покажется вам легкой!