Szukaj gry - Search game

Gra wyszukiwania to dwuosobowa gra o sumie stałej , która odbywa się w zestawie o nazwie przestrzeń poszukiwań. Poszukiwacz może wybrać dowolną ciągłą trajektorię z zastrzeżeniem ograniczenia maksymalnej prędkości. Zawsze zakłada się, że ani poszukujący, ani ukrywający się nie mają żadnej wiedzy na temat ruchu drugiego gracza, dopóki ich odległość od siebie nie będzie mniejsza lub równa promieniowi odkrycia i w tym momencie następuje przechwycenie. Jako modele matematyczne, gry wyszukiwania mogą być stosowane w takich obszarach, jak gry w chowanego, w które bawią się dzieci, lub reprezentacje niektórych taktycznych sytuacji wojskowych. Obszar gier wyszukiwania został wprowadzony w ostatnim rozdziale klasycznej książki Rufusa Isaacsa „Gry różnicowe” i został dalej rozwinięty przez Shmuela Gala i Steve'a Alperna . Gra o księżniczkach i potworach dotyczy ruchomego celu.

Strategia

Naturalną strategią poszukiwania nieruchomego celu na wykresie jest znalezienie minimalnej krzywej zamkniętej L, która pokrywa wszystkie łuki wykresu. (L nazywa się wycieczką po chińskim listonoszu ). Następnie przemierz L z prawdopodobieństwem 1/2 dla każdego kierunku. Ta strategia wydaje się działać dobrze, jeśli wykres jest Eulera . Ogólnie rzecz biorąc, ta losowa wycieczka z chińskim listonoszem jest rzeczywiście optymalną strategią wyszukiwania wtedy i tylko wtedy, gdy graf składa się z zestawu grafów Eulera połączonych w strukturę podobną do drzewa. Zwodniczo prosty przykład grafu spoza tej rodziny składa się z dwóch węzłów połączonych trzema łukami. Losowa wycieczka chińskiego listonosza (odpowiednik przechodzenia trzech łuków w losowej kolejności) nie jest optymalna, a optymalny sposób przeszukiwania tych trzech łuków jest skomplikowany.

Domeny nieograniczone

Ogólnie rzecz biorąc, rozsądnym schematem wyszukiwania domeny nieograniczonej, tak jak w przypadku algorytmu online , jest użycie znormalizowanej funkcji kosztu (nazywanej współczynnikiem konkurencyjności w literaturze informatycznej). Minimax trajektorii problemów tego typu jest zawsze sekwencją geometryczne (lub funkcję wykładniczą o ciągłych problemów). Ten wynik daje łatwą metodę znalezienia trajektorii minimaksowej poprzez minimalizację jednego parametru (generatora tej sekwencji) zamiast przeszukiwania całej przestrzeni trajektorii. Narzędzie to było wykorzystywane do rozwiązywania problemu wyszukiwania liniowego , tj. znajdowania celu na linii nieskończonej, która od kilkudziesięciu lat przyciągnęła wiele uwagi i była analizowana jako gra wyszukiwania. Został również wykorzystany do znalezienia trajektorii minimaksowej do przeszukiwania zestawu równoległych promieni. Optymalne wyszukiwanie w płaszczyźnie odbywa się za pomocą spiral wykładniczych. Wyszukiwanie zestawu równoległych promieni zostało później ponownie odkryte w literaturze informatycznej jako „problem ścieżki krowy”.

Bibliografia

  1. ^ Rufus Isaacs, Gry różnicowe , John Wiley and Sons, (1965),
  2. ^ a b c S. Gal, Search Games , Academic Press, New York (1980)
  3. ^ a b c S. Alpern i S. Gal, Teoria gier wyszukiwania i Rendezvous , Springer (2003).
  4. ^ Gal, Szmul (2001). „O optymalności prostej strategii przeszukiwania wykresów” . Międzynarodowy Dziennik Teorii Gier . 29 : 533-542. doi : 10.1007/s00182000056 .
  5. ^ Beck, Anatole; Newman, DJ (1970). "Jeszcze więcej o problemie wyszukiwania liniowego" . Izrael Dziennik Matematyki . 8 : 419–429. doi : 10.1007/BF02798690 .
  6. ^ M. Chrobak, Księżniczka pływająca we mgle szukająca potwornej krowy, ACM Sigact news, 35(2), 74-78 (2004).
  7. ^ MY Kao, JH Reif i SR Tate, Wyszukiwanie w nieznanym środowisku: optymalny algorytm losowy dla problemu ścieżki krowy , SODA 1993.