Игра на дереве, рубка ветки - PullRequest
12 голосов
/ 05 марта 2011

У нас есть лес укоренившихся деревьев.Два игрока делают чередующиеся ходы по следующему правилу: один ход - разрезать вершину и всех ее потомков.Игрок, который делает последний ход (не осталось вершин), выигрывает.

Как мы можем вычислить функцию Гранди для позиций в игре?

Предположим, у нас есть деревья и нам нужно сказать, есть ли текущая позициявыигрывает или проигрывает?

1 Ответ

4 голосов
/ 20 апреля 2011

Это игра Hackenbush . Я настоятельно рекомендую эту статью , которая с большой ясностью описывает числа Гранди и подробно обсуждает Хакенбуша в конце.

...