Argument o kradzieży strategii
W teorii gier kombinatorycznych argument dotyczący kradzieży strategii jest ogólnym argumentem , który w wielu grach dwuosobowych pokazuje, że drugi gracz nie może mieć gwarantowanej strategii wygrywającej . Argument o kradzieży strategii ma zastosowanie do każdej gry symetrycznej (taki, w którym każdy gracz ma ten sam zestaw dostępnych ruchów z tymi samymi wynikami, tak aby pierwszy gracz mógł „wykorzystać” strategię drugiego gracza), w którym dodatkowy ruch nigdy nie może być wadą. Kluczową właściwością argumentu dotyczącego kradzieży strategii jest to, że dowodzi on, że pierwszy gracz może wygrać (lub ewentualnie zremisować) grę bez konstruowania takiej strategii. Tak więc, chociaż może ci powiedzieć, że istnieje zwycięska strategia, dowód nie daje żadnych informacji o tym, czym jest ta strategia.
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 pierwszego ruchu – co według powyższych warunków nie jest wadą – pierwszy gracz może wtedy również grać zgodnie z tą zwycięską strategią. Rezultat jest taki, że obaj gracze mają gwarancję wygranej – co jest absurdem, a tym samym zaprzecza założeniu, że taka strategia istnieje.
Kradzież strategii została wymyślona przez Johna Nasha w latach czterdziestych XX wieku, aby pokazać, że gra w heksadecymalną grę zawsze wygrywa pierwszy gracz, ponieważ w tej grze nie są możliwe remisy. Jednak Nash nie opublikował tej metody, a József Beck przypisuje jej pierwszą publikację Alfredowi W. Halesowi i Robertowi I. Jewettowi w artykule z 1963 r. O kółko i krzyżyk, w którym również udowodnili twierdzenie Halesa-Jewetta . Inne przykłady gier, do których odnosi się ten argument, obejmują m , n , k -gry, takie jak gomoku . W grze Chomp strategia kradzieży pokazuje, że pierwszy gracz ma zwycięską strategię na dowolnej prostokątnej planszy (innej niż 1x1). W grze Sylver coinage strategia kradzieży została wykorzystana do pokazania, że pierwszy gracz może wygrać na pewnych pozycjach zwanych „końcami”. We wszystkich tych przykładach dowód nie ujawnia niczego na temat rzeczywistej strategii.
Przykład
Argument o kradzieży strategii można zastosować 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) stosuje strategię S , która gwarantuje wygraną. Pierwszy gracz (P1) umieszcza znak X w dowolnym miejscu. P2 odpowiada umieszczając O zgodnie z S . Ale jeśli P1 zignoruje pierwszy losowy X , P1 jest teraz w tej samej sytuacji co P2 w pierwszym ruchu P2: pojedynczy pionek wroga na planszy. P1 może zatem wykonać ruch zgodnie z S – czyli chyba że S wzywa do umieszczenia kolejnego X w miejscu, w którym znajduje się już zignorowany X. Ale w tym przypadku P1 może po prostu umieścić X w innej losowej pozycji na planszy, czego efektem netto będzie to, że jeden X znajdzie się na pozycji wymaganej przez S , podczas gdy inny znajdzie się na losowej pozycji i stanie się nowym zignorował figurę, pozostawiając sytuację jak poprzednio. Kontynuując w ten sposób, S ma, zgodnie z hipotezą, gwarancję uzyskania zwycięskiej pozycji (z dodatkowym zignorowanym X bez konsekwencji). Ale potem P2 przegrał – zaprzeczając przypuszczeniu, że P2 miał gwarantowaną strategię wygranej. Taka zwycięska strategia 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
| A | B | C | D | mi | F | G | H | ||
| 8 |      |
8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| A | B | C | D | mi | F | G | H | ||
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ć zastosowany do szachów. Obecnie nie wiadomo, czy białe lub czarne mogą wymusić zwycięstwo przy optymalnej grze, czy też obaj gracze mogą wymusić remis. Jednak praktycznie wszyscy studenci szachów uważają pierwszy ruch białych za przewagę, a statystyki ze współczesnych gier na wysokim poziomie pokazują, że procent wygranych białych jest o około 10% [potrzebne źródło] wyższy niż czarnych .
Iść
W Go podanie jest dozwolone. Kiedy pozycja wyjściowa jest symetryczna (szachownica pusta, żaden z graczy nie ma żadnych 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 zwykle przyznaje się punkty kompensacyjne , co powoduje, że pozycja wyjściowa jest asymetryczna, a argument o kradzieży strategii nie będzie już działał.
Elementarną strategią w grze jest „ lustrzane odbicie ”, w którym drugi gracz wykonuje ruchy po przekątnej przeciwne do ruchów tego przeciwnika. Podejście to można pokonać, stosując taktykę drabinkową , walki w ko lub skuteczną rywalizację o kontrolę nad centralnym punktem planszy.
Konstruktywność
Argument dotyczący kradzieży strategii pokazuje, że drugi gracz nie może wygrać, wyprowadzając sprzeczność z dowolnej hipotetycznej zwycięskiej strategii drugiego gracza. Argument ten jest powszechnie stosowany w grach, w których nie może być remisu, za pomocą prawa wyłączonego środka . Nie zawiera jednak jednoznacznej strategii dla pierwszego gracza iz tego powodu został nazwany niekonstruktywnym. 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 PSPACE-trudny w dwóch rodzajach gier, w których zastosowano argumenty kradnące strategię: minimalna gra poset i symetryczna gra Maker-Maker .