2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Детерминированная игра с полной информацией?
Сообщение21.05.2017, 07:09 
Аватара пользователя
Они так и называются: детерминированные игры с полной информацией.
Игры с кубиками: недетерминированные игры с полной информацией.
Карточные игры: недетерминированные игры с неполной информацией.

 
 
 
 Re: Детерминированная игра с полной информацией?
Сообщение21.05.2017, 08:05 
atlakatl в сообщении #1217730 писал(а):
Они так и называются: детерминированные игры с полной информацией.
Игры с кубиками: недетерминированные игры с полной информацией.
Карточные игры: недетерминированные игры с неполной информацией.

Ок

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

 
 
 
 Re: Детерминированная игра с полной информацией?
Сообщение21.05.2017, 13:24 
Аватара пользователя
atlakatl в сообщении #1217730 писал(а):
Они так и называются: детерминированные игры с полной информацией.

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

 
 
 
 Re: Детерминированная игра с полной информацией?
Сообщение21.05.2017, 15:27 
pppppppo_98 в сообщении #1217796 писал(а):
... То есть, если добавить к правилам игры правило о том, что одна из сторон имеет право выбора хода - то эта сторона заведомо имеет выигрышную стратегию, если конечно это аксиома верна

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

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

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group