Подразделы

Другие разделы

Дата и время

09/04/2025 06:38:29

Авторизация

Зарегистрироваться
Восстановить пароль

Занятие 14

Классификация игр Минимаксный алгоритм, альфа-бета отсечение Игра ним и другие Ним-значение и теория Гранди

Игра ним и другие

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

Пусть из кучки можно брать от 1 до

$k$ камней и первоначально в кучке

$n$ камней. Выигрывает тот, кто берет последний камень. Если в кучке от 1 до

$k$ , выигрывает первый игрок. Если в кучке

$k+1$ камень, то любой ход первого игрока приводит к ситуации, выигрышной для второго игрока. Для кучки от

$k+2$ до

$2*k+1$ у первого игрока есть ход, после которого в кучке остается

$k+1$ камень. Анализируя дальше, можно сделать вывод, что проигрышными являются кучки с числом камней кратным

$k+1$ . Результаты анализа удобно представить в таблице, в которой плюсом отмечены позиции выигрышные для первого игрока, а минусом — проигрышные. Пример таблицы для

$k=3$ .

Количество камней	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Результат игры	+	+	+	—	+	+	+	—	+	+	+	—	+	+	+	—	+

Проигрышными являются те позиции, любой ход из которых приводит к выигрышной позиции. Заполнение таблицы результатов выполняется как в задачах динамического программирования, и этот способ можно использовать для решения задачи в общем случае. Мизерный вариант игры получается сдвигом результатов исходной игры на одну клетку.

Количество камней	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Результат игры	—	+	+	+	—	+	+	+	—	+	+	+	—	+	+	+	—

То есть проигрышными становятся кучки, в которых число камней

$n$ mod

$(k+1)\ =\ 1$ .

Рассмотрим следующую игру. За ход из кучки разрешается брать любое число камней являющееся степенью числа 2 (то есть 1, 2, 4, 8 и т.д.). Построим таблицу. Если в кучке 1 или 2 камня, то выигрывает первый игрок. Если 3 камня, то первый проигрывает. Для 4 и 5 камней опять выигрывает первый, оставляя второму кучку из 3 камней.

Количество камней	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Результат игры	+	+	—	+	+	—	+	+	—	+	+	—	+	+	—	+	+

Анализ таблицы позволяет сделать предположение, что проигрышными позициями для первого игрока будут кучки из

$3*m$ камней, так как в них не существует хода, с помощью которого он может получить проигрышную позицию. Не существует целого p такого, что

$(3*m\ -\ 2^p)\$ mod 3 = 0, так как

$(3*m)\$ mod 3 = 0, а

$2^p$ mod 3

$≠\ 0.$

Если можно брать от 1 до

$[n/2]$ камней, то проигрышными будут позиции с числом камней 2, 5, 11, 23, 47, …,