Ordinateur Go - Computer Go

Computer Go est le domaine de l' intelligence artificielle (IA) dédié à la création d'un programme informatique qui joue au jeu de société traditionnel Go . Le jeu de Go est un sujet fertile de recherche sur l'intelligence artificielle depuis des décennies, culminant en 2017 avec AlphaGo Master remportant trois des trois matchs contre Ke Jie , qui à l'époque détenait en permanence le classement n°1 mondial pendant deux ans.

Performance

Le Go est un jeu de société complexe qui nécessite intuition, réflexion créative et stratégique. Il a longtemps été considéré comme un défi difficile dans le domaine de l' intelligence artificielle (IA) et est considérablement plus difficile à résoudre que les échecs . Beaucoup dans le domaine de l' intelligence artificielle considèrent que le Go requiert plus d'éléments qui imitent la pensée humaine que les échecs . Le mathématicien IJ Good a écrit en 1965 :

Aller sur un ordinateur ? – Afin de programmer un ordinateur pour qu'il joue un jeu raisonnable de Go, plutôt qu'un simple jeu légal – il est nécessaire de formaliser les principes d'une bonne stratégie, ou de concevoir un programme d'apprentissage. Les principes sont plus qualitatifs et mystérieux qu'aux échecs, et dépendent davantage du jugement. Je pense donc qu'il sera encore plus difficile de programmer un ordinateur pour jouer un jeu raisonnable de Go que d'échecs.

Avant 2015, les meilleurs programmes de Go ne parvenaient qu'à atteindre le niveau amateur . Sur le petit plateau 9×9, l'ordinateur s'en sort mieux, et certains programmes réussissent à remporter une fraction de leurs parties 9×9 contre des joueurs professionnels. Avant AlphaGo, certains chercheurs avaient affirmé que les ordinateurs ne battraient jamais les meilleurs humains à Go.

Premières décennies

Le premier programme de Go a été écrit par Albert Lindsey Zobrist en 1968 dans le cadre de sa thèse sur la reconnaissance de formes . Il a introduit une fonction d'influence pour estimer le territoire et le hachage Zobrist pour détecter ko .

En avril 1981, Jonathan K Millen a publié un article dans Byte sur Wally, un programme Go avec une carte 15x15 qui s'insère dans la RAM 1K du micro - ordinateur KIM-1 . Bruce F. Webster a publié un article dans le magazine en novembre 1984 sur un programme Go qu'il avait écrit pour Apple Macintosh , y compris la source MacFORTH .

En 1998, des joueurs très forts étaient capables de battre des programmes informatiques tout en donnant des handicaps de 25 à 30 pierres, un handicap énorme que peu de joueurs humains prendraient jamais. Il y a eu un cas lors du championnat du monde de go de 1994 où le programme gagnant, Go Intellect, a perdu les trois matchs contre les jeunes joueurs tout en recevant un handicap de 15 pierres. En général, les joueurs qui comprenaient et exploitaient les faiblesses d'un programme pouvaient gagner avec des handicaps beaucoup plus importants que les joueurs typiques.

21e siècle

Les développements de la recherche arborescente Monte Carlo et de l'apprentissage automatique ont amené les meilleurs programmes à un niveau dan élevé sur la petite carte 9x9. En 2009, les premiers programmes de ce type sont apparus et pouvaient également atteindre et conserver des rangs de niveau dan bas sur le serveur KGS Go sur la carte 19x19.

En 2010, lors du Congrès Européen de Go 2010 en Finlande, MogoTW a joué 19x19 Go contre Catalin Taranu (5p). MogoTW a reçu un handicap de sept pierres et a gagné.

En 2011, Zen a atteint 5 dan sur le serveur KGS, jouant des parties de 15 secondes par coup. Le compte qui a atteint ce rang utilise une version en cluster de Zen fonctionnant sur une machine à 26 cœurs.

En 2012, Zen a battu Takemiya Masaki (9p) de 11 points avec un handicap de cinq pierres, suivi d'une victoire de 20 points avec un handicap de quatre pierres.

En 2013, Crazy Stone a battu Yoshio Ishida (9p) dans un jeu 19×19 à quatre pierres de handicap.

Le Codecentric Go Challenge 2014, un match au meilleur des cinq dans un match égal 19x19, a été joué entre Crazy Stone et Franz-Jozef Dickhut (6d). Aucun joueur plus fort n'avait jamais accepté de jouer une compétition sérieuse contre un programme de go à égalité. Franz-Jozef Dickhut a gagné, mais Crazy Stone a remporté le premier match avec 1,5 point.

À partir de 2015 : l'ère de l'apprentissage en profondeur

En octobre 2015, le programme AlphaGo de Google DeepMind a battu Fan Hui , le champion d'Europe de Go, cinq fois sur cinq dans des conditions de tournoi.

En mars 2016, AlphaGo a battu Lee Sedol lors des trois premiers des cinq matchs. C'était la première fois qu'un maître de 9 dan jouait un match professionnel contre un ordinateur sans handicap. Lee a remporté le quatrième match, décrivant sa victoire comme « inestimable ». AlphaGo a remporté le match final deux jours plus tard.

En mai 2017, AlphaGo a battu Ke Jie , qui à l'époque était classé premier au monde, dans un match de trois matchs lors du Future of Go Summit .

En octobre 2017, DeepMind a révélé une nouvelle version d'AlphaGo, entraînée uniquement par l'auto-jeu, qui avait dépassé toutes les versions précédentes, battant la version Ke Jie dans 89 des 100 jeux.

Depuis que les principes de base d'AlphaGo avaient été publiés dans la revue Nature , d'autres équipes ont pu produire des programmes de haut niveau. En 2017, les projets Fine Art de Zen et Tencent étaient capables de vaincre des professionnels de très haut niveau à certains moments et le moteur open source Leela Zero est sorti.

Obstacles aux performances de haut niveau

Pendant longtemps, l'opinion largement répandue était que le go informatique posait un problème fondamentalement différent des échecs informatiques . On pensait que les méthodes reposant sur une recherche globale rapide avec relativement peu de connaissances du domaine ne seraient pas efficaces contre les experts humains. Par conséquent, une grande partie de l'effort de développement de Go sur ordinateur était pendant cette période axée sur les moyens de représenter les connaissances d'experts de type humain et de les combiner avec une recherche locale pour répondre à des questions de nature tactique. Il en résulta des programmes qui géraient bien de nombreuses situations mais qui présentaient des faiblesses très prononcées par rapport à leur gestion globale du jeu. En outre, ces programmes classiques n'ont presque rien gagné de l'augmentation de la puissance de calcul disponible en soi et les progrès dans le domaine étaient généralement lents.

Quelques chercheurs ont saisi le potentiel des méthodes probabilistes et ont prédit qu'elles finiraient par dominer le jeu sur ordinateur, mais beaucoup d'autres considéraient qu'un programme de Go-play puissant était quelque chose qui ne pourrait être réalisé que dans un avenir lointain, grâce aux progrès fondamentaux de technologie générale de l'intelligence artificielle. L'avènement des programmes basés sur la recherche Monte Carlo (débuté en 2006) a changé cette situation à bien des égards, les premiers joueurs de Go professionnels de 9 dan ayant été vaincus en 2013 par des ordinateurs multicœurs , bien qu'avec un handicap de quatre pierres.

Taille de la planche

Le grand tableau (19×19, 361 intersections) est souvent considéré comme l'une des principales raisons pour lesquelles un programme solide est difficile à créer. La grande taille du tableau empêche un chercheur alpha-bêta d'effectuer une analyse approfondie sans extensions de recherche importantes ni heuristiques d' élagage .

En 2002, un programme informatique appelé MIGOS (MIni GO Solver) a complètement résolu le jeu de Go pour le plateau 5×5. Les noirs gagnent, prenant tout l'échiquier.

Nombre d'options de déplacement

Poursuivant la comparaison avec les échecs, les mouvements de Go ne sont pas aussi limités par les règles du jeu. Pour le premier coup aux échecs, le joueur a vingt choix. Les joueurs de go commencent avec un choix de 55 mouvements légaux distincts, ce qui représente la symétrie. Ce nombre augmente rapidement à mesure que la symétrie est brisée, et bientôt presque tous les 361 points du tableau doivent être évalués. Certains coups sont beaucoup plus populaires que d'autres et certains ne sont presque jamais joués, mais tous sont possibles.

Fonction d'évaluation

Bien qu'une évaluation de comptage de matériel ne soit pas suffisante pour un jeu décent aux échecs, l'équilibre matériel et divers facteurs de position comme la structure des pions, sont faciles à quantifier.

Ces types de règles d'évaluation de position ne peuvent pas être appliqués efficacement à Go. La valeur d'une position Go dépend d'une analyse complexe pour déterminer si le groupe est vivant ou non, quelles pierres peuvent être connectées les unes aux autres, et des heuristiques autour de la mesure dans laquelle une position forte a une influence, ou dans quelle mesure une position faible position peut être attaquée.

Plus d'un mouvement peut être considéré comme le meilleur selon la stratégie utilisée. Afin de choisir un coup, l'ordinateur doit évaluer différents résultats possibles et décider lequel est le meilleur. Ceci est difficile en raison des compromis délicats présents dans Go. Par exemple, il peut être possible de capturer certaines pierres ennemies au prix de renforcer les pierres de l'adversaire ailleurs. Qu'il s'agisse d'un bon échange ou non peut être une décision difficile, même pour les joueurs humains. La complexité de calcul apparaît également ici, car un mouvement peut ne pas être immédiatement important, mais après de nombreux mouvements, il peut devenir très important à mesure que d'autres zones du plateau prennent forme.

Problèmes combinatoires

Parfois, il est mentionné dans ce contexte que divers problèmes combinatoires difficiles (en fait, n'importe quel problème NP-difficile ) peuvent être convertis en problèmes de type Go sur un plateau suffisamment grand ; cependant, la même chose est vraie pour d'autres jeux de société abstraits, y compris les échecs et le démineur , lorsqu'ils sont convenablement généralisés à un plateau de taille arbitraire. Les problèmes NP-complets ne tendent pas, dans leur cas général, à être plus faciles pour des humains non assistés que pour des ordinateurs correctement programmés : il est peu probable que des humains non assistés soient capables de rivaliser avec succès avec les ordinateurs pour résoudre, par exemple, des instances du problème de la somme des sous - ensembles .

Fin du jeu

Etant donné que la fin de partie contient moins de coups possibles que l'ouverture ( fuseki ) ou le milieu de partie, on pourrait supposer qu'elle est plus facile à jouer, et donc qu'un ordinateur devrait pouvoir l'aborder facilement. Aux échecs, les programmes informatiques fonctionnent généralement bien dans les phases finales d'échecs , en particulier une fois que le nombre de pièces est réduit dans la mesure où cela permet de tirer parti des bases de table finales résolues .

L'application des nombres surréalistes à la phase finale de Go, une analyse générale du jeu lancée par John H. Conway , a été développée par Elwyn R. Berlekamp et David Wolfe et décrite dans leur livre, Mathematical Go ( ISBN  978-1-56881- 032-4 ). Bien qu'il ne soit pas d'une utilité générale dans la plupart des circonstances de jeu, il facilite grandement l'analyse de certaines classes de positions.

Néanmoins, bien qu'une étude approfondie ait été menée, les phases finales de Go se sont avérées difficiles à PSPACE . Il y a plusieurs raisons pour lesquelles ils sont si durs :

  • Même si un ordinateur peut jouer parfaitement chaque zone de fin de partie locale, nous ne pouvons pas conclure que ses jeux seraient sans faille en ce qui concerne l'ensemble du plateau. Les autres domaines pris en compte dans les phases finales incluent les relations sente et gote , la hiérarchisation des différentes phases finales locales, le comptage et l'estimation des territoires, etc.
  • La phase finale peut impliquer de nombreux autres aspects du Go, y compris « la vie et la mort », qui sont également connus pour être NP-hard .
  • Chacune des zones de fin de partie locales peut s'affecter les unes les autres. En d'autres termes, ils sont de nature dynamique bien qu'isolés visuellement. Cela rend difficile le raisonnement pour les ordinateurs et les humains. Cette nature conduit à des situations complexes comme Triple Ko, Quadruple Ko, Molasses Ko et Moonshine Life.

Ainsi, les algorithmes de Go traditionnels ne peuvent pas jouer parfaitement à la phase finale de Go dans le sens de calculer directement le meilleur coup. De puissants algorithmes de Monte Carlo peuvent encore assez bien gérer les situations de fin de partie normales de Go, et en général, les classes les plus compliquées de problèmes de fin de partie de vie ou de mort sont peu susceptibles de survenir dans un jeu de haut niveau.

Ordre de jeu

Les moteurs de Go basés à Monte-Carlo ont la réputation d'être beaucoup plus disposés à jouer au tenuki , à se déplacer ailleurs sur le plateau, plutôt que de continuer un combat local que les joueurs humains. Il peut être difficile de calculer directement quand un déménagement local spécifique est requis. Cela a souvent été perçu comme une faiblesse au début de l'existence de ces programmes. Cela dit, cette tendance a persisté dans le style de jeu d'AlphaGo avec des résultats dominants, il s'agit donc peut-être plus d'une "bizarrerie" que d'une "faiblesse".

Recherche tactique

L'une des principales préoccupations d'un joueur de Go est de savoir quels groupes de pierres peuvent être maintenus en vie et lesquels peuvent être capturés. Cette classe générale de problèmes est connue sous le nom de vie et de mort . La stratégie la plus directe pour calculer la vie et la mort est d'effectuer une recherche arborescente sur les coups qui affectent potentiellement les pierres en question, puis d'enregistrer l'état des pierres à la fin de la ligne de jeu principale.

Cependant, compte tenu des contraintes de temps et de mémoire, il n'est généralement pas possible de déterminer avec une précision totale quels mouvements pourraient affecter la « vie » d'un groupe de pierres. Cela implique qu'une certaine heuristique doit être appliquée pour sélectionner les mouvements à considérer. L'effet net est que pour tout programme donné, il y a un compromis entre la vitesse de lecture et les capacités de lecture de vie et de mort.

Avec l'algorithme de Benson , il est possible de déterminer les chaînes qui sont inconditionnellement vivantes et n'auraient donc pas besoin d'être vérifiées à l'avenir pour la sécurité.

Représentation de l'État

Un problème auquel tous les programmes de Go doivent s'attaquer est de savoir comment représenter l'état actuel du jeu. Pour les programmes qui utilisent des techniques de recherche étendues, cette représentation doit être copiée et/ou modifiée pour chaque nouveau mouvement hypothétique considéré. Ce besoin impose la contrainte supplémentaire que la représentation doit être soit suffisamment petite pour être copiée rapidement, soit suffisamment flexible pour qu'un déplacement puisse être effectué et annulé facilement.

La façon la plus directe de représenter un tableau est un tableau à une ou deux dimensions, où les éléments du tableau représentent des points sur le tableau et peuvent prendre une valeur correspondant à une pierre blanche, une pierre noire ou une intersection vide . Des données supplémentaires sont nécessaires pour stocker le nombre de pierres capturées, à qui revient le tour et quelles intersections sont illégales en raison de la règle Ko .

Cependant, la plupart des programmes utilisent plus que les informations brutes du conseil d'administration pour évaluer les postes. Des données telles que quelles pierres sont connectées dans des chaînes, quelles chaînes sont associées les unes aux autres, quels groupes de pierres risquent d'être capturés et quels groupes de pierres sont effectivement morts sont nécessaires pour effectuer une évaluation précise de la position. Bien que ces informations puissent être extraites uniquement des positions des pierres, une grande partie peut être calculée plus rapidement si elles sont mises à jour de manière incrémentielle, par coup. Cette mise à jour incrémentielle nécessite le stockage de plus d'informations sur l'état de la carte, ce qui peut à son tour rendre la copie de la carte plus longue. Ce type de compromis est révélateur des problèmes liés à la création de programmes informatiques Go rapides.

Une méthode alternative consiste à avoir une seule carte et à effectuer et reprendre des mouvements de manière à minimiser les demandes sur la mémoire de l'ordinateur et à stocker les résultats de l'évaluation de la carte. Cela évite d'avoir à copier les informations encore et encore.

Conception du système

De nouvelles approches des problèmes

Historiquement, les techniques GOFAI (Good Old Fashioned AI) ont été utilisées pour aborder le problème de Go AI. Plus récemment, les réseaux de neurones ont été utilisés comme approche alternative. Un exemple d'un programme qui utilise des réseaux de neurones est WinHonte.

Ces approches tentent d'atténuer les problèmes du jeu de Go ayant un facteur de branchement élevé et de nombreuses autres difficultés.

Les résultats de la recherche Computer Go sont appliqués à d'autres domaines similaires tels que les sciences cognitives , la reconnaissance de formes et l'apprentissage automatique . La théorie des jeux combinatoires , une branche des mathématiques appliquées , est un sujet pertinent pour le Go sur ordinateur.

Philosophie de conception

Le seul choix qu'un programme doit faire est de savoir où placer sa prochaine pierre. Cependant, cette décision est rendue difficile par le large éventail d'impacts qu'une seule pierre peut avoir sur l'ensemble du plateau, et les interactions complexes que divers groupes de pierres peuvent avoir les uns avec les autres. Différentes architectures sont apparues pour traiter ce problème. L'utilisation la plus populaire:

Peu de programmes n'utilisent qu'une seule de ces techniques exclusivement ; la plupart combinent des portions de chacun dans un système synthétique.

Recherche d'arbre Minimax

Une technique d' IA traditionnelle pour créer un logiciel de jeu consiste à utiliser une recherche dans l'arborescence minimax . Cela implique de jouer tous les mouvements hypothétiques sur le plateau jusqu'à un certain point, puis d'utiliser une fonction d'évaluation pour estimer la valeur de cette position pour le joueur actuel. Le coup qui mène au meilleur plateau hypothétique est sélectionné et le processus est répété à chaque tour. Alors que les recherches arborescentes ont été très efficaces dans les échecs informatiques , elles ont connu moins de succès dans les programmes Computer Go. C'est en partie parce qu'il a été traditionnellement difficile de créer une fonction d'évaluation efficace pour un plateau de Go, et en partie parce que le grand nombre de mouvements possibles de chaque côté peut entraîner un facteur de branchement élevé . Cela rend cette technique très coûteuse en temps de calcul. Pour cette raison, de nombreux programmes qui utilisent largement les arbres de recherche ne peuvent jouer que sur la plus petite carte 9 × 9, plutôt que sur les pleines 19 × 19.

Il existe plusieurs techniques, qui peuvent grandement améliorer les performances des arbres de recherche en termes de vitesse et de mémoire. Les techniques d'élagage telles que l' élagage alpha-bêta , la recherche de variation principale et le MTD(f) peuvent réduire le facteur de ramification effectif sans perte de force. Dans les domaines tactiques tels que la vie et la mort, le Go se prête particulièrement bien aux techniques de mise en cache telles que les tables de transposition . Ceux-ci peuvent réduire la quantité d'efforts répétés, en particulier lorsqu'ils sont combinés à une approche d' approfondissement itérative . Afin de stocker rapidement une planche de Go pleine taille dans une table de transposition, une technique de hachage pour résumer mathématiquement est généralement nécessaire. Le hachage Zobrist est très populaire dans les programmes Go car il a de faibles taux de collision et peut être mis à jour de manière itérative à chaque mouvement avec seulement deux XOR , plutôt que d'être calculé à partir de zéro. Même en utilisant ces techniques d'amélioration des performances, les recherches d'arborescence complète sur une carte pleine taille sont toujours d'une lenteur prohibitive. Les recherches peuvent être accélérées en utilisant de grandes quantités de techniques d'élagage spécifiques à un domaine, comme ne pas considérer les mouvements où votre adversaire est déjà fort, et des extensions sélectives comme toujours considérer les mouvements à côté de groupes de pierres qui sont sur le point d'être capturées . Cependant, ces deux options introduisent un risque important de ne pas considérer un mouvement vital qui aurait changé le cours du jeu.

Les résultats des compétitions informatiques montrent que les techniques de correspondance de modèles pour choisir une poignée de mouvements appropriés combinées à des recherches tactiques localisées rapides (expliquées ci-dessus) étaient autrefois suffisantes pour produire un programme compétitif. Par exemple, GNU Go était compétitif jusqu'en 2008.

Systèmes basés sur la connaissance

Les novices apprennent souvent beaucoup des enregistrements de jeux d'anciens jeux joués par des joueurs maîtres. Il existe une hypothèse forte qui suggère que l'acquisition de connaissances sur le Go est la clé pour créer un ordinateur puissant. Par exemple, Tim Kinger et David Mechner soutiennent que « nous pensons qu'avec de meilleurs outils pour représenter et maintenir la connaissance du Go, il sera possible de développer des programmes de Go plus solides. Ils proposent deux voies : reconnaître les configurations communes des pierres et leurs positions et se concentrer sur les batailles locales. "Les programmes de Go manquent encore de connaissances qualitatives et quantitatives."

Après la mise en œuvre, l'utilisation de connaissances spécialisées s'est avérée très efficace dans la programmation du logiciel Go. Des centaines de directives et de règles de base pour un jeu fort ont été formulées par des amateurs et des professionnels de haut niveau. La tâche du programmeur est de prendre ces heuristiques , de les formaliser en code informatique et d'utiliser des algorithmes de correspondance de formes et de reconnaissance de formes pour reconnaître quand ces règles s'appliquent. Il est également important de disposer d'un système permettant de déterminer ce qu'il faut faire au cas où deux lignes directrices contradictoires s'appliqueraient.

La plupart des résultats relativement réussis proviennent des compétences individuelles des programmeurs à Go et de leurs conjectures personnelles sur Go, mais pas d'assertions mathématiques formelles ; ils essaient de faire en sorte que l'ordinateur imite la façon dont ils jouent au Go. "La plupart des programmes compétitifs ont nécessité 5 à 15 années-personnes d'efforts et contiennent 50 à 100 modules traitant de différents aspects du jeu."

Cette méthode a été jusqu'à récemment la technique la plus efficace pour générer des programmes de Go compétitifs sur une carte pleine grandeur. Handtalk (plus tard connu sous le nom de Goemate), The Many Faces of Go, Go Intellect et Go++ sont quelques exemples de programmes qui se sont fortement appuyés sur les connaissances d'experts, chacun d'entre eux ayant été considéré à un moment donné comme le meilleur programme de Go au monde.

Néanmoins, l'ajout de connaissances sur le Go affaiblit parfois le programme car certaines connaissances superficielles peuvent entraîner des erreurs : « les meilleurs programmes jouent généralement de bons mouvements de niveau maître. Cependant, comme tous les joueurs de jeux le savent, un seul mauvais mouvement peut ruiner un bon jeu. Performances du programme sur un jeu complet peut être bien inférieur au niveau maître."

Méthodes Monte-Carlo

Une alternative majeure à l'utilisation de connaissances et de recherches codées à la main est l'utilisation de méthodes Monte Carlo . Cela se fait en générant une liste de coups potentiels et, pour chaque coup, en jouant des milliers de jeux au hasard sur le tableau résultant. Le coup qui mène au meilleur ensemble de jeux aléatoires pour le joueur actuel est choisi comme le meilleur coup. L'avantage de cette technique est qu'elle nécessite très peu de connaissances du domaine ou d'intervention d'experts, le compromis étant des exigences accrues en mémoire et en processeur. Cependant, comme les coups utilisés pour l'évaluation sont générés au hasard, il est possible qu'un coup qui serait excellent à l'exception d'une réponse spécifique de l'adversaire soit évalué à tort comme un bon coup. Il en résulte des programmes forts d'un point de vue stratégique global, mais imparfaits d'un point de vue tactique. Ce problème peut être atténué en ajoutant une certaine connaissance du domaine dans la génération de mouvements et un plus grand niveau de profondeur de recherche en plus de l'évolution aléatoire. Certains programmes qui utilisent les techniques de Monte-Carlo sont Fuego, The Many Faces of Go v12, Leela, MoGo, Crazy Stone , MyGoFriend et Zen.

En 2006, une nouvelle technique de recherche, les limites supérieures de confiance appliquées aux arbres (UCT), a été développée et appliquée à de nombreux programmes 9x9 Monte-Carlo Go avec d'excellents résultats. UCT utilise les résultats des jeux collectés jusqu'à présent pour guider la recherche le long des lignes de jeu les plus réussies, tout en permettant d'explorer des lignes alternatives. La technique UCT ainsi que de nombreuses autres optimisations pour jouer sur la plus grande carte 19x19 ont conduit MoGo à ​​devenir l'un des programmes de recherche les plus puissants. Les premières applications réussies des méthodes UCT à 19x19 Go incluent MoGo, Crazy Stone et Mango. MoGo a remporté l' Olympiade informatique 2007 et a remporté un match de blitz (sur trois) contre Guo Juan, 5e Dan Pro, dans le 9x9 Go beaucoup moins complexe. The Many Faces of Go a remporté l' Olympiade informatique 2008 après avoir ajouté la recherche UCT à son moteur traditionnel basé sur la connaissance.

Apprentissage automatique

Alors que les systèmes basés sur les connaissances ont été très efficaces au Go, leur niveau de compétence est étroitement lié aux connaissances de leurs programmeurs et des experts du domaine associés. Une façon de briser cette limitation consiste à utiliser des techniques d' apprentissage automatique afin de permettre au logiciel de générer automatiquement des règles, des modèles et/ou des stratégies de résolution de conflits de règles.

Cela se fait généralement en permettant à un réseau de neurones ou à un algorithme génétique d'examiner une grande base de données de jeux professionnels ou de jouer à de nombreux jeux contre lui-même ou contre d'autres personnes ou programmes. Ces algorithmes sont alors capables d'utiliser ces données comme moyen d'améliorer leurs performances. AlphaGo a utilisé cela à bon escient. D'autres programmes utilisant des réseaux neuronaux ont été précédemment NeuroGo et WinHonte.

Les techniques d'apprentissage automatique peuvent également être utilisées dans un contexte moins ambitieux pour régler des paramètres spécifiques de programmes qui reposent principalement sur d'autres techniques. Par exemple, Crazy Stone apprend des modèles de génération de mouvements à partir de plusieurs centaines de jeux d'échantillons, en utilisant une généralisation du système de notation Elo .

AlphaGo

AlphaGo , développé par Google DeepMind , a fait une avancée significative en battant un joueur humain professionnel en octobre 2015, en utilisant des techniques combinant apprentissage profond et recherche arborescente Monte Carlo . AlphaGo est nettement plus puissant que les autres programmes de Go précédents et le premier à battre un professionnel humain de 9 dan dans un jeu sans handicap sur un plateau de taille normale.

Liste des programmes informatiques Go-play

  • AlphaGo , le premier programme informatique à gagner dans des matchs pairs contre un joueur de Go humain professionnel
  • AYA par Hiroshi Yamashita
  • BaduGI par Jooyoung Lee
  • Crazy Stone de Rémi Coulom (vendu sous le nom de Saikyo no Igo au Japon)
  • Darkforest par Facebook
  • Beaux-arts par Tencent
  • Fuego, un programme open source de Monte Carlo
  • Goban, programme Macintosh OS X Go de Sen:te (nécessite des extensions Goban gratuites)
  • GNU Go , un programme de Go classique open source
  • Go++ de Michael Reiss (vendu sous le nom de Strongest Go ou Tuyoi Igo au Japon)
  • Leela , le premier programme de Monte Carlo à vendre au public
  • Leela Zéro , une ré - implémentation du système décrit dans le AlphaGo zéro papier
  • The Many Faces of Go de David Fotland (vendu sous le nom d'AI Igo au Japon)
  • MyGoFriend de Frank Karger
  • MoGo de Sylvain Gelly ; version parallèle par de nombreuses personnes.
  • Programme Monte Carlo open source Pachi de Petr Baudiš, version en ligne Peepo de Jonathan Chetwynd, avec des cartes et des commentaires pendant que vous jouez
  • Smart Go par Anders Kierulf, inventeur du Smart Game Format
  • Steenvreter par Erik van der Werf
  • Zen de Yoji Ojima alias Yamato (vendu sous le nom de Tencho no Igo au Japon) ; version parallèle par Hideki Kato.

Compétitions entre les programmes de Go sur ordinateur

Plusieurs compétitions annuelles ont lieu entre les programmes informatiques de Go, la plus importante étant les événements de Go à l' Olympiade informatique . Des compétitions régulières, moins formelles, entre les programmes avaient lieu sur le KGS Go Server (mensuel) et le Computer Go Server (continu).

Les programmes de go-play les plus connus incluent Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, pachi et Fuego, tous énumérés ci-dessus ; et coldmilk d'auteur taïwanais, Steenvreter d'auteur néerlandais et DolBaram d'auteur coréen.

Histoire

La première compétition de Go sur ordinateur était sponsorisée par Acornsoft , et les premières régulières par USENIX . Ils se sont déroulés de 1984 à 1988. Ces compétitions ont introduit Nemesis, le premier programme de Go compétitif de Bruce Wilcox , et G2.5 de David Fotland , qui deviendra plus tard Cosmos et The Many Faces of Go.

L'un des premiers moteurs de la recherche sur le Go informatique était le prix Ing, un prix relativement important parrainé par le banquier taïwanais Ing Chang-ki , offert chaque année entre 1985 et 2000 au World Computer Go Congress (ou Ing Cup). Le vainqueur de ce tournoi a été autorisé à défier de jeunes joueurs à handicap dans un match court. Si l'ordinateur gagnait le match, le prix était décerné et un nouveau prix annoncé : un prix plus important pour avoir battu les joueurs avec un handicap inférieur. La série de prix Ing devait expirer soit 1) en l'an 2000, soit 2) lorsqu'un programme pouvait battre un professionnel de 1 dan sans handicap pour 40 000 000 de dollars NT . Le dernier gagnant était Handtalk en 1997, réclamant 250 000 dollars NT pour avoir remporté un match avec handicap de 11 pierres contre trois amateurs de 2 à 6 ans de 11 à 13 ans. Au moment où le prix a expiré en 2000, le prix non réclamé était de 400 000 dollars NT pour avoir remporté un match avec handicap de neuf pierres.

De nombreux autres grands tournois de Go régionaux ("congrès") avaient un événement de Go sur ordinateur. L'European Go Congress parraine un tournoi informatique depuis 1987, et l'événement USENIX est devenu le US/North American Computer Go Championship, organisé chaque année de 1988 à 2000 au US Go Congress.

Le Japon a commencé à parrainer des compétitions de go sur ordinateur en 1995. La FOST Cup a eu lieu chaque année de 1995 à 1999 à Tokyo. Ce tournoi a été supplanté par le Gifu Challenge, qui a eu lieu chaque année de 2003 à 2006 à Ogaki, Gifu. La Computer Go UEC Cup a lieu chaque année depuis 2007.

Problèmes de formalisation de règles dans les jeux informatiques

Lorsque deux ordinateurs jouent à une partie de Go l'un contre l'autre, l'idéal est de traiter le jeu de manière identique à deux humains jouant tout en évitant toute intervention de la part des humains réels. Cependant, cela peut être difficile lors du décompte de fin de partie. Le principal problème est que le logiciel de jeu de Go, qui communique généralement à l'aide du protocole standardisé de Go Text (GTP), ne conviendra pas toujours en ce qui concerne le statut vivant ou mort des pierres.

Bien qu'il n'y ait aucun moyen général pour deux programmes différents de « parler » et de résoudre le conflit, ce problème est principalement évité en utilisant les règles chinoises , Tromp-Taylor ou American Go Association (AGA) dans lesquelles le jeu continu ( sans pénalité) est requis jusqu'à ce qu'il n'y ait plus de désaccord sur le statut des pierres sur le plateau. En pratique, comme sur le serveur KGS Go, le serveur peut arbitrer un différend en envoyant une commande GTP spéciale aux deux programmes clients indiquant qu'ils doivent continuer à placer des pierres jusqu'à ce qu'il n'y ait plus de question sur le statut d'un groupe particulier (toutes les pierres mortes ont été capturés). Le serveur CGOS Go voit généralement les programmes démissionner avant même qu'un jeu n'atteigne la phase de notation, mais prend néanmoins en charge une version modifiée des règles de Tromp-Taylor nécessitant un jeu complet.

Ces ensembles de règles signifient qu'un programme qui était dans une position gagnante à la fin du jeu selon les règles japonaises (lorsque les deux joueurs ont passé) pourrait perdre en raison d'un mauvais jeu dans la phase de résolution, mais ce n'est pas un phénomène courant et est considéré comme une partie normale du jeu sous tous les ensembles de règles de zone.

Le principal inconvénient du système ci-dessus est que certains ensembles de règles (telles que les règles japonaises traditionnelles) pénalisent les joueurs pour avoir effectué ces mouvements supplémentaires, empêchant l'utilisation d'une lecture supplémentaire pour deux ordinateurs. Néanmoins, la plupart des programmes de Go modernes prennent en charge les règles japonaises contre les humains et sont compétents à la fois en jeu et en notation (Fuego, Many Faces of Go, SmartGo, etc.).

Historiquement, une autre méthode pour résoudre ce problème consistait à faire appel à un expert humain pour juger le jury final. Cependant, cela introduit de la subjectivité dans les résultats et le risque que l'expert manque quelque chose que le programme a vu.

Essai

De nombreux programmes sont disponibles qui permettent aux moteurs Go de l'ordinateur de jouer les uns contre les autres et ils communiquent presque toujours via le Go Text Protocol (GTP).

GoGUI et son addon gogui-twogtp peuvent être utilisés pour jouer deux moteurs l'un contre l'autre sur un seul système informatique. SmartGo et Many Faces of Go proposent également cette fonctionnalité.

Pour jouer le plus grand nombre d'adversaires possible, le serveur KGS Go permet le jeu Go Engine contre Go Engine ainsi que Go Engine contre Human dans les matchs classés et non classés. CGOS est un ordinateur dédié contre un serveur Go d'ordinateur.

Voir également

Les références

Lectures complémentaires

Liens externes