Ist das Brettspiel "Go" NP vollständig?

Question

Es gibt jede Menge Schach-KI, und offensichtlich sind einige von ihnen gut genug, um einige der besten Spieler der Welt zu schlagen.

Ich habe gehört, dass schon viele Versuche unternommen wurden, eine erfolgreiche KI für das Brettspiel Weiter aber bisher wurde nichts konzipiert, was über ein durchschnittliches Amateurniveau hinausgeht.

Könnte es sein, dass die Aufgabe der mathematischen Berechnung des optimalen Zuges zu einem bestimmten Zeitpunkt in Go ein NP-komplettes Problem ist?

Answer 1

Schach und Go sind beide EXPTIME vollständig . IIRC, Go hat mehr mögliche Züge, also denke ich, dass es ein höheres Vielfaches dieser Komplexitätsklasse ist als Schach. Wikipedia hat eine guter Artikel über die Komplexität von Go.

Answer 2

Selbst wenn Go nur in P es könnte immer noch etwas Schreckliches sein wie O(n^m) où n ist die Anzahl der Leerzeichen und m eine (große) feste Zahl ist. Selbst wenn man in P macht keine vernünftigen Berechnungen möglich.

Answer 3

Weder die Schach- noch die Go-KI werten alle Möglichkeiten vollständig aus, bevor sie sich für einen Zug entscheiden.

Schach-KIs verwenden verschiedene Heuristiken, um den Suchraum einzugrenzen und um zu quantifizieren, wie "gut" eine bestimmte Position auf dem Brett ist. Dies kann rekursiv geschehen, indem mögliche Brettstellungen 14-15 Züge im Voraus bewertet werden und ein Weg gewählt wird, der zu einer guten Stellung führt.

Es gibt ein wenig "Magie" in der Art und Weise, wie eine Brettposition quantifiziert wird, so dass die KI auf der obersten Ebene einfach sagen kann: Zug A > Zug B, also machen wir Zug A. Aber da es eine begrenzte Anzahl von Figuren gibt und sie alle einen quantifizierbaren Wert haben, kann ein "guter" Algorithmus implementiert werden.

Aber es ist viel schwieriger für ein Programm, zwei mögliche Brettpositionen in Go zu bewerten und die Berechnung A > B durchzuführen. Ohne diesen entscheidenden Teil ist es etwas schwierig, den Rest der KI zum Laufen zu bringen.