Настоящая лекция посвящена конечным детерминированным играм и клеточным автоматам.
Дискретная детерминированная игра двух лиц с полной информацией - это игра, в которой существует конечное множество позиций, в ней участвуют два игрока, которые ходят по очереди, и каждый ход игрока приводит к новой позиции, при этом игрок владеет всей информацией о позиции, в которой ему предстоит сделать ход, и обо всех допустимых ходах в этой позиции. Правила игры определяют начальную позицию игры, допустимые ходы игрока в каждой позиции, какая позиция является конечной, а также кто выигрывает, и при каких условиях объявляется ничья. Последовательность ходов и соответствующих им позиций, которая приводит от начальной позиции к конечной позиции, называется партией игры.
Конечные автоматы описывают состояния конечного множества элементов в дискретные моменты времени. Клеточные автоматы определяются пятью составляющими: множеством клеток, правилом определения соседних клеток, множеством состояний, начальным состоянием клеток и правилом перехода из текущего состояния в следующее состояние - из одного момента времени в следующий момент.
Рассматривается игра "Ним". Для поиска выигрышных ходов применяются битовые операции. Доказываются теоремы Бутона и Шпрага-Гранди. Приводятся примеры применения функции Шпрага-Гранди для поиска выигрышных стратегий в играх, представимых в виде суммы более простых игр. Кроме этого, обсуждаются элементарные клеточные автоматы, игра "Жизнь" - двумерный клеточный автомат и ее варианты.
Игра называется справедливой, если игроки в ней равноправны.
Математическая игра - это справедливая дискретная детерминированная игра двух лиц с полной информацией, в которой через конечное число шагов достигается либо выигрышная позиция для одного из игроков, либо ничейная, если она возможна. Игрок называется правильным, если он всегда ходит наилучшим образом. Игра с правильными игроками называется правильной игрой.
Ниже рассматриваются только математические игры.
Позиция для игрока называется выигрышной, если при правильной игре она приводит этого игрока к выигрышу. Позиция называется проигрышной, если при правильной игре она приводит к проигрышу. Ход для игрока называется выигрышным, если он приводит к проигрышной для противника позиции, и проигрышным, если противник получает выигрышную позицию. Таким образом, выигрышной является позиция, в которой игрок может сделать такой ход, что как бы ни играл его противник, его позиции всегда будут выигрышными. Соответственно, проигрышной является такая позиция игрока, что любой его ход приведет к позиции, выигрышной для противника. Стратегией игры является алгоритм выбора правильного хода. Стратегия называется выигрышной, если она приводит игрока к выигрышу.
Рассмотрим игру "Ним" - математическую игру, в которой все позиции делятся на выигрышные и проигрышные, поэтому она всегда заканчивается выигрышем одного игрока и проигрышем другого.
Игра "Ним" заключается в следующем. Имеется n кучек камней (или других однородных предметов). Два игрока ходят по очереди. За один ход разрешается взять любое ненулевое число камней из одной кучки. Выигрывает тот, кто берет последний камень ( рис. 5.1).
(рис 5.1) Кучки камней для игры "Ним"
Позицию в игре "Ним" можно описать в виде набора целых неотрицательных чисел $$(a_1, a_2, \dots, a_n)$$, которые равны числу камней в кучках. Если $$a_1 = a_2 = \dots = a_n = 0$$, то позиция называется нулевой.
Найдем выигрышную стратегию для игры "Ним".
Пусть кучка одна. Тогда первый игрок забирает сразу все камни и выигрывает. Таким образом, в случае одной кучки начальная позиция является выигрышной для первого игрока.
Для упрощения перебора будем описывать позицию $$(a_1, a_2, \dots, a_n)$$ так, чтобы выполнялось соотношение $$a_1 \le a_2 \le \dots \le a_n$$. Кроме того, на множестве позиций игры с n кучками введем отношение линейного порядка, аналогичного лексикографическому порядку для слов $$a_{1a2} \dots a_n$$.
Пусть кучек две. Позиция (0, k) является выигрышной для любого натурального k. Позиция (1, 1) - проигрышная. Любая позиция вида (1, k), где k > 1, является выигрышной, так как за один ход ее можно свести к проигрышной позиции. Наименьшей позицией, которая не сводится к проигрышной позиции (1, 1) за один ход, является позиция (2, 2). Позиция (2, 2) также является проигрышной, так как любой ход из нее приводит к выигрышной позиции. Соответственно, позиции вида (2, k), для k > 2, являются выигрышными. Следующей проигрышной позицией является (3, 3). Рассуждая аналогичным образом, получим, что проигрышная позиция в игре с двумя кучками содержит одинаковое число камней в кучках. Следовательно, выигрышная стратегия в игре с двумя кучками - выравнивать число камней в кучках.
Таким образом, если в начальной позиции обе кучки содержат равное число камней, то она является проигрышной для первого игрока, а если неравное, то выигрышной.
Пусть имеется три кучки. Из предыдущих рассуждений следует, что для m > 0 позиции (0, 0, m) являются выигрышными, а позиции (0, m, m) - проигрышными. Соответственно, позиции вида (k, m, m), для $$0 < k \le m$$, и (m, m, k), для k > m, являются выигрышными.
Наименьшей позицией, которая не сводится за один шаг к найденным проигрышным позициям, является (1, 2, 3). Поэтому данная позиция является проигрышной. Нетрудно видеть, что позиции (1, 4, 5) и (1, 6, 7) также являются проигрышными.
Наименьшей позицией, которая начинается с 2 и не сводится за один шаг к найденным проигрышным позициям, является позиция (2, 4, 6), затем идет (2, 5, 7).
Пример 1. Рассмотрим игру "Ним" с тремя кучками, содержащими 3, 5 и 7 камней ( рис. 5.1).
Все проигрышные позиции для этой игры имеют вид:
(0, k, k), для k от 1 до 5 включительно;
(1, 2, 3), (1, 4, 5), (2, 4, 6), (2, 5, 7), (3, 4, 7), (3, 5, 6).
Поэтому в позиции (3, 5, 7) существует 3 выигрышных хода: если игрок возьмет 1 камень из первой, второй или третьей кучки, то получится позиция (2, 5, 7), (3, 4, 7) или (3, 5, 6), соответственно. Все эти позиции являются проигрышными для второго игрока. Таким образом, позиция (3, 5, 7) является выигрышной для первого игрока. Выигрышная стратегия первого игрока - ходить так, чтобы противник получал проигрышную позицию.
Общее описание проигрышных позиций для игры "Ним" с тремя кучками приводится ниже. Если число кучек больше трех, то с помощью перебора можно найти проигрышные позиции аналогичным образом.
Рассмотрим более простой способ поиска выигрышной стратегии в игре Ним.
Утверждение 1. Побитовая операция $$\oplus$$ обладает следующими свойствами:
для произвольных целых неотрицательных чисел x, y и z.
Доказательство. Очевидно, что свойства выполняются на множестве {0, 1}. Поэтому они выполняются и для каждого двоичного разряда в двоичном представлении чисел x, y и z..
Утверждение 2. Побитовая операция $$\oplus$$ на множестве неотрицательных целых чисел обладает следующими свойствами:
x = y;y = z.Доказательство. 1) Пусть $$x \oplus y = 0$$. Тогда $$x = 0 \oplus x = x \oplus 0 = x \oplus (x \oplus y) = (x \oplus x) \oplus y = 0 \oplus y = y$$.
Если x = y, то $$x \oplus y = x \oplus x = 0$$
2) Пусть $$x \oplus y = x \oplus z$$. Тогда $$y = 0 \oplus y = (x \oplus x) \oplus y = x \oplus (x \oplus y) = x \oplus (x \oplus z) = (x \oplus x) \oplus z = 0 \oplus z = z.$$
Игра "Ним" известна в течение нескольких столетий, но первым ее полное решение опубликовал Чарльз Бутон в 1901 г. В теореме Бутона описываются проигрышные позиции этой игры, а также ее выигрышная стратегия.
Пусть $$X = (x_1, x_2, \dots, x_n)$$ - позиция в игре Ним с n кучками. Ним-суммой позиции X называется число $$x = x_1 \oplus x_2 \oplus \dots\oplus x_n$$.
Теорема (Бутона). Позиция $$(x_1, x_2, \dots, x_n)$$ является проигрышной в игре "Ним" тогда и только тогда, когда ее ним-сумма равна нулю.
Доказательство. Пусть $$(x_1, x_2, \dots, x_n)$$ - ненулевая позиция с нулевой ним-суммой, т. е. $$x_1 \oplus x_2 \oplus \dots\oplus x_n = 0$$. Будем считать, что $$x_1 > 0$$.
Возьмем из кучки $$x_1$$ произвольное ненулевое число камней k, так что $$0 < k \le x_1$$. Заметим, что $$ (x-1 - k) \oplus x_2 \oplus \dots\oplus x_n \ne 0$$. В самом деле, если $$ (x_1 - k) \oplus x_2 \oplus \dots\oplus x_n = 0$$, то из свойства 2 утверждения 2 следует, что $$x_1 = x_1 - k$$, что невозможно, так как k > 0. Аналогично для остальных кучек. Таким образом, произвольный ход из позиции с нулевой ним-суммой приводит к позиции с ненулевой ним-суммой.
Покажем теперь, что из позиции с ненулевой ним-суммой существует хотя бы один ход в позицию с нулевой ним-суммой.
Пусть $$ (x_1, x_2, \dots, x_n) $$ - позиция с ненулевой ним-суммой. Положим $$x = x_1 \oplus x_2 \oplus \dots\oplus x_n$$. Пусть двоичное представление числа x содержит i разрядов. Возьмем кучку j, такую, что в двоичном представлении числа $$x_j$$ в i-м разряде стоит 1.
Покажем, что $$x \oplus x_j < x_j$$. В самом деле, в i-м разряде двоичного представления числа $$x \oplus x_j$$ стоит 0, а значения, стоящие в старших разрядах, совпадают со значениями числа $$x_j$$, стоящими в тех же разрядах.
Далее, заменим в выражении $$x_1 \oplus x_2 \oplus \dots\oplus x_n$$ элемент $$x_j$$ на элемент $$x \oplus x_j$$. В результате получим:
$$ x_1 \oplus x_2 \oplus \dots\oplus (x \oplus x_j) \oplus \dots\oplus x_n=\\ = (x_1 \oplus x_2 \oplus \dots\oplus x_j \oplus \dots\oplus x_n) \oplus x = x \oplus x = 0. $$Таким образом, если из кучки j забрать $$x_j - (x \oplus x_j) $$ камней, то получится позиция с нулевой ним-суммой.
Следовательно, позиции с нулевой ним-суммой являются проигрышными, а остальные позиции - выигрышными. Выигрышная стратегия - ходить так, чтобы привести противника в позицию с нулевой ним-суммой, что всегда возможно сделать из позиции с ненулевой ним-суммой.
Пример 2. Для игры "Ним" с тремя кучками, содержащими 3, 5 и 7 камней, имеем: $$3 = 11_2, 5 = 101_2, 7 = 111_2$$.
Найдем ним-сумму начальной позиции.
В нулевом разряде каждого числа стоит 1. Поэтому следует либо оставить $$3 \oplus 1$$, или 2 камня в первой кучке, либо $$5 \oplus 1$$, или 4 камня во второй, либо $$7 \oplus 1$$, или 6 камней в третьей кучке.
Пример 3. Рассмотрим игру "Ним" с 4 кучками, которые содержат 17, 24, 7 и 11 камней. Имеем: $$17 = 10001_2, 24 = 11000_2, 7 = 111_2, 11 = 1011_2$$.
Найдем ним-сумму x начальной позиции:
Таким образом, $$x = 17 \oplus 24 \oplus 7 \oplus 11 = 5$$. Старший ненулевой разряд ним-суммы отличен от 0 только у числа 7. По теореме Бутона, в третьей кучке должно остаться $$5 \oplus 7$$, или 2 камня. Соответственно, взять из нее следует 5 камней. В результате противнику достанется проигрышная позиция с 4 кучками, содержащими 17, 24, 2 и 11 камней.
Рассмотрим функцию Шпрага-Гранди. Областью определения этой функции является множество позиций игры, а областью значений - множество неотрицательных целых чисел.
Функция Шпрага-Гранди определяется индуктивно. Если из позиции нельзя сделать ход, то значение функции в ней полагается равным 0. В противном случае значение функции в позиции S полагается равным наименьшему неотрицательному числу, которое отсутствует среди значений функции в позициях, в которые можно за один ход попасть из S.
Утверждение 3. Позиция является проигрышной тогда и только тогда, когда значение функции Шпрага-Гранди в этой позиции равно 0.
Доказательство. Пусть значение функции Шпрага-Гранди в позиции S равно 0. Тогда либо из позиции S нельзя сделать ход, либо все ходы из нее приводят к таким позициям, для которых значение функции Шпрага-Гранди положительно. Обратно, пусть значение функции Шпрага-Гранди в позиции S положительно. Тогда среди позиций, в которые можно из нее перейти, существует позиция, значение функции Шпрага-Гранди которой равно нулю.
Рассмотрим игру "Ним" с одной кучкой. Пусть P - множество позиций игры и $$\mathbb {Z}_0$$ - множество неотрицательных целых чисел. Обозначим через $$g: P \to \mathbb {Z}_0$$ функцию Шпрага-Гранди.
Утверждение 4. Функция Шпрага-Гранди на множестве позиций игры "Ним" с одной кучкой имеет вид: g(m) = m.
Доказательство. В позиции (m) существует m ходов: из кучки можно взять от 1 до m камней. Используем индукцию по m.
При m = 0 утверждение верно. Предположим, что утверждение верно для всех кучек, содержащих не более k камней. Пусть кучка содержит k + 1 камень. Из этой кучки можно взять от 1 до k + 1 камней и перейти при этом в позиции $$ (k), (k - 1), \dots, (1), (0) $$. По предположению индукции, значение функции Шпрага-Гранди в этих позициях соответственно равно $$k, k - 1, \dots, 1, 0$$. Наименьшее целое неотрицательное число, которое не входит во множество полученных значений, равно k + 1. Следовательно, g(k + 1) = k + 1.
Для доказательства теоремы Шпрага-Гранди понадобится еще одно свойство операции $$\oplus$$.
Утверждение 5. Если $$k < x \oplus y$$, то $$k = x' \oplus y$$ для некоторого x', такого что x' < x, или $$k = x \oplus y' $$ для некоторого $$y' $$, такого что $$y' < y$$.
Доказательство. Пусть i - самый старший разряд двоичного представления, в котором число $$x \oplus y$$ отличается от k. В этом разряде у числа k стоит 0, а у числа $$x \oplus y - 1$$. Поэтому в i-ом разряде одного из чисел x и y стоит 1, а другого - 0. Пусть в i-ом разряде числа x стоит 0
Покажем, что $$x \oplus k < y$$. Действительно, пусть разряд j старше разряда i. Тогда значения j-го разряда чисел $$x \oplus y$$ и k совпадают. Поэтому в j-ом разряде числа $$x \oplus k$$ стоит то же значение, что и в j-ом разряде числа $$x \oplus (x \oplus y) $$, равного y. Следовательно, i - это самый старший разряд двоичного представления числа $$x \oplus k$$, в котором оно отличается от y. Но в i-м разряде числа $$x \oplus k$$ стоит 0, а в том же разряде числа y стоит 1. Таким образом, $$x \oplus k < y$$. Положим $$y' = x \oplus k$$. Имеем:
Пусть P - множество позиций игры G, а F - бинарное отношение на P, такое что F = {(p, q) | существует ход, который переводит p в q}.
Пусть $$G_1$$ и $$G_2$$ - игры, $$P_1$$ и $$P_2$$ - множества позиций игр $$G_1$$ и $$G_2$$, а $$F_1$$ и $$F_2$$ - определенные выше бинарные отношения на множествах $$P_1$$ и $$P_2$$, соответственно
Суммой игр $$G_1$$ и $$G_2$$ называется игра G с множеством позиций P, таким что $$P = P_1 * P_2$$, а отношение F на множестве P имеет вид:
Пример 4. Игра "Ним" с двумя кучками является суммой двух игр "Ним" с одной кучкой.
Обозначим через $$ g_1: P_1 \to \mathbb {Z}_0, g_2: P_2 \to \mathbb {Z}_0 $$ и $$ g: P \to \mathbb {Z}_0 $$ функции Шпрага-Гранди игр $$ G_1, G_2 $$ и $$ G $$, соответственно.
Теорема (Шпрага-Гранди). Для любой позиции $$ (p_1, p_2) $$ игры $$ G $$ является верным следующее равенство:
$$ g(p_1, p_2) = g_1(p_1) \oplus g_2(p_2). $$Доказательство. Используем индукцию по максимальному числу оставшихся ходов.
Из позиции $$ (p_1, p_2) $$ игры G нельзя сделать ход тогда и только тогда, когда его нельзя сделать ни из позиции $$ p_1 $$ в игре $$ G_1 $$, ни из позиции $$ p_2 $$ в игре $$ G_2 $$. Поэтому $$ g(p_1, p_2) = 0 $$, тогда и только тогда, когда $$ g_1(p_1) = 0 $$ и $$ g_2(p_2) = 0 $$, а, следовательно, $$ g_1(p_1) \oplus g_2(p_2) = 0 $$.
Пусть $$ (q_1, q_2) $$ - позиция, в которую существует ход из позиции $$ (p_1, p_2) $$. Тогда, по определению, либо $$ q_1 = p_1, q_2 \ne p_2 $$, либо $$ q_2 = p_2, q_1 \ne p_1 $$.
Покажем, что $$ g_1(p_1) \oplus g_2(p_2) \ne g(q_1, q_2) $$. От противного. Предположим, что $$g_1(p_1) \oplus g_2(p_2) = g(q_1, q_2) $$. Пусть $$ (q_1, q_2) = (p_1, q_2) $$. Тогда, по предположению индукции, $$g(q_1, q_2) = g_1(p_1) \oplus g_2(q_2) $$. Следовательно, выполняется условие $$g_1(p_1) \oplus g_2(p_2) = g_1(p_1) \oplus g_2(q_2) $$, из которого по свойству 2 утверждения 2 следует, что $$g_2(p_2) = g_2(q_2) $$. Но в позицию $$q_2$$ существует ход из позиции $$p_2$$ в игре $$G_2$$, поэтому данное равенство невозможно по определению функции Шпрага-Гранди. Случай $$ (q_1, q_2) = (q_1, p_2) $$ рассматривается аналогично.
Итак, число $$g_1(p_1) \oplus g_2(p_2) $$ не совпадает ни с одним из значений функции Шпрага-Гранди в позициях, которые получаются с помощью некоторого хода из позиции $$ (p_1, p_2) $$.
Покажем, что число $$g_1(p_1) \oplus g_2(p_2) $$ является наименьшим целым неотрицательным числом, которое не принадлежит множеству $$Q = {g(q_1, q_2) | ((p_1, p_2), (q_1, q_2)) \in F}$$.
Пусть $$k < g_1(p_1) \oplus g_2(p_2) $$, где $$k \in \mathbb {Z}_0$$. Из утверждения 5 следует, что либо $$k = k_1 \oplus g_2(p_2) $$ для некоторого числа $$k_1$$ из $$\mathbb {Z}_0$$, такого что $$k_1 < g_1(p_1) $$, либо $$k = g_1(p_1) \oplus k_2$$ для некоторого $$k_2$$ из $$\mathbb {Z}_0$$, такого что $$k_2 < g_2(p_2) $$.
Пусть $$k = k_1 \oplus g_2(p_2) $$. Поскольку $$k_1 < g_1(p_1) $$, то, по определению функции Шпрага-Гранди, в игре $$G_1$$ найдется позиция $$q_1$$, в которую существует ход из позиции $$p_1$$, такая, что $$k_1 = g_1(q_1) $$. Следовательно, выполняется соотношение $$k = k_1 \oplus g_2(p_2) = g_1(q_1) \oplus g_2(p_2) = g(q_1, p_2) $$.
Последнее равенство верно по предположению индукции.
Заметим, что $$ (q_1, p_2) $$ - это позиция, в которую существует ход из позиции $$ (p_1, p_2) $$. Таким образом, среди значений функции Шпрага-Гранди в позициях, в которые существует ход из позиции $$ (p_1, p_2) $$, найдется любое неотрицательное целое число, меньшее, чем $$g_1(p_1) \oplus g_2(p_2) $$. Поэтому
$$g(p_1, p_2) = g_1(p_1) \oplus g_2(p_2).$$Следствие. Функция Шпрага-Гранди игры "Ним" с n кучками имеет вид:
В самом деле, игра "Ним" с n кучками является суммой n игр с одной кучкой. Пусть $$g_i: P_i \to \mathbb {Z}_0$$ - функция Шпрага-Гранди i-ой игры, определенная на множестве ее позиций $$P_i$$, для $$i = 1, 2, \dots, n$$. Из утверждения 3 следует, что $$g_i(x_i) = x_i$$. По методу математической индукции получаем указанную выше формулу.
Таким образом, теорема Бутона является следствием теоремы Шпрага-Гранди.
Пример 5. Рассмотрим следующую игру. В кучке имеется 9 камней. Два игрока ходят по очереди. За один ход игрок может взять от 1 до 3 камней. Выигрывает тот, кто берет последний камень. Построим функцию Шпрага-Гранди.
Пусть позицией является число камней в кучке. Тогда множество позиций игры описывается целыми числами от 0 до 9. Последовательно находим:
g(0) = 0; g(1) = 1; g(2) = 2; g(3) = 3; g(4) = 0; g(5) = 1; g(6) = 2; g(7) = 3; g(8) = 0; g(9) = 1.
Покажем, что в общем случае, g(m) = m mod 4, для $$m = 0, 1, 2, \dots$$ В самом деле, значение функции Шпрага-Гранди в позиции m определяется значениями этой функции в позициях m - 1, m - 2 и m - 3, для $$m \ge 3$$. Применим индукцию по m. При $$m \le 3$$ утверждение верно. Предположим, что оно верно при m = k, где $$k \ge 3$$. Пусть m = k + 1. По предположению индукции, в позициях k, k - 1 и k - 2 значение функции Шпрага-Гранди равно трем последовательным остаткам от деления на 4. Поэтому значение функции Шпрага-Гранди в позиции k + 1 равно недостающему остатку от деления на 4, так что g(m) = m mod 4 при $$m \ge 0$$.
Таким образом, проигрышными являются позиции, кратные 4. В частности, позиция 9 является выигрышной. Выигрышная стратегия игры - оставлять другому игроку число камней, кратное 4.
Пример 6. Рассмотрим игру, которая является обобщением игры из примера 5. Она заключается в следующем. Имеется n кучек. Два игрока ходят по очереди. За один ход игрок может взять от 1 до 3 камней из любой кучки. Выигрывает тот, кто берет последний камень.
Пусть кучка i содержит xi камней, для $$i = 1, 2, \dots, n$$. По теореме, функция Шпрага-Гранди для этой игры имеет вид:
Поэтому позиция является проигрышной тогда и только тогда, когда побитовая строгая дизъюнкция остатков от деления на 4 чисел $$x_i$$ равна 0, для $$i = 1, 2, \dots, n$$.
Найдем выигрышную стратегию игры. Заметим, что свойство позиции быть выигрышной или проигрышной зависит только от двух младших разрядов двоичного представления чисел $$x_i$$, для $$i = 1, 2, \dots, n$$.
Положим $$x = x_1 \mod 4 \oplus x_2 \mod 4 \oplus \dots\oplus x_n \mod 4$$.
Очевидно, что $$x \le 3$$. Пусть $$x \ne 0$$ и i - старший разряд двоичного представления числа x, значение которого равно 1. Тогда существует число $$x_j$$, в i-ом разряде двоичного представления которого стоит 1, так как i-ым является один из двух младших разрядов.
Заметим, что значения двоичных разрядов, старших i, чисел $$x_j$$ и $$x \oplus x_j$$ совпадают, при этом в разряде i числа $$x_j$$ стоит 1, а в том же разряде числа $$x \oplus x_j$$ стоит 0. Отсюда следует, что, во-первых, $$x \oplus x_j < x_j$$ и что, во-вторых, $$x_j - x \oplus x_j \le 3$$.
Заметим также, что $$ (x \oplus x_j) \mod 4 = x \oplus (x_j \mod 4) $$, так как $$x \le 3$$. Следовательно,
$$x_1 \mod 4 \oplus \dots \oplus (x \oplus x_j) \mod 4 \oplus \dots \oplus x_n \mod 4 = \\ = x \oplus (x_1 \mod 4 \oplus \dots \oplus x_j \mod 4 \oplus \dots \oplus x_n \mod 4) = x \oplus x = 0. $$Таким образом, выигрышный ход - взять ($$x_j - x \oplus x_j$$) камней из кучки, в которой находится $$x_j$$ камней.
Например, пусть кучки содержат 9, 6, 5 и 4 камня. Тогда 9 mod 4 \oplus 6 mod 4 \oplus 5 mod 4 \oplus 4 mod 4 = 1 \oplus 2 \oplus 1 \oplus 0 = 2.
Следовательно, позиция является выигрышной. Номер старшего ненулевого двоичного разряда числа 2 равен 1. Этот же разряд является ненулевым у числа 6. Имеем: $$6 - 2 \oplus 6 = 6 - 4 = 2$$. Поэтому выигрышный ход состоит в том, чтобы взять 2 камня из кучки, содержащей 6 камней.
Проигрышные позиции в игре "Ним" с тремя кучками обладают интересными свойствами.
Рассмотрим метод поиска проигрышных позиций для игры "Ним" с тремя кучками, который является сочетанием методов из п. 5.1.2 и 5.1.4.
Проигрышные позиции с ненулевыми упорядоченными значениями компонент можно построить с помощью таблицы сложения для операции $$\oplus$$ (см. ниже), так как число камней в третьей кучке равно результату применения операции \oplus к числу камней в первой и второй кучках. Эти позиции имеют вид:
(1, 2k, 2k + 1); (2, 4k, 4k + 2); (3, 4k, 4k + 3); (2, 4k + 1, 4k + 3); (3, 4k + 1, 4k + 2); (4, 8k, 8k + 4); (5, 8k, 8k + 5); (4, 8k + 1, 8k + 5); (5, 8k + 1, 8k + 4); (4, 8k + 2, 8k + 6); (5, 8k + 2, 8k + 7); (4, 8k + 3, 8k + 7); (5, 8k + 3, 8k + 6); (6, 8k, 8k + 6); (7, 8k, 8k + 7); (6, 8k + 1, 8k + 7); (7, 8k + 1, 8k + 6); (6, 8k + 2, 8k + 4); (7, 8k + 2, 8k + 5); (6, 8k + 3, 8k + 5); (7, 8k + 3, 8k + 4); …
для $$k = 1, 2, \dots$$ При фиксированном значении k проигрышные позиции находятся с помощью двоичного представления чисел, равных количеству камней в первых двух кучках. Например, при k = 1 для числа камней в первых двух кучках имеем:
1 1 1 1 10 10 10 10 ...
Вместо знака следует подставлять значения 0 и 1. Соответственно, при k = 1 имеется одна позиция, первая компонента в которой равна 1, четыре позиции, первая компонента которых равна 2 или 3, и 16 позиций, первая компонента которых равна 4, 5, 6 или 7, и так далее.
Соответственно, при k = 2 двоичное представление числа камней в первых двух (наименьших) кучках имеет вид:
1 1 1 1 100 100 100 100 ...
В общем случае, для целого неотрицательного s положим $$q = 2^s/$$ и $$p = 2^{s + 1}$$. Тогда проигрышными являются позиции, первая компонента которых равна $$q, q + 1, \dots, 2q - 1$$, вторая компонента принимает значения $$pk, pk + 1, \dots, pk + q - 1$$, для $$k = 1, 2, \dots$$, а третья компонента равна результату применения операции bitXor к первым двум компонентам.
Таким образом, пусть m - минимальное число камней в трех кучках, p - наименьшая степень 2, такая что m < p, и $$q=\fracp2$$. Тогда проигрышные позиции, содержащие m, находятся следующим образом:
Пример 7. Пусть m = 10, тогда p = 16 и q = 8. Проигрышные позиции с минимальным числом камней в трех кучках, равным 10, имеют вид:
(10, 16k, 16k + 10), (10, 16k + 4, 16k + 14), (10, 16k + 1, 16k + 11), (10, 16k + 5, 16k + 15), (10, 16k + 2, 16k + 8), (10, 16k + 6, 16k + 12), (10, 16k + 3, 16k + 9), (10, 16k + 7, 16k + 13),
для $$k = 1, 2, \dots$$, или
$$ (10, 16, 26), (10, 17, 27), (10, 18, 24), (10, 19, 25), (10, 20, 30), (10, 21, 31), (10, 22, 28), (10, 23, 29), (10, 32, 42), (10, 33, 43), \dots$$Рассмотрим таблицу сложения для операции $$\oplus$$, которая используется для построения проигрышных позиций в игре с тремя кучками: найдем значения $$x \oplus y$$, для $$x = q, q + 1, \dots, 2q - 1$$ и $$y = 0, 1, \dots, q - 1$$, где $$q = 2^s$$, для целого положительного числа s. Таблицы сложения для значений q, равных 2, 4 и 8 приведены в рис. 5.2.
(рис 5.2) Таблица сложения для операции разделительной дизъюнкции
Из свойств побитовой операции строгой дизъюнкции следует, что таблицы сложения в данном случае можно строить по определенному правилу, без вычисления двоичных представлений чисел x и y. Достаточно использовать схему, приведенную на рис. 5.3.
(рис 5.3) Схема для заполнения рис. 5.2
Схема применяется следующим образом. Заполнение таблиц начинается из углов, обозначенных жирными черными точками. В них помещается значение q. В направлениях, указанных стрелками, значения элементов таблицы увеличиваются на 1 в каждом столбце или строке. После заполнения крайних рядов, таблица делится на 4 равные по размеру квадратные подтаблицы, а затем та же схема применяется для заполнения пустых ячеек каждой из полученных таблиц (см. рис. 5.2). Заметим также, что, как элементы главной диагонали, так и элементы побочной диагонали каждой таблицы равны между собой. Например, для q = 4 получится результат, приведенный в рис. 5.4.
(рис 5.4) Построение таблицы сложения операции разделительной дизъюнкции при q = 4
Нетрудно заметить, что таблицы могут быть построены итеративно: текущая таблица получается из предыдущей заменой каждой ее ячейки таблицей 2 * 2 по правилу
при этом нулевой является таблица (1). Если одинаковые числа заменить квадратами одинакового цвета, то при q = 64 получится один из вариантов раскраски квадрата, приведенный на рис. 5.5.
(рис 5.5) "Цветовое" представление таблицы сложения операции разделительной дизъюнкции при q = 64
Рассмотрим примеры клеточных автоматов, которые имеют широкое применение в различных областях исследований.
Клеточный автомат - это пятерка $$\langle C, Q, N, q_0, f \rangle$$, где
C - множество клеток;Q - множество состояний клетки;Окрестность клетки образуют соседние с ней клетки (или ее соседи), а также сама клетка. Начальным является состояние множества клеток в момент времени 0. Правило перехода определяет, каким будет состояние клетки в момент времени i + 1, в зависимости от того, каким было ее состояние, а также состояние ее соседей в момент времени i.
Ниже рассматриваются примеры клеточных автоматов, в которых клетки могут принимать одно из двух состояний: 0 или 1.
Элементарный клеточный автомат - это одномерный автомат в виде бесконечной ленты, в котором соседними для клетки являются клетки, содержащие с ней общую сторону. Таким образом, каждая клетка имеет два соседа. Правило изменения состояния клетки определяется логической функцией с тремя аргументами, которыми являются состояния клеток ее окрестности. Всего существует 256 элементарных клеточных автоматов, по числу логических функций с 3 аргументами.
Пусть $$x_i$$ - клетка, а $$x_{i - 1}$$ и $$x_{i + 1}$$ - ее соседи слева и справа, соответственно. Пусть также N - целое число, такое что $$0 \le N \le 255$$, и двоичное представление числа N длины 8 имеет вид: $$b_0b_1b_2b_3b_4b_5b_6b_7$$. Правило Вольфрама, или правило N, описывает переходы между состояниями в элементарном клеточном автомате, в соответствии с таблицей истинности логической функции, которая представлена в табл. 5.1.
Если клетка $$x_i$$ в момент времени k находится в состоянии $$y-q^{(k)}_{0}$$, а ее соседи в состояниях$$x=q^{(k}}_{-1}$$ и $$z=q^{(k)}_{1}$$, соответственно, то состояние клетки xi в момент k + 1 имеет вид: $$q^{(k+1)}_{0}=f(x,y,z)$$.
| x | y | z | f |
|---|---|---|---|
| 0 | 0 | 0 | $$b_7$$ |
| 0 | 0 | 1 | $$b_6$$ |
| 0 | 1 | 0 | $$b_5$$ |
| 0 | 1 | 1 | $$b_4$$ |
| 1 | 0 | 0 | $$b_3$$ |
| 1 | 0 | 1 | $$b_2$$ |
| 1 | 1 | 0 | $$b_1$$ |
| 1 | 1 | 1 | $$b_0$$ |
Пример 8. Рассмотрим правило 110. Имеем:
$$110 = 01101110_2. $$Преобразование состояния клетки по правилу 110 имеет вид:
000 001 010 011 100 101 110 111 0 1 1 1 0 1 1 0
(ср. с таблицей истинности).
Множество состояний элементарного клеточного автомата представляется в виде конечного клеточного поля, строки которого соответствуют моментам времени. Обычно правая сторона поля отождествляется с левой, так что правым соседом крайней правой клетки является крайняя левая клетка, а левым соседом крайней левой клетки - крайняя правая клетка. Например, пусть поле имеет 9 клеток, начальное состояние центральной клетки равно 1, а остальных клеток - 0. Тогда по правилу 110 состояния клеточного поля в моменты времени 1 - 4 имеют вид:
Состояние множества клеток одномерного поля в момент времени k отображается в виде k-го ряда двумерного поля. Белый цвет клетки обозначает состояние 0, а черный - состояние 1. Например, если в начальный момент времени состояние 1 имеет только крайняя правая клетка, то последующие 29 состояний одномерного поля для правила 110 выглядят так, как показано на рис. 5.6 (a), где начальное состояние соответствует нижнему ряду поля.
Пример 9. Для числа 18 имеем: 18 = 000100102.
Поэтому правило 18 можно представить следующим образом:
На рис. 5.6 (b) правило 18 применяется к одномерному множеству клеток, образующему нижний ряд поля, в начальном состоянии которого 10 клеток, выбранных случайным образом, имеют состояние 1, а остальные клетки - состояние 0. Как и ранее, левая и правая границы поля отождествляются.
(рис 5.6) Клеточные автоматы для правила (a) 110; (b) 18; начальное состояние соответствует нижнему ряду поля
Игру "Жизнь" придумал в 1970 г. американский математик Джон Конвей. Она является клеточным автоматом, множество клеток которого представляет собой бесконечное двумерное клеточное поле. Соседними считаются клетки, имеющие хотя бы одну общую вершину, поэтому каждая клетка имеет 8 соседей. Клетки могут находиться в одном двух состояний - 0 или 1. В первом случае клетка называется пустой, или мертвой, а в втором - живой.
Правила Конвея размножения и гибели клеток имеют вид:
Игра прекращается, если на поле не остается ни одной живой клетки или конфигурация живых клеток станет неизменяемой, или устойчивой.
Пример 10. На рис. 5.7 приведен фрагмент игры для четырех фигур в момент времени k, для k от 0 до 4. Крайняя левая фигура ("диагональ") погибает на втором шаге. Вторая фигура, справа от нее, называется "мигалка" - это периодически повторяющаяся конфигурация с периодом 2. Третья фигура на втором шаге переходит в устойчивое состояние ("улей"). Четвертая фигура ("планер") за каждые четыре шага смещается по диагонали на одну клетку в направлении вправо-вниз.
(рис 5.7) Состояния конфигурации живых клеток в моменты времени от 0 до 4
Пример 11. Рассмотрим конфигурации живых клеток, которые называются "космическими кораблями". Каждая такая конфигурация перемещается - начальное взаимное расположение живых клеток периодически повторяется, при этом фигура смещается на 2 клетки по направлению движения: передней частью "корабля" является отрезок, содержащий в начальном состоянии 3 клетки. "Легкий", "средний" и "тяжелый космические корабли" показаны на рис. 5.8 (a-c).
(рис 5.8) Космический корабль: (a) легкий; (b) средний; (c) тяжелый
На рис. 5.10 (a-e) показано перемещение "легкого корабля".
(рис 5.10) Легкий космический корабль в моменты времени k от 0 до 4
Пример 12. Примером повторяющей без смещения конфигурации живых клеток с периодом 3 является кембриджский пульсар ( рис. 5.11).
(рис 5.11) Кембриджский пульсар в момент времени (a) 0; (b) 1; (с) 2
На рис. 5.12 (a-c) приведены примеры конфигураций живых клеток, каждая из которых за конечное время преобразуется в кембриджский пульсар.
(рис 5.12) Конфигурации, сходящиеся к кембриджскому пульсару
Периодически повторяющиеся фигуры называют осцилляторами.
Начальные конфигурации живых клеток, которые стабилизируются через большое число поколений, называются фигурами Мафусаила, по имени библейского персонажа, который дольше всех из допотопных жителей. Примеры таких конфигураций приведены на рис. 5.12 (a-c).
(рис 5.12) Фигуры Мафусаила: (a) "пентамино"; (b) "желудь"; (c) "кролики"
Фигуры "пентамино", "желудь" и "кролики" стабилизируются соответственно через 1103, 5206 и 17332 поколений.
Появление игры "Жизнь" привело к созданию клеточных автоматов со схожей структурой. Их называют жизнеподобными (Life-like) клеточными автоматами. Правила "зарождения" и "сохранения" жизни обозначаются в виде $$Bn_1\dotsn_p/Sm_1\dotsm_q$$, где $$n_i$$ - число живых соседей, при которых пустая клетка становится живой, а $$m_j$$ - число живых соседей, при которых живая клетка остается живой, где $$i = 1, \dots, p; j = 1, \dots, q$$. Для оригинальной игры "Жизнь" правило имеет вид: B3/S23.
Примерами известных жизнеподобных автоматов являются:
На рис. 5.13 (a-c) показаны некоторые состояния клеточного автомата "Репликатор", в котором каждая конфигурация является репликатором - бесконечно копирует себя.
(рис 5.13) "Репликатор" в момент времени (a) 0; (b) 4; (c) 5
Клеточный автомат "Лабиринт" создает изображения, похожие на лабиринт, из любого начального состояния ( рис. 5.14 (a-b) ).
(рис 5.14) "Лабиринт" в момент времени (a) 0; (b) 30
Клеточный автомат "Фредкин" порождает расширяющиеся конфигурации ( рис. 5.15 (a-c)).
(рис 5.15) "Фредкин" в момент времени (a) 0; (b) 5; (c) 7
У клеточного автомата "День и ночь" на бесконечном поле существуют периодические конфигурации живых клеток, которые при замене мертвых клеток живыми, а живых - мертвыми преобразуются в конфигурации, которые так же являются пери
(рис 5.16) "День и ночь": периодические конфигурации (a) живых клеток; (b) пустых клеток на поле из живых клеток
Для создания жизнеподобных клеточных автоматов, помимо прямоугольного поля, используется гексагональное поле, в котором клетки являются правильными шестиугольниками. На бесконечном поле каждая клетка обладает шестью соседями.
На рис. 5.17 (a-g) показаны примеры осцилляторов для жизнеподобного клеточного автомата, правило "зарождения" и "сохранения" жизни которого имеет вид: B2/S34.
Упражнение. Найдите период каждого осциллятора, приведенного на рис. 5.17.
(рис 5.17) Осцилляторы в игре с правилом B2/S34
На гексагональном поле существуют также стохастические клеточные автоматы, в которых пустая клетка становится живой с некоторой вероятностью, при заданном количестве соседей.
Например, пустая клетка становится живой с вероятностью $$\frac13$$, если она имеет ровно 2 живых соседа; живая клетка остается живой, если у нее имеется 1 или 2 живых соседа. Другим примером является клеточный автомат, в котором пустая клетка оживает с вероятностью 1, если имеет 3 живых соседа, и с вероятностью $$\frac16$$, если она имеет 2 живых соседа; живая клетка сохраняет жизнь, если она имеет 2 или 3 живых соседа.
Упражнения
x - неотрицательное целое число. Покажите, что если x четное, то $$x \oplus 1 = x + 1$$, а если нечетное, то $$x \oplus 1 = x - 1$$.Найдите выигрышный ход в игре "Ним", если он существует, в позиции
a) (19, 15, 4);
b) (8, 4, 12, 22);
c) (14, 25, 17, 3, 10).
Перечислите все проигрышные позиции в игре "Ним" с тремя кучками, если число камней в каждой кучке не превосходит
a) 10;
b) 15;
c) 20.
Постройте функцию Шпрага-Гранди и придумайте выигрышную стратегию для игры в камни с одной кучкой. В игре участвуют два игрока, игроки ходят по очереди. Выигрывает игрок, который берет последний камень. Кучка содержит m камней. За один ход игрок может взять от 1 до k камней, если k равно
4;
b) 7.
n кучками. В игре участвуют два игрока, игроки ходят по очереди. За один ход игрок может взять от 1 до 7 камней из любой кучки. Выигрывает игрок, который берет последний камень. Постройте функцию Шпрага-Гранди для этой игры.Рассмотрим игру в N. В игре участвуют два игрока, Игроки ходят по очереди. Имеется пять костяшек домино с очками от 1 до 5. Первый игрок кладет монету на любую костяшку и получает число очков, обозначенное на этой костяшке. Второй игрок перекладывает монету на любую другую костяшку и получает число очков, равное сумме очков другого игрока и очков, обозначенных на этой костяшке. Оставлять монету на той же костяшке нельзя, и так далее. Выигрывает игрок, который набирает ровно N очков или принуждает противника превзойти эту сумму. Придумайте выигрышную стратегию для игры в N, если она существует, для значения N, равного
a) 2;
b) 6;
с) 7;
d) 13;
e) 21;
f) 37.
Опишите с помощью клеток правила перехода для элементарного клеточного автомата, соответствующего правилу
a) 24;
b) 135;
с) 215.
Постройте логическую функцию, которая соответствует переходам в элементарном клеточном автомате для правила
a) 110;
b) 30;
с) 150.
Найдите состояния 1 - 10 элементарного клеточного автомата с начальным состоянием
,
если для переходов используется правило
a) 110;
b) 18;
c) 218;
d) 150;
e) 53;
f) 30.
Найдите состояния 1 - 10 элементарного клеточного автомата с начальным состоянием
1) 
;
2) 
,
в котором правило перехода определяется логической функцией
a) $$f(x, y, z) = x \oplus y \oplus z$$;
b) $$f(x, y, z) = x y \vee \neg z$$.
Найдите состояния 1 - 10 элементарного клеточного автомата с начальным состоянием
1) 
;
2) 
,
в котором правило определяется алгебраической функцией
a) f(x, y, z) = (x + y + z) mod 2,;
b) f(x, y, z) = (x y + x z) mod 2.
Определите, через сколько шагов становится устойчивой или периодической конфигурация живых клеток в игре "Жизнь", приведенная на рис. 5.18:
(рис 5.18) Начальные конфигурации живых клеток
Определите период приведенной на рис. 5.19 конфигурации живых клеток в игре "Жизнь":
a) "маяк";
b) "лягушка";
c) "пентадекатлон"
(рис 5.19) Начальные конфигурации живых клеток
Определите для жизнеподобной игры с правилом B3/S3, период осциллятора, приведенного на рис. 5.20:
(рис 5.20) Начальные конфигурации живых клеток
Определите для жизнеподобной игры с правилом B3/S13, период осциллятора, приведенного на рис. 5.18:
(рис 5.21) Начальные конфигурации живых клеток
Настоящая лекция посвящена конечным детерминированным играм и клеточным автоматам.
Дискретная детерминированная игра двух лиц с полной информацией - это игра, в которой существует конечное множество позиций, в ней участвуют два игрока, которые ходят по очереди, и каждый ход игрока приводит к новой позиции, при этом игрок владеет всей информацией о позиции, в которой ему предстоит сделать ход, и обо всех допустимых ходах в этой позиции. Правила игры определяют начальную позицию игры, допустимые ходы игрока в каждой позиции, какая позиция является конечной, а также кто выигрывает, и при каких условиях объявляется ничья. Последовательность ходов и соответствующих им позиций, которая приводит от начальной позиции к конечной позиции, называется партией игры.
Конечные автоматы описывают состояния конечного множества элементов в дискретные моменты времени. Клеточные автоматы определяются пятью составляющими: множеством клеток, правилом определения соседних клеток, множеством состояний, начальным состоянием клеток и правилом перехода из текущего состояния в следующее состояние - из одного момента времени в следующий момент.
Рассматривается игра "Ним". Для поиска выигрышных ходов применяются битовые операции. Доказываются теоремы Бутона и Шпрага-Гранди. Приводятся примеры применения функции Шпрага-Гранди для поиска выигрышных стратегий в играх, представимых в виде суммы более простых игр. Кроме этого, обсуждаются элементарные клеточные автоматы, игра "Жизнь" - двумерный клеточный автомат и ее варианты.
Игра называется справедливой, если игроки в ней равноправны.
Математическая игра - это справедливая дискретная детерминированная игра двух лиц с полной информацией, в которой через конечное число шагов достигается либо выигрышная позиция для одного из игроков, либо ничейная, если она возможна. Игрок называется правильным, если он всегда ходит наилучшим образом. Игра с правильными игроками называется правильной игрой.
Ниже рассматриваются только математические игры.
Позиция для игрока называется выигрышной, если при правильной игре она приводит этого игрока к выигрышу. Позиция называется проигрышной, если при правильной игре она приводит к проигрышу. Ход для игрока называется выигрышным, если он приводит к проигрышной для противника позиции, и проигрышным, если противник получает выигрышную позицию. Таким образом, выигрышной является позиция, в которой игрок может сделать такой ход, что как бы ни играл его противник, его позиции всегда будут выигрышными. Соответственно, проигрышной является такая позиция игрока, что любой его ход приведет к позиции, выигрышной для противника. Стратегией игры является алгоритм выбора правильного хода. Стратегия называется выигрышной, если она приводит игрока к выигрышу.
Рассмотрим игру "Ним" - математическую игру, в которой все позиции делятся на выигрышные и проигрышные, поэтому она всегда заканчивается выигрышем одного игрока и проигрышем другого.
Игра "Ним" заключается в следующем. Имеется n кучек камней (или других однородных предметов). Два игрока ходят по очереди. За один ход разрешается взять любое ненулевое число камней из одной кучки. Выигрывает тот, кто берет последний камень ( рис. 5.1).
(рис 5.1) Кучки камней для игры "Ним"
Позицию в игре "Ним" можно описать в виде набора целых неотрицательных чисел $$(a_1, a_2, \dots, a_n)$$, которые равны числу камней в кучках. Если $$a_1 = a_2 = \dots = a_n = 0$$, то позиция называется нулевой.
Найдем выигрышную стратегию для игры "Ним".
Пусть кучка одна. Тогда первый игрок забирает сразу все камни и выигрывает. Таким образом, в случае одной кучки начальная позиция является выигрышной для первого игрока.
Для упрощения перебора будем описывать позицию $$(a_1, a_2, \dots, a_n)$$ так, чтобы выполнялось соотношение $$a_1 \le a_2 \le \dots \le a_n$$. Кроме того, на множестве позиций игры с n кучками введем отношение линейного порядка, аналогичного лексикографическому порядку для слов $$a_{1a2} \dots a_n$$.
Пусть кучек две. Позиция (0, k) является выигрышной для любого натурального k. Позиция (1, 1) - проигрышная. Любая позиция вида (1, k), где k > 1, является выигрышной, так как за один ход ее можно свести к проигрышной позиции. Наименьшей позицией, которая не сводится к проигрышной позиции (1, 1) за один ход, является позиция (2, 2). Позиция (2, 2) также является проигрышной, так как любой ход из нее приводит к выигрышной позиции. Соответственно, позиции вида (2, k), для k > 2, являются выигрышными. Следующей проигрышной позицией является (3, 3). Рассуждая аналогичным образом, получим, что проигрышная позиция в игре с двумя кучками содержит одинаковое число камней в кучках. Следовательно, выигрышная стратегия в игре с двумя кучками - выравнивать число камней в кучках.
Таким образом, если в начальной позиции обе кучки содержат равное число камней, то она является проигрышной для первого игрока, а если неравное, то выигрышной.
Пусть имеется три кучки. Из предыдущих рассуждений следует, что для m > 0 позиции (0, 0, m) являются выигрышными, а позиции (0, m, m) - проигрышными. Соответственно, позиции вида (k, m, m), для $$0 < k \le m$$, и (m, m, k), для k > m, являются выигрышными.
Наименьшей позицией, которая не сводится за один шаг к найденным проигрышным позициям, является (1, 2, 3). Поэтому данная позиция является проигрышной. Нетрудно видеть, что позиции (1, 4, 5) и (1, 6, 7) также являются проигрышными.
Наименьшей позицией, которая начинается с 2 и не сводится за один шаг к найденным проигрышным позициям, является позиция (2, 4, 6), затем идет (2, 5, 7).
Пример 1. Рассмотрим игру "Ним" с тремя кучками, содержащими 3, 5 и 7 камней ( рис. 5.1).
Все проигрышные позиции для этой игры имеют вид:
(0, k, k), для k от 1 до 5 включительно;
(1, 2, 3), (1, 4, 5), (2, 4, 6), (2, 5, 7), (3, 4, 7), (3, 5, 6).
Поэтому в позиции (3, 5, 7) существует 3 выигрышных хода: если игрок возьмет 1 камень из первой, второй или третьей кучки, то получится позиция (2, 5, 7), (3, 4, 7) или (3, 5, 6), соответственно. Все эти позиции являются проигрышными для второго игрока. Таким образом, позиция (3, 5, 7) является выигрышной для первого игрока. Выигрышная стратегия первого игрока - ходить так, чтобы противник получал проигрышную позицию.
Общее описание проигрышных позиций для игры "Ним" с тремя кучками приводится ниже. Если число кучек больше трех, то с помощью перебора можно найти проигрышные позиции аналогичным образом.
Рассмотрим более простой способ поиска выигрышной стратегии в игре Ним.
Утверждение 1. Побитовая операция $$\oplus$$ обладает следующими свойствами:
для произвольных целых неотрицательных чисел x, y и z.
Доказательство. Очевидно, что свойства выполняются на множестве {0, 1}. Поэтому они выполняются и для каждого двоичного разряда в двоичном представлении чисел x, y и z..
Утверждение 2. Побитовая операция $$\oplus$$ на множестве неотрицательных целых чисел обладает следующими свойствами:
x = y;y = z.Доказательство. 1) Пусть $$x \oplus y = 0$$. Тогда $$x = 0 \oplus x = x \oplus 0 = x \oplus (x \oplus y) = (x \oplus x) \oplus y = 0 \oplus y = y$$.
Если x = y, то $$x \oplus y = x \oplus x = 0$$
2) Пусть $$x \oplus y = x \oplus z$$. Тогда $$y = 0 \oplus y = (x \oplus x) \oplus y = x \oplus (x \oplus y) = x \oplus (x \oplus z) = (x \oplus x) \oplus z = 0 \oplus z = z.$$
Игра "Ним" известна в течение нескольких столетий, но первым ее полное решение опубликовал Чарльз Бутон в 1901 г. В теореме Бутона описываются проигрышные позиции этой игры, а также ее выигрышная стратегия.
Пусть $$X = (x_1, x_2, \dots, x_n)$$ - позиция в игре Ним с n кучками. Ним-суммой позиции X называется число $$x = x_1 \oplus x_2 \oplus \dots\oplus x_n$$.
Теорема (Бутона). Позиция $$(x_1, x_2, \dots, x_n)$$ является проигрышной в игре "Ним" тогда и только тогда, когда ее ним-сумма равна нулю.
Доказательство. Пусть $$(x_1, x_2, \dots, x_n)$$ - ненулевая позиция с нулевой ним-суммой, т. е. $$x_1 \oplus x_2 \oplus \dots\oplus x_n = 0$$. Будем считать, что $$x_1 > 0$$.
Возьмем из кучки $$x_1$$ произвольное ненулевое число камней k, так что $$0 < k \le x_1$$. Заметим, что $$ (x-1 - k) \oplus x_2 \oplus \dots\oplus x_n \ne 0$$. В самом деле, если $$ (x_1 - k) \oplus x_2 \oplus \dots\oplus x_n = 0$$, то из свойства 2 утверждения 2 следует, что $$x_1 = x_1 - k$$, что невозможно, так как k > 0. Аналогично для остальных кучек. Таким образом, произвольный ход из позиции с нулевой ним-суммой приводит к позиции с ненулевой ним-суммой.
Покажем теперь, что из позиции с ненулевой ним-суммой существует хотя бы один ход в позицию с нулевой ним-суммой.
Пусть $$ (x_1, x_2, \dots, x_n) $$ - позиция с ненулевой ним-суммой. Положим $$x = x_1 \oplus x_2 \oplus \dots\oplus x_n$$. Пусть двоичное представление числа x содержит i разрядов. Возьмем кучку j, такую, что в двоичном представлении числа $$x_j$$ в i-м разряде стоит 1.
Покажем, что $$x \oplus x_j < x_j$$. В самом деле, в i-м разряде двоичного представления числа $$x \oplus x_j$$ стоит 0, а значения, стоящие в старших разрядах, совпадают со значениями числа $$x_j$$, стоящими в тех же разрядах.
Далее, заменим в выражении $$x_1 \oplus x_2 \oplus \dots\oplus x_n$$ элемент $$x_j$$ на элемент $$x \oplus x_j$$. В результате получим:
$$ x_1 \oplus x_2 \oplus \dots\oplus (x \oplus x_j) \oplus \dots\oplus x_n=\\ = (x_1 \oplus x_2 \oplus \dots\oplus x_j \oplus \dots\oplus x_n) \oplus x = x \oplus x = 0. $$Таким образом, если из кучки j забрать $$x_j - (x \oplus x_j) $$ камней, то получится позиция с нулевой ним-суммой.
Следовательно, позиции с нулевой ним-суммой являются проигрышными, а остальные позиции - выигрышными. Выигрышная стратегия - ходить так, чтобы привести противника в позицию с нулевой ним-суммой, что всегда возможно сделать из позиции с ненулевой ним-суммой.
Пример 2. Для игры "Ним" с тремя кучками, содержащими 3, 5 и 7 камней, имеем: $$3 = 11_2, 5 = 101_2, 7 = 111_2$$.
Найдем ним-сумму начальной позиции.
В нулевом разряде каждого числа стоит 1. Поэтому следует либо оставить $$3 \oplus 1$$, или 2 камня в первой кучке, либо $$5 \oplus 1$$, или 4 камня во второй, либо $$7 \oplus 1$$, или 6 камней в третьей кучке.
Пример 3. Рассмотрим игру "Ним" с 4 кучками, которые содержат 17, 24, 7 и 11 камней. Имеем: $$17 = 10001_2, 24 = 11000_2, 7 = 111_2, 11 = 1011_2$$.
Найдем ним-сумму x начальной позиции:
Таким образом, $$x = 17 \oplus 24 \oplus 7 \oplus 11 = 5$$. Старший ненулевой разряд ним-суммы отличен от 0 только у числа 7. По теореме Бутона, в третьей кучке должно остаться $$5 \oplus 7$$, или 2 камня. Соответственно, взять из нее следует 5 камней. В результате противнику достанется проигрышная позиция с 4 кучками, содержащими 17, 24, 2 и 11 камней.
Рассмотрим функцию Шпрага-Гранди. Областью определения этой функции является множество позиций игры, а областью значений - множество неотрицательных целых чисел.
Функция Шпрага-Гранди определяется индуктивно. Если из позиции нельзя сделать ход, то значение функции в ней полагается равным 0. В противном случае значение функции в позиции S полагается равным наименьшему неотрицательному числу, которое отсутствует среди значений функции в позициях, в которые можно за один ход попасть из S.
Утверждение 3. Позиция является проигрышной тогда и только тогда, когда значение функции Шпрага-Гранди в этой позиции равно 0.
Доказательство. Пусть значение функции Шпрага-Гранди в позиции S равно 0. Тогда либо из позиции S нельзя сделать ход, либо все ходы из нее приводят к таким позициям, для которых значение функции Шпрага-Гранди положительно. Обратно, пусть значение функции Шпрага-Гранди в позиции S положительно. Тогда среди позиций, в которые можно из нее перейти, существует позиция, значение функции Шпрага-Гранди которой равно нулю.
Рассмотрим игру "Ним" с одной кучкой. Пусть P - множество позиций игры и $$\mathbb {Z}_0$$ - множество неотрицательных целых чисел. Обозначим через $$g: P \to \mathbb {Z}_0$$ функцию Шпрага-Гранди.
Утверждение 4. Функция Шпрага-Гранди на множестве позиций игры "Ним" с одной кучкой имеет вид: g(m) = m.
Доказательство. В позиции (m) существует m ходов: из кучки можно взять от 1 до m камней. Используем индукцию по m.
При m = 0 утверждение верно. Предположим, что утверждение верно для всех кучек, содержащих не более k камней. Пусть кучка содержит k + 1 камень. Из этой кучки можно взять от 1 до k + 1 камней и перейти при этом в позиции $$ (k), (k - 1), \dots, (1), (0) $$. По предположению индукции, значение функции Шпрага-Гранди в этих позициях соответственно равно $$k, k - 1, \dots, 1, 0$$. Наименьшее целое неотрицательное число, которое не входит во множество полученных значений, равно k + 1. Следовательно, g(k + 1) = k + 1.
Для доказательства теоремы Шпрага-Гранди понадобится еще одно свойство операции $$\oplus$$.
Утверждение 5. Если $$k < x \oplus y$$, то $$k = x' \oplus y$$ для некоторого x', такого что x' < x, или $$k = x \oplus y' $$ для некоторого $$y' $$, такого что $$y' < y$$.
Доказательство. Пусть i - самый старший разряд двоичного представления, в котором число $$x \oplus y$$ отличается от k. В этом разряде у числа k стоит 0, а у числа $$x \oplus y - 1$$. Поэтому в i-ом разряде одного из чисел x и y стоит 1, а другого - 0. Пусть в i-ом разряде числа x стоит 0
Покажем, что $$x \oplus k < y$$. Действительно, пусть разряд j старше разряда i. Тогда значения j-го разряда чисел $$x \oplus y$$ и k совпадают. Поэтому в j-ом разряде числа $$x \oplus k$$ стоит то же значение, что и в j-ом разряде числа $$x \oplus (x \oplus y) $$, равного y. Следовательно, i - это самый старший разряд двоичного представления числа $$x \oplus k$$, в котором оно отличается от y. Но в i-м разряде числа $$x \oplus k$$ стоит 0, а в том же разряде числа y стоит 1. Таким образом, $$x \oplus k < y$$. Положим $$y' = x \oplus k$$. Имеем:
Пусть P - множество позиций игры G, а F - бинарное отношение на P, такое что F = {(p, q) | существует ход, который переводит p в q}.
Пусть $$G_1$$ и $$G_2$$ - игры, $$P_1$$ и $$P_2$$ - множества позиций игр $$G_1$$ и $$G_2$$, а $$F_1$$ и $$F_2$$ - определенные выше бинарные отношения на множествах $$P_1$$ и $$P_2$$, соответственно
Суммой игр $$G_1$$ и $$G_2$$ называется игра G с множеством позиций P, таким что $$P = P_1 * P_2$$, а отношение F на множестве P имеет вид:
Пример 4. Игра "Ним" с двумя кучками является суммой двух игр "Ним" с одной кучкой.
Обозначим через $$ g_1: P_1 \to \mathbb {Z}_0, g_2: P_2 \to \mathbb {Z}_0 $$ и $$ g: P \to \mathbb {Z}_0 $$ функции Шпрага-Гранди игр $$ G_1, G_2 $$ и $$ G $$, соответственно.
Теорема (Шпрага-Гранди). Для любой позиции $$ (p_1, p_2) $$ игры $$ G $$ является верным следующее равенство:
$$ g(p_1, p_2) = g_1(p_1) \oplus g_2(p_2). $$Доказательство. Используем индукцию по максимальному числу оставшихся ходов.
Из позиции $$ (p_1, p_2) $$ игры G нельзя сделать ход тогда и только тогда, когда его нельзя сделать ни из позиции $$ p_1 $$ в игре $$ G_1 $$, ни из позиции $$ p_2 $$ в игре $$ G_2 $$. Поэтому $$ g(p_1, p_2) = 0 $$, тогда и только тогда, когда $$ g_1(p_1) = 0 $$ и $$ g_2(p_2) = 0 $$, а, следовательно, $$ g_1(p_1) \oplus g_2(p_2) = 0 $$.
Пусть $$ (q_1, q_2) $$ - позиция, в которую существует ход из позиции $$ (p_1, p_2) $$. Тогда, по определению, либо $$ q_1 = p_1, q_2 \ne p_2 $$, либо $$ q_2 = p_2, q_1 \ne p_1 $$.
Покажем, что $$ g_1(p_1) \oplus g_2(p_2) \ne g(q_1, q_2) $$. От противного. Предположим, что $$g_1(p_1) \oplus g_2(p_2) = g(q_1, q_2) $$. Пусть $$ (q_1, q_2) = (p_1, q_2) $$. Тогда, по предположению индукции, $$g(q_1, q_2) = g_1(p_1) \oplus g_2(q_2) $$. Следовательно, выполняется условие $$g_1(p_1) \oplus g_2(p_2) = g_1(p_1) \oplus g_2(q_2) $$, из которого по свойству 2 утверждения 2 следует, что $$g_2(p_2) = g_2(q_2) $$. Но в позицию $$q_2$$ существует ход из позиции $$p_2$$ в игре $$G_2$$, поэтому данное равенство невозможно по определению функции Шпрага-Гранди. Случай $$ (q_1, q_2) = (q_1, p_2) $$ рассматривается аналогично.
Итак, число $$g_1(p_1) \oplus g_2(p_2) $$ не совпадает ни с одним из значений функции Шпрага-Гранди в позициях, которые получаются с помощью некоторого хода из позиции $$ (p_1, p_2) $$.
Покажем, что число $$g_1(p_1) \oplus g_2(p_2) $$ является наименьшим целым неотрицательным числом, которое не принадлежит множеству $$Q = {g(q_1, q_2) | ((p_1, p_2), (q_1, q_2)) \in F}$$.
Пусть $$k < g_1(p_1) \oplus g_2(p_2) $$, где $$k \in \mathbb {Z}_0$$. Из утверждения 5 следует, что либо $$k = k_1 \oplus g_2(p_2) $$ для некоторого числа $$k_1$$ из $$\mathbb {Z}_0$$, такого что $$k_1 < g_1(p_1) $$, либо $$k = g_1(p_1) \oplus k_2$$ для некоторого $$k_2$$ из $$\mathbb {Z}_0$$, такого что $$k_2 < g_2(p_2) $$.
Пусть $$k = k_1 \oplus g_2(p_2) $$. Поскольку $$k_1 < g_1(p_1) $$, то, по определению функции Шпрага-Гранди, в игре $$G_1$$ найдется позиция $$q_1$$, в которую существует ход из позиции $$p_1$$, такая, что $$k_1 = g_1(q_1) $$. Следовательно, выполняется соотношение $$k = k_1 \oplus g_2(p_2) = g_1(q_1) \oplus g_2(p_2) = g(q_1, p_2) $$.
Последнее равенство верно по предположению индукции.
Заметим, что $$ (q_1, p_2) $$ - это позиция, в которую существует ход из позиции $$ (p_1, p_2) $$. Таким образом, среди значений функции Шпрага-Гранди в позициях, в которые существует ход из позиции $$ (p_1, p_2) $$, найдется любое неотрицательное целое число, меньшее, чем $$g_1(p_1) \oplus g_2(p_2) $$. Поэтому
$$g(p_1, p_2) = g_1(p_1) \oplus g_2(p_2).$$Следствие. Функция Шпрага-Гранди игры "Ним" с n кучками имеет вид:
В самом деле, игра "Ним" с n кучками является суммой n игр с одной кучкой. Пусть $$g_i: P_i \to \mathbb {Z}_0$$ - функция Шпрага-Гранди i-ой игры, определенная на множестве ее позиций $$P_i$$, для $$i = 1, 2, \dots, n$$. Из утверждения 3 следует, что $$g_i(x_i) = x_i$$. По методу математической индукции получаем указанную выше формулу.
Таким образом, теорема Бутона является следствием теоремы Шпрага-Гранди.
Пример 5. Рассмотрим следующую игру. В кучке имеется 9 камней. Два игрока ходят по очереди. За один ход игрок может взять от 1 до 3 камней. Выигрывает тот, кто берет последний камень. Построим функцию Шпрага-Гранди.
Пусть позицией является число камней в кучке. Тогда множество позиций игры описывается целыми числами от 0 до 9. Последовательно находим:
g(0) = 0; g(1) = 1; g(2) = 2; g(3) = 3; g(4) = 0; g(5) = 1; g(6) = 2; g(7) = 3; g(8) = 0; g(9) = 1.
Покажем, что в общем случае, g(m) = m mod 4, для $$m = 0, 1, 2, \dots$$ В самом деле, значение функции Шпрага-Гранди в позиции m определяется значениями этой функции в позициях m - 1, m - 2 и m - 3, для $$m \ge 3$$. Применим индукцию по m. При $$m \le 3$$ утверждение верно. Предположим, что оно верно при m = k, где $$k \ge 3$$. Пусть m = k + 1. По предположению индукции, в позициях k, k - 1 и k - 2 значение функции Шпрага-Гранди равно трем последовательным остаткам от деления на 4. Поэтому значение функции Шпрага-Гранди в позиции k + 1 равно недостающему остатку от деления на 4, так что g(m) = m mod 4 при $$m \ge 0$$.
Таким образом, проигрышными являются позиции, кратные 4. В частности, позиция 9 является выигрышной. Выигрышная стратегия игры - оставлять другому игроку число камней, кратное 4.
Пример 6. Рассмотрим игру, которая является обобщением игры из примера 5. Она заключается в следующем. Имеется n кучек. Два игрока ходят по очереди. За один ход игрок может взять от 1 до 3 камней из любой кучки. Выигрывает тот, кто берет последний камень.
Пусть кучка i содержит xi камней, для $$i = 1, 2, \dots, n$$. По теореме, функция Шпрага-Гранди для этой игры имеет вид:
Поэтому позиция является проигрышной тогда и только тогда, когда побитовая строгая дизъюнкция остатков от деления на 4 чисел $$x_i$$ равна 0, для $$i = 1, 2, \dots, n$$.
Найдем выигрышную стратегию игры. Заметим, что свойство позиции быть выигрышной или проигрышной зависит только от двух младших разрядов двоичного представления чисел $$x_i$$, для $$i = 1, 2, \dots, n$$.
Положим $$x = x_1 \mod 4 \oplus x_2 \mod 4 \oplus \dots\oplus x_n \mod 4$$.
Очевидно, что $$x \le 3$$. Пусть $$x \ne 0$$ и i - старший разряд двоичного представления числа x, значение которого равно 1. Тогда существует число $$x_j$$, в i-ом разряде двоичного представления которого стоит 1, так как i-ым является один из двух младших разрядов.
Заметим, что значения двоичных разрядов, старших i, чисел $$x_j$$ и $$x \oplus x_j$$ совпадают, при этом в разряде i числа $$x_j$$ стоит 1, а в том же разряде числа $$x \oplus x_j$$ стоит 0. Отсюда следует, что, во-первых, $$x \oplus x_j < x_j$$ и что, во-вторых, $$x_j - x \oplus x_j \le 3$$.
Заметим также, что $$ (x \oplus x_j) \mod 4 = x \oplus (x_j \mod 4) $$, так как $$x \le 3$$. Следовательно,
$$x_1 \mod 4 \oplus \dots \oplus (x \oplus x_j) \mod 4 \oplus \dots \oplus x_n \mod 4 = \\ = x \oplus (x_1 \mod 4 \oplus \dots \oplus x_j \mod 4 \oplus \dots \oplus x_n \mod 4) = x \oplus x = 0. $$Таким образом, выигрышный ход - взять ($$x_j - x \oplus x_j$$) камней из кучки, в которой находится $$x_j$$ камней.
Например, пусть кучки содержат 9, 6, 5 и 4 камня. Тогда 9 mod 4 \oplus 6 mod 4 \oplus 5 mod 4 \oplus 4 mod 4 = 1 \oplus 2 \oplus 1 \oplus 0 = 2.
Следовательно, позиция является выигрышной. Номер старшего ненулевого двоичного разряда числа 2 равен 1. Этот же разряд является ненулевым у числа 6. Имеем: $$6 - 2 \oplus 6 = 6 - 4 = 2$$. Поэтому выигрышный ход состоит в том, чтобы взять 2 камня из кучки, содержащей 6 камней.
Проигрышные позиции в игре "Ним" с тремя кучками обладают интересными свойствами.
Рассмотрим метод поиска проигрышных позиций для игры "Ним" с тремя кучками, который является сочетанием методов из п. 5.1.2 и 5.1.4.
Проигрышные позиции с ненулевыми упорядоченными значениями компонент можно построить с помощью таблицы сложения для операции $$\oplus$$ (см. ниже), так как число камней в третьей кучке равно результату применения операции \oplus к числу камней в первой и второй кучках. Эти позиции имеют вид:
(1, 2k, 2k + 1); (2, 4k, 4k + 2); (3, 4k, 4k + 3); (2, 4k + 1, 4k + 3); (3, 4k + 1, 4k + 2); (4, 8k, 8k + 4); (5, 8k, 8k + 5); (4, 8k + 1, 8k + 5); (5, 8k + 1, 8k + 4); (4, 8k + 2, 8k + 6); (5, 8k + 2, 8k + 7); (4, 8k + 3, 8k + 7); (5, 8k + 3, 8k + 6); (6, 8k, 8k + 6); (7, 8k, 8k + 7); (6, 8k + 1, 8k + 7); (7, 8k + 1, 8k + 6); (6, 8k + 2, 8k + 4); (7, 8k + 2, 8k + 5); (6, 8k + 3, 8k + 5); (7, 8k + 3, 8k + 4); …
для $$k = 1, 2, \dots$$ При фиксированном значении k проигрышные позиции находятся с помощью двоичного представления чисел, равных количеству камней в первых двух кучках. Например, при k = 1 для числа камней в первых двух кучках имеем:
1 1 1 1 10 10 10 10 ...
Вместо знака следует подставлять значения 0 и 1. Соответственно, при k = 1 имеется одна позиция, первая компонента в которой равна 1, четыре позиции, первая компонента которых равна 2 или 3, и 16 позиций, первая компонента которых равна 4, 5, 6 или 7, и так далее.
Соответственно, при k = 2 двоичное представление числа камней в первых двух (наименьших) кучках имеет вид:
1 1 1 1 100 100 100 100 ...
В общем случае, для целого неотрицательного s положим $$q = 2^s/$$ и $$p = 2^{s + 1}$$. Тогда проигрышными являются позиции, первая компонента которых равна $$q, q + 1, \dots, 2q - 1$$, вторая компонента принимает значения $$pk, pk + 1, \dots, pk + q - 1$$, для $$k = 1, 2, \dots$$, а третья компонента равна результату применения операции bitXor к первым двум компонентам.
Таким образом, пусть m - минимальное число камней в трех кучках, p - наименьшая степень 2, такая что m < p, и $$q=\fracp2$$. Тогда проигрышные позиции, содержащие m, находятся следующим образом:
Пример 7. Пусть m = 10, тогда p = 16 и q = 8. Проигрышные позиции с минимальным числом камней в трех кучках, равным 10, имеют вид:
(10, 16k, 16k + 10), (10, 16k + 4, 16k + 14), (10, 16k + 1, 16k + 11), (10, 16k + 5, 16k + 15), (10, 16k + 2, 16k + 8), (10, 16k + 6, 16k + 12), (10, 16k + 3, 16k + 9), (10, 16k + 7, 16k + 13),
для $$k = 1, 2, \dots$$, или
$$ (10, 16, 26), (10, 17, 27), (10, 18, 24), (10, 19, 25), (10, 20, 30), (10, 21, 31), (10, 22, 28), (10, 23, 29), (10, 32, 42), (10, 33, 43), \dots$$Рассмотрим таблицу сложения для операции $$\oplus$$, которая используется для построения проигрышных позиций в игре с тремя кучками: найдем значения $$x \oplus y$$, для $$x = q, q + 1, \dots, 2q - 1$$ и $$y = 0, 1, \dots, q - 1$$, где $$q = 2^s$$, для целого положительного числа s. Таблицы сложения для значений q, равных 2, 4 и 8 приведены в рис. 5.2.
(рис 5.2) Таблица сложения для операции разделительной дизъюнкции
Из свойств побитовой операции строгой дизъюнкции следует, что таблицы сложения в данном случае можно строить по определенному правилу, без вычисления двоичных представлений чисел x и y. Достаточно использовать схему, приведенную на рис. 5.3.
(рис 5.3) Схема для заполнения рис. 5.2
Схема применяется следующим образом. Заполнение таблиц начинается из углов, обозначенных жирными черными точками. В них помещается значение q. В направлениях, указанных стрелками, значения элементов таблицы увеличиваются на 1 в каждом столбце или строке. После заполнения крайних рядов, таблица делится на 4 равные по размеру квадратные подтаблицы, а затем та же схема применяется для заполнения пустых ячеек каждой из полученных таблиц (см. рис. 5.2). Заметим также, что, как элементы главной диагонали, так и элементы побочной диагонали каждой таблицы равны между собой. Например, для q = 4 получится результат, приведенный в рис. 5.4.
(рис 5.4) Построение таблицы сложения операции разделительной дизъюнкции при q = 4
Нетрудно заметить, что таблицы могут быть построены итеративно: текущая таблица получается из предыдущей заменой каждой ее ячейки таблицей 2 * 2 по правилу
при этом нулевой является таблица (1). Если одинаковые числа заменить квадратами одинакового цвета, то при q = 64 получится один из вариантов раскраски квадрата, приведенный на рис. 5.5.
(рис 5.5) "Цветовое" представление таблицы сложения операции разделительной дизъюнкции при q = 64
Рассмотрим примеры клеточных автоматов, которые имеют широкое применение в различных областях исследований.
Клеточный автомат - это пятерка $$\langle C, Q, N, q_0, f \rangle$$, где
C - множество клеток;Q - множество состояний клетки;Окрестность клетки образуют соседние с ней клетки (или ее соседи), а также сама клетка. Начальным является состояние множества клеток в момент времени 0. Правило перехода определяет, каким будет состояние клетки в момент времени i + 1, в зависимости от того, каким было ее состояние, а также состояние ее соседей в момент времени i.
Ниже рассматриваются примеры клеточных автоматов, в которых клетки могут принимать одно из двух состояний: 0 или 1.
Элементарный клеточный автомат - это одномерный автомат в виде бесконечной ленты, в котором соседними для клетки являются клетки, содержащие с ней общую сторону. Таким образом, каждая клетка имеет два соседа. Правило изменения состояния клетки определяется логической функцией с тремя аргументами, которыми являются состояния клеток ее окрестности. Всего существует 256 элементарных клеточных автоматов, по числу логических функций с 3 аргументами.
Пусть $$x_i$$ - клетка, а $$x_{i - 1}$$ и $$x_{i + 1}$$ - ее соседи слева и справа, соответственно. Пусть также N - целое число, такое что $$0 \le N \le 255$$, и двоичное представление числа N длины 8 имеет вид: $$b_0b_1b_2b_3b_4b_5b_6b_7$$. Правило Вольфрама, или правило N, описывает переходы между состояниями в элементарном клеточном автомате, в соответствии с таблицей истинности логической функции, которая представлена в табл. 5.1.
Если клетка $$x_i$$ в момент времени k находится в состоянии $$y-q^{(k)}_{0}$$, а ее соседи в состояниях$$x=q^{(k}}_{-1}$$ и $$z=q^{(k)}_{1}$$, соответственно, то состояние клетки xi в момент k + 1 имеет вид: $$q^{(k+1)}_{0}=f(x,y,z)$$.
| x | y | z | f |
|---|---|---|---|
| 0 | 0 | 0 | $$b_7$$ |
| 0 | 0 | 1 | $$b_6$$ |
| 0 | 1 | 0 | $$b_5$$ |
| 0 | 1 | 1 | $$b_4$$ |
| 1 | 0 | 0 | $$b_3$$ |
| 1 | 0 | 1 | $$b_2$$ |
| 1 | 1 | 0 | $$b_1$$ |
| 1 | 1 | 1 | $$b_0$$ |
Пример 8. Рассмотрим правило 110. Имеем:
$$110 = 01101110_2. $$Преобразование состояния клетки по правилу 110 имеет вид:
000 001 010 011 100 101 110 111 0 1 1 1 0 1 1 0
(ср. с таблицей истинности).
Множество состояний элементарного клеточного автомата представляется в виде конечного клеточного поля, строки которого соответствуют моментам времени. Обычно правая сторона поля отождествляется с левой, так что правым соседом крайней правой клетки является крайняя левая клетка, а левым соседом крайней левой клетки - крайняя правая клетка. Например, пусть поле имеет 9 клеток, начальное состояние центральной клетки равно 1, а остальных клеток - 0. Тогда по правилу 110 состояния клеточного поля в моменты времени 1 - 4 имеют вид:
Состояние множества клеток одномерного поля в момент времени k отображается в виде k-го ряда двумерного поля. Белый цвет клетки обозначает состояние 0, а черный - состояние 1. Например, если в начальный момент времени состояние 1 имеет только крайняя правая клетка, то последующие 29 состояний одномерного поля для правила 110 выглядят так, как показано на рис. 5.6 (a), где начальное состояние соответствует нижнему ряду поля.
Пример 9. Для числа 18 имеем: 18 = 000100102.
Поэтому правило 18 можно представить следующим образом:
На рис. 5.6 (b) правило 18 применяется к одномерному множеству клеток, образующему нижний ряд поля, в начальном состоянии которого 10 клеток, выбранных случайным образом, имеют состояние 1, а остальные клетки - состояние 0. Как и ранее, левая и правая границы поля отождествляются.
(рис 5.6) Клеточные автоматы для правила (a) 110; (b) 18; начальное состояние соответствует нижнему ряду поля
Игру "Жизнь" придумал в 1970 г. американский математик Джон Конвей. Она является клеточным автоматом, множество клеток которого представляет собой бесконечное двумерное клеточное поле. Соседними считаются клетки, имеющие хотя бы одну общую вершину, поэтому каждая клетка имеет 8 соседей. Клетки могут находиться в одном двух состояний - 0 или 1. В первом случае клетка называется пустой, или мертвой, а в втором - живой.
Правила Конвея размножения и гибели клеток имеют вид:
Игра прекращается, если на поле не остается ни одной живой клетки или конфигурация живых клеток станет неизменяемой, или устойчивой.
Пример 10. На рис. 5.7 приведен фрагмент игры для четырех фигур в момент времени k, для k от 0 до 4. Крайняя левая фигура ("диагональ") погибает на втором шаге. Вторая фигура, справа от нее, называется "мигалка" - это периодически повторяющаяся конфигурация с периодом 2. Третья фигура на втором шаге переходит в устойчивое состояние ("улей"). Четвертая фигура ("планер") за каждые четыре шага смещается по диагонали на одну клетку в направлении вправо-вниз.
(рис 5.7) Состояния конфигурации живых клеток в моменты времени от 0 до 4
Пример 11. Рассмотрим конфигурации живых клеток, которые называются "космическими кораблями". Каждая такая конфигурация перемещается - начальное взаимное расположение живых клеток периодически повторяется, при этом фигура смещается на 2 клетки по направлению движения: передней частью "корабля" является отрезок, содержащий в начальном состоянии 3 клетки. "Легкий", "средний" и "тяжелый космические корабли" показаны на рис. 5.8 (a-c).
(рис 5.8) Космический корабль: (a) легкий; (b) средний; (c) тяжелый
На рис. 5.10 (a-e) показано перемещение "легкого корабля".
(рис 5.10) Легкий космический корабль в моменты времени k от 0 до 4
Пример 12. Примером повторяющей без смещения конфигурации живых клеток с периодом 3 является кембриджский пульсар ( рис. 5.11).
(рис 5.11) Кембриджский пульсар в момент времени (a) 0; (b) 1; (с) 2
На рис. 5.12 (a-c) приведены примеры конфигураций живых клеток, каждая из которых за конечное время преобразуется в кембриджский пульсар.
(рис 5.12) Конфигурации, сходящиеся к кембриджскому пульсару
Периодически повторяющиеся фигуры называют осцилляторами.
Начальные конфигурации живых клеток, которые стабилизируются через большое число поколений, называются фигурами Мафусаила, по имени библейского персонажа, который дольше всех из допотопных жителей. Примеры таких конфигураций приведены на рис. 5.12 (a-c).
(рис 5.12) Фигуры Мафусаила: (a) "пентамино"; (b) "желудь"; (c) "кролики"
Фигуры "пентамино", "желудь" и "кролики" стабилизируются соответственно через 1103, 5206 и 17332 поколений.
Появление игры "Жизнь" привело к созданию клеточных автоматов со схожей структурой. Их называют жизнеподобными (Life-like) клеточными автоматами. Правила "зарождения" и "сохранения" жизни обозначаются в виде $$Bn_1\dotsn_p/Sm_1\dotsm_q$$, где $$n_i$$ - число живых соседей, при которых пустая клетка становится живой, а $$m_j$$ - число живых соседей, при которых живая клетка остается живой, где $$i = 1, \dots, p; j = 1, \dots, q$$. Для оригинальной игры "Жизнь" правило имеет вид: B3/S23.
Примерами известных жизнеподобных автоматов являются:
На рис. 5.13 (a-c) показаны некоторые состояния клеточного автомата "Репликатор", в котором каждая конфигурация является репликатором - бесконечно копирует себя.
(рис 5.13) "Репликатор" в момент времени (a) 0; (b) 4; (c) 5
Клеточный автомат "Лабиринт" создает изображения, похожие на лабиринт, из любого начального состояния ( рис. 5.14 (a-b) ).
(рис 5.14) "Лабиринт" в момент времени (a) 0; (b) 30
Клеточный автомат "Фредкин" порождает расширяющиеся конфигурации ( рис. 5.15 (a-c)).
(рис 5.15) "Фредкин" в момент времени (a) 0; (b) 5; (c) 7
У клеточного автомата "День и ночь" на бесконечном поле существуют периодические конфигурации живых клеток, которые при замене мертвых клеток живыми, а живых - мертвыми преобразуются в конфигурации, которые так же являются пери
(рис 5.16) "День и ночь": периодические конфигурации (a) живых клеток; (b) пустых клеток на поле из живых клеток
Для создания жизнеподобных клеточных автоматов, помимо прямоугольного поля, используется гексагональное поле, в котором клетки являются правильными шестиугольниками. На бесконечном поле каждая клетка обладает шестью соседями.
На рис. 5.17 (a-g) показаны примеры осцилляторов для жизнеподобного клеточного автомата, правило "зарождения" и "сохранения" жизни которого имеет вид: B2/S34.
Упражнение. Найдите период каждого осциллятора, приведенного на рис. 5.17.
(рис 5.17) Осцилляторы в игре с правилом B2/S34
На гексагональном поле существуют также стохастические клеточные автоматы, в которых пустая клетка становится живой с некоторой вероятностью, при заданном количестве соседей.
Например, пустая клетка становится живой с вероятностью $$\frac13$$, если она имеет ровно 2 живых соседа; живая клетка остается живой, если у нее имеется 1 или 2 живых соседа. Другим примером является клеточный автомат, в котором пустая клетка оживает с вероятностью 1, если имеет 3 живых соседа, и с вероятностью $$\frac16$$, если она имеет 2 живых соседа; живая клетка сохраняет жизнь, если она имеет 2 или 3 живых соседа.
Упражнения
x - неотрицательное целое число. Покажите, что если x четное, то $$x \oplus 1 = x + 1$$, а если нечетное, то $$x \oplus 1 = x - 1$$.Найдите выигрышный ход в игре "Ним", если он существует, в позиции
a) (19, 15, 4);
b) (8, 4, 12, 22);
c) (14, 25, 17, 3, 10).
Перечислите все проигрышные позиции в игре "Ним" с тремя кучками, если число камней в каждой кучке не превосходит
a) 10;
b) 15;
c) 20.
Постройте функцию Шпрага-Гранди и придумайте выигрышную стратегию для игры в камни с одной кучкой. В игре участвуют два игрока, игроки ходят по очереди. Выигрывает игрок, который берет последний камень. Кучка содержит m камней. За один ход игрок может взять от 1 до k камней, если k равно
4;
b) 7.
n кучками. В игре участвуют два игрока, игроки ходят по очереди. За один ход игрок может взять от 1 до 7 камней из любой кучки. Выигрывает игрок, который берет последний камень. Постройте функцию Шпрага-Гранди для этой игры.Рассмотрим игру в N. В игре участвуют два игрока, Игроки ходят по очереди. Имеется пять костяшек домино с очками от 1 до 5. Первый игрок кладет монету на любую костяшку и получает число очков, обозначенное на этой костяшке. Второй игрок перекладывает монету на любую другую костяшку и получает число очков, равное сумме очков другого игрока и очков, обозначенных на этой костяшке. Оставлять монету на той же костяшке нельзя, и так далее. Выигрывает игрок, который набирает ровно N очков или принуждает противника превзойти эту сумму. Придумайте выигрышную стратегию для игры в N, если она существует, для значения N, равного
a) 2;
b) 6;
с) 7;
d) 13;
e) 21;
f) 37.
Опишите с помощью клеток правила перехода для элементарного клеточного автомата, соответствующего правилу
a) 24;
b) 135;
с) 215.
Постройте логическую функцию, которая соответствует переходам в элементарном клеточном автомате для правила
a) 110;
b) 30;
с) 150.
Найдите состояния 1 - 10 элементарного клеточного автомата с начальным состоянием
,
если для переходов используется правило
a) 110;
b) 18;
c) 218;
d) 150;
e) 53;
f) 30.
Найдите состояния 1 - 10 элементарного клеточного автомата с начальным состоянием
1) ;
2) ,
в котором правило перехода определяется логической функцией
a) $$f(x, y, z) = x \oplus y \oplus z$$;
b) $$f(x, y, z) = x y \vee \neg z$$.
Найдите состояния 1 - 10 элементарного клеточного автомата с начальным состоянием
1) ;
2) ,
в котором правило определяется алгебраической функцией
a) f(x, y, z) = (x + y + z) mod 2,;
b) f(x, y, z) = (x y + x z) mod 2.
Определите, через сколько шагов становится устойчивой или периодической конфигурация живых клеток в игре "Жизнь", приведенная на рис. 5.18:
(рис 5.18) Начальные конфигурации живых клеток
Определите период приведенной на рис. 5.19 конфигурации живых клеток в игре "Жизнь":
a) "маяк";
b) "лягушка";
c) "пентадекатлон"
(рис 5.19) Начальные конфигурации живых клеток
Определите для жизнеподобной игры с правилом B3/S3, период осциллятора, приведенного на рис. 5.20:
(рис 5.20) Начальные конфигурации живых клеток
Определите для жизнеподобной игры с правилом B3/S13, период осциллятора, приведенного на рис. 5.18:
(рис 5.21) Начальные конфигурации живых клеток
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.