ИГРА НА ГРАФЕ

- обобщение позиционной игры на случай, когда граф позиций не древовидный, а произвольный. Частным случаем И. на г. является игра Ним - антагонистическая игра с полной информацией, в к-рой для каждой окончательной позиции указано, выигрывает или проигрывает последний ходивший игрок. В простейшем варианте игра Ним состоит в следующем: имеется несколько кучек фишек, и игроки поочередно удаляют не менее одной фишки, причем каждый раз удаляемые фишки должны быть взяты из одной кучки. Игрок, удаливший последнюю фишку, выигрывает партию. Решение игры Ним состоит в описании для каждого игрока множества выигрышных позиций, т. е. таких позиций, начиная с к-рых данный игрок может выиграть при любой стратегии противника. Множество выигрышных позиций совпадает с множеством нулей функции Гранди (функция g, сопоставляющая каждой вершине k графа Г такое неотрицательное целое число g(k), что

Оно обладает свойствами внутренней и внешней устойчивости и в этом отношении аналогично понятию Н-М- решения в кооперативных играх.

Лит.:[1] Берж К., Общая теория игр нескольких лиц, пер. с франц., М., 1961; [2] Вouton С. L., "Ann. Math.", ser. 2, 1902, v. 3, № 1, p. 35-9.

A. H. Ляпунов.