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

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

Для начала хочу определиться с основными моментами. Во-первых, существует множество разновидностей игры гомоку, я остановился на таком варианте: игровое поле 15х15, крестики ходят первыми, выигрывает тот, кто первый построит 5 в ряд. Во-вторых, игровой алгоритм расчета хода компьютером для простоты буду называть AI.

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

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

Update 1

1. На 10% увеличил значимость весов для атаки. Теперь атака для AI предпочтительнее защиты при прочих равных. Например, если 4ка у AI и у пользователя, то AI предпочтет выиграть.

2. Изменил значения весов по шаблонам. При более четкой балансировки весов можно добиться лучшей игры AI.
Значения весов у шаблонов сейчас такие:
99999 - xxxxx - пять в ряд (финальная выигрышная линия)
7000 - _xxxx_ - открытая четверка
4000 - _xxxx - полузакрытая четверка (две таких четверки предпочтительнее одной открытой, возможно «интереснее игра» будет)
2000 - _x_xxx, _xx_xx, _xxx_x - полузакрытая четверка с брешью (2 таких четверки равны одной открытой четверке и «предпочтительнее» открытой тройки; но если только 1 такая четверка, то открытая тройка предпочтительнее)
3000 - _xxx_ - открытая тройка
1500 - _xxx - полузакрытая тройка
800 - _xx_x, _x_xx - полузакрытая тройка с брешью
200 - _xx_ открытая двойка
Также небольшие веса (от 1 до 20-30) есть вокруг всех ходов, для создания «небольшой случайности хода».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм победы

Для того чтобы научиться выигрывать или, по крайней мере, не проигрывать в крестики - нолики, нужно запастись вниманием и… терпением. При отсутствии ошибок с той или иной стороны игра будет заканчиваться ничьей бесконечно. Главный принцип, определяющий, как выиграть в крестики - нолики, заключается в создании ситуации, при которой после любого хода противника игрок заполнит одну из двух линий, то есть поставит три крестика или три нолика подряд. Пример такой ситуации показан на схеме №1.

Х	О	О
	Х
Х

Схема №1 (При любом ходе нолика крестики выигрывают).

Порядок действий

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

		О
	Х
Х

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

	О
!		!
!		!

Схема №3 (Занятие крестиком помеченных клеток ведет к проигрышу)

Поняв тактику, можно попробовать играть в вариант крестиков ноликов 5х5 на бесконечном поле. Для этого необходимы только тетрадный лист в клетку и ручка. Задача игры – выстроить линию из 5 фигур. Тактика крестиков будет заключаться в построении вилок, а нолики будут вынуждены блокировать атаки, то есть пресекать линии из 3 крестиков и блокировать вилки.

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

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

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

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

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

Варианты, когда игровое поле имеет размеры от 4 х 4 до бесконечности, рассмотрим ниже, после разбора комбинаций игры в поле 3х3.

Базовые принципы общие, и освоив алгоритм "три в ряд", вы сможете уверенно играть в более сложные и интересные варианты этой древней игры.

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

Игроки по очереди меняются, кому играть за крестиков и ноликов.

Древние китайцы вместо рисованных символов "Х" и "0" на поле ставили камни, черные и белые. Сейчас дома в качестве поля можно использовать шахматную доску и шашками обозначать клетку, на которую сделан ход.

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

Стратегия победы пошагово видеоразбор

Небольшой видео ролик, для тех, кому так проще воспринимать информацию. Кому интереснее читать, листаем дальше.

Возможны два варианта исхода игры:

1. Вы победили.
2. Ничья. Закончились пустые клетки на игровом поле и ходить больше некуда.

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

Для удобства рассказа, я каждый квадрат игрового поля обозначил цифрами, от 1 до 9.

(5) - центральная клетка.

(1), (3), (7), (9) - угловые клетки.

(2), (4), (6), (8) - боковые клетки.

Чтоб не растягивать повествование, я для каждого варианта первого хода буду рассматривать по одной комбинации. Если в моем примере нолики сходили в угловую клетку (1), а в вашем случае в угловую клетку (3), (7) или (9), то мысленно разверните поле и продолжайте ходить по изложенному мной алгоритму.

Ситуация №1, крестики ходят в центр

Когда крестики первым ходом занимают центральную клетку (5), ноликам остается ходить в угловую клетку или в боковую.

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

В нашем примере нолики сходили в боковую клетку (8).

Крестики ответным ходом занимают любую угловую клетку, для примера клетку (1) и получают линию из двух крестиков (см. рисунок).

Главная премудрость игры и основа всей тактики держится на двух принципах:

Принцип 1. Занимай ту клетку, которая принесет тебе немедленную победу;

Принцип 2. Если такой клетки нет, занимай клетку, которая принесет немедленную победу сопернику.

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

Крестики занимая клетку (7) нейтрализуют угрозу со стороны ноликов и одновременно с этим строят две линии из своих фигур. Для победы в следующем ходе крестикам нужно будет занять клетку (3) или (4). См. шаг 5.

Такое построение, когда одним ходом создается две угрозы, называется ВИЛКА.

Нолики в шестом шаге заняв клетку (3) закрывают одну угрозу со стороны крестиков.

Крестики по принципу 1, ходят в клетку (4) и одерживают победу.

Ситуация №2, крестики ходят в центр

Предположим, что теперь вы играете ноликами. Чтоб не проиграть эту встречу, первым ходом нужно занять угловую клетку. Без разницы какую, на ваш вкус (1), (3), (7) или (9). Для примера возьмем (1), см. рисунок ниже, шаг 2.

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

Нолики закрывают линию крестиков, и создают свою угрозу - см. шаг 4.

Крестики по принципу 2 ходят в квадрат (4), нолики отвечают в квадрат (6). См. шаг 5 и 6.

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

Вилку крестикам при таком начале игры построить не получится, но и ноликам не дадут. Если по невнимательности, после 6-го шага, нолики сходят в угловую клетку (9) вместо боковой (2) или (8), то крестики одержат победу построив горизонтальную линию (2)-(5)-(8).

Ситуация №3, крестики ходят в угол

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

Ход ноликов, как и в ситуации №1, от этого хода зависит исход игры. Если нолики сходили в боковую клетку, то вы построите вилку и победите.

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

В случае хода ноликами на боковую клетку, шаг 2, вы занимаете еще одну угловую клетку, образуя угрозу - линию из двух фигур. См. шаг 3.

Центр, клетку (5) умышленно оставим пустой для ноликов. Часто, нолики вместо того, чтоб закрыть вашу угрозу ходом в боковую клетку (2), радостно занимают центр.

Если противник попался на уловку и сходил в клетку (5), мы занимаем клетку (2) и линия построена (1)-(2)-(3)

Не будем недооценивать соперника, и он в шаге 4 закрыл нашу угрозу ходом на боковую клетку (2)

Крестикам ничего не остается, как по первому принципу занять центральную клетку (5) и построить вилку.

Теперь, см. шаг 6, куда бы нолик не ткнулся, у нас останется свободной одна из двух угловых клеток (7) или (9), ход в которую и принесет нам победу.

Ситуация №4, крестики ходят на боковую клетку

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

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

Рендзю, жемчужная нить, гомоку, пять в ряд

Когда вам стало тесно и скучно в игровом поле 3х3, и играть три в ряд уже не спортивно, переходим на большую игровую площадь.

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

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

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

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

По правилам, первый ход делают черные и им запрещено делать вилки 3х3, 4х4, а так же ряд из 6 и более "камней" своего цвета подряд.

Зато черные могут делать вилки размером 3х4, когда за один ход образуются две перекрещивающиеся линии - одна длиной три камня, вторая из 4 камней. Так что нет повода расслабляться у того, кто играет белыми.

Белые, за то, что ходят вторыми - имеют следующие преимущества:

• Могут строить вилки любого размера и любой кратности;
• Победу белым приносит линия не только 5 в ряд, но и из большего числа камней;
• Для своей победы белые могут вынудить построить черных линию из 6 и более камней подряд.

Ничья

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

Если оба игрока подряд отказались от хода, объявляется ничья.

Закончились все свободные клетки - ничья.

Получается, игрок еще может пропустить ход, потому что ему некуда ходить.

Гомоку, отличия от рендзю

1. Для черных отсутсвуют фолы (запрещенные ходы), и черные могут строить вилки любой кратности и длины.
2. Ряд из шести и более камней одного цвета не приносит победы ни одной из сторон.

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

Сервисы, где можно играть онлайн

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

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

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

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

С вами был Александр Утышев

В жизни бывают такие моменты, когда появляется свободное время, но абсолютно нечем себя занять. Если рядом с вами находится еще один скучающий человек, то вы вместе можете поиграть в простейшую игру, которая всем известна с детства - в крестики-нолики. У каждого человека на инстинктивном уровне заложено стремление к победе. «Как выигрывать в крестики-нолики?» - спросите вы. Это очень просто. Освоить несколько техник выигрыша вам поможет данная статья.

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

Сейчас мы рассмотрим несколько схем, которые помогут обыграть оппонента на поле размером 3х3. Итак, представим, что вы делаете первый ход. Советуем занять центральную клетку поля. Это даст вам существенное преимущество. В ответ на это ваш соперник может сделать два хода: поставить нолик (крестик) по диагонали от вашей фигуры или же прямо, по горизонтали или вертикали. Если оппонент выбрал второй вариант, то поздравляем! Теперь победа за вами! Следующим ходом можете поставить крестик (нолик) в любую свободную клетку поля, но только не симметрично фигуре противника относительно вашего первого хода. После этого сделайте так, чтобы в двух направлениях у вас стояло по две фигуры, и тогда соперник сможет помешать вам только в одном из них. Это одна из схем того, как выигрывать в крестики-нолики.

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

Как уже было сказано выше, размер поля в крестиках-ноликах может быть любым, но чаще всего используются 3х3, 4х4, 5х5. Чем больше размер поля, тем, соответственно, сложнее выиграть. В этом случае описанные выше схемы победы над оппонентом не работают, так как это уже другие крестики-нолики. 5 в ряд - это цель игры 5х5, и, чтобы выиграть, необходимо не просто знать некоторые стандартные позиции, но и уметь анализировать положение фигур на поле.

Итак, теперь вам известно, как выигрывать в крестики-нолики, поэтому любой соперник будет вам по плечу и не будет представлять для вас никакой угрозы! Желаем удачи в игре, хотя в данном случае она вам не понадобится: ведь вы знаете отличные схемы, которые непременно помогут вам победить!