Как начертить большое поле крестиков ноликов

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

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

Немного о правилах. Цель игры выстроить на девятиклеточном поле подряд 3 одинаковых фигуры (3 крестика или 3 нолика) по горизонтали, по вертикали или по диагонали раньше, чем это сделает ваш партнер по игре. Игра в крестики-нолики начинается с хода игрока, который ставит крестик в любой клетке на игровом поле три на три (отметим сразу, что у него гораздо больше шансов выиграть, чем у противника). После этого второй игрок ставит в любой свободной ячейке нолик. Затем снова ходит крестик. Потом опять нолик. И так продолжается до тех пор, пока:

1. Кто-то из игроков не построит в ряд или по диагонали 3 крестика или 3 нолика, и в результате чего будет признан победителем;
2. Не останется свободных клеток, и на поле не будет присутствовать трех идущих подряд одинаковых фигур — в этом случае объявляется ничья.

Тактика крестиков

Первый ход крестиков. Самой выгодной позицией является середина игрового поля, или как отмечено на схеме клетка №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 клеток.

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

Кроме того, рекомендуем ознакомиться с еще одной стратегией крестиков-ноликов 3 на 3 по ссылке.

Советуем также прочитать:

• Сторителлинг
• Лучшие настольные игры
• Санкт-Петербургский парадокс: каждый решает сам!
• Обзор на наш курс по «Быстрое чтение» от LazyLady
• Игры на развитие мышления
• Как побеждать в спорах: уроки от Артура Шопенгауэра. Часть четвёртая
• Как побеждать в спорах: уроки от Артура Шопенгауэра. Часть шестая
• Ошибка игрока: понятный разбор
• Шахматы для детей: развлечение или вклад в развитие?
• Шахматы для начинающих
• Гайд по Google Sheets: универсальный инструмент планирования

«Крестики-нолики» и другие игры на бумаге

Зимние каникулы – хорошее время, чтобы вспомнить тихие домашние игры из детства. Умеют ли современные дети играть в «крестики-нолики»? А по усложненным правилам? А в «точки»?

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

Крестики-нолики

Игроки по очереди ставят на свободные клетки поля 3×3 знаки. Один игрок ходит крестиками, а другой – ноликами. Первый, выстроивший в ряд 3 своих фигуры по вертикали, горизонтали или диагонали, выигрывает. Первый ход делает игрок, ставящий крестики. Три знака, составивших сплошной ряд, вычеркивают.

Три в ряд, или «безумные» крестики-нолики

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

Крестики-нолики на бесконечном поле

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

Коридорчики (палочки)

Для игры нужен лист бумаги в клетку прямоугольной или квадратной формы. Можно начертить игровое поле 6х6 клеток или другого размера. Игроки по очереди проводят горизонтальные или вертикальные линии в одну клетку. Игрок, которому удалось замкнуть линиями клетку (образовать квадрат 1х1), ставит в ней крестик (или нолик, или первую букву имени) и получает еще один ход. Замкнув две клетки, можно поставить свой знак в обеих. Когда все клетки окажутся занятыми, подсчитывают, кто «захватил» больше клеток.

Точки

Эта игра похожа на игру го. Поле игры — лист бумаги (в клетку) любого выбранного размера. Соперники по очереди ставят точки на пересечении линий, каждый своим цветом.

1. Игра идет на поле размером 39х32 пунктов. Пунктом считается пересечение линий на поле. Играют двое, разными цветами.
2. Игроки ходят по очереди (1 ход — одна точка). Первый ход каждого из соперников происходит в центральной части поля (8х15). Последующие ходы могут быть в любой пункт, если только он не в окруженной области. Возможности пропускать ход нет.
3. При создании непрерывной (по вертикали, горизонтали, диагонали) замкнутой линии образуется область. Если внутри нее есть точки противника (при этом могут быть пункты, не занятые чьими-либо точками), то это считается областью окружения, в которую далее запрещено ставить точку любому из игроков. Если точек соперника нет, то область свободная и в нее можно ставить точки.
4. При появлении в свободной области точки соперника, свободная область будет считаться областью окружения, при условии, что точка соперника не была завершающей в его окружении
5. Точки, попавшие в область окружения, далее не участвуют в образовании линий для окружения.
6. Точки, поставленные на краю поля, не окружаются.
7. Партия заканчивается, когда не осталось свободных мест, либо когда один из игроков говорит СТОП.
8. Побеждает игрок, который окружил большее число точек соперника. Есть также разновидность игры, в которой нужно захватить как можно больше территории противника.

Перегородки (змейка)

На листе в клетку чертится квадрат 10х10 так, чтобы его горизонтальные стороны располагались между линий тетрадной разметки. Каждый игрок делает ход своим цветом. Ход первого игрока – это соединение горизонтальной или вертикальной линией вершин одной клетки. Каждый ход второго игрока – соединение линией центров двух соседних клеток. Линии игроков не должны пересекаться. Побеждает тот, кто сможет соединить непрерывной линией две стороны большого квадрата (игрового поля).

Война вирусов

Игра для двоих или четного количества игроков, на поле 10*10 (можно и больше). Каждый игрок обозначает свои «вирусы» определенным символом – крестиком, точкой и т.д. За ход выставляется три «вируса». Начинают свое размножение вирусы из противоположных угловых клеток поля. Выставить «вирус» можно только рядом с другим своим «живым вирусом». Если рядом оказывается «вирус» противника, то его можно съесть, закрасив клетку в свой цвет. Такие образования называются «крепостями». Если «крепость» прикасается хоть к одному живому вирусу своего цвета, то от нее можно дальше в любом месте создавать новые «вирусы» или есть противника. Целью игры является полное уничтожение живых сил противника. Если обоим сторонам удается спрятать своих живых вирусов за крепостью из съеденных вирусов противника, игра заканчивается ничьей.

о детях от 7 до 10 лет Другие статьи автора

Крестики нолики «Без границ»

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

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

1. Поле может быть сколь угодно большим (На сколько хватит тетради)
2. Побеждает тот, кто поставит 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]

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

Суть анализа

Представим, что на игровом поле уже есть несколько атак одного и второго игрока. Кто-то из игроков делает ход (пускай крестики). Естественно ход он делает в пустую клетку – и тем самым он может:

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

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

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

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

Если какая-то клетка имеет больший вес, нежели другая, значит она приводит к созданию более опасных атак, либо к блокировке сильных атак противника. Все логично… мне кажется.
Если зайти на страницу и написать в консоли 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. «Рваную» атаку представляем, как несколько обычных
2. Считаем количество пустых клеток между центральной атакой и побочной
3. За каждую пустую клетку, делитель увеличиваем на 1
4. Вес центральной атаки просчитываем как обычно, вес побочных – делим на делитель

Рис 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 >> 

Далее. Поиск всех атак для одной клетки мы разделим на:

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;

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

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 )

getAttacks( cellX, cellY, subFig, dx, dy )< this.substitudeFigure( subFig ); //Уменьшаем итераторы – перебираем клетки. for( var x = cellX - dx, y = cellY - dy; Math.abs( x - cellX ) 
Обратите внимание, что если 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).


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'; >
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()
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 > 
Брейкпоинты
Да… снова термин, простите! Так мы будем называть ситуацию в игре, когда один неправильный ход решает исход игры.
Например, атака [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, '○' ); 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. Материала уже предостаточно, и его изложение, как я не пытался, оставляет желать лучшего. Но если ты смог дочитать до этого момента, дорогой читатель, то я тебе благодарен.
Мое мнение о полученном результате
Сойдет! Да, его можно обыграть, однако сделать это немножко проблематично лично для меня. Возможно я просто недостаточно внимателен. Попробуйте и вы свои силы.
Знаю, что можно проще, но не знаю как. Хотелось бы выслушать людей знающих или посмотреть на иные реализации такого бота.
Знаю, что можно лучше. Да… можно воспользоваться известными алгоритмами, вроде минимакса, но для этого нужно обладать некоторой базой знаний в области теории игр, чем похвастать увы не могу.
В будущем планирую добавить анализ брейкпоитов на несколько шагов вперед, что сделает бота еще более серьезным соперником. Однако сейчас не имею четкого представления о реализации сего; лишь имею предстоящую сессию и недописанный диплом – что меня огорчает.
Спасибо, если ты дочитал до конца.

крестики-нолики
javascript


JavaScript
Разработка игр
Логические игры

Как начертить большое поле крестиков ноликов

Игра "Крестики-нолики" на бесконечном поле
Эта страница позволит Вам онлайн сыграть в известную игру "Крестики-нолики" на бесконечном поле (еще называют "5 в ряд"). Реальное поле имеет размер 19*19 клеток, но для игры это равносильно бесконечности. Игра бесплатная и без регистрации. Также можно скачать программу "Крестики-нолики" для ПК.
Цель игры - построить непрерывный ряд из 5 крестиков (компьютер играет ноликами) по горизонтали, вертикали или диагонали. Выиграть у компьютера достаточно сложно, но вполне реально, хотя по сумме очков победить мало у кого получается.
По окончании партии следующая начнется автоматически. Первый ход всегда предоставляется человеку.
Для начала игры нажмите кнопку Начать игру 
Текущие результаты игры (компьютер : человек) - 0 : 0

Онлайн утилиты
Фотографии природы
Проверка совместимости
Читать фантастику
Духовные знания
Получить Благословение



Похожие публикации:

Err cache miss ошибка на андроиде что делать
Даны четыре целых числа определить сколько из них четных
Как заменить перевод строки на абзац в ворде
Как убрать гиперссылку в ворде на макбуке