Что такое ядро игры?

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

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

Игра довольно простая, если не сказать примитивная. Но когда я решил копнуть её поглубже, моя лопата вдруг звякнула обо что-то металлическое. Это оказалось ядро игры.

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

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

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

Любую позицию на доске я буду обозначать тройкой чисел A-B-C, где A - число клеток между первой парой шашек, В - между второй, а С - между третьей парой. Таким образом, исходная позиция записывается в виде 2-4-6. Порядок следования чисел не имеет никакого значения.

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

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

Следующий кусочек ядра нашёлся в позиции 1-4-5. И опять второй игрок побеждает, парируя любой ход противника в позицию 1-2-3 или х-х-0.

И, наконец, исходная позиция 2-4-6 оказалась тоже принадлежащей ядру! Любой ход "белых" парируется чёрными, приводя к одной из описанных выше позиций.

Кстати, теперь можно разрешить ходить не только вперёд, но и назад: ход назад парируется ходом вперёд на то же число клеток с удержанием расстояния между ними.

Далее, я рассмотрел новую исходную позицию - 6-6-6. Все шашки стоят на первой и последней линии. И она оказалась принадлежащей ядру. Там есть промежуточный кусок ядра 3-5-6, неизбежно приводящий к 1-4-5 или 1-2-3 или х-х-0. Либо игра сводится к предыдущей 2-4-6 - всё зависит от первого хода "белых".

Итак, мы видим, что чёрные выигрывают всегда, если исходная позиция принадлежит ядру. В противном случае, всегда выигрывают белые - ведь первым же ходом они ставят подходящую "ядерную" позицию.

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