Крестики-нолики… в них играли все, я уверен. Игра притягательна своей простотой, особенно когда ты тянешь часы где-нибудь на уроке, паре, а под рукой нет ничего, кроме тетрадного листа и простого карандаша. Уж не знаю, кто первым когда-то догадался рисовать кресты и кружки в 9 квадратах, но с тех пор игра нисколько не потеряла в востребованности, тем более, что народ придумал огромное множество её вариаций.
Эта статья про процесс разработки ИИ на javascript для игры в одну из таких вариаций крестиков-ноликов: получилось довольно много материала, но я разбавил его анимацией и картинками. В любом случае, хотя бы стоит попробовать поиграть в это.
Отличия этого варианта игры от оригинала в следующем:
Все просто… и в то же время сложно: исход игры не может быть просчитан заранее, как в классическом аналоге. Этот «маленький проектик» отнял у меня много времени и нервов. Надеюсь, что вам будет интересно.
Вынужден извиниться заранее за объем статьи и местами не совсем доходчивое изложение мысли, однако у меня не получилось сжать стаю без потери в содержании и качестве.
Рекомендую сначала ознакомиться с результатом. Код
Горячие клавиши и команды:
Начать нужно с реализации самой игры, т.е. написать приложение для двух игроков, пока без бота. Для своих целей я решил использовать javascript + jquery + bootstrap4, хотя он там практически не используется, но его лучше оставить – или таблица поплывет. Тут рассказывать особо нечего, материала по js, jquery и bootstrap на хабре полно. Скажу лишь, что использовал MVC. Да и вообще, объяснять абсолютно весь код я не буду – материала и без того получилось много.
Итак, игровое поле было готово. Можно устанавливать фигуры в клетки. Но победа кого-либо из игроков никак не фиксировалась.
Игра заканчивается, когда один из игроков поставит 5 фигур в ряд. «Все просто!» — подумал я. И начал сканировать абсолютно все клетки поля: сначала все горизонтали, потом вертикали и, наконец, диагонали.
Это тупой способ, но он работал. Однако, его можно было значительно улучшить, что я и сделал: Большая часть клеток будет оставаться пустой на протяжении всей игры – игровое поле слишком большое, чтоб его можно было заполнить целиком. Поскольку сканировать его нужно было каждый ход, а за один ход ставится только одна фигура — то можно сосредоточиться только на этой фигуре (клетке): просканировать только одну горизонталь, вертикаль и две диагонали клетки, которым принадлежит та самая клетка.
Плюс ко всему, не нужно сканировать все клетки линий. Поскольку конец игры – это 5 фигур в ряд, то фигуры, удаленные друг от друга на 6 клеток нас не интересуют. Достаточно сканировать по пять клеток в каждую из сторон. Не понятно? Смотри анимацию ниже.
Итак, мы уже написали страницу с крестиками-ноликами. Переходим к основной задаче – ИИ.
Нельзя просто так взять и написать код, если ты не знаешь как: нужно продумать логику бота.
Суть заключается в анализе игрового поля, хотя бы его части, и просчета цены (веса) каждой клетки на поле. Клетка с наибольшим весом – самая перспективная – туда бот и поставит фигуру. Основная сложность именно в просчете веса одной клетки.
Крестики и нолики – это фигуры.
Атакой будем называть несколько одинаковых фигур, стоящих рядом, на одной линии. По сути, это множество. Количество фигур в атаке – её мощность. Одна отдельная фигура – тоже атака (мощностью 1).
На соседних клетках атаки (на концах) могут быть пустые клетки или фигуры противника. Логично думать, что атаку с двумя пустыми клетками на «концах», мы можем развивать в двух направлениях, что делает ее более перспективной. Количество пустых клеток на «концах» атаки будем называть её потенциалом. Потенциал может принимать значения 0, 1 или 2.
Атаки обозначаем так: [ мощность атаки, потенциал ]. Например, атака [4:1].
Рис 1. Атака [4:1]
В ходе анализа мы будем оценивать все клетки, которые входят в определенную область. У каждой клетки будет просчитываться её вес. Он вычисляется на основе весов всех атак, на которые влияет данная клетка.
Представим, что на игровом поле уже есть несколько атак одного и второго игрока. Кто-то из игроков делает ход (пускай крестики). Естественно ход он делает в пустую клетку – и тем самым он может:
То есть, наш протагонист может атаковать и защищаться. А может и все сразу одним ходом. Для него важно, как первое, так и второе.
Суть анализа в следующем:
По сути, таким алгоритмом мы проверяем, что будет, если мы пойдем так… а что будет если так пойдет оппонент. Мы смотрим на один ход вперед и выбираем наиболее подходящую клетку – с наибольшим весом.
Если какая-то клетка имеет больший вес, нежели другая, значит она приводит к созданию более опасных атак, либо к блокировке сильных атак противника. Все логично… мне кажется.
Если зайти на страницу и написать в консоли SHOW_WEIGHTS = true, можно визуально прочувствовать работу алгоритма (Будут показаны веса клеток).
Пораскинул я мозгами и привел такое соответствие атак и весов:
Подобрано эмпирически – возможно это не оптимальный вариант.
Я добавил в массив атаки мощностью 5 с запредельно большим весом. Объяснить это можно тем, что бот анализирует игру, смотря на шаг вперед (подставляя фигуру в клетку). Пропуск такой атаки есть ни что иное, как поражение. Ну или победа… смотря для кого.
Атаки с большим потенциалом ценятся выше.
Атака [4:2] в большинстве случаев решает исход игры. Если игроку удалось создать такую атаку, то оппонент уже не сможет ее заблокировать. Однако это еще не победа. Противник может быстрее завершить игру, даже при наличие у нас на поле атаки [4:2], поэтому ее вес ниже, чем у атак мощностью 5. Смотри пример ниже.
Рис 2. Атака [4:2]
В этом абзаце код не представлен. Здесь мы вводим понятие делителя атаки и объясняем суть «рваных атак».
Рассмотрим такую ситуацию: при подстановке фигуры на удалении нескольких пустых клеток, но не более 5-и, расположена еще одна.
И вроде бы, две одинаковые фигуры, на одной линии… визуально это похоже на атаку, а по факту нет. Не порядок, так как такие «рваные» атаки также несут в себе потенциальную угрозу.
Специально для таких случаев, для каждой атаки будем просчитывать делитель. Изначально его значение равно 1.
Рис 3. Разбор «Рваной атаки». Сканируется клетка с желтым крестиком.
Таким образом, «рваные» атаки так же будут учитываться ИИ. На самом деле, это будут обычные атаки, но чем они дальше находятся от сканируемой клетки, тем меньшее влияние на нее оказывают и, соответственно, имеют меньший вес (благодаря делителю).
Во-первых, создадим класс атаки. У атаки будет 3 атрибута, о которых я писал ранее:
И один метод, который будет возвращать вес данной атаки:
Далее. Поиск всех атак для одной клетки мы разделим на:
Все это – линии, и алгоритм поиска атак на данных линиях можно обобщить: класс checkLine.
Однако, нам не нужно проверять всю линию целиком. Максимальная мощность атаки, которая нас интересует – 5. Безусловно, создать атаку мощностью, скажем, 6 – возможно. Но для ИИ, который анализирует игровую ситуацию следующего хода, все равно, что 6, что 5. Перспектива получить одну из этих атак говорит о конце игры на следующем ходу. Соответственно, вес анализируемой клетки будет в обоих случаях будет одинаковым.
Атрибуты класса:
Здесь надо остановиться, так как может возникнуть вопрос: зачем проверять 6-ую клетку, если максимальная мощность атаки – 5. Ответ – это нужно для определения потенциала удаленной от центра атаки.
Вот пример: атака мощностью 1 на картинке находится на границе сканируемой области. Чтобы узнать потенциал этой атаки нужно «заглянуть за границу».
Рис. 3. Сканирование 6-ых клеток. Если не просканировать 6-ую клетку, можно неправильно определить потенциал атаки.
Для завершения некоторых атак может просто не хватать места. Посчитав attackplace мы заранее можем понять, какие из атак бесперспективны.
Рис. 4. Место для атаки
Алгоритм следующий:
1) Начнем с центральной клетки. Она должна быть пустой (мы ведь собираемся сделать в нее ход, не так ли? Однако мы не забываем, что наш ИИ должен подставлять фигуры в данную клетку для анализа следующего хода. Фигура, которую мы подставляем – this.subfig – по умолчанию крестик. Поскольку центральная клетка изначально будет содержать в себе какую-либо фигуру после подстановки, то она будет принадлежать какой-то атаке this.curAttack:
Все эти пункты мы отобразили в значениях конструктора по умолчанию – смотри код выше.
2) Далее, уменьшая итератор, перебираем 5 клеток с одной стороны от сканируемой. За это отвечает функция getAttacks( cellX, cellY, subFig, dx, dy ), где:
cellX, cellY – координаты проверяемой клетки
subFig – фигура, которую мы подставляем в проверяемую клетку
dx, dy – изменения координат x и y в циклах – так мы задаем направление поиска:
В каком-то смысле, это вектор, параллельный линии поиска. Таким образом, одна функция сможет осуществлять поиск в 4-х направлениях и мы лишний раз не нарушим принцип DRY.
Код функции:
Обратите внимание, что если checkCell() что-то вернет, то выполнение цикла прекращается.
3) Проверяем фигуры данных клеток.
За это отвечает функция checkCell( x, y ):
Для начала запишем фигуру в переменную fig:
Model.Field – наше игровое поле.
fig может быть ‘x’, ‘o’, ‘b’ (граница), 0 (пустая клетка).
4) Если на 5-ой клетке фигура совпадает с центральной клеткой, значит атака «уперлась» в границу и для определения потенциала атаки придется «проверить границу» ( this.checkEdge = true).
Функция checkCell – готова. Однако продолжаем работать над классом checkLine.
5) После выполнения первого цикла, надо «развернуться». Переводим итератор в центр и центральную атаку, с индексом 0, убираем из массива атак и устанавливаем как текущую.
6) Далее идем в другую сторону от текущей клетки, увеличивая итератор.
Абсолютно такая же проверка фигур. (Код уже написан – функция getAttacks)
7) Все, мы собрали все атаки, что были на линии в один массив.
На этом с классом checkLine всё… закончили.
Ну а дальше все просто – создаем объект checkLine для каждой из линий (2 диагонали, горизонталь и вертикаль) и вызываем функцию getAttacks. То есть, для каждой линии — свой объект checkLine и, соответственно, свой набор атак.
Пусть за все это отвечает функция getAllAttacks() – уже отдельно от описанных выше классов;
На выходе имеем объект со всеми атаками для проверяемой клетки
Однако вы, возможно, заметили некую функцию-фильтр. Ее задача – отсеивать «бесперспективные» атаки:
Однако, если атака имеет мощность больше 5, то фильтр ее пропустит. Такие атаки бот должен видеть, их отсеивание приведет к косякам в конце игры.
Да… снова термин, простите! Так мы будем называть ситуацию в игре, когда один неправильный ход решает исход игры.
Например, атака [3:2] – это брейкпоинт. Если оппонент не заблокирует ее, поставив рядом фигуру, то следующим ходом, мы уже имеем на игровом поле атаку [4:2] – ну и исход игры решен, как ни крути (В подавляющем большинстве случаев).
Или атака [4:1]. Один зевок — и игру можно легко завершать.
Рис 5. Брейкпоинт
Тут все ясно и понятно, и тот алгоритм, о котором писалось выше уже способен учитывать брейкпоинты и своевременно их блокировать. Бот смотрит на ход вперед. Он увидит, что на следующем ходу оппонент способен создать атаку [5:1], например, вес которой 200 – значит хитрый ботяра пойдет сюда.
Однако, представим ситуацию, когда один из игроков умудряется получить на поле 2 брейкпоинта. И это, очевидно, не оставляет шансов сопернику, т.к. за один ход мы можем заблокировать только один брейкпоинт. Как научить наш ИИ блокировать такие атаки?
Рис 6. 2 Брейкпоинта
Все просто, при анализе клетки, при подстановке фигуры в нее, мы будем считать количество брейкпоинтов, которое мы получим на следующем ходу (бот смотрит на ход вперед, не забываем). Насчитав 2 брейкпоинта, мы увеличиваем вес клетки на 100.
И теперь, бот не только будет предотвращать такие игровые ситуации, но и сможет их создавать, что делает его теперь более грозным противником.
Начнем с очевидного: любая атака, мощностью 4 – брейкпоинт. Всего один пропущенный ход дает нам возможность завершить игру, т.е. поставить 5 фигур в ряд.
Далее, если потенциал атаки равен 2, то на блокировку такой атаки мы потратим на 1 ход больше, а значит существует брейкпоинт, мощностью 3. Но такой брейкпоинт всего один – это атака [3:2].
А далее сложнее – «рваные атаки».
Мы будем рассматривать только атаки с одной пустой клеткой посередине – не больше. Это объясняется тем, что для завершения атаки с двумя пустыми клетками посередь, нужно потратить минимум 2 хода – это явно не брейкпоинт.
Как мы помним, рваные атаки мы рассматриваем, как несколько обычных: одна центральная атака и побочные. Центральной атаке принадлежит сканируемая клетка, у побочных делитель больше 1 – об этом писалось выше.
Алгоритм нахождения брейкпоинта (можно проще – читай ниже):
Итак, основной ад позади — описан выше. Пора слепить из него что-то рабочее. Функция countWeight( x, y ) — принимает на вход координаты клетки, а возвращает ее вес. Что же у нее под капотом?
Во-первых, получим массив всех атак, которым клетка принадлежит. ( getAllAttacks( x, y ) ). Перебирая все линии, мы считаем количество брейкпоинтов. Если 2 брейкпоинта – вспоминаем, что такая ситуация может решить исход игры, и увеличиваем вес клетки на 100.
Однако все брейкпоинты должны принадлежать одному игроку, поэтому пришлось реализовать проверку в 2 шага: сначала крестики, потом нолики.
Поскольку в массиве весов атак ( ATTACK_WEIGHTS[] ) я не предусмотрел атаки мощностью 6 и больше, мне пришлось заменить их на атаки мощностью 5. Разницы никакой – все они приводят к концу игры.
Ну и суммируем веса атак – к этому все и шло.
Еще небольшой момент: чтобы бот в конце игры не тупил, когда он уже построил атаку мощностью 4 и думает над текущем ходом, необходимо значительно увеличить вес клетки для завершения такой атаки. Без этого, ИИ, просто на просто, может начать защищаться от «опасных» атак оппонента, хотя игра, казалось бы выиграна. Последний ход важен.
Теперь при вызове этой функции для конкретной клетки мы получим ее вес. Проводим эту операцию для всех клеток и выбираем наилучшую (с наибольшим весом). Туда и ходим)
Остальной код вы сможете найти на github. Материала уже предостаточно, и его изложение, как я не пытался, оставляет желать лучшего. Но если ты смог дочитать до этого момента, дорогой читатель, то я тебе благодарен.
Сойдет! Да, его можно обыграть, однако сделать это немножко проблематично лично для меня. Возможно я просто недостаточно внимателен. Попробуйте и вы свои силы.
Знаю, что можно проще, но не знаю как. Хотелось бы выслушать людей знающих или посмотреть на иные реализации такого бота.
Знаю, что можно лучше. Да… можно воспользоваться известными алгоритмами, вроде минимакса, но для этого нужно обладать некоторой базой знаний в области теории игр, чем похвастать увы не могу.
В будущем планирую добавить анализ брейкпоитов на несколько шагов вперед, что сделает бота еще более серьезным соперником. Однако сейчас не имею четкого представления о реализации сего; лишь имею предстоящую сессию и недописанный диплом – что меня огорчает.
Спасибо, если ты дочитал до конца.
Эта статья про процесс разработки ИИ на javascript для игры в одну из таких вариаций крестиков-ноликов: получилось довольно много материала, но я разбавил его анимацией и картинками. В любом случае, хотя бы стоит попробовать поиграть в это.
Отличия этого варианта игры от оригинала в следующем:
- Поле может быть сколь угодно большим (На сколько хватит тетради)
- Побеждает тот, кто поставит 5 фигур (если их можно так назвать) в ряд.
Все просто… и в то же время сложно: исход игры не может быть просчитан заранее, как в классическом аналоге. Этот «маленький проектик» отнял у меня много времени и нервов. Надеюсь, что вам будет интересно.
Перед тем, как начнем
Вынужден извиниться заранее за объем статьи и местами не совсем доходчивое изложение мысли, однако у меня не получилось сжать стаю без потери в содержании и качестве.
Рекомендую сначала ознакомиться с результатом. Код
Горячие клавиши и команды:
- D – ИИ сделает ход за вас
- T – посмотреть вес клетки
- Напишите в консоли SHOW_WEIGHTS = true, чтобы просматривать веса всех анализируемых клеток.
Начнем
Начать нужно с реализации самой игры, т.е. написать приложение для двух игроков, пока без бота. Для своих целей я решил использовать javascript + jquery + bootstrap4, хотя он там практически не используется, но его лучше оставить – или таблица поплывет. Тут рассказывать особо нечего, материала по js, jquery и bootstrap на хабре полно. Скажу лишь, что использовал MVC. Да и вообще, объяснять абсолютно весь код я не буду – материала и без того получилось много.
Итак, игровое поле было готово. Можно устанавливать фигуры в клетки. Но победа кого-либо из игроков никак не фиксировалась.
Сканирование «конца игры»
Игра заканчивается, когда один из игроков поставит 5 фигур в ряд. «Все просто!» — подумал я. И начал сканировать абсолютно все клетки поля: сначала все горизонтали, потом вертикали и, наконец, диагонали.
Это тупой способ, но он работал. Однако, его можно было значительно улучшить, что я и сделал: Большая часть клеток будет оставаться пустой на протяжении всей игры – игровое поле слишком большое, чтоб его можно было заполнить целиком. Поскольку сканировать его нужно было каждый ход, а за один ход ставится только одна фигура — то можно сосредоточиться только на этой фигуре (клетке): просканировать только одну горизонталь, вертикаль и две диагонали клетки, которым принадлежит та самая клетка.
Плюс ко всему, не нужно сканировать все клетки линий. Поскольку конец игры – это 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;
}
}
Приступим к самому боту
Итак, мы уже написали страницу с крестиками-ноликами. Переходим к основной задаче – ИИ.
Нельзя просто так взять и написать код, если ты не знаешь как: нужно продумать логику бота.
Суть заключается в анализе игрового поля, хотя бы его части, и просчета цены (веса) каждой клетки на поле. Клетка с наибольшим весом – самая перспективная – туда бот и поставит фигуру. Основная сложность именно в просчете веса одной клетки.
Терминология
Крестики и нолики – это фигуры.
Атакой будем называть несколько одинаковых фигур, стоящих рядом, на одной линии. По сути, это множество. Количество фигур в атаке – её мощность. Одна отдельная фигура – тоже атака (мощностью 1).
На соседних клетках атаки (на концах) могут быть пустые клетки или фигуры противника. Логично думать, что атаку с двумя пустыми клетками на «концах», мы можем развивать в двух направлениях, что делает ее более перспективной. Количество пустых клеток на «концах» атаки будем называть её потенциалом. Потенциал может принимать значения 0, 1 или 2.
Атаки обозначаем так: [ мощность атаки, потенциал ]. Например, атака [4:1].
Рис 1. Атака [4:1]
В ходе анализа мы будем оценивать все клетки, которые входят в определенную область. У каждой клетки будет просчитываться её вес. Он вычисляется на основе весов всех атак, на которые влияет данная клетка.
Суть анализа
Представим, что на игровом поле уже есть несколько атак одного и второго игрока. Кто-то из игроков делает ход (пускай крестики). Естественно ход он делает в пустую клетку – и тем самым он может:
- Развить свою атаку, а может быть и не одну, увеличив ее мощность. Может начать новую атаку и т.д.
- Препятствовать развитию атаки противника или и вовсе заблокировать ее.
То есть, наш протагонист может атаковать и защищаться. А может и все сразу одним ходом. Для него важно, как первое, так и второе.
Суть анализа в следующем:
- Бот подставляет в проверяемую клетку фигуры: сначала крестик, потом нолик.
- Далее он ищет все атаки, которые были получены такими ходами и суммирует их веса.
- Полученная сумма – это вес клетки.
- Подобный алгоритм выполняется для всех клеток игрового поля.
По сути, таким алгоритмом мы проверяем, что будет, если мы пойдем так… а что будет если так пойдет оппонент. Мы смотрим на один ход вперед и выбираем наиболее подходящую клетку – с наибольшим весом.
Если какая-то клетка имеет больший вес, нежели другая, значит она приводит к созданию более опасных атак, либо к блокировке сильных атак противника. Все логично… мне кажется.
Если зайти на страницу и написать в консоли SHOW_WEIGHTS = true, можно визуально прочувствовать работу алгоритма (Будут показаны веса клеток).
Веса атак
Пораскинул я мозгами и привел такое соответствие атак и весов:
ATTACK_WEIGHT = [[],[],[],[],[],[]];
ATTACK_WEIGHT[1][1] = 0.1;
ATTACK_WEIGHT[2][1] = 2;
ATTACK_WEIGHT[3][1] = 4;
ATTACK_WEIGHT[4][1] = 6;
ATTACK_WEIGHT[5][1] = 200;
ATTACK_WEIGHT[1][2] = 0.25;
ATTACK_WEIGHT[2][2] = 5;
ATTACK_WEIGHT[3][2] = 7;
ATTACK_WEIGHT[4][2] = 100;
ATTACK_WEIGHT[5][2] = 200;
ATTACK_WEIGHT[5][0] = 200;
Подобрано эмпирически – возможно это не оптимальный вариант.
Я добавил в массив атаки мощностью 5 с запредельно большим весом. Объяснить это можно тем, что бот анализирует игру, смотря на шаг вперед (подставляя фигуру в клетку). Пропуск такой атаки есть ни что иное, как поражение. Ну или победа… смотря для кого.
Атаки с большим потенциалом ценятся выше.
Атака [4:2] в большинстве случаев решает исход игры. Если игроку удалось создать такую атаку, то оппонент уже не сможет ее заблокировать. Однако это еще не победа. Противник может быстрее завершить игру, даже при наличие у нас на поле атаки [4:2], поэтому ее вес ниже, чем у атак мощностью 5. Смотри пример ниже.
Рис 2. Атака [4:2]
«Рваные» атаки
В этом абзаце код не представлен. Здесь мы вводим понятие делителя атаки и объясняем суть «рваных атак».
Рассмотрим такую ситуацию: при подстановке фигуры на удалении нескольких пустых клеток, но не более 5-и, расположена еще одна.
И вроде бы, две одинаковые фигуры, на одной линии… визуально это похоже на атаку, а по факту нет. Не порядок, так как такие «рваные» атаки также несут в себе потенциальную угрозу.
Специально для таких случаев, для каждой атаки будем просчитывать делитель. Изначально его значение равно 1.
- «Рваную» атаку представляем, как несколько обычных
- Считаем количество пустых клеток между центральной атакой и побочной
- За каждую пустую клетку, делитель увеличиваем на 1
- Вес центральной атаки просчитываем как обычно, вес побочных – делим на делитель
Рис 3. Разбор «Рваной атаки». Сканируется клетка с желтым крестиком.
Таким образом, «рваные» атаки так же будут учитываться ИИ. На самом деле, это будут обычные атаки, но чем они дальше находятся от сканируемой клетки, тем меньшее влияние на нее оказывают и, соответственно, имеют меньший вес (благодаря делителю).
Алгоритм поиска атак
Во-первых, создадим класс атаки. У атаки будет 3 атрибута, о которых я писал ранее:
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
}
}
Далее. Поиск всех атак для одной клетки мы разделим на:
- Поиск на горизонтали
- Поиск на вертикали
- Поиск на диагонали 45 градусов
- Поиск на диагонали 135 градусов
Все это – линии, и алгоритм поиска атак на данных линиях можно обобщить: класс checkLine.
Однако, нам не нужно проверять всю линию целиком. Максимальная мощность атаки, которая нас интересует – 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;
Все эти пункты мы отобразили в значениях конструктора по умолчанию – смотри код выше.
2) Далее, уменьшая итератор, перебираем 5 клеток с одной стороны от сканируемой. За это отвечает функция getAttacks( cellX, cellY, subFig, dx, dy ), где:
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 )
В каком-то смысле, это вектор, параллельный линии поиска. Таким образом, одна функция сможет осуществлять поиск в 4-х направлениях и мы лишний раз не нарушим принцип DRY.
Код функции:
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 == '0' || 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[0];
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, '0', 1, 0 );
cO['90'] = this.getAttacksLine( cellX, cellY, '0', 0, 1 );
cO['45'] = this.getAttacksLine( cellX, cellY, '0', 1, -1 );
cO['135'] = this.getAttacksLine( cellX, cellY, '0', 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 )
- С нулевым потенциалом.
Однако, если атака имеет мощность больше 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
}
Брейкпоинты
Да… снова термин, простите! Так мы будем называть ситуацию в игре, когда один неправильный ход решает исход игры.
Например, атака [3:2] – это брейкпоинт. Если оппонент не заблокирует ее, поставив рядом фигуру, то следующим ходом, мы уже имеем на игровом поле атаку [4:2] – ну и исход игры решен, как ни крути (В подавляющем большинстве случаев).
Или атака [4:1]. Один зевок — и игру можно легко завершать.
Рис 5. Брейкпоинт
Тут все ясно и понятно, и тот алгоритм, о котором писалось выше уже способен учитывать брейкпоинты и своевременно их блокировать. Бот смотрит на ход вперед. Он увидит, что на следующем ходу оппонент способен создать атаку [5:1], например, вес которой 200 – значит хитрый ботяра пойдет сюда.
Однако, представим ситуацию, когда один из игроков умудряется получить на поле 2 брейкпоинта. И это, очевидно, не оставляет шансов сопернику, т.к. за один ход мы можем заблокировать только один брейкпоинт. Как научить наш ИИ блокировать такие атаки?
Рис 6. 2 Брейкпоинта
Все просто, при анализе клетки, при подстановке фигуры в нее, мы будем считать количество брейкпоинтов, которое мы получим на следующем ходу (бот смотрит на ход вперед, не забываем). Насчитав 2 брейкпоинта, мы увеличиваем вес клетки на 100.
И теперь, бот не только будет предотвращать такие игровые ситуации, но и сможет их создавать, что делает его теперь более грозным противником.
Как понять, что атака – брейкпоинт
Начнем с очевидного: любая атака, мощностью 4 – брейкпоинт. Всего один пропущенный ход дает нам возможность завершить игру, т.е. поставить 5 фигур в ряд.
Далее, если потенциал атаки равен 2, то на блокировку такой атаки мы потратим на 1 ход больше, а значит существует брейкпоинт, мощностью 3. Но такой брейкпоинт всего один – это атака [3:2].
А далее сложнее – «рваные атаки».
Мы будем рассматривать только атаки с одной пустой клеткой посередине – не больше. Это объясняется тем, что для завершения атаки с двумя пустыми клетками посередь, нужно потратить минимум 2 хода – это явно не брейкпоинт.
Как мы помним, рваные атаки мы рассматриваем, как несколько обычных: одна центральная атака и побочные. Центральной атаке принадлежит сканируемая клетка, у побочных делитель больше 1 – об этом писалось выше.
Алгоритм нахождения брейкпоинта (можно проще – читай ниже):
- Введем переменную score
- Берем центральную атаку, считаем мощность
- Берем одну из побочных, если ее делитель не больше 2х.
- Score – сумма мощностей центральной и побочной атак
- Если потенциалы центральной и побочной атак равны 2, то для блокировки такой атаки нужно потратить на один ход больше. Поэтому, score увеличиваем на 1
- Если score >= 4, то это брейкпоинт
На самом деле брейкпоинты можно было просто перечислить, их не так много, но это я понял далеко не сразу.
isBreakPoint( attackLine ){
if( ! attackLine || ! attackLine.length ) return false;
var centAtk;
attackLine.forEach( ( a )=>{
if( a.divider == 1 )
centAtk = a;
})
if( centAtk.capability >= 4 )
return true
if( centAtk.potential == 2 && centAtk.capability >= 3 )
return true;
var res = false;
attackLine.forEach( ( a )=>{
var score = centAtk.capability;
if( a.divider == 2 ){ //side attack
if( centAtk.potential == 2 && a.potential == 2 )
score++;
if( score + a.capability >= 4 ){
res = true;
return;
}
}
})
return res;
}
Да соберем, наконец, все воедино
Итак, основной ад позади — описан выше. Пора слепить из него что-то рабочее. Функция countWeight( x, y ) — принимает на вход координаты клетки, а возвращает ее вес. Что же у нее под капотом?
Во-первых, получим массив всех атак, которым клетка принадлежит. ( 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, '0' );
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. Материала уже предостаточно, и его изложение, как я не пытался, оставляет желать лучшего. Но если ты смог дочитать до этого момента, дорогой читатель, то я тебе благодарен.
Мое мнение о полученном результате
Сойдет! Да, его можно обыграть, однако сделать это немножко проблематично лично для меня. Возможно я просто недостаточно внимателен. Попробуйте и вы свои силы.
Знаю, что можно проще, но не знаю как. Хотелось бы выслушать людей знающих или посмотреть на иные реализации такого бота.
Знаю, что можно лучше. Да… можно воспользоваться известными алгоритмами, вроде минимакса, но для этого нужно обладать некоторой базой знаний в области теории игр, чем похвастать увы не могу.
В будущем планирую добавить анализ брейкпоитов на несколько шагов вперед, что сделает бота еще более серьезным соперником. Однако сейчас не имею четкого представления о реализации сего; лишь имею предстоящую сессию и недописанный диплом – что меня огорчает.
Спасибо, если ты дочитал до конца.
Комментарии (17)
GarryC
22.11.2018 14:01+1Насколько я помню, в рэндзю начинающий выигрывает, если не ограничить его второй ход. У Вас программа научилась выигрывать при отсутствии ограничений?
igruh
22.11.2018 14:34+1Неверно, в рэндзю есть фолы и дебютный регламент.
ainoneko
23.11.2018 09:03Неверно,
"Глубокая истина".
В «советском» рэндзю было ограничение на второй ход чёрных и не было фолов.
AlexUsov
22.11.2018 16:08-1Крестики-нолики не шахматы и программа может гарантированно всегда выигрывать на таком большом поле. Я как то делал подобное обычным брутфорсом, используя оптимизацию альфа-бета отсечением. И даже не на полную глубину, а всего на несколько шагов. Чем эффективнее эвристическая функция, тем на меньшую глубину нужно сканировать игровое дерево. Уже плохо помню и если не ошибаюсь обыграть или достигнуть ничьи, можно было только на поле из 3 клеток при первом ходе игрока.
ryzhikovas
22.11.2018 18:01+1Минимакс совсем не страшен, просто попробуйте реализовать. Цель этого метода — выбрать последовательность ходов бота, которая при самых сильных ходах игрока-соперника приведет к лучшему для бота результату. Достигается эта цель путем «заглядывания в будущее» на некоторое количество ходов вперед и оценки состояния игровой доски в каждом из вариантов будущего. Реализовать минимакс можно рекурсивной функцией, в которой вы перебираете все варианты хода из некоторого набора для бота (копируете состояние поля, делаете ход) и, рекурсивно спускаясь, вызываете эту же функцию, но перебираете ходы игрока. Продолжаете рекурсию… Остается только вовремя остановиться, оценить, используя ваши эвристики, все позиции на нижнем уровне рекурсии и выбрать ход, который привел к наилучшей для бота позиции при любых ходах игрока.
ukhanov
22.11.2018 21:17+1В своё время в 70-х развлекались с этим на фортране. Оценочная функция была аналитической. Рекурсию позволить себе не могли. Играла программа безобразно.
Так что уважуха автору.
ainoneko
23.11.2018 09:11Сначала мне показалось, что это действительно другая игра: слова
Побеждает тот, кто поставит 5 фигур (если их можно так назвать) в ряд.
можно понять и так, что каждый игрок может ставить любую «фигуру» по своему выбору.
Только на словах «Кто-то из игроков делает ход (пускай крестики)» стало понятно, что нет.
hipposphaericus
24.11.2018 00:53Неплохая попытка. Для курсовой и начинающего игрока — действительно «Сойдет!» Но, знаете, почему сильнейшие программы были написаны при помощи сильных игроков? Именно потому что программа играет на уровне своего хозяина. Отвлеченный математик не всегда способен уловить нюансы игры — что именно нужно анализировать и на что обращать внимание, сводя всё к тупому перебору вариантов. Вероятно поэтому долго не могли написать бота для Го, играющего на уровне выше первых любительских данов — профи игроки этим не занимались, а начинающий или даже средний игрок просто не способен алгоритмизировать сильную игру без тупого перебора, на который уходит много времени. АльфаГо справилась только с привлечением гигантских мощностей и огромных объемов обучения, а также с привлечением к разработке сильных игроков, которые указали узкие места. Кстати, у меня была идея, в каких случаях АльфаГо будет трудно одолеть человека (версии, игравшей с Ли Седолем).
Ваше честное «его можно обыграть, однако сделать это немножко проблематично лично для меня» — подтверждает правило. Попробуйте дойти в рэндзю или гомоку до уровня I дана — вы совсем по другому станете смотреть на свои «брейкпоинты» и возможно сможете написать более-менее сильного бота. Подскажу со своего среднего уровня — сильный игрок будет искать скорее «двойное обозначение» (т.е. позицию, в которой противник не может защититься от построения вилки, т.к. позиция позволяет построить две вилки в разных частях позиции), чем отыгрывать четверки (уменьшая комплексность позиции и теряя возможные линии атаки).
Ну и конечно изучите хотя бы историю вопроса — начиная с названия игр, которые вы пытаетесь алгоритмизировать (гомоку, пять в ряд) и их терминологии, их тактики и стратегии. Вступление в стиле «еще в древнем Китае была известна игра, в которую школьники и студенты всего мира играли на уроках в 20-м веке» определенно лучше вступления «не знаю кто придумал играть в крестики-нолики на доске 9х9». )) 9х9 — это обучающая доска в Го (на которой обычно не играли, просто показывали правила, начинающим), то есть это минимальная доска в играх с камнями (Го, Гомоку, Рэндзю). Для ускорения партии («сбацаем по быстрому, пока учитель не смотрит») играли и на такой маленькой доске, но играть на ней сложно, обычно использовали ученическую 13х13, которую японцы немного увеличили до 15х15 для игры в рэндзю, а нормальная доска для гомоку — 19х19 (обычная доска в Го).AlexPelmen Автор
24.11.2018 19:29Спасибо за комментарий.
Каюсь, я действительно не знал об истории вопроса. Впредь буду внимательнее.
К слову сказать, началось все с небольшого негласного спора с другом, и со своей первостепенной задачей движок справился — он обыграл его.
В то же время, я остался доволен результатом и решил им поделиться.
gerasimenkoao
Все, хорошо, но есть два замечания:
Игра известна под названием "пять в ряд"
Вот не надо приплетать эти популярные слова — ИИ — да не смешите меня, тогда шахматные программы вообще можно называть НАДМОЗГ, да реализовав алгоритм на R, можно было-бы сказать что проект из области bigdata.
В свое время данную игру даже на бейсике писали(просто брейпоинты по-другому звались ;-), а так, статье ставлю положительную оценку — "за волю к победе"
igruh
Гомоку и рэндзю грустно переминаются в углу.
anprs
В английском языке словосочетание artificial intelligence не имеет антропоморфной окраски, которую оно приобрело в традиционном русском переводе: слово intelligence в используемом контексте скорее означает «умение принимать разумные решения», а вовсе не «интеллект» (для которого есть английский аналог intellect).
В данном конкретном случае «интеллект» — вычислительная составляющая способности программы достигать своей цели (обыгрывать человека)
в своей узкой области применения.
mayorovp
Компьютерных соперников для игр испокон веков называли ИИ.
Mabu
Вы так говорите, как будто написать игру на бейсике намного проще, чем не на бейсике.