Le jeu de plateau "Go" NP est-il terminé?

Il ya beaucoup d'IA Chess autour, et évidemment certains sont assez bons pour battre certains des plus grands joueurs du monde. J'ai entendu dire que de nombreuses tentatives ont été faites pour écrire des IA réussies pour le jeu de plateau Go, mais jusqu'à présent rien n'a été conçu au-delà du niveau d'amateur moyen.Le jeu de plateau "Go" NP est-il terminé?

Est-ce que la tâche consistant à calculer mathématiquement le mouvement optimal à un moment donné dans Go est un problème NP-complet?

Source

2009-11-12 sharkin

Vous ne savez pas pourquoi vous avez été abaissé. C'est une question légitime. +1 – mpen

Eh bien, les algorithmes actuels de Monte Carlo et similaires ont poussé la frontière au niveau amateur moyen. Les noms à rechercher comprennent Zenith, Many Faces of Go, Fuego, Leela, entre autres. – Svante

Echecs et Go sont tous les deux EXPTIME complete. IIRC, Go a plus de mouvements possibles, donc je pense que c'est un multiple plus élevé de cette classe de complexité que les échecs. Wikipedia a un good article sur la complexité de Go.

Source

2009-11-12 23:28:18 rmeador

+12

Vous pourriez mentionner que les deux résultats sont pour des versions généralisées des jeux. Les jeux avec des cartes de taille constante peuvent, trivialement, être tous deux résolus en temps constant. (Bien que la constante soit trop grande pour que nous puissions y faire face maintenant, et peut-être jamais.) – ShreevatsaR

En ce qui concerne la compréhension de ce que signifie un expert: «Les échecs sont EXPTIME-complets» Le point de ShreevatsaR est très important. – PeterAllenWebb

Même si Go est seulement dans P il pourrait encore être quelque chose comme horrible O(n^m) où n est le nombre de places et m est une (grande) nombre fixe. Même être dans P ne rend pas quelque chose de raisonnable à calculer.

Source

2009-11-13 04:52:17 BCS

Ni les IA d'échecs ni de Go n'évaluent complètement toutes les possibilités avant de décider d'un coup.

Les IA d'échecs utilisent diverses heuristiques pour affiner l'espace de recherche et quantifier la «bonne» position d'une position donnée sur la carte. Cela peut être fait de manière récursive en évaluant les positions possibles du tableau 14-15 et en choisissant un chemin qui mène à une bonne position. Il y a un peu de 'magie' dans la façon dont une position de la carte est quantifiée, donc au niveau supérieur, l'IA peut simplement aller Déplacer A> Déplacer B donc faire le Déplacer A. Mais comme il y a un nombre limité de pièces et ils ont tous une valeur quantifiable un algorithme «assez bon» peut être mis en œuvre.

Mais il s'avère qu'il est beaucoup plus difficile pour un programme d'évaluer deux positions de carte possibles dans Go et d'effectuer ce calcul A> B. Sans cette pièce critique, c'est un peu difficile de faire le reste de l'IA.

Source

2009-11-28 05:28:53

Le jeu de plateau "Go" NP est-il terminé?

Répondre

Questions connexes