Оглавление рубрики "Похождения Сильвера"
В первой части мы рассмотрели игру, в которую играли пираты в штиль. Ставили бутылки в рядок и сбивали их выстрелами, причем сбивать можно либо одну бутылку, либо две подряд стоящие. Кто сбил последнюю, то и выиграл.
Попутно кратенько рассмотрели теорию игр Шпрага-Гранди. Если игра описана набором позиций и переходами между ними и выигрывает тот, кто сделал последний ход, то позиции можно присвоить числовую оценку по некоторому правилу. А если игра состоит из нескольких игр и на каждом ходу игрок выбирает "доску" и делает на ней ход, то оценка такой позиции вычисляется по оценке позиций на досках как поразрядная сумма. При этом позиция проигрышная тогда и только тогда, когда ее оценка равна нулю. А правило таково: оценка позиции есть минимальное неотрицательное число, которое не является оценкой какой-либо следующей позиции. Если ход нет (нет следующих позиций), оценка равна нулю (игрок уже проиграл).
Теперь ясно, как надо играть. Если ряд сплошной, надо разбить его на два равных и повторять ходы противника. Оценка для ряда из одной бутылки равна 1 (единственная позиция, в которую можно перейти, проигрышная), для ряда из двух она равна 2 (можно перейти в проигрышную и в позицию 1), для трех это 3, для четырех оценка равна 1 (оценки 3 и 2 заняты, позиция 2-2 имеет оценку нуль, позиция 2-1 дает 3, так как в двоичном коде это 10-01 и поразрядно дает двоичное 11, то есть 3; единичка свободна). Ну, и так далее. Для каждого ряда оценка получается через уже полученные, для многих рядов складываем оценки поразрядно. Надо присылать противнику позиции с нулевой оценкой.
Теперь рассмотрим такую задачу: проигрывает тот, кто сбил последнюю бутылку. То есть, надо одинокую бутылку прислать противнику.
Сильвер знал, что эта задача уже не сводится к формату Шпрага-Гранди. Точнее, не допускает разложение игры на отдельные подыгры (не нравится мне сия орфография, пусть будет под-игры). Если считать, что есть невидимая бутылка, которую надо сбить последней, то в каждой под-игре такая будет, а это не годится.
Я, кстати, не знаю хорошего алгоритма. Если есть идеи — буду благодарен.
Давайте по старинке. Рассуждать. Для начала немного простых соображений.
- Если прислать противнику нечетное число одиночных бутылок (разделенных промежутками), то это победа. Если четное, то проигрыш.
- Если получить от противника любое число одиночек и одну пару, то это победа: из пары можно сделать одну, а можно ни одной: то есть нечет всегда можно обеспечить.
- То же справедливо для тройки и любого числа одиночек. Из тройки можно сделать две одиночки или одну одиночку. Можно еще пару сделать, но нам это не надо.
- Если мы даем противнику четное число одиночек и четное (но ненулевое) число пар и троек (каждое четное), то это победа. Мы можем поддерживать такую симметрию, что бы не делал противник, повторяя ходы.
Получается, что четное число единичек без двоек и троек "токсично", а с парой (или более) двоек-троек напротив, выигрышно. Это имеется в виду "дать противнику".
Итак, мы можем поддерживать симметрию, пока есть куски длиной в 2 и 3, причем симметрично. Рассмотрим более крупные, чем два и три.
Если противник получит 4-4, "прикрытые" парами двоек и троек? Ходы и двойками, тройками и одиночками не меняют ситуации (пока хоть что-то осталось). Из четверки можно сделать тройку, двойку, 1-2 и 1-1. Мы можем повторить ход с другой четверкой и выиграть.
Однако "голые" 4-4 токсичны: противник сделает из четверки 1-1 и мы вынуждены либо дать ему двойку или тройку, либо еще пару единиц, что даст четное количество 4. Если противник будет выбивать двойки и тройки, а мы — повторять ходы, то он вычистит все прикрытие и выиграет. Причем наличие четного числа единичек ему не помеха (а вот нечетное — помеха).
Но мы не обязаны повторять ходы всегда! Когда останется последняя двойка или тройка, мы нарушим симметрию одиночек, сделав их число нечетным. Противник получит 4-4 и нечетную серию одиночек. Рано или поздно ему придется или "тронуть" четверку, или прислать нам "голую" 4-4, что для него поражение. Если он сделает из четверки тройку или двойку, мы сделаем то же, обеспечив четность одиночек. Это победа. Если он превратит четверку в 1-1, мы получим нечетную серию единичек и четверку; превратив ее в 1-1, мы посылаем нечетную серию единичек и выигрываем.
Итак, 4-4, прикрытые четной серией двоек и троек и четным числом одиночек, выигрышны (если эту позицию дать противнику).
А вот дальше не вижу удобной схемы! Задача рекурсивная: имея позицию, можно посмотреть все позиции, которые из нее получаются. Если есть среди них проигрышная, ее противнику и пришлем. Если нет, то она сама проигрышная. База рекурсии: одна бутылка — она проигрышная по определению.
Ни скриншоте скрипт на Перл. Весь, вместе с комментариями и документацией: рекурсия вещь компактная. Сам скрипт — первые 11 строк: берем позицию из командной строки, передаем фукнции win, докладываем результат и потом еще запишем просчитанные позиции, чтоб не пропали. Сама рекрсивная функция win занимает строки с 20 по 38 и сбивает бутылку с проверкой полученной позиции или две, если можно, и тоже проверяет позицию.
Привожу таблицу раскладов. Там не все... А что делать?! Найду формулу, сообщу.
Пример. Начальная позиция: 25 бутылок в ряд. Сильвер сбивает одну, делая 6 и 18. Противник, допустим, 4 и 18. Сильвер отвечает 3-18. Противник делает 3 и 8-8. Сильвер отвечает 1-1 и 8-8. Противник: 1-1-3-3-8. Сильвер сбивает одну одиночку. Противник восстанавливает: 1-1-3-8. Сильвер повторяет ход: 1-1-1-8. Противник сбивает единичку, Сильвер другую. Противник — третью, оставляя Сильверу восьмерку. Сильвер делает 5-1, ну и далее понятно.
Удачи в море!