Ist es NP-schwer, internationale Drafts korrekt zu spielen?

26

Ist das folgende Problem NP-schwer?

Wenn Sie eine Kartenkonfiguration für internationale Entwürfe haben , finden Sie einen einzigen legalen Schritt.n×n

Das entsprechende Problem für amerikanische Kontrolleure (auch englische Entwürfe genannt) ist in der Polynomzeit trivial lösbar. Es gibt drei Hauptunterschiede zwischen diesen beiden Spielen.n×n

Der erste und wichtigste Unterschied ist die Regel des „fliegenden Königs“. Bei Dame kann ein König über eine benachbarte gegnerische Figur in zwei Schritten Entfernung in eine beliebige diagonale Richtung auf ein leeres Feld springen . In internationalen Entwürfen kann ein König über ein gegnerisches Teil in beliebiger Entfernung springen, indem er eine beliebige Entfernung entlang einer Diagonale zurücklegt.

Wie bei Dame kann das gleiche Stück verwendet werden, um eine Reihe von Stücken in einer einzigen Runde zu erfassen. Im Gegensatz zu Checkern werden erfasste Teile in internationalen Entwürfen jedoch erst nach Ablauf der gesamten Sequenz entfernt. Die einfangende Figur kann mehrmals über dasselbe leere Feld springen oder auf diesem landen, sie darf jedoch nicht mehr als einmal über die gegnerische Figur springen.

Schließlich haben sowohl Kontrolleure als auch internationale Drafts eine erzwungene Eroberungsregel: Wenn Sie die Figur eines Gegners erobern können, müssen Sie dies tun. Die Regelregeln stimmen jedoch nicht überein, wenn es mehrere Optionen für mehrere gibt. Bei Checkern können Sie eine beliebige maximale Abfolge von Erfassungen auswählen . Mit anderen Worten, Sie können eine beliebige Erfassungssequenz auswählen, die endet, wenn das Erfassungsstück nicht mehr erfasst werden kann. Bei internationalen Entwürfen müssen Sie die längste Abfolge von Erfassungen auswählen . Mein Problem ist also gleichbedeutend mit:

Suchen Sie bei einer Kartenkonfiguration für internationale Entwürfe einen Zug, der die maximale Anzahl der gegnerischen Figuren erfasst.n×n

Es würde genügen zu beweisen, dass das folgende Problem NP-vollständig ist. (Es ist offensichtlich in NP.)

Kann (und muss) eine Spielerin bei einer Brettkonfiguration für internationale Drafts, an denen nur Könige beteiligt sind , alle gegnerischen Figuren in einem Zug erobern ?n×n

Das entsprechende Checker-Problem kann in Polynomialzeit beantwortet werden. Dies ist eine unterhaltsame Hausaufgabe. Das Problem ähnelt eher Demaine, Demaine und Eppsteins Analyse der Phutball-Endspiele . Eine Lösung für die unterhaltsame Hausaufgabe erscheint am Ende ihrer Arbeit. Eine Lösung findet sich auch in der Veröffentlichung von Frankel et al. das beweist, dass es PSPACE-schwer ist, Dame optimal zu spielen; siehe auch Robsons 1984er Beweis, dass Checker tatsächlich EXPTIME-vollständig sind.

Jeffε
quelle
Tippfehler ? "es ist offensichtlich in P" - vielleicht meinst du "in NP"? Woher bekommen Sie diese Fragen?
Suresh Venkat
Ja, behoben. Das Problem wurde ebenfalls umformuliert. Es ist nicht klar, dass die Anzahl der legalen Züge von einer bestimmten Position nur ein Polynom ist.
Jeffs
Dieser stammt aus dem Schreiben einer Lösung für die "unterhaltsame Hausaufgabe".
Jeffs
Ich denke, die unausgesprochene zusätzliche Frage hier ist, wie komplex das Spiel selbst ist (um festzustellen, ob ein Spieler gewinnen kann). Ist es EXPTIME-vollständig, wie es die Kontrolleure tun? Wahrscheinlich, aber der Beweis für die Kontrolleure ist ziemlich kompliziert.
Bob Hearn

Antworten:

24

OK, hier ist die Reduktion. Es stellt sich heraus, dass Sie keine Planarität brauchen. Auch für "einen legalen Zug finden" nehme ich die Entscheidungsfrage als "ist Zug X legal?".

Lassen Sie uns stattdessen mit einem Spiel arbeiten, bei dem sich Teile orthogonal statt diagonal bewegen. Dieses Spiel ist äquivalent (sehen Sie sich nur das um 45 Grad gedrehte Zeichenbrett an), mit Ausnahme der Kanteneigenschaften, die wir nicht verwenden werden. Wir verwenden zwei Gadgets: Merge / Split und Crossover. Siehe http://www.hearn.to/draughts.pdf . Wir nehmen an, es gibt einen einzigen weißen König auf dem Brett, der bewegt werden kann. (Kein anderes Objekt kann eine signifikante Anzahl von Objekten erfassen.) Es bewegt sich durch die angegebenen Korridore und erfasst dabei schwarze Objekte.

Zuerst verschmelzen: Wenn der König auf einem der N Pfade A eintritt (indem er ein nicht gezeigtes schwarzes Stück einnimmt), kann er bei B aussteigen. es kann entlang eines beliebigen Pfades A austreten (wieder ein äußeres schwarzes Stück einfangen). Dies ist ein Einweg-Gadget (da das schwarze Ausgangsstück nur einmal erfasst werden kann).

Zweitens Crossover. Wenn der König über A (C) eintritt, kann er bei B (D) aussteigen. Es kann nicht in der Mitte anhalten und die Route ändern, da dies ein nicht erfassendes Bewegungssegment wäre.

Konstruieren Sie nun anhand eines gerichteten Graphen eine entsprechende Spielkonfiguration wie folgt. Erstellen Sie für jeden Scheitelpunkt eine Zusammenführung, die in eine Teilung eingeht. Leiten Sie die geteilten Ausgaben zu den Zusammenführungseingängen der Scheitelpunkt-Minianwendungen (Zusammenführen + Teilen), die den Scheitelpunkten entsprechen, mit denen die ausgehenden Kanten verbunden sind, und verwenden Sie bei Bedarf Überkreuzungen. Starten Sie den König mit einer zusätzlichen Eingabe für einen beliebigen Scheitelpunkt (mit einem schwarzen Teil, den Sie einfangen müssen, damit er in den Scheitelpunkt eintritt).

Zum Schluss gleichen Sie alle "Kantenlängen" an, indem Sie nach Bedarf zusätzliche schwarze Teile entlang der Ausgabe- / Eingabepfade hinzufügen. Wenn es V Ecken und k schwarze Teile entlang jeder Kante gibt, kann der König 2V + kV + 1 Teile erfassen, wenn und nur wenn es eine Hamilton-Schaltung des entsprechenden Graphen gibt. Wenn dem König ein alternativer Zug zur Verfügung steht, ist es NP-vollständig, eine einfache Kette von 2V + kV-Teilen zu erfassen, um festzustellen, ob dieser alternative Zug zulässig ist.

Bob Hearn
quelle
2
Schöne Ermäßigung!
Jeffs
Aber können Sie die zweite Frage beantworten? Ist es NP-schwer, in einem Zug zu gewinnen?
Jeffs
Vielleicht ... Ich denke, dass die Geräte so modifiziert werden könnten, dass der König nach Abschluss einer Hamilton-Schaltung alle schwarzen Teile auf den "Drähten" einfangen könnte. Die Merge / Split-internen Teile müssten noch während der Hamilton-Schaltung erfasst werden, so dass es noch NP-schwer wäre. Die Idee wäre, Lücken in den Korridoren zu öffnen, die an die schwarzen Teile angrenzen, damit die Korridore gekreuzt, aber nicht von innen verlassen werden können.
Bob Hearn
Ich denke, es würde auch einige zusätzliche Navigationsgeräte außerhalb der Korridore erfordern, aber es sollte machbar sein.
Bob Hearn
5

Hier ist eine mögliche Alternative zu Bobs Reduktion, diesmal aus dem (ungerichteten) Hamilton-Zyklus. Ich bin nicht zu 100% davon überzeugt, dass die Details korrekt sind - ich habe bereits mehrere Probleme gefunden und behoben -, aber ich bin sicher, dass sie in einen korrekten Beweis umgewandelt werden können. Wie Bob betont, hat diese Reduzierung einen schwerwiegenden Fehler. Der weiße König kann leicht von seinem kanonischen Weg durch das Brett abweichen. Dieser Fehler kann behoben werden, indem das Cross-Over-Gadget von Bob an geeigneten Stellen hinzugefügt wird (glaube ich) , aber dann unterscheidet es sich nicht wesentlich von seiner Reduzierung.

GnmG-1

O(n2)×O(n2)O(n2+m)kkhnh

Eckgerät

horizontales 4-Splitter-Gerät

Hort-Gadget

kkk(ich,j)ichjxy

eine Kante

hn2+4nG

Jeffε
quelle
Sehr schön. Aber ich sehe ein paar Probleme, von denen eines auch meine Reduktion hat. Erstens kann der König, wenn er eine Ecke verlässt, irgendwo anhalten und möglicherweise eine andere Ecke unangemessen betreten. Zweitens gibt es nichts, was den König zwingen könnte, zum ursprünglichen Scheitelpunkt zurückzukehren. es könnte auf jedem Scheitelpunkt enden. Meins hat das gleiche Problem, aber es kann leicht für jede Reduzierung behoben werden, indem ein entsprechendes zusätzliches Stück hinzugefügt wird, um es im Startscheitelpunkt zu erfassen.
Bob Hearn
Das zweite Problem lässt sich leicht beheben: Verschieben Sie den Startpunkt für den König tiefer in die Horde.
Jeffs
Das erste Problem ist jedoch schwerwiegender. Ich denke, wir brauchen doch Ihre Crossover-Geräte. Drat!
Jeffs
Ich denke, das Entfernen des schwarzen Ausgangsstücks aus dem Ecken-Gadget und das Hinzufügen eines schwarzen Stücks an jedem Arm des Eingangssplitters für jeden Scheitelpunkt könnte ebenfalls den Trick bewirken.
Bob Hearn
3

Warum haben Sie mir dieses Problem nicht gestellt, als ich an meiner Dissertation arbeitete?

OK, ich habe eine Reduktion von Planar Directed Hamiltonian Cycle.

Bob Hearn
quelle
1
Erzählen Sie! (Können Sie die Reduzierung kurz beschreiben?)
Ryan Williams
Entschuldigung, Bob; Ich habe damals nicht daran gedacht. Ja, bitte beschreiben (oder verlinken) Sie die Ermäßigung!
Jeffs
Dies ist keine wirkliche Antwort.
Dave Clarke
1
Nein ... Ich dachte, ich würde zu der Zeit einen Kommentar hinzufügen. Ich verstehe jetzt nicht, wie ich dem Hauptbeitrag einen Kommentar hinzufügen kann.
Bob Hearn
Sie benötigen 100 Ruf, um einen Kommentar hinzuzufügen. Es ist ein Feechur.
Jeffs