Big Data
Devoir Maison de la semaine 3
février 2017
Jean Méhat

Le travail demandé consistait à reprendre le code utilisé pour la semaine 2 et à le modifier pour comparer le nombre de noeuds explorés (1) par minimax (2) par alphabeta(-Infini, +Infini) et (3) par minimax(Perdant, Gagnant).

J'ai donc repris le code de la semaine passée (ici). Je n'ai rien modifié dans l'infrastructure du jeu (représentation d'une position ; génération des coups légaux ; application et reprise d'un coup). J'ai en revanche fait fonctionner la fonction minimax et écrit la fonction alphabéta ; ajouté une fonction run pour les faire tourner ; appelé run trois fois avec les bons arguments dans la fonction main. Le code est ici.

Pour mettre en évidence la relation entre les fonctions minimax et alphabeta, j'ai mis le code en page de telle façon que les deux fonctions apparaissent sur deux colonnes, avec leurs lignes identiques alignées. On les trouve sur la page 2 du listing suivant.

J'ai fait tourner le programme pour diverses configurations ; par exemple, avec rien que des tas d'une seule allumette, on obtient les résultats suivants (les trois premiers nombres sont le nombre de noeuds explorés par minimax, par alphabéta(-Infini, +Infini) et par alphabéta(Perdant, Gagnant) ; la fin de la ligne est la repésentation de la position explorée) :

1 1 1 # 
2 2 2 # 1
5 5 3 # 1 1
16 12 10 # 1 1 1
65 31 11 # 1 1 1 1
326 76 56 # 1 1 1 1 1
1957 207 57 # 1 1 1 1 1 1
13700 550 400 # 1 1 1 1 1 1 1
109601 1657 401 # 1 1 1 1 1 1 1 1
986410 4866 3610 # 1 1 1 1 1 1 1 1 1
9864101 16261 3611 # 1 1 1 1 1 1 1 1 1 1
108505112 52372 39722 # 1 1 1 1 1 1 1 1 1 1 1
1302061345 191655 39723 # 1 1 1 1 1 1 1 1 1 1 1 1
      

Si on tente de visualiser naïvement ces nombres (j'utilise GnuPlot ; la commande est plot 'data' using 1 with lines, 'data' using 2 with lines, 'data' using 3 with lines), la courbe minimax force l'échelle du schéma de telle manière que les deux autres courbes ne sont même pas visibles (elles sont cachées par l'axe des X) :

On peut visualiser ces données d'une façon exploitable en utilisant une échelle logarithmique (avec Gnuplot, en ajoutant la commande set logscale y). On obtient alors le schéma suivant

Appelons M(x) le nombre de noeuds explorés par Minimax pour x tas. On peut remarquer sur que les nombres observés, on a M(n+1) = n M(n) + 1. C'est un peu plus que la fonction factorielle et c'est ce qui se traduit par la pente croissante de la courbe en rouge sur le schéma.

On voit qu'on n'utilise pas alphabéta de la façon optimale : la courbe verte n'est pas exactement à mi-chemin entre l'axe des x et la courbe rouge (ce qui traduirait sqrt(M(x)) sur notre échelle logarithmique).

Avec rien que des tas de deux allumettes, j'obtiens le résultat :

1 1 1 # 
4 4 4 # 2
33 27 25 # 2 2
550 149 52 # 2 2 2
16201 1866 1403 # 2 2 2 2
751056 8406 2808 # 2 2 2 2 2
50541769 262490 217077 # 2 2 2 2 2 2
367422402 950516 434156 # 2 2 2 2 2 2 2
      

Je vous rappelle encore une fois que minimax n'est pas la bonne manière de trouver un coup gagnant à Nim. Il y a beaucoup plus rapide.