Оглавление рубрики "Похождения Сильвера"
Возвращаемся к жизнеописанию Сильвера! В штиль, когда кончался ром, пираты развлекались стрельбой по пустым бутылкам. На планшир ставили бутылки в рядок, и по очереди стреляли. Сбить можно одну или две рядом стоящие бутылки. Кто последнюю сбил, тот и выиграл.
Сильвер стрелял обычно первым, как старший по званию. И всегда выигрывал. Как?
Иногда кто-то требовал право первого выстрела. Но понять стратегию пираты не могли, поэтому Сильвер все равно, как правило, выигрывал. Порой он предлагал поставить бутылки в кольцо вокруг пирата с теми же условиями: сбивать одну или пару рядом стоящих. И выигрывал при втором ходе. Как?
Когда пираты всё-таки поняли хитрость, Сильвер предложил расставлять бутылки не сплошным рядом, а с промежутками — произвольно. И играть по тем же правилам. Иногда Сильвер стрелял первый, иногда уступал очередь — но всегда выигрывал. Как?
В конце заметки я поставлю несколько вопросов, ответы на которые мне пока неизвестны.
Первая задача: "сбей последнюю бутылку"
Итак, какова выигрышная стратегия в такой игре? Сильвер сбивал одну или две бутылки в середине, разбивая ряд на два одинаковых. Затем симметрично повторял ходы противника.
При этом, что бы не делал противник, Сильвер возвращает ему два одинаковых множества бутылок. Если в одном множестве бутылки кончились, Сильвер уберет оставшиеся в другом, и выиграет.
Если первым стрелял не Сильвер, то у противника был шанс. Однако, если не знать стратегии, то Сильвер может вернуть себе контроль. Порой удавалось выровнять два ряда, если разница была в одну или две бутылки.
Например, противник разбил ряд в 18 бутылок на два ряда в 9 и 7, сбив две бутылки. Сильвер сбивает две с краю, сделав два ряда по 7. Это победа.
Или можно получить от противника один ряд, если противник сбивал бутылку или две с краю, и сделать два равных.
Например, если противник из ряда в 18 сделал ряд в 17, сбив одну бутылку с краю. Сильвер делает два ряда по 8, сбив одну в центре.
В остальных же случаях все сложно. Игра в общем случае, когда начинаешь с произвольного числа рядов, похожа на игру Ним, только с ограничением на число сбитых бутылок. Я не знаю пока простого алгоритма. А непростой сейчас изложу, но кратко.
Та же игра, бутылки расставлены как угодно
Итак, теперь бутылки стоят как угодно, но сбивать можно две подряд стоящие (или одну).
Есть такая теория игр Шпрага-Гранди. Я о ней расскажу в другой раз, а сейчас тезисно. Рассматриваются игры, которые описываются ориентированным графом: набором позиций и переходами между ними: из какой в какую можно попасть. И нужно, чтобы противник не смог сделать хода.
Суть в том, что каждой позиции присваивается число (оценка позиции), и это число равно наименьшему неотрицательному целому числу, которое не является оценкой позиции, в которую игрок может перейти своим ходом.
Если среди этих позиций нет позиции с нулевой оценкой, то оценка нуль; если есть нуль, но нет 1, то 1; и так далее. Если хода нет, оценка нуль.
То есть, пусть из данной позиции я могу перейти в позиции А, Б и В, и эти позиции имеют оценки 0, 2 и 42. Тогда наименьшее число, которого здесь нет, это 1: это и будет оценка моей позиции.
Доказывается, что позиция проигрышная, если и только если ее оценка равна нулю. А также, если есть две игры данного класса, и при каждом ходе игрок выбирает "доску" и делает на ней ход, то оценка такой позиции есть поразрядная двоичная сумма оценок позиции на отдельных досках.
Отсюда элементарно следует алгоритм для игры Ним! Выигрыш для одной кучки очевиден: забираем всё, и всё; а n кучек — это n игр.
Поразрядная сумма это сумма в каждом разряде двоичного представления чисел по правилам 0+0=1+1=0, 0+1=1+0=1.
Ряд из бутылок есть отдельная игра. Поэтому, зная оценки для рядов, можно получить оценку для любого расклада.
Ряд из одной бутылки оценивается числом 1: ведь противник проиграл. Из ряда в 2 бутылки можно сделать ничего (0) или одну бутылку (1). Так что оценка равна 2. Далее надо смотреть, на какие два ряда можно данный ряд разбить.
Ряд в n бутылок может быть превращен в n-1 и n-2, так что оценки этх позиций заняты. Занят и нуль, так как ряд можно превратить в два равных с нулевой поразрядной суммой. Остальное надо проверять, поразрядно складывая оценки (уже полученные) для i и n-i-1 и для i и n-i-2. Вот оценки для первых нескольких чисел:
1 → 1; 2 → 2; 3 → 3; 4 → 1; 5 → 4; 6 → 3; 7 → 2; 8 → 1; 9 → 3; 10 → 2;
11 → 6; 12 → 1; 13 → 4; 14 → 3; 15 → 2; 16 → 1; 17 → 3; 18 → 2; 19 → 4;
20 → 1; 21 → 5; 22 → 3; 23 → 2; 24 → 1; 25 → 3.
Вряд ли больше 25 бутылок в одном ряду, правда?
Например, первый игрок выбивает бутылку или две из середины, прислав Сильверу два ряда: из 10 и из 3 бутылок. Сильвер сбивает одну, оставив 9. Оценка девятки и тройки одна и та же, равна трем: поразрядная сумма нуль, так что позиция проигрышная.
Другой пример: Сильвер получил 7 и 1. Сильвер выбивает из длинного ряда две бутылки, оставив три слева, две справа и передав противнику три ряда: 1, 2, 3. В двоичном коде 01, 10, 11: сумма поразрядно равна нулю. Партнер проиграет.
А вот если Сильверу досталось 6 и 3, то позиция проигрышная. Ему надо сделать любой ход и опять надеяться на ошибку противника. А вот какой ход оставляет больше возможностей для ошибки — это тоже задача, только уже психологическая.
В принципе, Сильвер может оценить позицию, состоящую из данного набора рядов из бутылок: выигрышная она или проигрышная, и выбрать, стрелять первым или нет. Потом его уже не победить.
Игра с бутылками, которые стоят кольцом
Если бутылки стоят кольцом, то выигрывает второй стрелок. Первый сделает один пробел, превратив кольцо в ряд с двумя концами, а Сильвер делает из этого ряда два одинаковых.
Если же первый стреляет Сильвер, ситуация похожа на уже изученную. Есть два ряда, и надо постараться сделать из них проигрышную позицию.
А если можно сбивать ровно одну бутылку?
Тогда всё намного проще! Можно даже не применять теорию Шпрага-Гранди. Нечетные ряды, как бы бутылки не стояли, выигрышные; четные проигрышные. Но теорию применить поучительно, советую это проделать. Докажите по индукции, что для четного n оценка нуль, а для нечетного равна единице. Потом любое количество рядов (а промежутки теперь ничему не мешают) складывается поразрядно: четные не влияют, а нечетные дают 1, если их нечетное количество, и 0, если четное. Кстати, число ходов от тактики не зависит, очевидно.
А что, если можно сбивать две бутылки не подряд?
Здесь опять перестает играть роль расположение бутылок. Можно сбить одну, можно две. Делим мысленно все бутылки на два множества (если их нечетное количество, сбиваем одну; если четное, то две) и повторяем ходы противника.
А если можно сбивать любое число бутылок, стоящих подряд?
Это игра Ним. Запишите длины рядов в двоичной системе и сложите поразрядно. Надо противнику присылать сумму нуль. Это всегда возможно.
Ну, пусть можно сбивать одну, две или три бутылки, стоящие подряд.
По сути ничего не меняется. Ряды из 1, 2 и 3 бутылок имеют оценки 1, 2 и 3, соответственно. Далее смотрим, на какие ряды можно разделить данный. Всегда присутствуют n-1, n-2 и n-3, а также пары i, n-i-1 при i от 1 до n-2; i, n-i-2 при i от 1 до n-3; i, n-i-3 при i от 1 до n-4. Пары проверяем поразрядной суммой. Получаем такие оценки:
1 → 1; 2 → 2; 3 → 3; 4 → 4; 5 → 1; 6 → 6; 7 → 3; 8 → 2; 9 → 1; 10 → 8;
11 → 3; 12 → 6; 13 → 1; 14 → 4; 15 → 3; 16 → 2; 17 → 1; 18 → 4; 19 → 3;
20 → 5; 21 → 1; 22 → 6; 23 → 3; 24 → 2; 25 → 1.
Если изначально ряд один, так же делим его на два равных, а вот если нет, то пригождаются оценки. Например, пара 5-9 проигрышная, а 5-10 выигрышная: делим 10 на 2 и 7, оценки рядов будут 2, 1 и 3, в двоичном коде 10, 01 и 11, в сумме поразрядно это нуль.
Итак, вопросы, на которые я ответа пока не знаю:
- Игра "не сбивай последнюю". Казалось бы, решается введением воображаемой "последней бутылки", которая стоит отдельно и сбивается последней. Но ведь дать противнику два ряда по две бутылки — это победа... Держать симметрию и вовремя соскочить, скорее всего, вариант, но не совсем понятно пока, когда соскакивать. Я разберусь и напишу заметку.
- Как играть, если стрелков трое? Или больше?
- Самое главное: есть ли формула для оценки позиции, или надо считать все варианты рекурсивно? У меня есть скрипт на Перле, но у Сильвера его не было! А в уме разложить ряд в сто бутылок всеми способами на два, держа в памяти оценки от 1 до 99... Нужна формула, которая для сплошного ряда дает оценку его как функцию его длины. Но я даже не уверен, что есть такая формула...
У четных прослеживается тенденция: (2 1 3 1) (2 1 3 1) (2 1 3 1)... У нечетных пока не вижу.
Если найду ответ (а это не основной приоритет в моей жизни) или кто-то подскажет, заметка будет обновлена! А может, напишу новую.
Заранее спасибо.
Оглавление рубрики "Похождения Сильвера"