L'article anglais sur Wikipédia est plus détaillé et contient du pseudo-code : https://en.wikipedia.org/wiki/Minimax
Comment on crée ce putain d'arbre ?
Tu choisis le nombre de demi-coups que tu souhaites simuler dans le futur : ce sera le profondeur maximale de ton arbre. Tu prends la partie de ton jeu en cours, tu regardes quels sont les coups possibles (suivant si c'est à toi ou ton adversaire de jouer). Pour chaque coup jouable, tu crées un nouveau nœud enfant et tu lui associes la position de jeu correspondante résultante du coup joué. Tu répètes le procédé jusqu'à atteindre la profondeur maximale (récursivement, type parcours en profondeur, ça doit bien se faire).
Ce qu'il faut comprendre c'est qu'à chaque nœud est associé une certaine position future de la partie (le chemin menant à ce nœud représente les coups successifs des deux joueurs).
quand on utilise une fonction récursive pour le crée, on commence donc par le haut de l'arbre pour descendre vers les feuilles OR c'est l'inverse qu'il faudrait faire puisqu'on récupère d'abord les valeurs des feuilles pour les faire remonté aux noeud (comment j'fais ça ?)
Comment on le parcours ? (Il y a une histoire de branche gauche ?)
En effet, les valeurs intéressantes sont celles des feuilles. On a utilisé une première fonction récursive pour le créer et le stocker dans une structure concrète. Maintenant, on va utiliser une autre fonction récursive pour le parcourir et sélectionner le meilleur coup à jouer.
Tu commences par le haut de l'arbre, donc lorsque tu appelleras ta fonction, elle va s’appeler récursivement pour s’exécuter sur un nœud d'une profondeur supérieure, et ainsi de suite jusqu'à atteindre la profondeur maximale que tu auras défini.
Maintenant que ta fonction a atteint une feuille, elle peut évaluer la position de jeu, puis retourner un score qui sera récupéré et utilisé par l'appel récursif de ta fonction qui a été fait à la profondeur du dessus. Et ainsi de suite jusqu'à retourner à ton nœud racine.
Ta fonction, lorsqu'elle a atteint une feuille, elle regarde l'état du jeu que tu as préalablement stocké et associé au noeud, et elle donne un score indiquant quel joueur à l'avantage.
Lorsqu'elle est à un noeud juste avant une feuille, elle récupère les valeurs de chaque noeud enfant (des feuilles), et choisit le meilleur score dont elle prend alors la valeur et qu'elle peut retourner. Comme ça le noeud juste au dessus peut lui aussi le récupérer et l'utiliser pour déterminer quel est le meilleur coup.
L'histoire de branche gauche, je ne vois pas ce que c'est. Il faut juste faire attention au fait que ton arbre représente tes coups mais aussi ceux de ton adversaire, alternativement entre chaque profondeur.
On recrée l'arbre a chaque fois que l'ordi doit prendre une décision ou on stock cet arbre ?
Tu pourrais théoriquement réutiliser une sous-partie de ton arbre au tour suivant (celle qui correspond au coup joué réellement), mais ignorons cela. Pars du principe qu'il faudra reconstruire l'arbre à chaque fois que tu voudras choisir le meilleur coup.
-------
En pratique, on utilise une seule fonction récursive qui parcours l'arbre en même temps qu'elle le construit. Et on ne stocke pas toutes les positions de jeu car cela prendrait trop de place.
Mais essaye de commencer avec la première technique que je t'ai décrit, si tu le veux bien. On verra pour la deuxième technique après. C'est pour déjà que tu comprennes bien le principe du Minimax.
