Branching Factor und Tiefe

Question

Frage

Ein einfaches Zwei-Spieler-Spiel beinhaltet einen Stapel von N Streichhölzer und zwei Spieler, die abwechselnd Windungen haben. In jedem Spielzug entfernt ein Spieler 1, 2 oder 3 Streichhölzer vom Stapel. Der Spieler, der den letzten Streichholz entfernt, verliert das Spiel.

A) Was sind der Verzweigungsfaktor und die Tiefe des Spielbaums (geben Sie eine allgemeine Lösung, ausgedrückt in N)? Wie groß ist die Suche Platz?

B) Wie viele einzigartige Zustände gibt es im Spiel? Für große N, was könnte getan werden, um die Suche effizienter zu machen?

Antwort

A) sagte ich der Verzweigungsfaktor 3 sein würde, aber ich gerechtfertigt, weil der Spieler nur könnte je 3 Ursachen entfernen up, unseren Baumes in der Regel drei Kinder haben würde Sinn. Der zweite Teil in Bezug auf die Tiefe, bin ich mir nicht sicher.

B) N x 2 wobei N die Anzahl der verbleibenden Treffer ist. Ich bin mir nicht sicher, wie wir die Suche effizienter gestalten könnten. Vielleicht Einführung von Alpha-Beta-Beschneidung?

Answer 1

A: Für die Tiefe, stellen Sie sich vor, was die längste mögliche Spiel aussehen würde. Es ist das Spiel, das aus beiden Spielern besteht, die nur 1 Match in jedem Zug entfernen. Da es n Übereinstimmungen gibt, würde ein solches Spiel n Runden dauern: der Baum hat die Tiefe n.

B: Es gibt nur 2 * N-Zustände, von denen jeder aus 3 Zuständen höherer Matchstick-Anzahl zugänglich ist. Da die Anzahl der Übereinstimmungen im Laufe des Spiels notwendigerweise abnimmt, ist der Graph der möglichen Zustände ein DAG (Directed Acyclic Graph). Ein dynamisches Programmierverfahren ist daher möglich, um dieses Spiel zu analysieren. Am Ende sehen Sie, dass die optimale Bewegung nur von N mod 4 abhängt, wobei N die Anzahl der verbleibenden Treffer ist.

EDIT: Beweisidee für die N mod 4: Jede Position ist entweder eine verlierende oder eine gewinnende Position. Eine Verlustposition ist eine Situation, in der, egal, was Sie spielen, Ihr Gegner optimal spielt und Sie verlieren. In ähnlicher Weise ist eine Gewinnposition eine Situation, in der der Gegner nicht gewinnen kann, wenn Sie die richtigen Züge spielen. N = 1 ist eine Verlustposition (nach Definition des Spiels). Daher sind N = 2,3,4 Gewinnpositionen, weil Sie den Gegner durch Verlieren der richtigen Anzahl von Spielen in eine verlierende Position bringen. N = 5 ist eine Verlustposition, denn unabhängig davon, welche zulässige Anzahl von Spielen Sie entfernen, bringen Sie den Gegner in eine Gewinnposition. N = 6,7,8 sind Gewinnpositionen ... Sie bekommen die Idee.

Jetzt geht es nur darum, diesen Beweis formell zu machen: Nehmen Sie als Hypothese, dass eine Position N eine Verlustposition ist, wenn und nur wenn N mod 4 = 1. Wenn das bis zu einer Ganzzahl k gilt, können Sie beweisen, dass es für k+1 gilt. Es ist gültig bis k = 4 wie wir zuvor gezeigt haben. Bei Wiederholung gilt dies für alle N.

Answer 2

Der Zustand des Spiels jederzeit durch wiederum deren beschrieben ist und die Anzahl der von jedem Spieler gehalten Begegnungen. Nach n Zügen gibt es 3^n mögliche Historien, aber für große n, viele weniger als 3^n mögliche Zustände, so dass Sie Zeit sparen können, indem Sie zum Beispiel erkennen, dass Sie einem Zustand begegnen, den Sie bereits kennengelernt haben ausgearbeitet einen Wert für vorher.

Siehe auch https://en.wikipedia.org/wiki/Nim - falls dieser Nim ist, oder eine Vielzahl von Nim gibt es bereits effiziente Strategien für sie ausgearbeitet.