artificial-intelligence - juego - alphago zero

¿El juego de mesa “Go” NP está completo?

Question

Hay un montón de AI de ajedrez por ahí, y evidentemente algunos son lo suficientemente buenos como para vencer a algunos de los mejores jugadores del mundo.

He oído que se han hecho muchos intentos para escribir AI con éxito para el juego de mesa Go , pero hasta ahora no se ha concebido nada más allá del nivel medio amateur.

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

Answer 1

Chess and Go están EXPTIME completos . 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 buen artículo sobre la complejidad de Go.

Answer 2

Ni las IA de Ajedrez ni de Go evalúan completamente todas las posibilidades antes de decidir un movimiento.

Las IA del ajedrez utilizan diversas heurísticas para reducir el espacio de búsqueda y para cuantificar qué tan "buena" es una posición dada en el tablero. Esto se puede hacer de forma recursiva al evaluar las posibles posiciones de la tabla 14-15, avanzando y eligiendo un camino que lleve a una buena posición.

Hay un poco de "magia" en cómo se cuantifica la posición de una tabla, de modo que en el nivel superior, la IA puede simplemente mover Mover A> Mover B, por lo tanto, hagamos Mover A. Pero ya que hay un número limitado de piezas y todas tienen valor cuantificable se puede implementar un algoritmo ''suficientemente bueno''.

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

Answer 3

Incluso si Go está simplemente en P , podría ser algo horrible 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 computar algo.