Сложность гекса со случайным порядком поворота.

Я думал о варианте гексагона , где вместо двух игроков поочередно делают ходы, каждый ход, выбранный случайным образом, делает ход. Насколько сложно определить шансы каждого игрока на победу? Эта проблема, очевидно, есть в PSPACE, но не может ли она быть NP-сложной, а тем более PSPACE-полной. Трудности возникают из-за того, что случайность не позволяет игроку сделать выбор между вариантами; если этому игроку повезло, он получает достаточно ходов, два берут оба варианта, а если игроку не повезло, оппонент получает достаточно ходов, чтобы заблокировать оба варианта. С другой стороны, я не могу придумать какие-либо алгоритмы полиномиального времени для этого.

cc.complexity-theory board-games Итай Бар-Натан
источник

Пусть S будет n-битной двоичной строкой, представляющей, какой игрок принимает ход. В худшем случае вы восстанавливаете стандартную игру с гексами, если случайная последовательность 010101 ... или 101010 .... Таким образом, ваша проблема, по крайней мере, так же сложна, как у стандартного гекса.

Мухаммед Аль-Туркистани

Есть две возможные интерпретации этой игры. (1) Перед каждым ходом игроки подбрасывают монету, чтобы определить, кто будет следующим. (2) В начале игры игроки подбрасывают монету

раза (на доске размера

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

n^{2}

$n^2$

n

$n$

Питер Шор

Действительно, я имею в виду первое толкование, что монета подбрасывается прямо перед ходом. Кроме того, я заметил еще одну двусмысленность в моем вопросе: точность, с которой я хочу знать вероятность. Хотя при постановке вопроса у меня сложилось впечатление, что я хочу знать вероятность с полной точностью, но я хочу знать только вероятность с логарифмической точностью. Как и разница между PP и BPP, последнее кажется более полезным и естественным.

Итай Бар-Натан

@Itai: Еще один вопрос. Почему вы утверждаете, что это явно в PSPACE? Мне кажется, что это рецензируемая игра, что означало бы, что естественная теоретическая сложность верхней границы - EXPTIME. Смотрите Фейдж и Килиан, «Делая игры короткими».

Питер Шор

@tukistany Бесполезный не означает тривиальный!

Джефф

Ответы:

Возможно, вы захотите взглянуть на статью «Хекс в случайном порядке и другие отборочные игры» Ювала Переса, Одеда Шрамма, Скотта Шеффилда и Дэвида Уилсона. Из введения:

«Шестнадцатеричный ход - это то же самое, что и обычный шестнадцатеричный, за исключением того, что вместо чередующихся ходов игроки бросают монету перед каждым ходом, чтобы решить, кому достанется следующий камень. Хотя обычный шестнадцатеричный код, как известно, сложно проанализировать, оптимальная стратегия для рандома -Вернуть Hex оказалось очень просто. "

Так что, действительно, ваша интуиция была права: это будет в BPP (или, возможно, P).

Питер Шор
источник

Я просто поражен, что люди действительно работали над этим :) Хорошая ссылка!

Суреш Венкат

Это действительно хорошее доказательство тоже. Я думаю, что слышал, как Скотт Шеффилд упоминал об этом в одном из своих выступлений (но потом я полностью забыл об этом, пока он не появился в Google).

Питер Шор

Кроме того, на сайте Дэвида Уилсона действительно есть приложение, которое позволяет вам играть в Hex со случайным ходом (я полагаю, против их опубликованной стратегии): dbwilson.com/#software

Энди Друкер

Во время своего последнего визита в Израиль, вдохновленного статьей PSSW, Одед Шрамм и я сыграли немало раундов случайных шахмат, чтобы понять, что это не особенно интересная игра.

Гил Калай

Оказывается, существует замечательная связь (благодаря Дэвиду Ричману) между играми со случайным ходом и играми со ставками , где игроки делают ставки на следующий ход; см. arxiv.org/pdf/0812.3677.pdf и users.math.yale.edu/~sp547/pdf/Discrete-bidding-games.pdf Это соединение позволяет по существу оптимально играть в торгах Hex, используя работу Переса и др. Мне это нравится, потому что в играх со ставками, по крайней мере, якобы, нет удачи, и я думаю, что торги в Hex были бы более приятными, чем в игре со случайным ходом. (Однако указывать цену за каждый ход может быть невыносимо трудной задачей.)

Энди Друкер