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

Для начала хочу определиться с основными моментами. Во-первых, существует множество разновидностей игры гомоку, я остановился на таком варианте: игровое поле 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) есть вокруг всех ходов, для создания «небольшой случайности хода».

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

Правила как играть в крестики нолики

Играть в крестики-нолики можно в любом месте и все что вам понадобится для соревнования — это листок бумаги, ручки и карандаши и, конечно, противник. Но при желании можно купить готовый набор для крестиков-ноликов. Причём такая настольная игра понравится даже малышам, ведь все детали вы ней выполнены в ярком цвете.

Играть в крестики-нолики можно в любом месте.

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

1. Расчертите игровое поле из квадратов с размерами 3*3.
2. Договоритесь, кто из участников будет ходить крестиками или ноликами.
3. Первый игрок ставит фигуру в любую из клеточек, после чего ход переходит следующему участнику.
4. Второй игрок рисует символ в свободной клеточке, и ход возвращается к первому участнику.
5. Игра продолжается пока не заполнятся все клетки, или один из участников не сделает цепочку из трёх одинаковых символов. Причём ряд идёт по горизонтали, вертикали или диагонали.

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

Как выиграть в игре на двоих

Выиграть в эту игру можно не только благодаря удаче. Советы, которые помогут победить противника:

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

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

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

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

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

Х	О	О
	Х
Х

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

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

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

		О
	Х
Х

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

	О
!		!
!		!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Материал о том, как побеждать, или, по крайней мере, никогда не програть в крестики-нолики, предлагает со ссылкой на 4brain.ru.

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

Немного о правилах. Цель игры выстроить на девятиклеточном поле подряд 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: еще одна стратегия

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

Начинаем с угловой клетки

Суть этой стратеги заключается в том, что «крестик» осуществляет первый ход не в центральную ячейку, а в угловую. В этом случае, нолик имеет несколько вариантов действий.

Вариант 1. «Нолик» ходит в центр. Этот вариант наиболее вероятен как для умелого, так и для неискушенного игрока по тем причинам, которые описывались в предшествующей статье . В этом случае игроку за крестики предлагается поставить свою фигуру в противоположный от первого хода угол. Теперь происходит второй ход нолика, который будет являться решающим. Если нолик ставит фигуру в неугловую клетку, то крестик вынужден защищаться, и игра, скорее всего, закончится ничьей. А если же нолик занимает угловую ячейку, то в этом случае у «крестиков» появляется беспроигрышная стратегия: возможность сделать «вилку», заняв оставшийся угол. Это алгоритм действий выглядит следующим образом:

Вариант 2. «Нолик» ходит в бок. В этом случае «крестики» уже с первого хода имеют выигрышную стратегию: необходимо сделать ход в центр, заставив «ноликов» защищаться, а затем ход в угол, чтобы получилась «вилка». Эта тактика изображена ниже:

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

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

Что делать ноликам?

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