Il gioco da tavolo "Go" NP è completo?

Question

Ci sono un sacco di IA di scacchi in giro, ed evidentemente alcune sono abbastanza buone da battere alcuni dei più grandi giocatori del mondo.

Ho sentito che sono stati fatti molti tentativi per scrivere AI di successo per il gioco da tavolo Go, ma finora nulla è stato concepito oltre il livello medio amatoriale.

Potrebbe essere che il compito di calcolare matematicamente la mossa ottimale in un dato momento in Go sia un problema NP-completo?

Answer 1

Chess and Go sono entrambi EXPTIME complete. IIRC, Go ha più mosse possibili, quindi penso che sia un multiplo più alto di quella classe di complessità rispetto agli scacchi. Wikipedia ha un good article sulla complessità di 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. Anche essere in P non rende qualcosa di ragionevole da calcolare.

Answer 3

Nessuna delle IA di scacchi o Go valuta completamente tutte le possibilità prima di decidere su una mossa.

Gli IA di scacchi utilizzano varie euristiche per restringere lo spazio di ricerca e per quantificare quanto "buona" sia una determinata posizione sulla scacchiera. Questo può essere fatto in modo ricorsivo valutando le possibili posizioni della tavola 14-15 avanti e scegliendo un percorso che porti ad una buona posizione.

C'è un po 'di "magia" nel modo in cui una posizione di bordo viene quantificata in modo tale che al livello più alto, l'intelligenza artificiale può semplicemente andare Sposta A> Muovi B quindi lascia spostare A. Ma poiché c'è un numero limitato di pezzi e tutti hanno un valore quantificabile che può essere implementato un algoritmo 'abbastanza buono'.

Ma risulta molto più difficile per un programma valutare due possibili posizioni della scheda in Go e effettuare il calcolo A> B. Senza quel pezzo critico è un po 'difficile far funzionare il resto dell'intelligenza artificiale.