Une nouvelle IA gagne au rendez-vous. Une IA similaire peut-elle gagner aux échecs? Peut-il réaliser une auto-formation pure?

20

L'une des questions les plus populaires posées sur ce site concerne la perspective d' une IA d'échecs purement autodidacte.

Aujourd'hui, ChessBase est distrait de sa couverture du tournoi FIDE Candidates pour signaler qu'une nouvelle IA bat, pour la première fois, un maître de premier plan du jeu de go plutôt différent, qui avait résisté aux IA de type échecs pendant de nombreuses années. Une première lecture du rapport suggère que la nouvelle go go est différente des IA d'échecs, mais est plus une IA de jeu général (GGP). L'article de ChessBase n'utilise cependant pas le terme GGP, mais semble dire que le go AI peut gagner aux jeux vidéo simples.

Y a-t-il une raison pour laquelle une telle IA gagnante ne pourrait pas, avec des ajustements mineurs, gagner également aux échecs? Dans l'affirmative, une telle IA promet-elle d'atteindre l'auto-formation pure dont plusieurs excellentes réponses à la question précédente ont déjà discuté, ce qui n'était pas encore possible à l'époque? Pourquoi ou pourquoi pas?

Je soupçonne qu'aucune réponse vraiment complète et pleinement informée à ma question n'est encore disponible, donc même une réponse partielle basée sur une expertise connexe serait appréciée.

Pour plus d'informations, consultez également cette question et ses réponses.

MISE À JOUR

Lorsque la question ci-dessus a été publiée pour la première fois il y a cinq jours et que certaines des bonnes réponses ci-dessous ont été données, les premières nouvelles concernant la victoire de go AI venaient d'apparaître. Depuis lors, des informations et des commentaires supplémentaires sont apparus.

Depuis lors, une table ronde à cinq volets assez lisible a été particulièrement intéressante dans laquelle Jonathan Schaeffer remarque:

L'apprentissage des jeux humains permet d'accélérer l'apprentissage du programme. AlphaGo pourrait apprendre à devenir un joueur fort par lui-même, sans utiliser les jeux humains. Le processus d'apprentissage prendrait juste plus de temps.

Selon l'animatrice de la table ronde, Schaeffer est "[c] professeur d'informatique à l'Université de l'Alberta et l'homme qui a résolu les dames"; il est donc probable qu'il pourrait être qualifié pour commenter.

Pour plus d'informations, voici le compte rendu d'une autre discussion ouverte, dont beaucoup de participants semblent mieux informés que d'habitude. La discussion a eu lieu pendant le match.

Nouvelle mise à jour, un an et demi plus tard: commentateur @MarkS. écrit:

Ceci est juste un commentaire car il s'agit de Go, pas d'échecs, mais AlphaGo Zero a atteint une "pure auto-formation" juste en se disant qui a gagné (et non le score final) et est plus fort et beaucoup plus efficace que l'IA qui a battu Lee Sedol . Pour plus d'informations, consultez deepmind.com/blog/alphago-zero-learning-scratch

thb
la source
Je vous suggère de le demander sur des forums plus techniques. L'IA est un sujet compliqué, et il faut avoir une expertise importante pour le comprendre. En regardant les réponses ici, je ne suis pas sûr que vous obteniez une réponse raisonnable.
Salvador Dali
5
Les réponses données sont très appréciées. J'en ai voté plus d'un. Si je n'en ai pas encore accepté, ce n'est pas une critique des réponses, mais une reconnaissance que la question est si difficile et le sujet si nouveau que la réponse acceptable n'est peut-être pas encore disponible. Laissons cette question ouverte un moment pour voir si, après un certain temps, une réponse non disponible aujourd'hui devient disponible plus tard. Merci.
thb
1
Ceci est juste un commentaire car il s'agit de Go, pas d'échecs, mais AlphaGo Zero a atteint une "pure auto-formation" juste en se disant qui a gagné (et non le score final) et est plus fort et beaucoup plus efficace que l'IA qui a battu Lee Sedol . Pour plus d'informations, voir deepmind.com/blog/alphago-zero-learning-scratch
Mark S.
1
@thb Je pense que AlphaZero est une telle IA.
Harry Weasley
1
Depuis décembre 2017, AlphaZero s'est enseigné un style d'échecs uniquement à partir des règles du jeu arxiv.org/pdf/1712.01815.pdf et a rejeté StockFish de manière convaincante.
saille

Réponses:

14

Bien bien bien! DeepMind a publié un article dans lequel ils disent avoir programmé et entraîné un ordinateur de réseau neuronal pour battre Stockfish.

Avec 1 minute de temps de réflexion par mouvement, leur ordinateur AlphaZero a battu Stockfish de +25, = 25, -0 avec du blanc et + 3, = 47,0- comme du noir.

Ils ont "formé" 3 ordinateurs distincts pour jouer aux échecs, au shogi et au go et battre leurs rivaux de silicium de manière convaincante.

Voici comment le document décrit la formation et l'évaluation -

Les jeux d'auto-jeu sont générés en utilisant les derniers paramètres de ce réseau de neurones, en omettant l'étape d'évaluation et la sélection du meilleur joueur.

AlphaGo Zero a réglé l'hyper-paramètre de sa recherche par optimisation bayésienne. Dans AlphaZero, nous réutilisons les mêmes hyper-paramètres pour tous les jeux sans réglage spécifique au jeu. La seule exception est le bruit qui est ajouté à la politique antérieure pour assurer l'exploration; ceci est proportionné au nombre typique de mouvements légaux pour ce type de jeu.

Comme AlphaGo Zero, l'état du plateau est encodé par des plans spatiaux basés uniquement sur les règles de base de chaque jeu. Les actions sont encodées soit par des plans spatiaux, soit par un vecteur plat, là encore basé uniquement sur les règles de base de chaque jeu (voir Méthodes).

Nous avons appliqué l'algorithme AlphaZero aux échecs, au shogi et aussi à Go. Sauf indication contraire, les mêmes paramètres d'algorithme, architecture de réseau et hyper-paramètres ont été utilisés pour les trois jeux. Nous avons formé une instance distincte d'AlphaZero pour chaque jeu. La formation s'est déroulée sur 700 000 étapes (mini-lots de taille 4 096) à partir de paramètres initialisés de manière aléatoire, en utilisant 5 000 TPU de première génération pour générer des jeux en self-play et 64 TPU de deuxième génération pour former les réseaux de neurones. De plus amples détails sur la procédure de formation sont fournis dans les méthodes.

La figure 1 montre les performances d'AlphaZero lors de l'apprentissage par renforcement en auto-jeu, en fonction des étapes d'entraînement, sur une échelle Elo (10). Aux échecs, AlphaZero a surpassé Stockfish après seulement 4 heures (pas de 300k); en shogi, AlphaZero a surpassé Elmo après moins de 2 heures (pas de 110k); et dans Go, AlphaZero a surpassé AlphaGo Lee (29) après 8 heures (pas de 165k).

Nous avons évalué les instances d'AlphaZero entièrement entraînées contre Stockfish, Elmo et la version précédente d'AlphaGo Zero (entraînées pendant 3 jours) aux échecs, shogi et Go respectivement, en jouant 100 matchs avec des contrôles de temps de tournoi d'une minute par coup. AlphaZero et le précédent AlphaGo Zero utilisaient une seule machine avec 4 TPU. Stockfish et Elmo ont joué à leur niveau de compétence le plus élevé en utilisant 64 threads et une taille de hachage de 1 Go. AlphaZero a battu tous les adversaires de manière convaincante, perdant zéro match contre Stockfish et huit matchs contre Elmo (voir le matériel supplémentaire pour plusieurs exemples de jeux), ainsi que la défaite de la version précédente d'AlphaGo Zero (voir tableau 1).

Leur ordinateur a utilisé une nouvelle forme de puce appelée "TPU" ( Tensor Processing Unit ) développée par Google pour les tâches d'apprentissage automatique.

Ils affirment également que leur algorithme de recherche d'arbre Monte Carlo est meilleur et plus "humain" que les algorithmes de recherche alpha-bêta traditionnels -

Nous avons également analysé les performances relatives de la recherche MCTS d'AlphaZero par rapport aux moteurs de recherche alpha-bêta de pointe utilisés par Stockfish et Elmo. AlphaZero ne recherche que 80 000 positions par seconde dans les échecs et 40 000 dans le shogi, contre 70 millions pour Stockfish et 35 millions pour Elmo. AlphaZero compense le nombre inférieur d'évaluations en utilisant son réseau de neurones profond pour se concentrer de manière beaucoup plus sélective sur les variations les plus prometteuses - sans doute une approche de recherche plus «humaine», comme proposé à l'origine par Shannon. La figure 2 montre l'évolutivité de chaque joueur par rapport au temps de réflexion, mesurée sur une échelle Elo, par rapport à Stockfish ou Elmo avec un temps de réflexion de 40 ms. Le SCTM d'AlphaZero évoluait plus efficacement avec le temps de réflexion que Stockfish ou Elmo,

Voici quelques jeux -

Stockfish - AlphaZero, 0-1
1. e4 e5 2. Nf3 Nc6 3. Bb5 Nf6 4. d3 Bc5 5. Bxc6 dxc6 6. OO Nd7 7. Nbd2 O-O 8. Qe1 f6 9. Nc4 Rf7 10. a4 Bf8 11. Kh1 Nc5 12. a5 Ne6 13. Ncxe5 fxe5 14. Nxe5 Rf6 15. Ng4 Rf7 16. Ne5 Re7 17. a6 c5 18. f4 Qe8 19. axb7 Bxb7 20. Qa5 Nd4 21. Qc3 Re6 22. Be3 Rb6 23. Nc4 Rb4 24. b3 a5 25. Rxa5 Rxa5 26. Nxa5 Ba6 27. Bxd4 Rxd4 28. Nc4 Rd8 29. g3 h6 30. Qa5 Bc8 31. Qxc7 Bh3 32. Rg1 Rd7 33. Qe5 Qxe5 34. Nxe5 Ra7 35. Nc4 g5 36. Rc1 Bg7 37. Ne5 Ra8 38. Nf3 Bb2 39. Rb1 Bc3 40. Ng1 Bd7 41. Ne2 Bd2 42. Rd1 Be3 43. Kg2 Bg4 44. Re1 Bd2 45. Rf1 Ra2 46. ​​h3 Bxe2 47. Rf2 Bxf4 48. Rxe2 Be5 49. Rf2 Kg7 50. g4 Bd4 51. Re2 Kf6 52. e5 + Bxe5 53. Kf3 Ra1 54. Rf2 Re1 55. Kg2 + Bf4 56. c3 Rc1 57. d4 Rxc3 58. dxc5 Rxc5 59. b4 Rc3 60. h4 Ke5 61 . hxg5 hxg5 62. Re2 + Kf6 63. Kf2 Be5 64. Ra2 Rc4 65. Ra6 + Ke7 66. Ra5 Ke6 67. Ra6 + Bd6 0-1

Jeu

Stockfish - AlphaZero, 0-1
1. e4 e5 2. Nf3 Nc6 3. Bb5 Nf6 4. d3 Bc5 5. Bxc6 dxc6 6. OO Nd7 7. c3 O-O 8. d4 Bd6 9. Bg5 Qe8 10. Re1 f6 11. Bh4 Qf7 12. Nbd2 a5 13. Bg3 Re8 14. Qc2 Nf8 15. c4 c5 16. d5 b6 17. Nh4 g6 18. Nhf3 Bd7 19. Rad1 Re7 20. h3 Qg7 21. Qc3 Rae8 22. a3 h6 23. Bh4 Rf7 24. Bg3 Rfe7 25. Bh4 Rf7 26. Bg3 a4 27. Kh1 Rfe7 28. Bh4 Rf7 29. Bg3 Rfe7 30. Bh4 g5 31. Bg3 Ng6 32. Nf1 Rf7 33. Ne3 Ne7 34. Qd3 h5 35. h4 Nc8 36. Re2 g4 37. Nd2 Qh7 38. Kg1 Bf8 39. Nb1 Nd6 40. Nc3 Bh6 41. Rf1 Ra8 42. Kh2 Kf8 43. Kg1 Qg6 44. f4 gxf3 45. Rxf3 Bxe3 + 46. ​​Rfxe3 Ke7 47. Be1 Qh7 48. Rg3 Rg7 49. Rxg7 + Qxg7 50. Re3 Rg8 51. Rg3 QH8 52. Nb1 Rxg3 53. Bxg3 Qh6 54. Nd2 Bg4 55. kh2 Rd7 56. b3 axb3 57. Nxb3 Qg6 58. Nd2 Bd1 59. Nf3 Ba4 60. Nd2 KE7 61 . Bf2 Qg4 62. Qf3 Bd1 63. Qxg4 Bxg4 64. a4 Nb7 65. Nb1 Na5 66. Be3 Nxc4 67. Bc1 Bd7 68. Nc3 c6 69. Kg1 cxd5 70. exd5 Bf5 71. Kf2 Nd6 72. Be3 Ne4 + 73. Nxe4 Bxe4 74. a5 bxa5 75. Bxc5 + Kd7 76. d6 Bf5 77. Ba3 Kc6 78. Ke1 Kd5 79. Kd2 Ke4 80. Bb2 Kf4 81. Bc1 Kg3 82. Ke2 a4 83. Kf1 Kxh4 84. Kf2 Kg4 85. Ba3 Bd7 86. Bc1 Kf5 87. Ke3 Ke6 0-1

Blanc: AlphaZero Noir: Stockfish

AlphaZero - Stockfish, 1-0
1. Nf3 Nf6 2. c4 b6 3. d4 e6 4. g3 Ba6 5. Qc2 c5 6. d5 exd5 7. cxd5 Bb7 8. Bg2 Nxd5 9. OO Nc6 10. Rd1 Be7 11. Qf5 Nf6 12. e4 g6 13. Qf4 O-O 14. e5 Nh5 15. Qg4 Re8 16. Nc3 Qb8 17. Nd5 Bf8 18. Bf4 Qc8 19. h3 Ne7 20. Ne3 Bc6 21. Rd6 Ng7 22. Rf6 Qb7 23. Bh6 Nd5 24. Nxd5 Bxd5 25. Rd1 Ne6 26. Bxf8 Rxf8 27. Qh4 Bc6 28. Qh6 Rae8 29. Rd6 Bxf3 30. Bxf3 Qa6 31. h4 Qa5 32. Rd1 c4 33. Rd5 Qe1 + 34. Kg2 c3 35. bxc3 Qxc3 36. h5 Re7 37. Bd1 Qe1 38. Bb3 Rd8 39. Rf3 Qe4 40. Qd2 Qg4 41. Bd1 Qe4 42. h6 Nc7 43. Rd6 Ne6 44. Bb3 Qxe5 45. Rd5 Qh8 46. ​​Qb4 Nc5 47. Rxc5 bxc5 48. Qh4 Rde8 49. Rf6 Rf8 50. Qf4 a5 51. g4 d5 52. Bxd5 Rd7 53. Bc4 a4 54. g5 a3 55. Qf3 Rc7 56. Qxa3 Qxf6 57. gxf6 Rfc8 58. Qd3 Rf8 59. Qd6 Rfc8 60. a4 1- 0
Brian Towers
la source
Lisez simplement le journal. Vraiment incroyable. Bien sûr, cela ne signifie pas que vous ne pourriez pas construire quelque chose d'encore plus fort avec les techniques traditionnelles combinées avec AlphaZero, mais quand même ...
BlindKungFuMaster
10

D'accord, je dois admettre que j'avais tort. Bien que je soutienne que cela était dû à la connaissance de l'opinion des experts, et non à l'objectivité générale: Pour citer l' article : "Cependant, les programmes d'échecs utilisant les SCTM traditionnels étaient beaucoup plus faibles que les programmes de recherche alpha-bêta (4, 24); tandis que l'alpha -les programmes bêta basés sur des réseaux de neurones n'ont pas pu auparavant rivaliser avec des fonctions d'évaluation plus rapides et artisanales. "

Apparemment, les échecs sont suffisamment profonds stratégiquement pour que vous puissiez élaborer une stratégie avec quelqu'un qui pourrait vous calculer. Pour moi, c'est une grande surprise parce que le développement des moteurs d'échecs allait dans la direction opposée. (Apparemment, il y a encore une légère mise en garde quant à savoir si AlphaZero est vraiment plus fort que Stockfish: Stockfish joué avec seulement 1 Go pour les tables de hachage et 64 cœurs peut ne pas vraiment correspondre à quatre TPU)

C'est aussi une chose vraiment, vraiment excitante, car AlphaZero a très probablement des forces très différentes des moteurs traditionnels.

Cela signifie également que je mets à jour ma conviction de l'importance d'AlphaGo en tant que percée technologique par beaucoup. Fondamentalement, briser le shogi, Go et les échecs avec une seule configuration est complètement incroyable, sans parler de dizaines d'autres jeux qui pourraient probablement être joués à un niveau surhumain par AlphaZero.

Il y a une belle explication pour expliquer pourquoi les SCTM sont en fait une idée décente même pour les échecs par rapport à la recherche alpha-bêta (du papier): "AlphaZero évalue les positions en utilisant une approximation de fonction non linéaire basée sur un réseau neuronal profond, plutôt que linéaire approximation de la fonction utilisée dans les programmes d'échecs typiques. Cela fournit une représentation beaucoup plus puissante, mais peut également introduire des erreurs d'approximation fallacieuses. Les SCTM font la moyenne de ces erreurs d'approximation, qui ont donc tendance à s'annuler lors de l'évaluation d'un grand sous-arbre. En revanche, la recherche alpha-bêta calcule un mini-max explicite, qui propage les plus grosses erreurs d'approximation à la racine du sous-arbre. " (souligné par moi)

Voici mon ancienne réponse, contenant encore quelques points valables, malgré la conclusion étant remplacée par la réalité.

Tout d'abord, Alphago n'est pas un système de jeu général. C'est un programme conçu uniquement pour jouer au go et rien d'autre. Il est cependant construit à partir de certains blocs de construction qui ont une applicabilité beaucoup plus large, tels que les réseaux de neurones convolutifs , qui ont été utilisés dans la reconnaissance d'image et qui ont une application immédiate dans les diagnostics médicaux, et l' apprentissage par renforcement qui a été utilisé pour maîtriser les jeux Atari mentionnés dans l'article.

En outre, les moteurs actuels "apprennent" en jouant eux-mêmes : "Du jour au lendemain, les six ordinateurs de Lefler jouent à plus de 14 000 jeux chacun pendant une période de huit heures." Six machines multipliées par 14 000, c'est beaucoup de jeux ", dit-il. Et avec à chaque partie jouée, la base de données devient plus profonde et plus riche. Il y a même un intérêt sportif à regarder les ordinateurs jouer les uns contre les autres.

Pour en venir à l'essentiel de votre question:

Il y a une différence importante entre les échecs et le go, du moins du point de vue d'un programmeur. Les échecs sont plus un jeu tactique, tandis que le go est plus un jeu stratégique. Cela signifie que dans le calcul des échecs, la profondeur l'emporte sur l'évaluation positionnelle. C'est fondamentalement l'aperçu clé qui distingue les "vieux" moteurs comme Fritz, Shredder, Junior et la nouvelle génération comme Fruit, Rybka, Houdini, Stockfish, Komodo. Parce qu'à la fin de chaque ligne, vous devez évaluer la position et que vous souhaitez calculer le lot de lignes et que la qualité de l'évaluation n'est pas aussi importante que la profondeur de recherche, les moteurs d'échecs ont des fonctions d'évaluation allégées et rapides.

En revanche, la complexité tactique est trop grande même pour les ordinateurs. Par conséquent, évaluer les positions et les mouvements avec précision est essentiel. Ce qu'Alphago apporte de nouveau au jeu, c'est ce pouvoir d'évaluation, basé sur des réseaux de neurones convolutifs .

Pour enfin arriver à mon point: alors que les fonctions d'évaluation des échecs sont maigres et rapides, les réseaux de neurones ont des millions, parfois des milliards de paramètres. Parce que «apprendre» dans ce contexte signifie ajuster les paramètres, il y a beaucoup plus de progrès possibles pour les programmes d'auto-apprentissage.

Donc, oui, vous pouvez utiliser une configuration comme Alphago pour créer un moteur d'échecs, mais ce ne serait pas particulièrement bon. L'exécution de la fonction d'évaluation prendrait tellement de temps que vous auriez à utiliser un énorme cluster de gpus pour atteindre les profondeurs de recherche nécessaires (ce que fait Alphago). Vous pouvez créer une très bonne fonction d'évaluation , mais le compromis de vitesse n'en vaut pas la peine.

BlindKungFuMaster
la source
1
Je ne serais pas d'accord avec vous sur le fait que vous pourriez utiliser une configuration comme Alphago pour créer un moteur d'échecs, mais ce ne serait pas particulièrement bon . Je peux parier quelque chose sur le fait que dans moins d'un an, il y aura un moteur d'échecs qui s'appuiera fortement sur NN (il aura très probablement une recherche d'arbre et monte carlo, mais ce n'est pas important), qui sera proche de stockfish de pointe. Et ce moteur ne proviendra pas d'une super-société (car l'intérêt pour les échecs s'est dissipé des chercheurs en IA il y a longtemps), mais plutôt d'un hobbist fort.
Salvador Dali
Monte carlo est complètement inutile aux échecs. Et bien que les NN ne soient pas inutiles, ils sont tout simplement trop lents.
BlindKungFuMaster
3
Pourquoi exactement les SCTM sont-ils inutiles? Il est très logique de démarrer à partir d'une position actuelle du plateau, d'exécuter 1000 jeux avec une profondeur de nœud de 5 et de voir quel nœud a de meilleures chances. C'est très similaire à ce que vous faites, quand vous regardez la statistique des mouvements dans la base de données et voyez qu'après 14. Kg4 blanc gagne 25%, mais avec 14. Rb2 il gagne avec 45%. Avez-vous des preuves de phrases complètement inutiles ?
Salvador Dali
2
Les SCTM ne concernent pas le hasard, il s'agit de simulation. Livres d'introduction de base sur MC vous montrant un exemple d'aléatoire uniquement pour montrer le point. Vous pouvez jouer une position nette plusieurs fois avec la profondeur de nœud de 6 qui est super rapide (et toujours assez fiable), et vous permettra d'estimer approximativement quel mouvement est le meilleur.
Salvador Dali
1
Mes déclarations ne sont pas audacieuses, elles sont grand public. Il suffit de lire quelques sites de programmation d'échecs, vous trouverez plus ou moins mes arguments. Les SCTM sont connus depuis une décennie et dans les échecs, d'autres choses fonctionnent mieux. D'un autre côté, je ne pense pas que vos déclarations soient basées sur autre chose qu'un sentiment d'intestin, donc ce sera mon dernier commentaire.
BlindKungFuMaster
5

Il existe un projet appelé spawkfish qui tente de faire exactement cela. Il s'agit d'un moteur basé sur un réseau de neurones dont le but "est d'explorer comment les progrès récents de l'informatique Go peuvent être appliqués au monde des échecs informatiques".

C'est un projet jeune et le moteur est encore assez faible. Le jouer est intéressant, car son jeu de position est meilleur que sa tactique.

Jardin d'Alexandre
la source
2
Vous ne plaisantiez pas avec cette dernière phrase. Je viens de jouer quelques matchs contre lui, et chacun est entré dans une phase finale assez nivelée, seulement pour voir le poisson-fraise laisser tomber soudainement du matériel (dans un cas, suspendre une tour de nulle part). Étrange.
ETD
Depuis que vous avez répondu, de nouvelles informations concernant le go AI semblent être apparues. J'ai mis à jour la question pour créer un lien vers les nouvelles, si cela vous intéresse.
thb
Le site web de Spawkfish semble avoir disparu ...
hkBst
4

Une IA similaire peut-elle gagner aux échecs? Peut-il réaliser une auto-formation pure?

La réponse courte est non!"

Chess and go sont radicalement différents dans leur relative simplicité et leur complexité relative qui découle de leur géométrie et de la façon dont vous gagnez. Celles-ci se combinent pour rendre un programme qui est bon dans l'un inutile à l'autre.

Aux échecs, vous gagnez en matant l'adversaire, les points ne comptent pas. Bien sûr, un adversaire sensé démissionnera souvent avant de livrer échec et mat mais le principe est le même. En jeu, vous gagnez en ayant plus de points à la fin de la partie. Si j'ai un roi et une reine et que vous avez un roi, une tour et un pion, mais que vous avez construit une forteresse, peu importe que j'ai 9 points pour la reine et vous n'avez que 6 points pour votre tour et votre pion. Le jeu est un match nul.

Cela fait une différence fondamentale dans la complexité entre les échecs et le go. En cours, vous pouvez simplement conserver le score et vous saurez qui gagne. Aux échecs, le seul moyen de savoir qui gagne est le calcul pur. En ce sens, les échecs sont beaucoup plus complexes que d'aller.

En même temps, en raison de la géométrie des deux jeux, il y a des ordres de grandeur plus de possibilités en jeu qu'aux échecs. En ce sens, le go est beaucoup plus complexe que les échecs.

Un programme d'échecs fonctionne par calcul de force brute de tous les mouvements possibles jusqu'à une certaine profondeur qui détermine sa force. Un programme go ne peut pas fonctionner comme ça et jouer quelque chose de plus avancé que le niveau débutant go.

L'objectif de base de go est de contrôler plus de territoire que votre adversaire. À la fin d'une partie, peu importe que la différence soit de 1 pierre ou 100 pierres, les deux sont des victoires. Chaque fois que vous placez une pierre, vous faites deux choses. Vous augmentez votre territoire, potentiel ou réel, et vous diminuez celui de votre adversaire.

Parfois, lorsqu'il s'agit d'une augmentation ou d'une diminution réelle du territoire, il est facile de calculer la valeur du déplacement, mais lorsqu'il est potentiel, il est très difficile à évaluer. En tant que joueur de go faible, je comprends le "réel" beaucoup mieux que le "potentiel" et un joueur plus fort me battra en construisant un territoire potentiel beaucoup plus grand au centre tandis que je construis un territoire réel plus petit sur les bords et dans les coins. Le joueur le plus fort aura acquis la capacité de juger par l'intuition et la sensation de jouer à de nombreux jeux et de reconnaître comment construire un territoire "potentiel".

Plus tôt, j'ai dit que chaque fois que je place une pierre, cela augmente mon territoire (réel ou potentiel) et diminue celui de mon adversaire (en fait, si c'est un geste stupide, cela fera le contraire!). Dans une position donnée, tous les mouvements ne sont pas identiques. Une pierre placée dans une position peut valoir beaucoup plus ou beaucoup moins qu'une pierre placée dans une autre.

Typiquement, dans un jeu, il y aura de petits "combats" où les joueurs placeront leurs pierres les uns à côté des autres, délimitant leur territoire et limitant celui de leur adversaire. Pendant ce temps, il existe des possibilités de commencer à jalonner du territoire dans une autre partie du plateau ou de passer à un combat ailleurs où les deux joueurs ont déjà des pierres.

Ce qui est très important dans ces situations, c'est de savoir quand arrêter un combat, car les gains potentiels ont diminué, et de passer à un autre combat ou peut-être de partir en territoire vierge. Parfois, cela dépend d'un calcul difficile, mais souvent il est beaucoup plus nébuleux et n'est pas soumis au calcul. En tant que joueur faible, c'est là qu'un payeur fort m'écrase à chaque fois.

Dans ces situations, l'ordinateur utilise des méthodes probabilistes pour générer un score attendu pour un mouvement particulier. Parfois, la valeur réelle se révélera un peu moins, parfois un peu plus, mais à long terme, elle disparaîtra plus ou moins. Il continuera de choisir le coup avec la valeur attendue la plus élevée, dans l'espoir qu'au cours d'un match, de petites erreurs seront annulées et que sa stratégie gagnera.

Ce n'est pas une stratégie qui semble familière aux joueurs d'échecs et qui ne fonctionnera pas aux échecs. C'est quelque chose qui semble familier à quiconque suit ce qui se passe sur les marchés boursiers. Cela ressemble beaucoup à quelque chose appelé "trading à haute fréquence" où les ordinateurs feront des milliers de petits paris ou juste des paris proposés chaque seconde pour "nickel et dime" le marché et peut-être même le déplacer très marginalement en leur faveur sur des périodes de millisecondes.

Les marchés financiers sont déjà dominés par ce type de trading algorithmique, ce qui suggère que ce type de programme a déjà triomphé dans un domaine beaucoup plus lucratif qu'un jeu de société.

Brian Towers
la source
4
Le trading à haute fréquence n'a rien à voir avec le jeu. Des algorithmes totalement différents afaik. De plus, il y a beaucoup de choses intéressantes dans votre réponse, mais il est difficile de voir le point principal, peut-être d'ajouter un TL; DR. ;-)
BlindKungFuMaster
@BlindKungFuMaster Le principe sous-jacent derrière HFT et AlphaGo est probabiliste. Le gain attendu de ce "coup" est de x%. À long terme, l'accumulation de ces mouvements / paris va gagner le jeu pour AlphaGo ou faire fortune pour les traders HFT. Cependant, de temps en temps, il y aura un "crash flash" ou un "mouvement miracle" d'un Lee Se-dol qui transforme un gain / profit en perte. Cela n'invalide en rien sa programmation. Il n'est pas programmé pour trouver le meilleur mouvement absolu à chaque fois. C'est un peu comme des pseudo solutions à un problème de voyageur de commerce qui essaient de se rapprocher de 5% du meilleur.
Brian Towers
Depuis que vous avez répondu, de nouvelles informations concernant le go AI semblent être apparues. J'ai mis à jour la question pour créer un lien vers les nouvelles, si cela vous intéresse.
thb
1
@thb, je pense que cette réponse est maintenant quelque peu obsolète étant donné le nouveau succès d'AlphaZero, comme dans arxiv.org/abs/1712.01815
Mark S.
@Will No. Pourquoi? Ne jugez pas les autres par vos propres normes superficielles.
Brian Towers
4

(Quiconque souhaite une discussion technique approfondie pour AlphaGo peut consulter mon article )

Réponse courte : Non

Réponse longue :

Tout d'abord, nous devons comprendre pourquoi Google n'a pas mis en œuvre l'alpha-bêta dans AlphaGo. Stockfish et Komodo (et tous les moteurs d'échecs) ont une alpha-bêta, pourquoi AlphaGo ne le ferait-il pas?

Raison : il n'existe aucun moyen simple et bon marché d'évaluer avec précision une position Go de manière statique.

Aux échecs, nous pouvons toujours compter les matériaux, un moyen très efficace d'évaluer statiquement une position. Bien qu'il ne soit pas parfait, c'est très rapide et un très bon proxy pour les échecs.

La recherche dans l'espace d'état avec Monte-Carlo est une méthode inférieure à l'alpha-bêta. Google aurait mis en œuvre l'alpha-bêta s'ils le pouvaient, mais ils ne le pouvaient pas. Ainsi, ils ont été obligés d'utiliser quelque chose de beaucoup plus lent.

Le moteur d'échecs ne jouerait pas mieux avec Monte-Carlo.

SmallChess
la source
Il est temps de reconsidérer, ou peut-être pas encore?
Evargalo
3

Je suis en désaccord avec les autres réponses. Je suis informaticien qui travaille professionnellement dans le domaine de l'intelligence artificielle et je suis également candidat master en échecs et 3 dan en igo.

Je pense qu'il n'est pas clair pour le moment si les méthodes de Deep Mind pourraient être appliquées aux échecs, mais je pense que c'est possible.

Actuellement, les meilleurs programmes de jeu d'échecs s'appuient de plus en plus sur l'heuristique et tenter d'utiliser l'architecture AlphaGo pour les échecs serait d'une certaine manière dans la même ligne de pensée.

Une caractéristique architecturale clé d'AlphaGo qui devrait être modifiée est sa méthode d'identification des carrés clés (ou des cartes de chaleur), qui est particulière aux jeux de type igo et n'est pas directement applicable aux échecs. Il faudrait développer un analogue de cette méthode pour rendre l'architecture AlphaGo pertinente aux échecs. Par exemple, nous pourrions avoir le concept de "pièces clés" plutôt que de carrés clés.

Je pense que l'argument selon lequel l'architecture AlphaGo n'est pas pertinente pour les échecs parce que les échecs sont plus tactiques n'est pas une très bonne affirmation car, finalement, les deux ont des arbres de recherche dont la forme est assez similaire pour qu'AlphaGo puisse définitivement être adapté aux échecs.

Cecil De Vere
la source
Je vous ai donné un +1, car vos affirmations pourraient être correctes, mais nous ne savons pas avec certitude jusqu'à ce que quelqu'un publie un article.
SmallChess
Euh? Le document existe déjà, comme l'a souligné Brian Towers. La réponse est oui.
boson thermomagnétique condensé
On dirait que j'avais raison, heh.
Cecil De Vere
@CecilDeVere n'est pas en désaccord avec les autres réponses, 2 d'entre eux ont indiqué la bonne réponse. Et pas en déclarant que ce n'est pas clair pour le moment, alors qu'il est clair que cette réponse est oui (pas peut-être).
boson condensé thermomagnétique du
3

La réponse est oui! Google vient de le prouver hier, quand AlphaZero a battu le meilleur programme d'échecs en utilisant uniquement des connaissances sur les règles et une auto-formation pure sans aucune connaissance des échecs humains. La réponse acceptée est fausse. Le lien vers l'article est ici: lien

zaifrun
la source