Введение

Игра стратегии, математическая игра стратегии.

Ним — это математическая игра стратегии, в которой два игрока поочередно убирают (или "нимуют") объекты из отдельных куч. На каждом ходу игрок должен убрать как минимум один объект и может убрать любое количество объектов, при условии, что все они взяты из одной кучи. В зависимости от версии игры, цель состоит либо в том, чтобы не взять последний объект, либо в том, чтобы взять последний объект. Ним является основополагающей для теоремы Спрага — Гранди, которая, по сути, утверждает, что каждая беспристрастная игра эквивалентна игре Ним с одной кучей.

История

В варианты игры ним играли с древних времен. Считается, что игра возникла в Китае — она тесно напоминает китайскую игру 捡石子 jiǎn shízi, или «подбирание камней», — но происхождение точно не установлено; самые ранние европейские упоминания об игре ним относятся к началу XVI века. Свое нынешнее название игра получила благодаря Чарльзу Л. Бутону из Гарвардского университета, который также разработал полную теорию игры в 1901 году, однако происхождение названия так и не было полностью объяснено. Оксфордский словарь английского языка выводит название от немецкого глагола nimm, означающего «бери». На Всемирной выставке в Нью-Йорке в 1939 году компания Westinghouse представила машину под названием Nimatron, которая играла в ним. С 11 мая 1940 года по 27 октября 1940 года лишь немногим удалось победить машину за этот шестимесячный период; в случае победы им вручали монету с надписью «Nim Champ». Это была также одна из первых электронных компьютерных игр. Компания Ferranti построила компьютер для игры в ним, который был продемонстрирован на Фестивале Британии в 1951 году. В 1952 году Герберт Коппель, Юджин Грант и Говард Бейлер, инженеры из корпорации W. L. Maxon, разработали машину, играющую в ним против человека и регулярно выигрывающую. Описывалась машина для игры в ним, собранная из конструктора Tinkertoy. Игра ним была темой колонки «Математические игры» Мартина Гарднера в журнале Scientific American за февраль 1958 года. Версия игры ним появляется — и имеет символическое значение — в фильме французской новой волны «В прошлом году в Мариенбаде» (1961).

Игровые игры и иллюстрации

Ним обычно играется как игра в "мизер", в которой проигрывает игрок, взявший последний объект. Ним также может быть сыгран как игра с "нормальным ходом", в которой выигрывает игрок, взявший последний объект. В обычной игре или в игре в "мизер", когда есть ровно одна куча, содержащая по крайней мере два объекта, игрок, который ходит следующим, может легко выиграть. Если этот ход удаляет все или все, кроме одного объекта из кучи, содержащей два или более объектов, то ни одна куча не будет содержать более одного объекта, и игроки будут вынуждены поочередно удалять ровно один объект до конца игры. Если игрок оставляет четное количество ненулевых куч (как это делается в обычной игре), то он берет последний объект; если игрок оставляет нечетное количество куч (как это делается в игре в "мизер"), то последний объект берет другой игрок. Обычная игра ведется между двумя игроками и играется с тремя кучами, содержащими любое количество объектов. Два игрока по очереди берут любое количество объектов из любой одной кучи. Цель – быть последним, кто возьмет объект. В игре в "мизер" цель состоит в том, чтобы заставить противника взять последний оставшийся объект. Следующий пример обычной игры разыгрывается между вымышленными игроками Бобом и Алисой, которые начинают с куч, содержащих три, четыре и пять объектов. Куча AКуча BКуча CХод 3 4 5 Игра начинается 1 4 5 Боб берет 2 из A 1 4 2 Алиса берет 3 из C 1 3 2 Боб берет 1 из B 1 2 2 Алиса берет 1 из B 0 2 2 Боб берет всю кучу A, оставляя два объекта по 2 0 1 2 Алиса берет 1 из B 0 1 1 Боб берет 1 из C, оставляя два объекта по 1. (В игре в "мизер" он взял бы 2 из C, оставляя (0, 1, 0).) 0 0 1 Алиса берет 1 из B 0 0 0 Боб берет всю кучу C и выигрывает.

Победовые позиции

Практическая стратегия победы в игре ним заключается в том, чтобы привести оппонента к одной из следующих позиций, и затем на каждом последующем ходу переходить к одной из меньших позиций. Только последний ход различается в вариантах игры с выигрышем последнего хода (нормальная игра) и проигрышем последнего хода (мизерная игра). 2 кучи3 кучи4 кучи1 1 *1 1 1 **1 1 1 *2 21 2 31 1 n3 31 4 51 2 4 74 41 6 71 2 5 65 51 8 91 3 4 66 6 2 4 61 3 5 77 72 5 72 3 4 58 83 4 72 3 6 79 93 5 62 3 8 9n n4 8 124 5 6 74 9 134 5 8 95 8 13n n m m5 9 12n n n n * Действует только для нормальной игры. ** Действует только для мизерной игры. Для обобщений n и m могут быть любыми значениями больше 0, и они могут быть равны.

Игра "100"

Похожая версия — "игра в 100": два игрока начинают с 0 и поочередно прибавляют к сумме число от 1 до 10. Игрок, который первым достигнет 100, побеждает. Выигрышная стратегия заключается в том, чтобы достичь числа, в котором цифры идут подряд (например, 01, 12, 23, 34) и контролировать игру, последовательно достигая чисел этой последовательности. Как только один из игроков достигает 89, противник может выбирать только числа от 90 до 99, а следующий ход в любом случае позволит достичь 100.

Правило многократного набора

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

Игра Гранди

В игре Гранди, еще одной вариации игры ним, некоторое количество объектов помещается в начальную кучу, и два игрока поочередно разделяют кучу на две неравные непустые кучи. Таким образом, шесть объектов можно разделить на кучи 5+1 или 4+2, но не 3+3. В игру Гранди можно играть по правилам мизера или обычной игры.

Жадный ним

Жадный ним — это вариация, в которой игроки ограничены выбором камней только из самой большой кучи. Это конечная беспристрастная игра. У жадного нима мизера те же правила, что и у жадного нима, но последний игрок, который может сделать ход, проигрывает. Пусть наибольшее количество камней в куче равно m, а второе по величине количество камней в куче равно n. Пусть pm — количество куч с m камнями, а pn — количество куч с n камнями. Тогда существует теорема, утверждающая, что игровые позиции с чётным pm являются P-позициями. Эту теорему можно доказать, рассмотрев позиции, где pm нечётно. Если pm больше 1, из этой кучи можно удалить все камни, чтобы уменьшить pm на 1, и новый pm станет чётным. Если pm = 1 (то есть самая большая куча уникальна), есть два случая: если pn нечётно, размер самой большой кучи уменьшается до n (так что теперь новая pm становится чётной). Если pn чётно, самая большая куча удаляется полностью, оставляя чётное количество самых больших куч. Таким образом, существует ход в состояние, где pm чётно. Обратно, если pm чётно, и возможен какой-либо ход (pm ≠ 0), то он должен привести игру в состояние, где pm нечётно. Конечная позиция игры чётная (pm = 0). Следовательно, каждая позиция игры с чётным pm должна быть P-позицией.

Индекс-к ним

Обобщение многокучной игры ним было названо "ним с индексом k" или "index k nim" Э. Х. Муром, который проанализировал его в 1910 году. В игре index k nim игроки могут удалять объекты не только из одной кучи, но из одной и до k различных куч. Количество удаляемых из каждой кучи элементов может быть как произвольным, так и ограничено максимум r элементами, как в вышеописанной "игре вычитания". Выигрышная стратегия следующая: как и в обычном многокучном ниме, рассматривается двоичное представление размеров куч (или размеров куч по модулю r + 1). В обычном ниме формируется сумма XOR (или сумма по модулю 2) каждой двоичной цифры, и выигрышная стратегия заключается в том, чтобы обнулить каждую такую сумму XOR. В обобщении к index k nim формируется сумма каждой двоичной цифры по модулю k + 1. Снова выигрышная стратегия состоит в том, чтобы сделать эту сумму равной нулю для каждой цифры. Действительно, вычисленное таким образом значение равно нулю в конечной позиции, и для любой конфигурации куч, для которой это значение равно нулю, любое изменение не более чем k куч сделает это значение ненулевым. И наоборот, для конфигурации с ненулевым значением всегда можно выбрать не более k куч и взять из них элементы так, чтобы значение стало равным нулю.

Здание

Строящий ним — это вариант игры ним, в котором два игрока сначала формируют игру. Дано n камней и s пустых куч. Игроки по очереди помещают ровно один камень в кучу по своему выбору. Как только все камни размещены, начинается игра в ним, начиная со следующего игрока, который должен сделать ход. Эта игра обозначается BN(n, s).

Высшее измерение

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

График

Стартовая доска представляет собой несвязный граф, и игроки по очереди удаляют смежные вершины.

Конфеты

Candy nim — это версия классической игры ним, в которой игроки стремятся одновременно достичь двух целей: забрать последний объект (в данном случае, конфету) и к концу игры собрать максимальное количество конфет.