Argument kradnący strategię - Strategy-stealing argument
W kombinatorycznej teorii gier The Argument strategia kradzieży jest ogólny argument, że pokazy dla wielu gier dla dwóch graczy , że drugi gracz nie może mieć gwarantowaną strategię wygrywającą . Argument kradzieży strategii ma zastosowanie do każdej gry symetrycznej (takiej, w której każdy z graczy ma ten sam zestaw dostępnych ruchów z tymi samymi wynikami, tak aby pierwszy gracz mógł „użyć” strategii drugiego gracza), w której nie można nigdy wykonać dodatkowego ruchu wada.
Argument działa poprzez uzyskanie sprzeczności . Zakłada się, że zwycięska strategia istnieje dla drugiego gracza, który jej używa. Ale potem, z grubsza mówiąc, po wykonaniu dowolnego dowolnego pierwszego ruchu - co z uwagi na powyższe warunki nie jest wadą - pierwszy gracz może wtedy również grać zgodnie z tą wygrywającą strategią. W rezultacie obaj gracze mają gwarancję wygranej - co jest absurdem, a tym samym zaprzecza założeniu, że taka strategia istnieje.
Kradzież strategii został wymyślony przez Johna Nasha w latach czterdziestych XX wieku, aby pokazać, że gra heksów jest zawsze wygraną pierwszego gracza, ponieważ remisy w tej grze nie są możliwe. Jednak Nash nie opublikował tej metody, a Beck (2008) przypisuje swoją pierwszą publikację Alfredowi W. Halesowi i Robertowi I. Jewettowi w artykule o kółku i krzyżyk z 1963 roku, w którym udowodnili również twierdzenie Halesa-Jewetta . Inne przykłady gier, do których stosuje się argument obejmują m , n , k -games takich jak Gomoku . W grze w monety Sylver kradzież strategiczna została wykorzystana, aby pokazać, że pierwszy gracz wygrywa, a nie, że gra kończy się remisem.
Przykład
Argument kradzieży strategii może być użyty na przykładzie gry w kółko i krzyżyk , dla planszy i wygrywających rzędów dowolnej wielkości. Załóżmy, że drugi gracz (P2) używa strategii S, która gwarantuje wygraną. Pierwszy gracz (P1) umieszcza X na dowolnej pozycji. P2 odpowiada umieszczając O według S . Ale jeśli P1 zignoruje pierwszy losowy X , P1 jest teraz w tej samej sytuacji, co P2 w pierwszym ruchu P2: pojedynczy element wroga na planszy. P1 może więc wykonać ruch zgodnie z S - to znaczy, chyba że S zażąda umieszczenia kolejnego X tam, gdzie zignorowany X jest już umieszczony. Ale w tym przypadku gracz P1 może po prostu umieścić X na innej losowej pozycji na stole, czego efektem netto będzie to, że jeden X będzie na pozycji wymaganej przez S , a inny będzie w losowej pozycji i stanie się nowym zignorowany kawałek, pozostawiając sytuację jak poprzednio. Kontynuując w ten sposób, hipoteza S gwarantuje wygrywającą pozycję (z dodatkowym ignorowanym X bez konsekwencji). Ale potem P2 przegrał - zaprzeczając przypuszczeniu, że P2 miał gwarantowaną zwycięską strategię. Dlatego taka strategia wygrywająca dla P2 nie istnieje, a kółko i krzyżyk jest albo wymuszoną wygraną dla P1, albo remisem. (Dalsza analiza pokazuje, że w rzeczywistości jest to remis).
Ten sam dowód dotyczy każdej silnej gry pozycyjnej .
Szachy
| za | b | do | re | mi | fa | sol | godz | ||
| 8 |      |
8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| za | b | do | re | mi | fa | sol | godz | ||
Istnieje klasa pozycji szachowych zwana Zugzwang, w której gracz zobowiązany do ruchu wolałby „pasować”, gdyby było to dozwolone. Z tego powodu argument o kradzieży strategii nie może być stosowany do szachów. Obecnie nie wiadomo, czy białe czy czarne mogą wymusić wygraną optymalną grą, czy też obaj gracze mogą wymusić remis. Jednak praktycznie wszyscy uczniowie szachów uważają pierwszy ruch białych za przewagę, a statystyki z nowoczesnych gier na wysokim poziomie wskazują, że procent wygranych białych jest o około 10% wyższy niż czarnych.
Udać się
Mijanie w Go jest dozwolone. Kiedy pozycja początkowa jest symetryczna (pusta plansza, żaden z graczy nie ma punktów), oznacza to, że pierwszy gracz może ukraść zwycięską strategię drugiego gracza, po prostu rezygnując z pierwszego ruchu. Jednak od lat 30. XX wieku drugiemu graczowi przyznaje się zwykle kilka punktów wyrównawczych , co sprawia, że pozycja wyjściowa jest asymetryczna, a argument o kradzieży strategii nie będzie już działał.
Podstawową strategią w grze jest „ mirror go ”, w której drugi gracz wykonuje ruchy po przekątnej przeciwne do ruchów tego przeciwnika. Takie podejście można pokonać stosując taktykę drabinkową , walki ko lub z powodzeniem konkurować o kontrolę nad centralnym punktem planszy.
Konstruktywność
Argument kradzieży strategii pokazuje, że drugi gracz nie może wygrać, wyprowadzając sprzeczność z hipotetycznej strategii wygrywającej drugiego gracza. Argument ten jest powszechnie stosowany w grach, w których nie może być remisu, za pomocą prawa wykluczonego środka . Nie zawiera jednak jednoznacznej strategii dla pierwszego gracza i dlatego została nazwana niekonstruktywną. Rodzi to pytanie, jak właściwie obliczyć zwycięską strategię.
W przypadku gier ze skończoną liczbą osiągalnych pozycji, takich jak chomp , zwycięską strategię można znaleźć poprzez wyczerpujące wyszukiwanie. Jednak może to być niepraktyczne, jeśli liczba pozycji jest duża.
W 2019 roku Greg Bodwin i Ofer Grossman udowodnili, że problem znalezienia zwycięskiej strategii jest trudny na PSPACE w dwóch rodzajach gier, w których używano argumentów kradnących strategię: w grze minimum poset i symetrycznej grze Maker-Maker .