Es el juego de mesa “Ir” NP completa?

Question

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

He oído que se han hecho muchos intentos para escribir con éxito la IA del juego de la junta Ir , pero hasta ahora nada se ha concebido más allá del nivel aficionado medio.

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

Answer 1

Ajedrez y Go son tanto EXPTIME completa . IIRC, Go tiene más movimientos posibles, así que creo que un múltiplo más alto de esa clase de complejidad que el ajedrez. Wikipedia tiene una buena artículo sobre la complejidad de Ir.

Answer 2

Aunque Go es sólo en P aún 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 estando en P no hace algo razonable para calcular.

Answer 3

Ni ajedrez o va a evaluar inhibidores de la aromatasa por completo todas las posibilidades antes de decidir un movimiento.

Ajedrez IA utiliza diversas heurísticas para reducir el espacio de búsqueda, y para cuantificar la 'buena' una posición dada en el tablero pasa a ser. Esto se puede hacer de forma recursiva mediante la evaluación de posibles posiciones en el tablero 14-15 se mueve adelante y elegir un camino que conduce a una buena posición.

Hay un poco de 'magia' en la forma en que se cuantifica una posición en el tablero por lo que el que en el nivel superior, la IA puede simplemente ir a mover una> mover, por lo tanto B permite hacer mover A. Pero ya que hay un número limitado de piezas y todos ellos tienen un valor cuantificable 'suficientemente bueno' algoritmo puede ser implementado.

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