Детерминированная игра с полной информацией?

[ramazanov.iteam]

Пишу программу, которая позволяла бы играть игры типа шахмат, для которых справедливо следующее:
1) в этой игре игрокам не разрешается вступать в сговор друг с другом
2) в эту игру играют 2 игрока, выигрыши которых противоположны
3) для обоих сторон отсутствует элемент неопределенности (порядок ходов строго определён, начальная позиция всегда одна и та же и она полностью известна обоим игрокам, отсутствует элемент случайности, каждая позиция в игре одинаково и в полной мере известен обоим игрокам, количество вариантов хода в любой позиции - это конечное число)
4) Нельзя бесконечно играть. Строго определено, кто, когда, как выигрывает. Всего исходов игры 3: первый игрок выиграл, второй игрок выиграл и ничья. Также строго определено, сколько раз может повторяться одна и та же позиция. Назовём это число лимитом на повтор позиции. При достижении этого лимита, игра тут же заканчивается победой одной из сторон или ничьей. Это тоже строго оговорено в правилах игры
5) Если наступает такая позиция, что невозможно сделать ход, то игра немедленно останавливается победой одного из игроков или ничьей

Понятно, что, для таких игр количество позиции ограничено и можно построить граф игры, передвигаясь по которому игроки не попадут в бесконечный цикл, то есть игра когда-нибудь закончится и существует беспроигрышная стратегия хотя бы для одного из игроков.

А теперь собственно вопрос: как обозвать такие игры? Детерминированные игры с полной информацией? Обхватывает ли это определение полностью эти игры?

[atlakatl]

Они так и называются: детерминированные игры с полной информацией.
Игры с кубиками: недетерминированные игры с полной информацией.
Карточные игры: недетерминированные игры с неполной информацией.

[ramazanov.iteam]

atlakatl в сообщении #1217730 писал(а):

Они так и называются: детерминированные игры с полной информацией.
Игры с кубиками: недетерминированные игры с полной информацией.
Карточные игры: недетерминированные игры с неполной информацией.

Ок

[pppppppo_98]

Камрад - не знаю чем это может помочь, но как-то мне попадалась книженция (и я ее прочел) аксиома выбора и аксиомы детерминированности, о замене аксиомы выбора теории множеств аксиомой детерминированности, причем доказано, что эти аксиомы несовместимы. И что-то если мне память не отказывает - выигрышная стратегия существует всегда - так утверждает аксиома детерминированности... То есть, если добавить к правилам игры правило о том, что одна из сторон имеет право выбора хода - то эта сторона заведомо имеет выигрышную стратегию, если конечно это аксиома верна

[Geen]

atlakatl в сообщении #1217730 писал(а):

Они так и называются: детерминированные игры с полной информацией.

Наверное надо добавить "конечные", "двух игроков" и "с нулевой суммой"

[Iam]

pppppppo_98 в сообщении #1217796 писал(а):

... То есть, если добавить к правилам игры правило о том, что одна из сторон имеет право выбора хода - то эта сторона заведомо имеет выигрышную стратегию, если конечно это аксиома верна

Это относится, в частности, к играм, у которых сдвиг очередности хода эквивалентен смене позиций.

Для других случаев это далеко не так. Пусть n игроков, распределенных по двум коалициям, сидят за круглым столом и двигают фишку по дугам графа. Проигрывает коалиция, которая не может сделать ход.

В статье из Дискретной математики за 2016 г. (Циклические разложения множеств, разделяющие орграфы и циклические классы игр с гарантированным выигрышем) построены конструкции позиционных игр на графах, в которых, например, коалиция из 9 игроков всегда выигрывает у коалиции из 64 игроков независимо от того, какой игрок (из 73) начинает игру.