Игра на графе

- обобщение позиционной игры на случай, когда граф позиций не древовидный, а произвольный. Частным случаем И. на г. является игра Ним - антагонистическая игра с полной информацией, в к-рой для каждой окончательной позиции указано, выигрывает или проигрывает последний ходивший игрок. В простейшем варианте игра Ним состоит в следующем: имеется несколько кучек фишек, и игроки поочередно удаляют не менее одной фишки, причем каждый раз удаляемые фишки должны быть взяты из одной кучки. Игрок, удаливший последнюю фишку, выигрывает партию. Решение игры Ним состоит в описании для каждого игрока множества выигрышных позиций, т. е. таких позиций, начиная с к-рых данный игрок может выиграть при любой стратегии противника. Множество выигрышных позиций совпадает с множеством нулей функции Гранди (функция g, сопоставляющая каждой вершине k графа Г такое неотрицательное целое число g(k), что [img: http://localhost:8080/file/021001-79.jpg] Оно обладает свойствами внутренней и внешней устойчивости и в этом отношении аналогично понятию Н-М- решения в кооперативных играх.