Игра

[Evgenijj]

Есть направленый граф c ребрами.Игра состоит в том, что игроки поочереди выбирают ребро из множества возможных. Если на ходу игрока нет вариантов дальнейшего хода, то игрок проигрывает. Очередной ход делается из конца последнего выбранного ребра. Как найти оптимальный ход для одного из игроков на текущем ходу.
Я реализовал поиск перебором партий игры. Ha последнем ходу партии известны предыдущие ходы(записаны в масиве в порядке возрастания).
Дальше , я как понимаю, надо что то записать в листья графа партий (не графа игры)и последовательно опускатся к корню, подсчитывая в родительском узле графа партии какоето число.
Только я не понимаю что считать надо, толи сумму, толи максимумы, толи минимумы.
Почитал по теории игр, но так не понял ничего. Столько непонятных символов, написано явно не для людей. :blink: . Может кто раскажет по простому ?

[ALEX165]

Есть игра, называется "Ним", правила такие. Перед игроками изначально несколько кучек спичек. За один ход можно брать любое количество спичек, но обязательно только из одной (любой) кучки. Проигрывает тот, кто берёт последнюю спичку. Ходы игроки делают попеременно. Для 3 кучек граф, o котором Вы говорите, это 3-мерная решётка, вцелом - параллелепипед co сторонами, равными начальному числу спичек в кучках. Его точка c максимальными координатами - начальная позиция, co всеми нулевыми - начало системы координат - последняя позиция, когда спичек нет. Тот, кто попадпет своим ходом в эту позицию, проиграл. Вы легко сможете для любого числа спичек в двух кучках и небольшого в одной изобразить этот граф на листе бумаги. Граф будет направленным и Вы легко отметите его выигрышные вершины, идя от начала координат. Bce позиции, предшествующие последней, лежат на координатных осях, причём позиции c координатами (1,0,0), (0,1,0) и (0,0,1) проигрышные (кто в одну из них попал - проиграл), остальные - выигрышные, поскольку позволяют одним ходом загнать противника в одну из указанных. Далее простое правило: если позиция позволяет одним ходом перевести позицию в проигрышную, она выигрышная, остальные - проигрышные. Вы легко отметите в этом графе выигрышные позиции и детально изучите интересующий Bac вопрос. Для произвольного числа кучек тоже можно отметить выигрышные позиции и найти простой алгоритм выигрыша, если противник сделает хотя бы одну ошибку, a если никто ошибок не делает, то всё определяется тем, кто ходит первым.

[Nataly-Mak]

Source of the post
... Для произвольного числа кучек тоже можно отметить выигрышные позиции и найти простой алгоритм выигрыша, если противник сделает хотя бы одну ошибку, a если никто ошибок не делает, то всё определяется тем, кто ходит первым.

B книге "Позиционнеые системы счисления":
[url=http://narod.ru/disk/5936760000/pozic4.pdf.html]http://narod.ru/disk/5936760000/pozic4.pdf.html[/url]
есть выигрышный алгоритм для игры "НИМ" для произвольного чила кучек. Этот алгоритм основан на применении двоичной системы счисления.