L'algorithme de Monte Carlo, c'est fini! (exemple de code) - Vidéo

L'algorithme de Monte Carlo, le chien alpha, vous l'aurez compris!

Le 9-15 mars dernier, un événement majeur s'est produit dans le monde du Go: une bataille entre humains et machines a eu lieu à Séoul, en Corée du Sud. Le match s'est terminé par une défaite humaine, le champion du monde de go, Lee Hsiung, devant AlphaGo, le programme d'intelligence artificielle de Google, 1 à 4. Alors, qu'est-ce qu'AlphaGo et où est la clé pour gagner?

• AlphaGo et les algorithmes de Monte Carlo

Selon Xinhua, le programme AlphaGo est un jeu de Go développé par DeepMind, une équipe américaine de Google, et appelé par les amateurs de jeu chinois " Alpha Shit ".

Dans un article précédent, nous avons parlé d'algorithmes de réseaux de neurones développés par Google pour permettre aux machines d'apprendre de manière autonome, AlphaGo étant un produit similaire.

Le vice-président et secrétaire général de l'Association chinoise d'automatisation, Wang Feiyu, a déclaré que les programmeurs n'avaient pas besoin de maîtriser le jeu, ils avaient seulement besoin de connaître les règles de base du jeu. AlphaGo était conçu par un groupe de scientifiques informatiques exceptionnels, plus précisément des experts en apprentissage automatique.

Alors, où est la clé pour que AlphaGo apprenne à être un génie?

Quel est l'algorithme de Monte Carlo?L'algorithme de Monte-Carlo, comme on l'appelle communément, est basé sur le fait que les algorithmes de Monte-Carlo ne sont pas des algorithmes. Si vous avez 1000 pommes dans le panier et que vous fermez les yeux pour en choisir la plus grosse, vous pouvez choisir sans limitation. Ainsi, vous pouvez fermer les yeux et en choisir une au hasard, puis en choisir une au hasard par rapport à la première, en laissant grande, puis en choisir une au hasard par rapport à la précédente, en laissant grande.

Autrement dit, l'algorithme de Monte Carlo est le suivant: plus il y a d'échantillons, plus il y a de solutions optimales, mais ce n'est pas la meilleure garantie, car si vous avez 10 000 pommes, vous en trouverez probablement plus.

L'algorithme de Las Vegas peut être comparé à lui: Il est communément dit que si une serrure a 1000 clés à choisir, mais qu'une seule est correcte. Ainsi, à chaque fois que vous essayez de prendre une clé au hasard, vous ne pouvez pas l'ouvrir, vous en changez une autre. Plus vous essayez, plus vous avez de chances d'ouvrir, mais avant d'ouvrir, les mauvaises clés sont inutiles.

Donc, l'algorithme de Las Vegas est la meilleure solution possible, mais il n'est pas nécessairement possible de le trouver. Supposons qu'il n'y ait pas une seule clé de 1000 clés pour ouvrir une serrure, la vraie clé est la 1001e, mais il n'y a pas d'algorithme 1001 dans l'échantillon, et l'algorithme de Las Vegas ne peut pas trouver la clé pour ouvrir une serrure.

L'algorithme de Monte Carlo d'AlphaGoLa difficulté du Go est particulièrement grande pour l'intelligence artificielle, car il y a tellement de façons de jouer au Go que l'ordinateur a du mal à les distinguer. Il y a beaucoup de possibilités de jeu de go. Il y a beaucoup de possibilités de jeu de go à chaque étape, il y a 19 x 19 = 361 types de jeux de go au début. Il peut y avoir jusqu'à 10 170 types de jeux de go pour 150 tours. En second lieu, les règles sont trop délicates et le choix des jeux dépend en partie de l'intuition acquise.

AlphaGo n'est pas seulement un algorithme de Monte Carlo, mais une mise à niveau de l'algorithme de Monte Carlo.

AlphaGo a terminé le jeu de chess grâce à un algorithme de recherche Monte Carlo et à deux réseaux de neurones profonds. Avant de se battre contre Lee Sichstone, Google a d'abord entraîné le réseau neuronal de Alpha Go avec les près de 30 millions de pas de l'homme contre une souris, lui permettant de prédire comment un joueur humain professionnel va tomber.

Leur tâche consiste à choisir en coopération les pas les plus prometteurs, à abandonner les défauts évidents, et à contrôler le calcul dans la mesure où les ordinateurs peuvent le faire.

Le logiciel de jeu traditionnel, qui utilise généralement une recherche violente, y compris un ordinateur bleu profond, qui crée un arbre de recherche pour tous les résultats possibles (chaque résultat est un fruit sur l'arbre) et effectue une recherche par exploration selon les besoins, a déclaré Yi Yanqiang, chercheur à l'Institut d'automatisation de l'Académie des sciences de Chine. Cette méthode est également réalisable pour les jeux d'échecs, de jumping, etc., mais pas pour le Go, car il y a une probabilité de chute trop grande pour que le ordinateur ne puisse pas construire ce fruit pour effectuer une recherche par exploration.

Le profondeur du réseau neurale, explique-t-il, ressemble à celle du cerveau humain, avec de nombreuses couches connectées comme si c'était le cerveau humain. Les deux réseaux neuraux d'AlphaGo sont le réseau stratégique et le réseau d'évaluation.

Le réseau de stratégie de la souris est principalement utilisé pour générer des stratégies de chute. Dans le processus de jeu, il ne pense pas à ce qu'il devrait faire, mais à ce que le joueur humain pourrait faire. C'est-à-dire qu'il prédit l'endroit où l'homme jouera la prochaine fois en fonction de l'état actuel de la planche d'échecs.

Cependant, les réseaux stratégiques ne savent pas si ce qu'ils font est bien ou mal, ils savent seulement si c'est le même jeu que celui des humains, alors ils doivent évaluer le réseau pour jouer.

Le réseau d'évaluation de l'axe évalue l'ensemble du tableau pour chaque hypothèse possible, puis donne un avertissement de gain. Ces valeurs sont retournées à l'algorithme de recherche d'arbres de Monte Carlo, qui déduit la marche avec le plus grand avertissement de gain en répétant le processus ci-dessus.

AlphaGo utilise ces deux outils pour analyser la situation et juger des avantages et des inconvénients de chaque stratégie suivante, tout comme les joueurs humains jugent de la situation actuelle et de la situation future.

L'algorithme de Monte Carlo est sans aucun doute au cœur d'AlphaGo.

Deux petites expériences Pour finir, deux petites expériences avec l'algorithme de Monte Carlo.

• 1.计算圆周率pi。

Principe: d'abord, dessiner un carré, dessiner son cercle intérieur, puis dessiner un point de dessin aléatoire dans ce carré, en plaçant le point qui tombe dans le cercle à peu près P, alors P = surface du cercle / surface du carré. P est égal à Pi.RR) / ((2R*2R) = Pi/4, ce qui signifie que Pi = 4P

Les étapes: 1. Si l'on place le centre du cercle à son point d'origine et qu'on en fait un cercle avec R comme rayon, alors la surface d'un quart de cercle du premier quadrant est Pi.RR/4 2. Faire le carré de l'extrémité d'un quart de cercle, dont les coordonnées sont ((0,0) ((0,R) ((R,0) ((R,R), alors la surface du carré est RR 3. Prenez les points (x, y) de manière aléatoire, de sorte que 0 <= x <= r et 0 <= y <= r, c'est-à-dire que le point est dans le carré. 4. avec la formule X.X+YY< RR détermine si le point est dans la circonférence d'un quart de cercle. 5. Si N est le nombre de points (c'est-à-dire le nombre d'expériences), alors M est le nombre de points (c'est-à-dire les points qui satisfont à l'étape 4) qui se trouvent dans le cercle 1/4.

P est égal à M/N, donc Pi est égal à 4 fois N/M.La première image

M_C ((10000) a été exécuté avec 3.1424

• 2.蒙特卡洛模拟求函数极值，可避免陷入局部极值

# Générer au hasard un nombre sur l'intervalle [-2,2], en recherchant son y correspondant, et trouver la valeur la plus élevée considérée comme la valeur extrême de la fonction sur [-2,2]La photo 2

Après 1000 simulations, la valeur extrême est 185.12292832389875 (extrêmement précise)

Vous voyez, les gars, c'est clair. Le code peut être écrit à la main, c'est amusant! Le site officiel de WeChat est le suivant: