Ist das Brettspiel "Go" NP abgeschlossen?

Question

Es gibt viele Schach-KI's, und offensichtlich sind einige gut genug, um einige der größten Spieler der Welt zu schlagen.

Ich habe gehört, dass viele Versuche unternommen wurden, erfolgreiche AI's für das Brettspiel Go zu schreiben, aber bis jetzt wurde nichts über den durchschnittlichen Amateurlevel hinaus gedacht.

Könnte es sein, dass die Aufgabe, die optimale Bewegung zu einem bestimmten Zeitpunkt in Go mathematisch zu berechnen, ein NP-vollständiges Problem ist?

Answer 1

Schach und Go sind beide EXPTIME complete. IIRC, Go hat mehr mögliche Züge, daher halte ich es für ein höheres Vielfaches dieser Komplexitätsklasse als Schach. Wikipedia hat eine good article über die Komplexität von Go.

Answer 2

Auch wenn Go ist nur in P könnte es etwas sein, noch horrend wie O(n^m) wo n die Anzahl der Räume und m ist einige (große) festgelegte Anzahl. Selbst in P zu sein macht nichts vernünftiges zu berechnen.

Answer 3

Weder Chess or Go AIs bewerten alle Möglichkeiten vollständig, bevor Sie sich für einen Zug entscheiden.

Schach-AIs verwenden verschiedene Heuristiken, um den Suchraum einzuschränken und um zu quantifizieren, wie gut eine gegebene Position auf der Tafel ist. Dies kann rekursiv durchgeführt werden, indem mögliche Platinenpositionen bewertet werden 14-15 bewegt sich voraus und wählt einen Pfad, der zu einer guten Position führt.

Es gibt ein bisschen "Magie" darin, wie eine Brettposition quantifiziert wird, so dass die KI auf der obersten Ebene einfach gehen kann Move A> Move B deshalb Move A. Aber da gibt es eine begrenzte Anzahl an Teilen und sie alle haben einen quantifizierbaren Wert und ein 'gut genug' Algorithmus kann implementiert werden.

Aber es ist viel schwieriger für ein Programm, zwei mögliche Boardpositionen in Go auszuwerten und diese A> B Berechnung zu machen. Ohne dieses kritische Stück ist es etwas schwierig, den Rest der KI zu arbeiten.