ИГРА НА ГРАФЕ


ИГРА НА ГРАФЕ

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

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

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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ИГРА НА ГРАФЕ" в других словарях:

  • ФК «Ньюкасл Юнайтед» в сезоне 2011/2012 — Ньюкасл Юнайтед Сезон 2011/12 Тренер …   Википедия

  • Crysis 2 — Обложка игры Разработчики …   Википедия

  • Игрок — (Player) Определение биржевого игрока, условия игры на бирже Информация об определении биржевого игрока, игра на бирже, покупка и продажа акций Содержание Содержание Определения описываемого предмета Истоки игры на Зачем играть на бирже Как… …   Энциклопедия инвестора

  • Фондирование — (Funding) Фондирование это процесс финансирования активных операций банка Ставка и коэффициент фондирования при расчетах матрицы, целевое фондирование и его источники Содержание >>>>>>>>> …   Энциклопедия инвестора

  • Сборная Германии по футболу — Прозвища Die Nationalelf, Bundesteam, Bundesmannschaft, Bundesmaschine, Deutschen Конфедерация УЕФА Федерация …   Википедия

  • Сленг участников интеллектуальных игр/Temp — Сленг участников интеллектуальных игр (далее  сленг)  набор слов, чаще всего  общеупотребительных, используемый в кругу игроков с другим значением.Сленг можно условно разделить [ [http://www.krylenko.com/chgk/library/znatoky/s ch. Б. Бурдой] ] .… …   Википедия

  • Гарринча — Гарринча …   Википедия

  • Postal 2 — Обложка диска Postal 2 Разработчик …   Википедия

  • Пирс, Пол — Пол Пирс Paul Pierce …   Википедия

  • Покер на костях — У этого термина существуют и другие значения, см. Покер (значения). Компьютерная версия Покера на костях  « …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.