Uproszczona wersja Zwycięzca gry karcianej

Zadałem ten problem w MathOverflow , bez zadowalającej odpowiedzi.

Rozważ następującą grę dla dwóch graczy, która jest uproszczeniem gry karcianej o nazwie Zwycięzca . (Poniższe sformułowanie zostało zaczerpnięte z komentarza Guillaume Brunerie na temat MathOverflow.)

Jest dwóch graczy A i B. Każdy gracz ma zestaw kart (podzbiór $\{1,\dots,n\}$ ), widoczne z obu graczy. Celem gry jest pozbycie się własnych kart. Pierwszy gracz zagrywa dowolną kartę na stole, a następnie drugi gracz musi zagrać (ściśle) większą kartę i tak dalej, dopóki jeden z graczy nie będzie mógł zagrać lub zdecyduje się spasować. Następnie karty na stole są odrzucane, a drugi gracz zaczyna od nowa, zagrywając dowolną kartę (po której nastąpi większa karta). I tak dalej, dopóki jeden z dwóch graczy nie skończy kart i nie wygra gry.

Chcę poznać najlepszą strategię dla graczy (jeśli uda mu się wygrać).

Formalna definicja

Oznacz przez $w(i,A,B)$ konfiguracja gry, w której znajduje się zestaw kart pierwszego gracza $A$ , zestaw kart drugiego gracza to $B$ , a największa karta na stole to $i$ , gdzie $i=0$ oznacza, że na stole nie ma karty. Chciałbym algorytm obliczyć, podany $i,A,B$ , czy pierwszy gracz ma zwycięską strategię w konfiguracji $w(i,A,B)$ .

Formalnie chciałbym, aby algorytm obliczył funkcję $f$ zdefiniowane w następujący sposób:

Pozwolić $\mathbb{Z}_n = \left\{1, 2, \cdots, n\right\}$ , $\mathrm{Bool} = \left\{\mathrm{False}, \mathrm{True}\right\}$ .

Funkcjonować $f:\;\left\{ 0, 1, \cdots, n \right\} \times 2^{\mathbb{Z}_n} \times 2^{\mathbb{Z}_n} \to \mathrm{Bool}$

gdzie

f (i, A, B) = {\begin{cases} F a l s e & B = \emptyset \\ T r u e & B \neq \emptyset \land \exists j \in A : j > i, f (j, B, A - {j}) = F a l s e \\ T r u e & B \neq \emptyset \land f (0, B, A) = F a l s e \\ F a l s e & otherwise \end{cases}

$f ( i, A, B ) = \begin{cases} \mathrm{False} & B = \emptyset \\ \mathrm{True} & B \ne \emptyset \land \exists j \in A: j > i, f(j, B, A - \left\{j\right\}) = \mathrm{False} \\ \mathrm{True} & B \ne \emptyset \land f(0, B, A) = \mathrm{False} \\ \mathrm{False} & \textrm{otherwise} \end{cases}$

Złe strategie

Oto kilka niewłaściwych strategii:

Zawsze graj najmniejszą kartą. Pozwolić $n = 3, A = \{1,3\}, B = \{2\}$ , zwycięska strategia dla gracza A w konfiguracji $w(0, A, B)$ jest grać w karty $3$ . Jeśli gracz A zagrywa kartę 1, przegrywa.
Zagraj najmniejszą kartą, chyba że inny gracz ma tylko jedną kartę. Jest to strategia silniejsza niż strategia 1, ale jest również błędna. Pomyśl tylko o konfiguracji $w(0, \{1, 4, 6, 7\}, \{2, 3, 5, 8\})$ . Jeśli gracz A zastosuje strategię 2, przegra: $1\rightarrow2\rightarrow4\rightarrow5\rightarrow6\rightarrow8\rightarrow\textrm{pass}\rightarrow3$ , więc gracz A przegrywa.

gt.game-theory card-games

— Yai0Phah
źródło

To pytanie jest interesujące, ale spróbuj uczynić je tak czytelnym, jak to możliwe. Na przykład, nie musisz kopiować dosłownie komentarza Guillaume Brunerie, w tym części „Myślę, że to gracz A powinien być znany graczowi…”, która różni się od założenia w twoim pytaniu i może tylko mylić czytelników. Rozważ też usunięcie pierwszego sformułowania trzech: drugi sformułowanie zapewnia intuicyjne zrozumienie, trzeci sformalizowanie definicji i nie sądzę, że pierwszy służy jakimkolwiek celom.

— Tsuyoshi Ito

Być może najlepszym sposobem na analizę tego jest napisanie programu, który obliczy optymalne ruchy dla dowolnej pozycji i poszuka wzorców. Nie ma a priori powodu, że ta gra powinna mieć fajną strategię.

— Peter Shor,

Chciałbym zacząć od strategii z małą liczbą kart i zacząć od tego. Na przykład, jeśli każdy gracz ma 2 karty, wygrywa ten, który ma najwyższą kartę, niezależnie od tego, który gracz ma następną turę. Zagrywa najwyższą kartę, drugi gracz musi spasować, a następnie zagrywa swoją ostatnią kartę.

— Joe

Czy ktoś może mi pomóc w przeprojektowaniu opisu GB, tak aby był zgodny z PostScript 1? Przykro mi, że nie jestem native speakerem i opisanie tak złożonej gry jest poza moimi umiejętnościami.

— Yai0Phah

@Tsuyoshi: Jeśli gracz A zawsze zagrywa najmniejszą kartę, gracz B wygrywa. Jeśli gracz A zagrywa kartę 1 i nie zawsze zagrywa najmniejszą kartę, gracz A może wygrać. Oznacza to, że zawsze istnieje mniejszy kontrprzykład dla strategii 2, która zawsze wygrywa.

— Peter Shor

To prawdopodobnie powinien być komentarz, ale jest za długi.

Pokrewną grę studiowali Jeff Kahn, Jeff Lagarias i Hans Witsenhausen w serii artykułów Single-Suit Two-Person Card Play I, II, III oraz On Laskar's Card Game. W grze, którą studiowali, każdy gracz ma $n$ karty, rozdawane z $2n$ karty ponumerowane $1$ $\ldots$ $2n$ . Każda lewa składa się z dwóch kart, wyższa karta wygrywa lewę, a zwycięzca prowadzi. Celem jest jak najwięcej lew.

Udowodnili szereg interesujących faktów na temat optymalnej strategii, ale nie byli w stanie znaleźć wydajnego algorytmu dla optymalnej gry, a także nie byli w stanie udowodnić, że była trudna do pokonania.

W grze z misère , w której każda osoba próbuje podjąć jak najmniejszą liczbę lew, była w stanie podać optymalną strategię.

W przeważającej części wyniki te uzyskano najpierw patrząc na wyniki programu komputerowego, który znalazł optymalną strategię dla małych instancji, a następnie szukając wzorców do uzyskania domniemań, a na koniec potwierdzając te domysły. Podejrzewam, że byłoby to również owocne podejście do gry PO.

— Peter Shor
źródło