Czy NP jest trudny do prawidłowego grania w drafty międzynarodowe?

26

Czy następujący problem jest trudny NP?

Biorąc pod uwagę konfigurację forum dla międzynarodowych projektów , znajdź jeden legalny ruch.n×n

Odpowiedni problem dla amerykańskich warcabów (inaczej angielskich wersji roboczych) można w prosty sposób rozwiązać w czasie wielomianowym. Istnieją trzy główne różnice między tymi dwiema grami.n×n

Pierwszą i najbardziej znaczącą różnicą jest zasada „latającego króla”. W warcabach król może przeskoczyć kawałek sąsiadującego przeciwnika na puste pole dwa kroki dalej w dowolnym kierunku po przekątnej. W przeciągach międzynarodowych król może przeskoczyć kawałek przeciwnika na dowolną odległość, przesuwając dowolną odległość wzdłuż przekątnej.

Podobnie jak w warcabach, ten sam element można wykorzystać do przechwycenia serii elementów w jednej turze. Jednak w przeciwieństwie do warcabów, przechwycone elementy w przeciągach międzynarodowych nie są usuwane, dopóki cała sekwencja się nie skończy. Kawałek przechwytujący może kilkakrotnie przeskoczyć lub wylądować na tym samym pustym polu, ale nie może przeskoczyć pionka przeciwnika więcej niż raz.

Wreszcie, zarówno warcaby, jak i projekty międzynarodowe mają zasadę wymuszonego przejęcia: jeśli możesz schwytać kawałek przeciwnika, musisz. Jednak reguły reguł nie zgadzają się, gdy istnieje kilka opcji dla wielu. W warcabach możesz wybrać dowolną maksymalną sekwencję przechwytywania; innymi słowy, możesz wybrać dowolną sekwencję przechwytywania, która kończy się, gdy przechwytujący element nie może już przechwycić. W projektach międzynarodowych musisz wybrać najdłuższą sekwencję przechwytywania. Zatem mój problem jest równoważny z następującym:

Biorąc pod uwagę konfigurację planszy dla międzynarodowych przeciągów , znajdź ruch, który uchwyci maksymalną liczbę przeciwnych pionków.n×n

Wystarczy udowodnić, że następujący problem jest NP-zupełny. (Jest oczywiście w NP.)

Biorąc pod uwagę konfigurację planszową dla międzynarodowych draftu, w których biorą udział tylko królowie , czy (i dlatego musi) jeden gracz może przechwycić wszystkie elementy przeciwnika w jednej turze?n×n

Odpowiedzi na problem warcabów można rozwiązać w czasie wielomianowym; to zabawne zadanie domowe. Problem wygląda bardziej podobnie do analizy końcowych gier Phutball Demaine, Demaine i Eppstein ; rozwiązanie zabawnej pracy domowej pojawia się na końcu ich artykułu. Rozwiązanie pojawia się również w pracy FOCS 1978 autorstwa Frankela i in. dowodzi to, że optymalne granie w warcaby jest trudne dla PSPACE; zobacz także dowód Robsona z 1984 r., że warcaby są w rzeczywistości DODATKOWE.

Jeffε
źródło
literówka? „jest oczywiście w P” - może masz na myśli „w NP”? GDZIE otrzymujesz te pytania?
Suresh Venkat
Tak, naprawione. Przeredagował także problem; nie jest jasne, czy liczba legalnych ruchów z danej pozycji jest tylko wielomianowa.
Jeffε
Ten powstaje z napisania rozwiązania „zabawnego zadania domowego”.
Jeffε,
Myślę, że niewypowiedziane dodatkowe pytanie brzmi: jaka jest złożoność samej gry (określenie, czy jeden gracz może wygrać)? Czy jest to EXPTIME-complete, tak jak warcaby? Prawdopodobnie, ale dowód na warcaby jest dość skomplikowany.
Bob Hearn

Odpowiedzi:

24

OK, oto redukcja. Okazuje się, że mimo wszystko nie potrzebujesz płaskości. Ponadto, jeśli chodzi o „znaleźć legalny ruch”, zadaję pytanie, ponieważ „czy ruch X jest legalny?”.

Najpierw pracujmy zamiast tego w grze, w której pionki poruszają się prostopadle zamiast po przekątnej. Ta gra jest równoważna (wystarczy spojrzeć na planszę obróconą o 45 stopni), z wyjątkiem właściwości krawędzi, których nie będziemy używać. Używamy dwóch gadżetów: scalania / podziału i podziału. Zobacz http://www.hearn.to/draughts.pdf . Zakładamy, że na planszy jest jeden Biały Król do ruchu. (Żaden inny element nie będzie w stanie uchwycić żadnej znaczącej liczby elementów.) Porusza się przez wskazane korytarze, przechwytując czarne kawałki po drodze.

Najpierw połącz: jeśli król wejdzie na którąkolwiek z N ścieżek A (przechwytując czarny kawałek, nie pokazano), może wyjść w B. Podobnie, jeśli odwrócimy gadżet i wejdzie on w B, przechwytując pokazany kawałek, może opuścić dowolną ścieżkę A (ponownie, chwytając zewnętrzny czarny kawałek). Jest to gadżet jednorazowego użytku (ponieważ czarny kawałek wyjścia można uchwycić tylko raz).

Po drugie, zwrotnica. Jeśli król wejdzie przez A (C), może wyjść w B (D). Nie może zatrzymać się na środku i zmieniać tras, ponieważ byłby to nieuchwytny segment ruchu.

Teraz, mając skierowany wykres, skonstruuj odpowiednią konfigurację gry w następujący sposób. Dla każdego wierzchołka stwórz scalenie, które zasila się na podział. Kieruj podzielone wyjścia do danych wejściowych scalania gadżetów wierzchołków (scalanie + podział) odpowiadających wierzchołkom, z którymi wychodzące krawędzie łączą się, używając w razie potrzeby zwrotnic. Rozpocznij króla od dodatkowego wejścia do dowolnego wierzchołka (z czarnym kawałkiem do przechwycenia, aby mógł wejść do wierzchołka).

Na koniec wyrównaj wszystkie „długości krawędzi”, dodając w razie potrzeby dodatkowe czarne elementy wzdłuż ścieżek wyjściowych / wejściowych. Jeśli są V wierzchołki i k czarnych kawałków wzdłuż każdej krawędzi, król może przechwycić 2 V + kV + 1 sztuk, tylko wtedy, gdy istnieje obwód hamiltonowski na odpowiednim wykresie. Jeśli król ma dostępny ruch alternatywny, przechwycenie prostego łańcucha elementów 2 V + kV, a następnie ustalenie, czy ten ruch alternatywny jest legalny, jest NP-zakończone.

Bob Hearn
źródło
2
Niezła redukcja!
Jeffε
Ale czy potrafisz odpowiedzieć na drugie pytanie? Czy wygrywanie jednym ruchem NP-trudne?
Jeffε
Może ... Myślę, że gadżety można zmodyfikować, aby po ukończeniu obwodu hamiltonowskiego król mógł następnie przechwycić wszystkie czarne elementy na „drutach”. Scalanie / dzielenie elementów wewnętrznych nadal musiałoby zostać przechwycone podczas obwodu hamiltonowskiego, więc nadal byłoby trudne NP. Pomysł polegałby na otwarciu luk w korytarzach przylegających do czarnych elementów, które pozwoliłyby na przejście korytarzy, ale bez wyjścia z wnętrza.
Bob Hearn
Wydaje mi się, że zajęłoby to także dodatkowe urządzenia nawigacyjne poza korytarzami, ale powinno być wykonalne.
Bob Hearn
5

Oto możliwa alternatywa dla redukcji Boba, tym razem z (nieukierowanego) cyklu hamiltonowskiego. Nie jestem w 100% pewien, że szczegóły są poprawne - już znalazłem i naprawiłem kilka problemów - ale jestem pewien, że można je wmasować we właściwy dowód. Jak podkreśla Bob, ta redukcja ma poważny błąd; biały król może łatwo zejść ze swojej kanonicznej ścieżki przez planszę. Ten błąd można naprawić, dodając gadżet crossovera Boba w odpowiednich lokalizacjach (tak myślę) , ale nie różni się on znacznie od jego redukcji.

Niech będzie niekierowanym wykresem z wierzchołkami i krawędziami . Narysuj w płaszczyźnie, umieszczając jej wierzchołki w regularnie rozmieszczonych punktach na linii o nachyleniu i rysując każdą krawędź jako odcinek poziomy plus odcinek pionowy, oba powyżej linii wierzchołków.n m G - 1GnmG1

Teraz zmniejszamy ten rysunek do planszy (obróconej o 45 stopni) z czarnymi szachownicami i jednym białym królem. Potrzebujemy trzech rodzajów gadżetów: narożników, rozgałęźników i hord. Narożnik zawiera dwa czarne elementy, które można schwytać razem, zmieniając kierunek białego króla. -splitter zawiera pojedynczy element, który musi być zrobione w określonym kierunku, z miejsc szczególnych dla króla przechwytywania wskoczyć. Wreszcie, skarb to duża skrzynia pełna czarnych kawałków, które muszą być schwytane w określonej kolejności, dla pewnej dużej stałej . Na poniższych rysunkach szare koła są elementami, których nie można uchwycić.O ( n 2 + m ) k k h n hO(n2)×O(n2)O(n2+m)kkhnh

gadżet narożny

poziomy gadżet z 4 rozdzielaczami

gadżet skarbów

Teraz zamień każdy wierzchołek stopnia na skarb, podłączony do poziomego rozdzielacza i pionowego rozdzielacza. Dla każdej krawędzi umieść stałą liczbę narożników wyrównanych z rozdzielaczami dla skarbu i skarbu . Jest to łatwe przygotowanie rogach dla różnych krawędziach leżeć pod różnymi - i -coordinates. Umieść białego króla w jednym ze skarbów, w pozycji pokazanej przez biały okrąg powyżej.k k ( i , j ) i j x ykkk(i,j)ijxy

jedna krawędź

Biały król może schwytać co najmniej przeciwległych elementów - każdy element w każdym skarbie plus cztery dodatkowe elementy krawędzi na wierzchołek - tylko wtedy, gdy wykres jest hamiltonianem.Ghn2+4nG

Jeffε
źródło
Bardzo dobrze. Ale widzę kilka problemów, z których jeden ma również moja redukcja. Po pierwsze, kiedy król wychodzi z rogu, może zatrzymać się w dowolnym miejscu, potencjalnie umożliwiając mu niewłaściwe wejście do innego rogu. Po drugie, nic nie zmusza króla do powrotu do początkowego wierzchołka; może kończyć się na dowolnym wierzchołku. Mój ma ten sam problem, ale można go łatwo naprawić w celu zmniejszenia, dodając odpowiedni dodatkowy element, aby uchwycić go w wierzchołku początkowym.
Bob Hearn,
Drugi problem jest łatwy do rozwiązania: przenieś miejsce początkowe króla w głąb hordy.
Jeffε
Ale pierwszy problem jest poważniejszy. Myślę, że w końcu potrzebujemy twoich crossoverowych gadżetów. Drat!
Jeffε
Myślę, że usunięcie czarnego elementu wyjściowego z gadżetu narożnego i dodanie czarnego elementu na każdym ramieniu rozdzielacza wejściowego dla każdego wierzchołka może również załatwić sprawę.
Bob Hearn,
3

Dlaczego nie przedstawiłeś mi tego problemu, kiedy pracowałem nad moją pracą magisterską?

OK, mam redukcję z Planarskiego cyklu Hamiltonianowskiego.

Bob Hearn
źródło
1
Powiedz! (Czy możesz krótko opisać redukcję?)
Ryan Williams
Przepraszam, Bob; wtedy o tym nie myślałem. Tak, proszę opisać (lub link do) obniżkę!
Jeffε
To nie jest tak naprawdę odpowiedź.
Dave Clarke
1
Nie ... Myślałem, że dodałem wtedy komentarz. Teraz nie widzę, jak dodać komentarz do głównego postu.
Bob Hearn
Potrzebujesz 100 reputacji, aby dodać komentarz. To feechur.
Jeffε