Умеете ли вы играть в "рассаду"?

К сожалению, далеко не каждая игра имеет день рождения. Игра "рассада" его имеет - она была изобретена профессором Дж. Конуэем и М. Патерсоном 21 февраля 1967 года.

Правила просты. На листе бумаги, который представляет собой "игровое пространство", нарисовано несколько точек. Играют двое, делая ходы по очереди. Каждым ходом игрок может либо соединить линией (не обязательно прямой) какие-нибудь две точки и поставить на этой линии новую точку, например, так (для наглядности новая точка обведена) - рис. 12, либо нарисовать петлю, т. е. замкнутую кривую, исходящую из некоторой точки, и поставить на ней новую точку (рис. 13). Линии, в том числе петли, не должны иметь самопересечений и не могут проходить через точку, не являющуюся концом данной линии. Запрещено также проводить линии, пересекающие уже имеющиеся линии. Например, на рис. 14 показанные пунктиром ходы запрещены. Здесь в случае а пунктирная линия пересекает ранее проведенную, в случае б она имеет самопересечение, в случае в она проходит через точку, не являющуюся ее концом. Кроме этих ограничений имеется еще одно: из каждой точки должно выходить не более трех "ростков". Например, на рис. 15 обозначенный пунктиром ход не разрешается, так как в результате него из точки А выходили бы четыре "ростка".

Рис. 12

Рис. 13

Рис. 14

Рис. 15

Как видно, ограничений довольно много, так что не в каждой позиции можно сделать хоть какой-нибудь ход. Например, в позиции на рис. 16 невозможно сделать ни одного хода.

Рис. 16

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

"Рассада" - абсолютно результативная игра, т. е. в ней нет ничьих. Не позднее чем после 3 × N - 1 ходов, где N - число исходных точек, партия заканчивается победой одного из игроков. Игра хороша также тем, что для нее не требуется почти никаких атрибутов - нужны только лист бумаги и карандаш.

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

При малом числе исходных точек игру удается проанализировать полностью. Например, если вначале есть лишь одна точка, то побеждает второй игрок (рис. 17). А вот анализ игры в "рассаду" на двух точках, более сложный, который показывает, как второй игрок добивается победы (рис. 18). Можно также показать, что при трех, четырех или пяти исходных точках выигрывает (при оптимальной игре) начинающий. Если число исходных точек больше пяти, полный анализ становится невозможным из-за сильного ветвления "дерева игры". Здесь не спасают даже современные ЭВМ.

Рис. 17

Рис. 18

Многие игры, в том числе и "рассада", допускают обращение. А именно, смысл имеет игра, обратная данной. Что такое игра, обратная данной? Это значит, что целью игры является как бы свой проигрыш, при том, что все остальные правила остаются в силе. Например, в обратной "рассаде" выигравшим считается тот, кто не может сделать ход. Обратная "рассада" оказывается ничуть не проще, для анализа, чем обыкновенная. Известно, что при одной исходной точке побеждает первый игрок, при двух, трех и четырех - второй.