¿Está completo el juego de mesa "Go" NP?

Question

Hay muchas IA de ajedrez, y evidentemente algunas son lo suficientemente buenas para derrotar a algunos de los mejores jugadores del mundo.

He oído que se han realizado muchos intentos para escribir exitosas IA para el juego de mesa Go, pero hasta ahora nada se ha concebido más allá del nivel promedio de aficionados.

¿Podría ser que la tarea de calcular matemáticamente el movimiento óptimo en un momento dado en Go es un problema NP-completo?

Answer 1

Chess and Go son ambos EXPTIME complete. IIRC, Go tiene más movimientos posibles, así que creo que es un múltiplo más alto de esa clase de complejidad que el ajedrez. Wikipedia tiene un good article sobre la complejidad de Go.

Answer 2

Aunque Go es sólo en P todavía podría ser algo horrendo como O(n^m) donde n es el número de espacios y m es un número fijo (grande). Incluso estar en P no hace que sea razonable calcular.

Answer 3

Ni Chess ni Go AI evalúan completamente todas las posibilidades antes de decidirse por un movimiento.

Ajedrez Las IA usan varias heurísticas para delimitar el espacio de búsqueda y para cuantificar cuán 'buena' es una posición determinada en el tablero. Esto se puede hacer de forma recursiva evaluando posibles posiciones de la tabla 14-15 movimientos por delante y eligiendo una ruta que conduzca a una buena posición.

Hay un poco de "magia" en cómo se cuantifica una posición de tablero así que en el nivel superior, la IA simplemente puede ir Mover A> Mover B, por lo tanto, mover A. Pero como hay un número limitado de piezas y todos tienen un valor cuantificable, se puede implementar un algoritmo "lo suficientemente bueno".

Pero resulta ser mucho más difícil para un programa evaluar dos posibles posiciones de la placa en Ir y hacer ese cálculo A> B. Sin esa pieza crítica es un poco difícil hacer que el resto de la IA funcione.