Złożoność heksów z losową kolejnością tur.

Myślałem o wariancie heksowym , w którym zamiast dwóch graczy wykonujących ruchy na przemian, każda kolej losowo wybrana przez gracza wykonuje ruch. Jak trudno jest określić szanse wygranej każdego gracza? Ten problem występuje oczywiście w PSPACE, ale nie może być trudny do NP, a tym bardziej kompletny w PSPACE. Trudności wynikają z tego, że losowość uniemożliwia graczowi zmuszenie do dokonania wyboru spośród opcji; jeśli ten gracz ma szczęście, otrzymuje wystarczającą liczbę ruchów, dwie biorą obie opcje, a jeśli gracz ma pecha, przeciwnik dostaje wystarczającą liczbę ruchów, aby zablokować obie opcje. Z drugiej strony nie mogę wymyślić żadnych algorytmów czasu wielomianowego.

cc.complexity-theory board-games Itai Bar-Natan
źródło

Niech S będzie n-bitowym ciągiem binarnym, który reprezentuje, który gracz bierze turę. W najgorszym przypadku odzyskujesz standardową grę heksadecymalną, jeśli losowa sekwencja to 010101 ... lub 101010 .... Twój problem jest co najmniej tak trudny jak standardowy hex.

Mohammad Al-Turkistany

Istnieją dwie możliwe interpretacje tej gry. (1) Tuż przed każdą turą gracze rzucają monetą, aby ustalić, kto będzie następny. (2) Na początku gry gracze rzucają monetą

razy (na planszy rozmiaru

) i używają tej sekwencji do swoich rund. Turkistany zdają się przyjmować model (2); oryginalne pytanie jest dwuznaczne, ale sądzę, że z niektórych jego słów Itai pyta o (1), co może być łatwiejsze niż standardowe hex.

n^{2}

$n^2$

n

$n$

Peter Shor

Rzeczywiście mam na myśli pierwszą interpretację, że moneta jest odwracana tuż przed ruchem. Dodatkowo w swoim pytaniu zauważyłem inną dwuznaczność: precyzję, z jaką chcę poznać prawdopodobieństwo. Podczas gdy miałem wrażenie, że zadałem pytanie, chcę poznać prawdopodobieństwo z całkowitą precyzją, ale chcę poznać tylko prawdopodobieństwo z precyzją logarytmiczną. Podobnie jak różnica między PP i BPP, później wydaje się bardziej użyteczny i naturalny.

Itai Bar-Natan

@Itai: Kolejne pytanie. Dlaczego twierdzisz, że jest to oczywiście w PSPACE? Wydaje mi się, że jest to gra referencyjna, co oznaczałoby, że górna granica teoretycznej złożoności to EXPTIME. Zobacz Feige and Kilian, „Making Games Short”.

Peter Shor,

@tukistany Bezużyteczne NIE oznacza, że jest trywialne!

Jeffε

Odpowiedzi:

Warto przyjrzeć się artykułowi „Losowa kolejna klątwa i inne gry selekcyjne” autorstwa Yuvala Peresa, Odeda Schramma, Scotta Sheffielda i Davida Wilsona. Od wprowadzenia:

„Klątwa o losowej kolejce jest taka sama jak zwykła klątwa, z tą różnicą, że zamiast naprzemiennych tur, gracze rzucają monetą przed każdą turą, aby zdecydować, kto umieści następny kamień. Chociaż zwykły klątwę jest bardzo trudny do przeanalizowania, optymalna strategia losowa -Turn Hex okazuje się bardzo prosty. ”

Rzeczywiście, twoja intuicja była słuszna: będzie w BPP (a może P).

Peter Shor
źródło

Dziwi mnie to, że ludzie naprawdę nad tym pracowali :) Niezłe referencje!

Suresh Venkat

To też naprawdę niezły dowód. Myślę, że słyszałem, jak Scott Sheffield wspomniał o tym w jednym ze swoich wystąpień (ale potem zupełnie o tym zapomniałem, dopóki nie pojawił się w Google).

Peter Shor,

Ponadto na stronie Davida Wilsona znajduje się aplikacja, która pozwala ci grać w losowo zakręcone heksy

Andy Drucker

Podczas swojej ostatniej wizyty w Izraelu, zainspirowanej artykułem PSSW, Oded Schramm i ja zagraliśmy kilka rund losowych szachów, aby zrozumieć, że nie jest to szczególnie interesująca gra.

Gil Kalai,

Okazuje się, że istnieje niezwykły związek (z powodu Davida Richmana) między grami losowymi i grami licytacyjnymi , w których gracze licytują następny ruch; zobacz arxiv.org/pdf/0812.3677.pdf i users.math.yale.edu/~sp547/pdf/Discrete-bidding-games.pdf To połączenie pozwala na optymalną grę w zasadzie licytacji Hex, wykorzystując pracę Peres et al. Podoba mi się to, ponieważ licytowanie gier jest, przynajmniej pozornie, pozbawione szczęścia i myślę, że licytacja Hexa byłaby bardziej satysfakcjonująca w grze niż Hexa losowego. (Licytowanie każdej tury może być jednak irytująco wymagającym zadaniem.)

Andy Drucker