Teoria gier kombinatorycznych - Combinatorial game theory

Ten artykuł dotyczy teorii gier kombinatorycznych. Aby zapoznać się z teorią, która obejmuje gry losowe i gry o niedoskonałej wiedzy, zobacz Teoria gier .
Matematycy grający w Konane na warsztatach z teorii gier kombinatorycznych

Kombinatoryczna teoria gier ( CGT ) to gałąź matematyki i informatyki teoretycznej, która zazwyczaj bada gry sekwencyjne z doskonałymi informacjami . Badanie zostało w dużej mierze ogranicza się do dwóch graczy gier , które mają miejsce , że gracze po kolei zmieniając w określony sposób lub ruchów , aby osiągnąć określony zwycięską warunek. CGT nie badało tradycyjnie gier losowych ani tych, które wykorzystują niedoskonałe lub niekompletne informacje, preferując gry, które oferują doskonałe informacjew której stan gry i zestaw dostępnych ruchów jest zawsze znany obu graczom. Jednak wraz z postępem technik matematycznych rodzaje gier, które można matematycznie analizować, rozszerzają się, a zatem granice pola ciągle się zmieniają. Uczeni zazwyczaj definiują, co rozumieją przez „grę” na początku artykułu, a definicje te często różnią się, ponieważ są specyficzne dla analizowanej gry i nie mają reprezentować całego zakresu dziedziny.

Gry kombinatoryczne obejmują dobrze znane gry, takie jak szachy , warcaby i Go , które są uważane za nietrywialne, oraz kółko i krzyżyk , które jest uważane za trywialne, w sensie „łatwe do rozwiązania”. Niektóre gry kombinatoryczne mogą również mieć nieograniczony obszar gry, na przykład nieskończone szachy . W CGT ruchy w tych i innych grach są reprezentowane jako drzewo gry .

Gry kombinatoryczne obejmują również łamigłówki kombinatoryczne dla jednego gracza, takie jak Sudoku oraz automaty bez gracza, takie jak Gra w życie Conwaya (chociaż w najściślejszej definicji „gry” mogą wymagać więcej niż jednego uczestnika, stąd oznaczenia "puzzle" i "automaty".)

Ogólnie rzecz biorąc, teoria gier obejmuje gry losowe, gry z niedoskonałą wiedzą oraz gry, w których gracze mogą poruszać się jednocześnie i mają tendencję do przedstawiania sytuacji decyzyjnych z prawdziwego życia.

CGT kładzie inny nacisk niż „tradycyjna” lub „ekonomiczna” teoria gier, która początkowo została opracowana do badania gier o prostej strukturze kombinatorycznej, ale z elementami przypadku (chociaż uwzględnia również ruchy sekwencyjne, patrz gra w formie rozszerzonej ). Zasadniczo CGT wniosło nowe metody analizy drzew gier, na przykład za pomocą liczb surrealistycznych , które są podklasą wszystkich dwuosobowych gier z doskonałą informacją. Rodzaj gier badany przez CGT jest również przedmiotem zainteresowania sztucznej inteligencji , zwłaszcza w przypadku automatycznego planowania i harmonogramowania . W CGT mniejszy nacisk położono na udoskonalanie praktycznych algorytmów wyszukiwania (takich jak heurystyka przycinania alfa-beta zawarta w większości podręczników sztucznej inteligencji), ale większy nacisk na opisowe wyniki teoretyczne (takie jak miary złożoności gry lub dowody istnienia optymalnego rozwiązania bez koniecznie określając algorytm, taki jak argument strategia-kradzież ).

Ważnym pojęciem w CGT jest rozwiązana gra . Na przykład gra w kółko i krzyżyk jest uważana za grę rozwiązaną, ponieważ można udowodnić, że każda gra zakończy się remisem, jeśli obaj gracze będą grać optymalnie. Uzyskanie podobnych wyników dla gier o bogatych strukturach kombinatorycznych jest trudne. Na przykład w 2007 roku ogłoszono, że pionki zostały rozwiązane słabo — optymalna gra obu stron również prowadzi do remisu — ale ten wynik był dowodem wspomaganym komputerowo . Inne gry z prawdziwego świata są w większości zbyt skomplikowane, aby umożliwić pełną analizę dzisiaj, chociaż teoria odniosła kilka ostatnich sukcesów w analizie końcówek Go. Zastosowanie CGT do pozycji ma na celu określenie optymalnej sekwencji ruchów dla obu graczy aż do zakończenia gry, a tym samym odkrycie optymalnego ruchu w dowolnej pozycji. W praktyce ten proces jest niezwykle trudny, chyba że gra jest bardzo prosta.

Pomocne może być rozróżnienie między kombinatorycznymi „grami matematycznymi” interesującymi głównie matematyków i naukowców do rozważania i rozwiązywania, a kombinatorycznymi „zabawami” interesującymi ogół populacji jako forma rozrywki i rywalizacji. Jednak wiele gier należy do obu kategorii. Na przykład Nim to gra, która odegrała kluczową rolę w fundamentach CGT i jest jedną z pierwszych gier komputerowych. Kółko i krzyżyk jest nadal używany do nauczania studentów informatyki podstawowych zasad projektowania gier AI .

Historia

CGT powstało w związku z teorią gier bezstronnych , w której każda gra dostępna dla jednego gracza musi być dostępna również dla drugiego. Jedną z takich gier jest Nim , którą można całkowicie rozwiązać. Nim jest grą bezstronną dla dwóch graczy i podlega normalnym warunkom gry , co oznacza, że ​​gracz, który nie może się poruszyć, przegrywa. W latach 30. XX wieku twierdzenie Sprague-Grundy'ego pokazało, że wszystkie bezstronne gry są równoważne stosom w Nim, pokazując tym samym, że duże unifikacje są możliwe w grach rozważanych na poziomie kombinatorycznym, w których liczą się szczegółowe strategie, a nie tylko korzyści.

W latach sześćdziesiątych Elwyn R. Berlekamp , John H. Conway i Richard K. Guy wspólnie wprowadzili teorię partyzanckiej gry , w której złagodzono wymóg, by gra dostępna dla jednego gracza była dostępna dla obu. Ich wyniki zostały opublikowane w ich książce Winning Ways for your Mathematical Plays w 1982 roku. Jednak pierwszą pracą opublikowaną na ten temat była książka Conwaya z 1976 roku On Numbers and Games , znana również jako ONAG, która wprowadziła pojęcie liczb surrealistycznych i uogólnienie do Gry. On Numbers and Games był także owocem współpracy Berlekampa, Conwaya i Guya.

Gry kombinatoryczne są generalnie, zgodnie z konwencją, przedstawiane w formie, w której jeden gracz wygrywa, podczas gdy drugi nie ma już żadnych ruchów. Łatwo jest przekształcić dowolną grę skończoną z tylko dwoma możliwymi wynikami w równoważną, w której obowiązuje ta konwencja. Jednym z najważniejszych pojęć w teorii gier kombinatorycznych jest suma dwóch gier, czyli gra, w której każdy gracz może wybrać ruch w jednej lub drugiej grze w dowolnym momencie gry, a gracz wygrywa gdy jego przeciwnik nie ma ruchu w żadnej z gier. Ten sposób łączenia gier prowadzi do bogatej i potężnej struktury matematycznej.

Conway stwierdził w ONAG, że inspiracją dla teorii gier partyzanckich była jego obserwacja rozgrywki w końcówkach Go , które często można rozłożyć na sumy prostszych końcówek, odizolowanych od siebie w różnych częściach planszy.

Przykłady

Tekst wprowadzający Winning Ways wprowadził dużą liczbę gier, ale następujące przykłady posłużyły jako motywujące przykłady teorii wprowadzającej:

  • Niebiesko-czerwony Hackenbush — Na poziomie skończonym ta partyzancka gra kombinatoryczna umożliwia konstruowanie gier, których wartości są dwójkowymi liczbami wymiernymi . Na poziomie nieskończonym pozwala konstruować wszystkie wartości rzeczywiste, a także wiele nieskończonych, które należą do klasy liczb surrealistycznych .
  • Niebiesko-czerwono-zielony Hackenbush — pozwala na wprowadzenie dodatkowych wartości w grze, które nie są liczbami w tradycyjnym sensie, na przykład gwiazdka .
  • Ropuchy i żaby - Pozwala na różne wartości gry. W przeciwieństwie do większości innych gier, pozycję można łatwo przedstawić za pomocą krótkiego ciągu znaków.
  • Dominowanie - Różne ciekawe gry, takie jak gorące gry , pojawiają się jako pozycje w Domineering, ponieważ czasami pojawia się zachęta do ruchu, a czasami nie. Pozwala to na omówienie temperatury gry .
  • Nim - Bezstronna gra . Pozwala to na budowę strzelców . (Może być również postrzegany jako zielony tylko specjalny przypadek niebiesko-czerwono-zielonego Hackenbusha.)

Klasyczna gra Go miała wpływ na wczesną teorię gier kombinatorycznych, a następnie Berlekamp i Wolfe opracowali dla niej teorię gry końcowej i temperatury (patrz odniesienia). Uzbrojeni w to byli w stanie zbudować wiarygodne pozycje końcowe w Go, z których mogli dać doświadczonym graczom Go wybór stron, a następnie pokonać ich w dowolny sposób.

Inną grą badaną w kontekście kombinatorycznej teorii gier są szachy . W 1953 r. Alan Turing napisał o grze: „Jeżeli można całkiem jednoznacznie wyjaśnić w języku angielskim, za pomocą symboli matematycznych, jeśli jest to wymagane, jak należy wykonać obliczenia, to zawsze można zaprogramować dowolny komputer cyfrowy do wykonywania tych obliczeń. , pod warunkiem, że pojemność magazynowa jest odpowiednia." W artykule z 1950 roku Claude Shannon oszacował dolną granicę złożoności drzewa gry w szachach na 10 120 , a dziś jest to określane jako liczba Shannona . Szachy pozostają nierozwiązane, chociaż szeroko zakrojone badania, w tym prace z wykorzystaniem superkomputerów , pozwoliły stworzyć tabele końcowe partii szachowych , które pokazują wynik idealnej gry dla wszystkich partii końcowych z siedmioma lub mniejszymi figurami. Nieskończone szachy mają jeszcze większą kombinatoryczną złożoność niż szachy (chyba że badane są tylko ograniczone partie końcowe lub złożone pozycje z niewielką liczbą bierek).

Przegląd

Gra, w najprostszym ujęciu, to lista możliwych "ruchów", które może wykonać dwóch graczy, nazwanych lewy i prawy . Pozycja gry wynikająca z dowolnego ruchu może być uważana za inną grę. Ta idea patrzenia na gry pod kątem ich możliwych przesunięć do innych gier prowadzi do rekurencyjnej matematycznej definicji gier, która jest standardem w kombinatorycznej teorii gier. W tej definicji każda gra ma notację {L|R} . L jest zbiorem pozycji w grze, na które może przejść lewy gracz, a R jest zbiorem pozycji w grze, na które może przejść prawy gracz; każda pozycja w L i R jest zdefiniowana jako gra przy użyciu tej samej notacji.

Posługując się przykładem Dominowania , oznacz każde z szesnastu pudełek na planszy cztery na cztery jako A1 dla kwadratu u góry z lewej strony, C2 dla trzeciego pudełka od lewej w drugim rzędzie od góry i tak dalej. Używamy np. (D3, D4) do oznaczenia pozycji w grze, w której pionowe domino zostało umieszczone w prawym dolnym rogu. Wtedy początkową pozycję można opisać w kombinatorycznej teorii gier jako

W standardowej grze Cross-Cram gracze wykonują naprzemiennie tury, ale ta przemiana jest rozumiana domyślnie przez definicje kombinatorycznej teorii gier, a nie zakodowana w stanach gry.

20x20kwadrat.png20x20kwadrat.png
20x20kwadrat.png

Powyższa gra opisuje scenariusz, w którym dla każdego gracza pozostał tylko jeden ruch i jeśli któryś z graczy wykona ten ruch, ten gracz wygrywa. (Nieistotne otwarte pole w C3 zostało pominięte na diagramie.) {|} na liście ruchów każdego gracza (odpowiadające pojedynczemu polu pozostałemu po ruchu) nazywa się grą zerową i może być w rzeczywistości skrócone do 0. zerowa gra, żaden z graczy nie ma żadnych ważnych ruchów; w ten sposób gracz, którego tura jest, gdy nadchodzi gra zerowa, automatycznie przegrywa.

Typ gry na powyższym diagramie również ma prostą nazwę; nazywa się to gwiezdną grą , która może być również skracana do ∗. W grze gwiezdnej jedyny prawidłowy ruch prowadzi do gry zerowej, co oznacza, że ​​ktokolwiek pojawi się w grze gwiezdnej, automatycznie wygrywa.

Dodatkowym rodzaj gry, nie znaleziono w apodyktyczny, to loopy gra, w której ważna akcja albo w lewo albo w prawo to gra, która następnie prowadzi z powrotem do pierwszej części gry można. Warcaby , na przykład, stają się zapętlone, gdy jeden z pionków się promuje, ponieważ wtedy może bez końca przechodzić między dwoma lub więcej kwadratami. Gra, która nie posiada takich ruchów nazywa się loopfree .

Skróty gier

Liczby

Liczby reprezentują liczbę wolnych ruchów lub przewagę ruchu danego gracza. Zgodnie z konwencją liczby dodatnie oznaczają przewagę dla Lewej strony, podczas gdy liczby ujemne oznaczają przewagę dla Prawa. Są one definiowane rekurencyjnie, gdzie 0 jest przypadkiem podstawowym.

0 = {|}
1 = {0|}, 2 = {1|}, 3 = {2|}
-1 = {|0}, -2 = {|−1}, -3 = {|−2}

Gra zera to strata dla pierwszego gracza.

Suma gier liczbowych zachowuje się jak liczby całkowite, na przykład 3 + −2 = 1.

Gwiazda

Gwiazdka , zapisywana jako ∗ lub {0|0}, jest wygraną pierwszego gracza, ponieważ każdy z graczy musi (jeśli pierwszy poruszy się w grze) przejść do gry zerowej, a zatem wygrać.

∗ + ∗ = 0, ponieważ pierwszy gracz musi zmienić jedną kopię ∗ na 0, a drugi gracz będzie musiał również zmienić drugą kopię ∗ na 0; w tym momencie pierwszy gracz przegrałby, ponieważ 0 + 0 nie dopuszcza żadnych ruchów.

Gra ∗ nie jest ani pozytywna, ani negatywna; to i wszystkie inne gry, w której pierwszy gracz wygrywa (z której strony niezależnie odtwarzacz jest włączony) Mówi się, że rozmyta z lub mylone z 0; symbolicznie piszemy ∗ || 0.

W górę

Up , zapisane jako ↑, jest pozycją w kombinatorycznej teorii gier. W notacji standardowej ↑ = {0|∗}.

−↑ = ↓ ( w dół )

Up jest ściśle dodatnie (↑ > 0), ale jest nieskończenie małe . Podwyżka jest zdefiniowana w sposobach wygrywania dla twoich zabaw matematycznych .

W dół

Down , zapisane jako ↓, jest pozycją w kombinatorycznej teorii gier. W notacji standardowej ↓ = {∗|0}.

−↓ = ↑ ( w górę )

Down jest ściśle ujemny (↓ < 0), ale jest nieskończenie mały . Down jest zdefiniowany w sposobach wygrywania dla twoich zabaw matematycznych .

„Gorące” gry

Rozważ grę {1|−1}. Oba ruchy w tej grze są zaletą dla gracza, który je wykonuje; więc mówi się, że gra jest „gorąca”; jest większa niż dowolna liczba mniejsza niż -1, mniejsza niż dowolna liczba większa niż 1 i rozmyta z dowolną liczbą pomiędzy. Jest zapisany jako ±1. Można go dodawać do liczb lub mnożyć przez dodatnie, w oczekiwany sposób; na przykład 4 ± 1 = {5|3}.

Nimbery

Bezstronny gra jest jeden, gdzie na każdej pozycji w grze, te same ruchy są dostępne dla obu graczy. Na przykład Nim jest bezstronny, ponieważ każdy zestaw obiektów, które może usunąć jeden gracz, może zostać usunięty przez drugiego. Jednak dominacja nie jest bezstronna, ponieważ jeden gracz umieszcza domino poziome, a drugi pionowe. Podobnie warcaby nie są bezstronne, ponieważ gracze posiadają różnokolorowe pionki. Dla dowolnej liczby porządkowej można zdefiniować bezstronną grę uogólniającą Nim, w której w każdym ruchu każdy z graczy może zastąpić liczbę dowolną mniejszą liczbą porządkową; tak zdefiniowane gry określane są mianem nimbrów . Twierdzenie Sprague-Grundy'ego stwierdza, że ​​każda bezstronna gra jest równoważna z nimberem.

„Najmniejsze” nimbry – najprostsze i najmniej zgodne ze zwykłym porządkiem porządków – to 0 i ∗.

Zobacz też

Uwagi

Bibliografia

Zewnętrzne linki