Analiza zmodyfikowanej wersji gry karcianej „War”

Prostą grą, w którą zwykle bawią się dzieci, w grę wojenną grają dwie osoby korzystające ze standardowej talii 52 kart do gry. Początkowo talia jest tasowana i wszystkie karty rozdawane są dwóm graczom, dzięki czemu każda z nich ma 26 losowych kart w losowej kolejności. Zakładamy, że gracze mogą badać (ale nie zmieniać) obie talie, aby każdy z nich znał karty i kolejność kart w obu taliach. Zazwyczaj jest to notatka wykonywana w praktyce, ale nie zmienia to niczego w sposobie grania i pomaga zachować tę wersję pytania całkowicie deterministyczną.

Następnie gracze odkrywają najwyższe karty ze swoich talii. Gracz, który odkrywa większą kartę (zgodnie ze zwykłą kolejnością: 2, 3, 4, 5, 6, 7, 8, 9, 10, walet, królowa, król, as) wygrywa rundę, umieszczając pierwszą swoją kartę ( wysoka karta) u dołu jego talii, a następnie karta przeciwnika (niska karta) u dołu talii (zazwyczaj kolejność tego nie jest egzekwowana, ale aby zachować pierwszą wersję tego pytania deterministyczną, taką jak wykonanie zostanie wykonane).

W przypadku remisu każdy gracz odkrywa cztery dodatkowe karty z wierzchu talii. Jeśli czwarta karta pokazana przez jednego gracza jest wyższa niż czwarta karta pokazana przez innego gracza, gracz z wyższą czwartą kartą wygrywa wszystkie karty zagrane podczas rozstrzygnięcia remisu, w którym to przypadku karty zwycięzcy są najpierw umieszczane na dole talia zwycięzcy (w kolejności pierwsze wejście, pierwsze wyjście; innymi słowy, starsze karty są umieszczane na dole jako pierwsze), a następnie karty przegranych (w tej samej kolejności).

W przypadku kolejnych remisów proces powtarza się do momentu wyłonienia zwycięzcy remisu. Jeśli jeden gracz zabraknie kart i nie może kontynuować zerwania remisu, gracz, który nadal ma karty, zostaje ogłoszony zwycięzcą. Jeśli obaj gracze wyczerpią karty, aby zagrać w tym samym czasie, gra zostanie uznana za remis.

Rundy są rozgrywane, dopóki jeden gracz nie skończy kart (tj. Nie ma już kart w swojej talii), w którym to momencie gracz, który nadal ma karty, zostaje ogłoszony zwycięzcą.

Jak opisano grę do tej pory, ani umiejętność, ani szczęście nie są zaangażowane w ustalenie wyniku. Ponieważ istnieje skończona liczba permutacji 52 kart, istnieje skończona liczba sposobów, w jakie talie mogą być początkowo rozdawane, i wynika z tego (ponieważ jedyną informacją o stanie w grze jest aktualny stan talii obu graczy ) wynik każdej konfiguracji gry można ustalić z góry. Z pewnością możliwe jest, aby wygrać grę wojenną, a tym samym przegrać. Pozostawiamy również otwartą możliwość, że gra wojenna może doprowadzić do remisu lub nieskończonej pętli; w przypadku całkowicie deterministycznej wersji opisanej powyżej może tak być lub nie.

Kilka odmian gry, które starają się uczynić ją bardziej interesującą (i nie, nie wszystkie wymagają przekształcenia w grę do picia). Jednym ze sposobów, które postanowiłem uczynić grę bardziej interesującą, jest umożliwienie graczom deklarowania automatycznych „atutów” w niektórych rundach. W każdej rundzie każdy gracz (lub obaj gracze) może zadeklarować „atut”. Jeśli jeden gracz zadeklaruje „atut”, ten gracz wygrywa rundę niezależnie od zagranych kart. Jeśli obaj gracze ogłaszają „atut”, rundę traktuje się jako remis i gra jest odpowiednio kontynuowana.

Można sobie wyobrazić różnorodne zasady ograniczające zdolność graczy do atutowania (nieograniczone atutowanie zawsze prowadzi do gry w remis, ponieważ gracze atutują w każdej turze). Proponuję dwie wersje (tuż nad głową; prawdopodobnie bardziej interesujące wersje w tym stylu są prawdopodobnie możliwe) War oparte na tym pomyśle, ale wykorzystujące różne mechanizmy ograniczania atutów:

1. Częstotliwość-War: Gracze mogą tylko atutem, jeśli nie zostały one zmyślone w poprzednich rund.$k$
2. Revenge-War: Gracze mogą atutować tylko wtedy, gdy nie wygrali rundy w poprzednich rundach.$k$

Teraz pytania, które dotyczą każdej z opisanych powyżej wersji:

1. Czy istnieje strategia taka, że ​​w przypadku niektórych zestawów możliwych początkowych konfiguracji gry gracz, który z niej korzysta, zawsze wygrywa (strategia silnie wygrywająca)? Jeśli tak, jaka jest ta strategia? Jeśli nie, dlaczego nie?
2. Czy istnieje strategia taka, że ​​w przypadku niektórych zestawów możliwych początkowych konfiguracji gry gracz, który ją stosuje, zawsze może wygrać lub wymusić remis (strategia wygrywająca)? Jeśli tak, jaka jest ta strategia? Jeśli nie, dlaczego nie?
3. Czy ich początkowe konfiguracje gry nie pozwalają na wygraną (np. Gracz stosujący dowolną ustaloną strategię zawsze może zostać pokonany przez gracza stosującego ustaloną strategię )? Jeśli tak, jakie są i wyjaśnić?$S$$S'$

Mówiąc wprost, myślę o „strategii” jako ustalonym algorytmie, który określa, w których rundach gracz korzystający ze strategii powinien przebijać. Na przykład algorytm „atut, kiedy możesz” to strategia, a algorytm (algorytm heurystyczny). Innym sposobem, o który pytam, jest:

Czy istnieje jakaś dobra (lub dająca się udowodnić optymalna) heurystyka do grania w te gry?

Doceniamy odniesienia do analiz takich gier (nie znam żadnej analizy tej wersji Wojny ani zasadniczo równoważnych gier). Wyniki dla dowolnego są interesujące i doceniane (zauważ, że w obu przypadkach prowadzi do nieograniczonego przebijania, o czym już mówiłem).$k$$k=0$

Jeśli dobrze rozumiem, wszystkie informacje o grze są dostępne dla obu graczy. Oznacza to, że początkowa konfiguracja i wszystkie możliwe ruchy są znane obu graczom (głównie dlatego, że obaj gracze mogą patrzeć na karty drugiego gracza). To sprawia, że ​​gra jest grą o doskonałej informacji o sumie zerowej. Istnieje zatem idealna strategia dostępna dla obu graczy, która osiągnęłaby najlepszy wynik w każdej grze dla tego gracza. Zostało to udowodnione w 1912 r. Przez niemieckiego matematyka Ernsta Zermelo.

Nie wiem, na czym polega strategia, ale można sobie wyobrazić zbudowanie dla niej dużego drzewa gry i skłonienie komputera do znalezienia strategii za pomocą algorytmu min-max .

Drzewo każdej gry miałoby zrootować ręce dwóch graczy. Gałęzie drzewa odpowiadają ruchom graczy. W najprostszym przypadku polegają one po prostu na ustanowieniu wymaganych kart. W bardziej zaawansowanych przypadkach można wykonać ruch „atutowy”. Wewnętrzne węzły drzewa rejestrują aktualną konfigurację kart wraz z wszelkimi informacjami na temat stanu „atutów”. Liście drzewa odpowiadają pozycjom końcowym gry, które będą oznaczone, powiedzmy, +1 dla wygranej dla Gracza 1, 0 dla remisu i -1 dla wygranej dla Gracza 2. Na razie ignoruj ​​zapętlanie gier.

Teraz algorytm min-max będzie działał w następujący sposób (z perspektywy Gracza 1). Załóżmy, że patrzy na węzeł, w którym Gracz 1 wykonuje ruch, a poniższe węzły są opatrzone adnotacjami +1, 0 lub -1 ( wypłata) wraz z wyborami, jakich musi dokonać gracz, aby uzyskać określony wynik. Gracz 1 po prostu wybiera węzeł o największej wypłacie, rejestruje tę wypłatę i wybór wymagany do jej uzyskania. W przypadku węzła, w którym gracz 2 wykonuje ruch, wybierany jest węzeł o minimalnej wypłacie, a wybór jest rejestrowany. Odzwierciedla to, że Gracz 2 dąży do jak najniższego wyniku, aby wygrać. Jest to propagowane do drzewa. Wybory zapisane w każdym węźle odpowiadają najlepszej strategii, jaką może wybrać gracz. Ostateczna wypłata określa, kto wygra. Jest to ostatecznie funkcja pod względem wypłaty, chociaż dokładny wybór ruchów może się różnić.

Potencjalnie zapętlone konfiguracje można włączyć do drzewa gry, po prostu dodając pętle, które wracają do już widzianej konfiguracji (podczas przetwarzania z góry). Dla takich węzłów bierzesz największy stały punkt, jeśli jest to węzeł, w którym gra Gracz 1, a najmniej stały punkt, gdy Gracz 2 gra.

Zauważ, że gdybyś nie założył, że obaj gracze mogą badać obie talie, to podejście nie miałoby zastosowania. Gra wymagałaby wtedy szansy, a wybrana strategia byłaby specyficzna dla gry.

To, czy dla jednego z graczy istnieje silna, czy słaba strategia wygrywająca, zależy od wyniku algorytmu min-max zastosowanego do wszystkich drzew. Ale z pewnością jest ich wiele .... Obliczenie drzewa dla jednego jest prawdopodobnie dość łatwe, ponieważ gra nie ma zbyt wielu wyborów.