Rozwiązana gra - Solved game

Rozwiązany gra to gra , której wynik (wygrana, przegrana lub remis ) można poprawnie przewidzieć z dowolnej pozycji, zakładając że obaj gracze grać idealnie. Pojęcie to jest zwykle stosowane do abstrakcyjnych gier strategicznych , a zwłaszcza do gier z pełną informacją i bez elementu losowego; rozwiązanie takiej gry może wykorzystać kombinatoryczną teorię gier i/lub pomoc komputerową.

Przegląd

Gra dla dwóch graczy może być rozwiązany na kilku poziomach:

Bardzo słaby
Udowodnij, czy pierwszy gracz wygra, przegra, czy zremisuje z początkowej pozycji, przy doskonałej grze po obu stronach. Może to być niekonstruktywny dowód (prawdopodobnie zawierający argument dotyczący kradzieży strategii ), który nie musi w rzeczywistości określać żadnych ruchów idealnej gry.
Słaby
Zapewnij algorytm, który zapewni zwycięstwo jednemu graczowi lub remis dla jednego z nich, przeciwko wszelkim możliwym ruchom przeciwnika, od początku gry. Oznacza to, że stwórz co najmniej jedną kompletną grę idealną (wszystkie ruchy zaczynają się do końca) z dowodem, że każdy ruch jest optymalny dla gracza, który go wykonuje.
Silny
Zapewnij algorytm, który może wykonać perfekcyjne ruchy z dowolnej pozycji, nawet jeśli popełniono już błędy po jednej lub obu stronach.

Pomimo swojej nazwy, wielu teoretyków gier uważa, że ​​„ultra-słabe” dowody są najgłębsze, najciekawsze i wartościowe. „Ultra-słabe” dowody wymagają od badacza wnioskowania o abstrakcyjnych właściwościach gry i wykazania, w jaki sposób te właściwości prowadzą do pewnych wyników, jeśli zrealizowana zostanie doskonała gra.

W przeciwieństwie do tego, „silne” dowody często następują brutalną siłą — używając komputera do wyczerpującego przeszukiwania drzewa gry, aby dowiedzieć się, co by się stało, gdyby zrealizowano idealną grę. Wynikowy dowód daje optymalną strategię dla każdej możliwej pozycji na planszy. Jednak te dowody nie są tak pomocne w zrozumieniu głębszych powodów, dla których niektóre gry można rozwiązać jako remis, a inne, pozornie bardzo podobne gry, można rozwiązać jako wygraną.

Biorąc pod uwagę zasady każdej gry dwuosobowej ze skończoną liczbą pozycji, zawsze można w banalny sposób skonstruować algorytm minimaksowy , który wyczerpująco przemierzyłby drzewo gry . Jednakże, ponieważ w przypadku wielu nietrywialnych gier taki algorytm wymagałby niewykonalnej ilości czasu, aby wygenerować ruch w danej pozycji, gra nie jest uważana za rozwiązaną słabo lub silnie, chyba że algorytm może być uruchomiony na istniejącym sprzęcie w rozsądnym czasie. Wiele algorytmów opiera się na ogromnej, wstępnie wygenerowanej bazie danych i w rzeczywistości jest niczym więcej.

Jako przykład mocnego rozwiązania, gra w kółko i krzyżyk jest możliwa do rozwiązania jako remis dla obu graczy z doskonałą grą (wynik nawet ręcznie ustalany przez uczniów). Gry takie jak nim również wymagają rygorystycznej analizy z wykorzystaniem kombinatorycznej teorii gier .

To, czy gra jest rozwiązana, niekoniecznie jest tym samym, co to, czy gra jest interesująca dla ludzi. Nawet mocno rozwiązana gra może nadal być interesująca, jeśli jej rozwiązanie jest zbyt złożone, aby można je było zapamiętać; i odwrotnie, słabo rozwiązana gra może stracić swoją atrakcyjność, jeśli zwycięska strategia jest wystarczająco prosta do zapamiętania (np. Maharajah and the Sepoys ). Bardzo słabe rozwiązanie (np. Chomp lub Hex na wystarczająco dużej planszy) generalnie nie wpływa na grywalność.

Idealna gra

W teorii gier , doskonała gra jest zachowanie lub strategia gracza, który prowadzi do najlepszego możliwego wyniku dla tego odtwarzacza niezależnie od odpowiedzi przez przeciwnika. Idealna gra dla gry jest znana, gdy gra jest rozwiązana. Na podstawie reguł gry każda możliwa pozycja końcowa może zostać oceniona (jako wygrana, przegrana lub remis). Dzięki rozumowaniu wstecznemu można rekursywnie ocenić pozycję nieostateczną jako identyczną z pozycją, która jest o jeden ruch dalej i jest najlepiej oceniana dla gracza, którego jest to ruch. Tak więc przejście między pozycjami nigdy nie może skutkować lepszą oceną poruszającego się gracza, a idealny ruch na pozycji byłby przejściem między pozycjami, które są równo oceniane. Na przykład doskonały gracz na wylosowanej pozycji zawsze dostanie remis lub wygraną, nigdy nie przegra. Jeśli istnieje wiele opcji z tym samym wynikiem, perfekcyjna gra jest czasami uważana za najszybszą metodę prowadzącą do dobrego wyniku lub najwolniejszą metodę prowadzącą do złego wyniku.

Idealną grę można uogólnić na niedoskonałe gry informacyjne , jako strategię gwarantującą najwyższy minimalny oczekiwany wynik niezależnie od strategii przeciwnika. Na przykład idealną strategią dla nożyczek do papieru skalnego byłoby losowe wybranie każdej z opcji z równym (1/3) prawdopodobieństwem. Wadą tego przykładu jest to, że strategia ta nigdy nie będzie wykorzystywać nieoptymalnych strategii przeciwnika, więc oczekiwany wynik tej strategii w porównaniu z jakąkolwiek strategią zawsze będzie równy minimalnemu oczekiwanemu wynikowi.

Choć strategia optymalna z gry może (jeszcze) nie być znana, komputer gra-playing może nadal korzystać z rozwiązań w grze z niektórych Endgame pozycjach (w postaci tablebases Endgame ), który pozwoli doskonale bawić się po jakimś punkt w grze. Programy komputerowe są dobrze znane z robienia tego.

Rozwiązane gry

Awari (gra rodziny Mancala )
Wariant Oware umożliwiający zakończenie gry „Grand slams” został mocno rozwiązane przez Henri Bal i Johna Romein na Vrije Universiteit w Amsterdamie , Holandia (2002). Każdy gracz może zmusić grę do remisu.
Pałeczki do jedzenia
Drugi gracz zawsze może wymusić wygraną.
Połącz cztery
Najpierw rozwiązany przez Jamesa D. Allena 1 października 1988 r., a niezależnie przez Victora Allisa 16 października 1988 r. Pierwszy gracz może wymusić wygraną. Silnie rozwiązany przez 8-warstwową bazę danych Johna Trompa (4 lutego 1995). Słabo rozwiązany dla wszystkich rozmiarów desek, w których szerokość+wysokość wynosi co najwyżej 15 (oraz 8×8 ​​pod koniec 2015 r.) (18 lutego 2006 r.).
Warcaby angielskie (warcaby)
Ten wariant warcabów 8×8 został słabo rozwiązany 29 kwietnia 2007 roku przez zespół Jonathana Schaeffera . Ze standardowej pozycji startowej obaj gracze mogą zagwarantować remis z perfekcyjną grą. Warcaby to największa jak dotąd rozwiązana gra, z przestrzenią wyszukiwania 5×10 20 . Liczba przeprowadzonych obliczeń wyniosła 10 14 , które zostały wykonane w okresie 18 lat. Proces obejmował od 200 komputerów stacjonarnych w szczytowym momencie do około 50.
Fanorona
Słabo rozwiązany przez Maartena Schadda. Gra jest remisem.
Bezpłatny gomoku
Rozwiązany przez Victora Allisa (1993). Pierwszy gracz może wymusić wygraną bez otwierania zasad.
Duch
Rozwiązany przez Alana Franka przy użyciu oficjalnego słownika graczy Scrabble w 1987 roku.
Klątwa
  • Argumentem strategia kradzieży (używane przez Johna Nasha ) pokazuje, że wszystkie kwadratowych rozmiary zarządu nie mogą zostać utracone przez pierwszego gracza. W połączeniu z dowodem na niemożność remisu pokazuje to, że gra jest bardzo słaba, gdy wygrywa pierwszy gracz.
  • Mocno rozwiązany przez kilka komputerów dla rozmiarów płyt do 6×6.
  • Jing Yang zademonstrował zwycięską strategię (słabe rozwiązanie) dla plansz o rozmiarach 7×7, 8×8 i 9×9.
  • Zwycięska strategia dla Hexa z zamianą jest znana na planszy 7×7.
  • Silne rozwiązanie Hex na płycie N × N jest mało prawdopodobne, ponieważ wykazano, że problem jest kompletny w PSPACE .
  • Jeśli Hex jest rozgrywany na planszy N × ( N + 1), gracz, który ma krótszą odległość do połączenia, zawsze może wygrać dzięki prostej strategii parowania, nawet z niekorzystną grą jako drugi.
  • Słabe rozwiązanie jest znane dla wszystkich ruchów otwierających na planszy 8×8.
Sześciopionek
Wariant 3×3 rozwiązany jako wygrana czarnych, kilka innych większych wariantów też rozwiązanych.
Kalah
Większość wariantów rozwiązanych przez Geoffreya Irvinga, Jeroena Donkersa i Josa Uiterwijka (2000) z wyjątkiem Kalah (6/6). Wariant (6/6) rozwiązał Anders Carstensen (2011). W większości przypadków udowodniono silną przewagę pierwszego gracza. Mark Rawlings z Gaithersburg, MD, obliczył wielkość wygranej pierwszego gracza w wariancie (6/6) (2015). Po utworzeniu 39 GB baz danych końcówek, wyszukiwaniach łącznie 106 dni czasu procesora i ponad 55 bilionach węzłów, udowodniono, że przy doskonałej grze pierwszy gracz wygrywa z 2. Należy pamiętać, że wszystkie te wyniki odnoszą się do przechwytywania Empty-pit wariant i dlatego mają bardzo ograniczone zainteresowanie w standardowej grze. Analiza standardowej gry została opublikowana dla Kalah(6,4), która jest wygrana 8 dla pierwszego gracza, oraz Kalah(6,5), która jest wygrana 10 dla pierwszego gracza. Trwa analiza Kalah(6,6) ze standardowymi zasadami, jednak udowodniono, że jest to wygrana co najmniej 4 dla pierwszego gracza.
L gra
Łatwo rozwiązać. Każdy gracz może zmusić grę do remisu.
Przegrywając szachy
Słabo rozwiązany jako wygrana białych zaczynając od 1. e3.
Maharadża i Sipojowie
Ta asymetryczna gra to wygrana dla gracza sipajów z poprawną grą.
Nimi
Mocno rozwiązany.
Morris dziewięciu mężczyzn
Rozwiązany przez Ralpha Gassera (1993). Każdy gracz może zmusić grę do remisu.
Porządek i chaos
Rozkaz (Pierwszy gracz) wygrywa.
Ohvalhu
Słabo rozwiązany przez ludzi, ale sprawdzony przez komputery. (Dakon nie jest jednak identyczny z Ohvalhu, grą, którą faktycznie obserwował de Voogt)
Pangki
Mocno rozwiązany przez Jasona Doucette (2001). Gra jest remisem. Istnieją tylko dwa unikalne pierwsze ruchy, jeśli odrzucisz lustrzane pozycje. Jeden wymusza remis, a drugi daje przeciwnikowi wymuszoną wygraną w 15.
Pentomina
Słabo rozwiązany przez HK Ormana. To wygrana dla pierwszego gracza.
Poddavki („rosyjskie warcaby gratisów ”)
Rozwiązany przez Osipova i Morozeva w 2011 roku. Białe zwycięstwo.
Kwarto
Rozwiązany przez Luca Goossensa (1998). Dwóch doskonałych graczy zawsze wylosuje.
Qubic
Słabo rozwiązany przez Orena Patashnika (1980) i Victora Allisa . Pierwszy gracz wygrywa.
Gra podobna do renju bez reguł otwarcia
Twierdzono, że rozwiązali go János Wagner i István Virág (2001). Wygrana pierwszego gracza.
Sim
Słabo rozwiązane: wygraj drugiego gracza.
Teeko
Rozwiązany przez Guy Steele (1998). W zależności od wariantu wygrany pierwszy gracz lub remis.
Morris trzech mężczyzn
Banalnie rozwiązany. Każdy gracz może zmusić grę do remisu.
Trzej muszkieterowie
Mocno rozwiązany przez Johannesa Laire w 2009 i słabo rozwiązany przez Ali Elabridi w 2017. Jest to wygrana dla niebieskich figur (ludzi kardynała Richelieu, czyli wroga).
Kółko i krzyżyk
Banalnie mocno rozwiązywalny ze względu na małe drzewo gry. Mecz kończy się remisem, jeśli nie popełniono błędów, bez możliwości pomyłki w ruchu otwierającym.
Tygrysy i Kozy
Słabo rozwiązany przez Yew Jin Lim (2007). Gra jest remisem.
Gra Wythoffa
Mocno rozwiązany.

Częściowo rozwiązane gry

Szachy
Główny artykuł: Rozwiązywanie szachów
Pełne rozwiązanie szachów pozostaje nieuchwytne i spekuluje się, że złożoność gry może uniemożliwić jej kiedykolwiek rozwiązanie. Dzięki wstecznej analizy komputerowej , tablebases Endgame (silne rozwiązania) zostały znalezione na wszystkich trzech do siedmiu sztuk zakończeń , licząc dwóch królów jak kawałki.
Niektóre warianty szachów na mniejszej planszy ze zmniejszoną liczbą bierek zostały rozwiązane. Niektóre inne popularne warianty również zostały rozwiązane; na przykład słabym rozwiązaniem Maharajah and the Sepoys jest łatwo zapadająca w pamięć seria ruchów, która gwarantuje zwycięstwo graczowi „sepoys”.
Udać się
Plansza 5×5 została słabo rozwiązana dla wszystkich ruchów otwierających w 2002 roku. Plansza 7×7 została słabo rozwiązana w 2015 roku. Ludzie zwykle grają na planszy 19×19, która jest o ponad 145 rzędów wielkości bardziej złożona niż 7×7.
Warcaby międzynarodowe
Wszystkie pozycje końcowe z pionkami od dwóch do siedmiu zostały rozwiązane, a także pozycje z pionkami 4×4 i 5×3, gdzie każda ze stron miała jednego króla lub mniej, pozycje z pięcioma przeciwnikami na czterech, pozycje z pięcioma przeciwnikami na trzech i jeden król i pozycje z czterema mężczyznami i jednym królem przeciwko czterem ludziom. Pozycje końcowe zostały rozwiązane w 2007 roku przez Eda Gilberta ze Stanów Zjednoczonych. Analiza komputerowa wykazała, że ​​istnieje duże prawdopodobieństwo remisu, jeśli obaj gracze grają perfekcyjnie.
m , n , k -game
Łatwo jest pokazać, że drugi gracz nigdy nie może wygrać; zobacz argument o kradzieży strategii . Prawie wszystkie przypadki zostały rozwiązane słabo dla k ≤ 4. Niektóre wyniki są znane dla k = 5. Gry są losowane dla k ≥ 8.
Reversi (Otello)
Słabo rozwiązany na planszy 4×4 i 6×6 jako drugi gracz wygrywa w lipcu 1993 przez Joela Feinsteina. Na planszy 8×8 (standardowej) jest matematycznie nierozwiązana, chociaż analiza komputerowa pokazuje prawdopodobny remis. Nie istnieją żadne mocno zakładane szacunki, inne niż zwiększone szanse dla gracza rozpoczynającego (czarnych) na planszach 10×10 i większych.

Zobacz też

Bibliografia

Dalsza lektura

  • Allis, pokonując mistrza świata? Najnowocześniejsze gry komputerowe. w nowych podejściach do badań nad grami planszowymi.

Zewnętrzne linki