o jogo de tabuleiro “Go” NP está completa?

Question

Há uma abundância de cerca de Xadrez AI, e, evidentemente, alguns são bons o suficiente para bater alguns dos maiores jogadores do mundo.

Ouvi dizer que muitas tentativas foram feitas para escrever bem sucedida AI para o jogo de tabuleiro Go , mas até agora nada foi concebida além do nível médio amador.

Será que a tarefa de calcular matematicamente o melhor movimento a qualquer momento em Go é um problema NP-completo?

Answer 1

Xadrez e Go são ambos EXPTIME completa . IIRC, Go tem mais movimentos possíveis, então eu acho que a maior múltiplo de que classe de complexidade que o xadrez. Wikipedia tem um bom artigo da complexidade do Go.

Answer 2

Mesmo Go é meramente em P poderia ainda ser algo horrendo como O(n^m) onde n é o número de espaços e m alguma (grande) número fixo. Mesmo estando em P não faz algo razoável de computação.

Answer 3

Nem xadrez ou Go AIs avaliar completamente todas as possibilidades antes de decidir sobre um movimento.

Chess AIs utilizar várias heurísticas para diminuir o espaço de busca, e para quantificar como 'bom' uma determinada posição no conselho passa a ser. Isso pode ser feito de forma recursiva, avaliando possíveis posições do tabuleiro 14-15 movimentos adiante e escolher um caminho que leva a uma posição boa.

Há um pouco de 'magia' em como a posição do tabuleiro é quantificada de modo a que, no nível superior, o AI pode simplesmente ir mover um> Mover B, portanto, permite que se mova A. Mas uma vez que há um número limitado de peças e todos eles têm valor quantificável de um algoritmo de 'bom o suficiente' pode ser implementado.

Mas acaba por ser muito mais difícil para um programa para avaliar duas posições do tabuleiro possíveis em Go e fazer com que A> B cálculo. Sem essa peça fundamental é um pouco difícil de fazer o resto do trabalho AI.