È il gioco da tavolo “Go” NP completo?

Question

Ci sono un sacco di circa di scacchi AI, ed evidentemente alcuni sono sufficiente per battere alcuni dei più grandi giocatori del mondo.

Ho sentito che molti tentativi sono stati fatti per scrivere con successo IA per il gioco da tavolo Go , ma finora nulla è stato concepito al di là di livello amatoriale media.

E 'possibile che il compito di calcolare matematicamente la mossa ottimale in un dato momento in Go è un problema NP-completo?

Answer 1

Scacchi e Go sono entrambi EXPTIME completa . IIRC, Go ha più mosse possibili, quindi penso che una maggiore multiplo di quella classe di complessità di scacchi. Wikipedia ha una buon articolo della complessità del Go.

Answer 2

Anche se Go è solo in P potrebbe essere ancora qualcosa di orrendo come O(n^m) dove n è il numero di spazi e m è un po '(grande) numero fisso. Pur essendo in P non fa qualcosa di ragionevole per calcolare.

Answer 3

Né scacchi o Go IA valutare completamente tutte le possibilità prima di decidere su una mossa.

IA scacchi utilizzano varie euristiche per restringere lo spazio di ricerca, e di quantificare una data posizione 'buono' sul tabellone sembra essere. Questo può essere fatto in modo ricorsivo valutando le possibili posizioni di bordo 14-15 si muove avanti e la scelta di un percorso che conduce ad una buona posizione.

C'è un po 'di 'magia' nel modo in cui una posizione di bordo viene quantificata in modo che il che al livello più alto, l'IA può semplicemente andare spostare un> Sposta B consente quindi si muovono A. Ma dal momento che c'è un numero limitato di pezzi e tutti hanno valore quantificabile un algoritmo 'abbastanza buona' può essere implementato.

Ma si scopre di essere molto più difficile per un programma per valutare due possibili posizioni di bordo di andare a fare che il calcolo A> B. Senza questo pezzo critico è un po 'difficile fare il resto del lavoro AI.