П. 1. Крестики-нолики

Исследуем известную игру крестики-нолики. Правила следующие:: 1) играют на доске 3 ´ 3; 2) ходят по очереди: 1-й игрок ставит крестик на любое свободное поле, 2-й игрок — нолик; 3) выигрывает тот, кто первым поставит в ряд 3 своих значка (по вертикали, горизонтали или диагонали).

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

	´

	´

´

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

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

o	´

´
o	´

´
o	´
		o

´		´
o	´
		o

´		´
o	´
o		o

´	´	´
o	´
o		o

Покажем, что если первый игрок поставил первый крестик в центр поля, а второй игрок поставил первый нолик на середину любой стороны, то второй игрок форсированно проигрывает (если, конечно, первый игрок не поддается, а играет правильно). Пусть второй игрок поставил нолик на середину левой стороны. Достаточно рассмотреть этот случай, т.к. остальные 3 случая (второй игрок ставит нолик на середину других сторон) эквивалентны этому (получаются из него зеркальной симметрией). Тогда выигрышная партия первого иг­рока показана слева. Этот выигрыш форсирован, т.к. первый игрок выигрывает независимо от ходов второго игрока.

Задание 2. Сколько всего разных ноликов — с учетом симметрии — может поставить второй игрок в ответ на каждый из трех первых ходов первого игрока? Нарисуйте все эти разные ответы второго игрока, а также остальные эквивалентные ответы с осями симметрии. Какие из этих ответов приводят к форсированному проигрышу второго игрока? Докажите.

Существуют игры-гибриды тетриса и крестиков-ноликов: это все цветные тетрисы, где пропадают ряды из 3 и более элементов одного цвета (Columns, Tetcolor и другие).

п. 2. Безумные крестики-нолики

´
		·

´		·

	´
·

´		·

´
·

	´
	·

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

´		o

	´

´
		o

´
		o

´
	o

	´

o	´

	´
o

	´
	o

o	´

o
	´

´

	´
o

´	o

	´
	o

Ответ на задание 2. Существует 12 разных первых ходов второго игрока. Все они приведены на дереве вариантов. 7 из них закрашены: они ведут к форсированному проигрышу второго игрока.

4 проигрышных ответа 2-го игрока приходится на первый ход 1-го игрока в угол. Следовательно, с новичками, плохо играющими в эту игру, нужно начинать первым ходом в угол, и тогда только единственный ответ 2-го игрока не ведет к проигрышу. Поэтому если ответ 2-го игрока достаточно случаен, то в 4 случаях из 5 2-й игрок форсированно проигрывает!

Задание 3. На дереве выше изображены 15 досок с ходами. Дорисуйте дерево ходов до конца: 1) с учетом симметрии, рисуя только разные ходы; 2) дерево обрывается, если позиция ведет к форсированному выигрышу или ничьей; 3) игроки не совсем тупые и реагируют на непосредственную угрозу поставить 3-й знак. Есть ли позиции с форсированным выигрышем 2-го игрока? Может ли 2-й игрок заставить выиграть 1-го? А наоборот? Сколько всего получилось разных досок с ходами?

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

Следующая разновидность игры еще интереснее: это безумные кре­с­тики-нолики. Здесь каждый игрок при своем ходе может поставить как крестик, так и нолик — что ему заблагорассудится. Побеждает тот, кто первым закончит ряд из одинаковых знаков, безразлично каких. Однако игроки оказываются в неравном положении: начинающий всегда выигрывает. Можно играть и безумные поддавки: ходят любыми знаками и проигрывает тот, кто первым образует ряд из трех одинаковых знаков.

Задание 4. Найдите и нарисуйте выигрыш первого игрока в безумных крестиках-ноликах. Кто выигрывает в безумных поддавках? Докажите.