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

Złe strategie

Oto kilka niewłaściwych strategii:

1. 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.
2. 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.

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.