Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата

 

 

 

Игра ним и другие аналогичные игры

Существует несколько игр, в которых двое играющих A и B, руководствуясь определёнными правилами, по очереди вынимают то или иное число фишек из одной или нескольких кучек – побеждает тот, кто берёт последнюю фишку. Простейшая такая игра – это игра с одной кучкой фишек, и сделать ход в ней – значит взять из кучки любое число фишек от 1 до m включительно. Многие подобные игры поддаются исследованию с помощью числа Шпрага-Гранди G(C). Пустой позиции O, не содержащей фишек, отвечает G(O)=0. Комбинацию кучек, состоящих соответственно из x, y, … фишек, обозначим C=(x, y, …) и предположим, что допустимые ходы переводят C в другие комбинации: D, E, … Тогда G(C) есть наименьшее неотрицательное число, отличное от G(D), G(E), … Это позволяет по индукции определить G(C) для любой комбинации C, разрешённой правилами игры. Так, в упомянутой задаче G(x)=x mod (m+1).

0 – и тогда всё повторяется снова. Такая игра после конечного числа ходов заканчивается победой A.

К подобным играм относится ним. Имеется произвольное число кучек фишек, и игроки по очереди выбирают одну какую-то кучку и вынимают из неё любое число фишек (но хотя бы одну обязательно).

Более общий случай представляет игра Мура, которую также можно назвать k-ним. Правила её те же, что и в обычном ниме (1-ним), но здесь разрешается бать фишки из любого количества кучек, не превосходящего k.

Ещё одна подобная игра – Кегли. В ней фишки разложены в ряд, и при каждом ходе убирается одна какая-либо фишка или две соседние. При этом ряд может разбиться на два меньших ряда. Выигрывает тот, кто возьмёт последнюю фишку. Обобщённая вариация этой игры известна под именем игры Витхоффа.

Есть интересная вариация игры ним под названием “звёздный ним”. Она довольно проста, но стратегия в ней видна не сразу. Играют в эту игру на звездообразной фигуре, изображённой на рис. 1, слева. Поставьте по одной фишке на каждую из девяти вершин звезды. Игроки A и B делают ходы по очереди, снимая при каждом ходе либо одну, либо две фишки, соединённые отрезком прямой. Тот, кто снимает последнюю фишку выигрывает.

 

 

 

 

 

 

 

 

 

 

 

Рекомендуем скачать другие рефераты по теме: доклад по обж, законодательство реферат.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата