par Maxime Audouin
L'intelligence artificielle pour jouer aux échecs
Deep Blue, le premier
à battre les champions
Alan T uring et C laude Shannon ont commencé
da ns les années 1950 les premiers travaux
sur l' intelligence artific iell e appliquée au jeu
d'échec. Mais c'est à la fin des années 1990
qu' IBM marqua l' hi sto ire en créant Deep
Blue, une mac hine conçue spéc ifiquement
pour jouer à ce je u. E n 1997 , avec la victo ire de
Deep Blue sur le célè bre champion Kas parov,
une machine se cl assait devant les humains
lors d ' un tournoi du plu s haut ni veau.
Depui s, de nombre ux progrès ont été réa li sés,
permettant de mettre au po int plusieurs
programmes solides qui fo nctionnent sur
des machines personnelles (ordinateurs ou
téléphones) et qui battraient aujourd ' hui
Deep Blue. Ces progrès sont du s à de grandes
avancées importantes en algorithmique.
l'algorithme du logiciel Chess
La société Magma Mobile a suivi les traces de
Deep Blue pour développer Chess, son Intelligence Artificielle pour téléphone, disponible
sur http://m.magmamobile.com/Chess/
Les programmes d'échecs reposent tous sur le
même principe : une fonction qui peut donner:
• une estimation de la valeur d'un plateau
(l'estimation du plateau peut être le nombre
de pièces blanches pondérées par leurs valeurs moins le nombre de pièces noires pondérées par leurs valeur).
• une fonction de recherche (voir en encadré
le programme). Cette fonction simule chaque
mouvement possible sur le plateau, et se rappelle récursivement. Quand elle arrive à une
profondeur donnée ou à une fin de partie, elle
décide d'une valeur à renvoyer.
Le logiciel
Chess
sur iPad.
Si on compte les plateaux d'échecs sur lesquels ont été joués moins de huit coups, on
obtient déjà 84 milliards de plateaux. Ce qui
veut dire qu'il faudrait faire 84 milliards d'appels à la fonction de recherche pour simuler
seulement huit coups.
Malgré la puissance de calcul des ordinateurs
modernes, ce nombre est trop grand : l'intelligence artificielle mettrait trop longtemps
à jouer. Il existe heureusement un grand
nombre de raffinements, dont le plus connu
est l'alphabeta .
Le temps de calcul de cet algorithme dépend
évidement de la profondeur et du nombre de
coups par plateau, mais aussi de l'ordre de
recherche des coups. Il permet néanmoins de
parvenir à un résultat en un temps acceptable
pour les joueurs.
L E PROGRAMME « RECHERCHE »
fonction recherche (p; plateau)
si la partie est.finie alors renvoyer le score
sip = oalors
renvoyer une estimation du score
soit max = +oo
pour tous les plateau; faire
fin
soit score = - recherche(p - 1; plateau)
max = max(score; max)
renvoyer max
Hors-série n°52. Mathématiques & informatique Tangente
L'intelligence artificielle pour jouer aux échecs
Deep Blue, le premier
à battre les champions
Alan T uring et C laude Shannon ont commencé
da ns les années 1950 les premiers travaux
sur l' intelligence artific iell e appliquée au jeu
d'échec. Mais c'est à la fin des années 1990
qu' IBM marqua l' hi sto ire en créant Deep
Blue, une mac hine conçue spéc ifiquement
pour jouer à ce je u. E n 1997 , avec la victo ire de
Deep Blue sur le célè bre champion Kas parov,
une machine se cl assait devant les humains
lors d ' un tournoi du plu s haut ni veau.
Depui s, de nombre ux progrès ont été réa li sés,
permettant de mettre au po int plusieurs
programmes solides qui fo nctionnent sur
des machines personnelles (ordinateurs ou
téléphones) et qui battraient aujourd ' hui
Deep Blue. Ces progrès sont du s à de grandes
avancées importantes en algorithmique.
l'algorithme du logiciel Chess
La société Magma Mobile a suivi les traces de
Deep Blue pour développer Chess, son Intelligence Artificielle pour téléphone, disponible
sur http://m.magmamobile.com/Chess/
Les programmes d'échecs reposent tous sur le
même principe : une fonction qui peut donner:
• une estimation de la valeur d'un plateau
(l'estimation du plateau peut être le nombre
de pièces blanches pondérées par leurs valeurs moins le nombre de pièces noires pondérées par leurs valeur).
• une fonction de recherche (voir en encadré
le programme). Cette fonction simule chaque
mouvement possible sur le plateau, et se rappelle récursivement. Quand elle arrive à une
profondeur donnée ou à une fin de partie, elle
décide d'une valeur à renvoyer.
Le logiciel
Chess
sur iPad.
Si on compte les plateaux d'échecs sur lesquels ont été joués moins de huit coups, on
obtient déjà 84 milliards de plateaux. Ce qui
veut dire qu'il faudrait faire 84 milliards d'appels à la fonction de recherche pour simuler
seulement huit coups.
Malgré la puissance de calcul des ordinateurs
modernes, ce nombre est trop grand : l'intelligence artificielle mettrait trop longtemps
à jouer. Il existe heureusement un grand
nombre de raffinements, dont le plus connu
est l'alphabeta .
Le temps de calcul de cet algorithme dépend
évidement de la profondeur et du nombre de
coups par plateau, mais aussi de l'ordre de
recherche des coups. Il permet néanmoins de
parvenir à un résultat en un temps acceptable
pour les joueurs.
L E PROGRAMME « RECHERCHE »
fonction recherche (p; plateau)
si la partie est.finie alors renvoyer le score
sip = oalors
renvoyer une estimation du score
soit max = +oo
pour tous les plateau; faire
fin
soit score = - recherche(p - 1; plateau)
max = max(score; max)
renvoyer max
Hors-série n°52. Mathématiques & informatique Tangente