Algorithme Negamax Alpha Beta
MortyMars
Membre
Bonjour à tous 
Je reviens vers la communauté, toujours concernant mon projet de fork d'un jeu d'échecs en Objective-C, mais cette fois pour un sujet d'algorithmique.
En effet, le programme présente un bug récurrent et fugitif dans le coeur du code de l'algo Negamax Alpha Beta constituant le moteur de l'IA.
Dans environ 50% des cas j'obtiens un comportement ératique du programme, observable à la piètre qualité des coups joués par l'IA, et traçable dans le code par des valeurs absconses retournées (cf. la zone du code repérée dans le fichier 'Déroulé Negamax.xlsx')
Merci donc, à tous ceux qui verront ici une potentielle récréation à leurs activités stressantes 
, d'une idée, d'un avis, ou d'un partage d'expérience.
Le fichier 'Déroulé Negamax' qui concatène les appels entre les différentes méthodes concernées doit pouvoir suffire à vous faire une idée ; mais pour les plus curieux l'ensemble du code est dispo via le lien Github repris en signature : voir alors en particulier le fichier Minimax.m
Bien cordialement 
Réponses
Je n'ai clairement pas le temps de m'y intéresser, mais ne pourrais-tu pas mettre en place des tests unitaires ? Typiquement il est assez difficile de mettre le plateau dans une configuration particulière à la main, et là tu pourrais vérifier les états à chaque étape.
Merci Céroce pour ton (indéfectible) retour
).
Mon idée n'est pas -bien sûr- que quelqu'un d'autre que moi se lance dans des recherches chronophages (d'autant que de mon coté j'ai tout le temps de la retraite
Mon espoir est plutôt de réveiller le souvenir d'une expérience similaire parmi les membres.
Au demeurant ton intervention m'amène une nouvelle piste avec les "tests unitaires" auxquels je vais m'intéresser de près, car jusqu'ici mon "déboggage" se limitait à quelques breakpoints, NSLog ou writeToFile...
Vite fait, mais :
Ne devrais-tu pas tester la prochain coup adverse sur le nouveau plan où tu as effectué ton action ?
De plus, comme dans tes for loop, toutes tes variables d'itération s'appellent
moveEnCours, cela ne prête pas confusion ? Pareil pour les autres variables : score, etc. Pas sûr qu'Objective-C s'y retrouve...Pourrait y avoir même de la récursivité là-dedans...
Le depth, à chaque nouvelle boucle for, tu testes toutes les possibilités du camp adverse, non ? Ou c'est le NegaMax qui fait ça ?
C'est pas très clair tout ça...
Mais de ce que j'ai compris, tu testes chaque coup possible pour le joueur A, tu testes la meilleure réponse pour le joueur B, tu testes la meilleure réponse du joueurA à ce nouveau coup, etc, le tout pour 5 coups d'avance, et ensuite tu déduis quelle était la meilleur stratégie, c'est ça ?
Tu ne réécris pas
side, donc à chaque fois c'est le même dans tes boucles, non ?Dans l'doute, commente ton code, écris ce que tu souhaites faire avant les boucles, etc, cela te permettra peut-être d'y voir plus clair (et nous aussi).
Merci Larme pour ton retour
Oui, c'est bien ce qui est fait, les 'Moves' possibles 'otherSide' sont les coups adverses.
Et oui, c'est bien un appel récursif qui se fait au sein de 'NegamaxForSide', ce que ne révèle pas forcément très clairement le tableau Excel qui se voulait représentatif du code parcouru séquentiellement.
C'est l'appel récursif dans 'NegamaxForSide' qui permet de descendre dans l'arbre des coups possibles Joueur, IA, Joueur,...
Oui, c'est tout à fait ça, et lorsque depth=0 on sort de l'appel récursif et on évalue le 'board' (du seul point de vue matériel)
C'est le paramètre 'otherside' passé à la méthode NegamaxForSide qui assure le changement de camp à chaque nouvel appel récursif
J'avais pensé que le fichier Excel du déroulé des appels entre méthodes ferait le job
Je joins le fichier minimax.m qui sera en définitive plus parlant...
Je dois encore pousser un peu plus mes tests, mais je me suis déjà enlevé une belle épine du pied en abandonnant -dans 'BestMoveForSide' et 'NegamaxForSide'- les valeurs +INFINITY et -INFINITY (qui n'avaient pas semblé poser de problème particulier jusqu'ici, même affectées à des entiers ??!!) et en les remplaçant par des valeurs ne produisant pas de comportements inattendus (+100000 et -100000 qui conviennent dans l'idée car ce sont des valeurs jamais atteintes par une évaluation de 'board').
Le comportement du jeu est nettement moins ératique, pour ne pas dire conforme aux attentes : je croise les doigts pour que ça le reste.
À suivre ...
Non, mais je n'ai regardé que le doc en pièce-jointe, et pas vu le fichier sur GitHub, donc je soupçonnais une non-récursion, alors que c'est juste qu'elle était déroulée...
Concernant
INFINITYet ton test à valeur de100k, utilises plutôtINT_MAX.Le truc, c'est que ton
INFINITY, c'estHUGE_VALF, donc1e50f.Or,
int, c'est 2 ou 4 bytes (en fonction de la plateforme, mais de nos jours, ça s'ra 4 normalement), donc les valeurs seront -32,768/32,767 -2,147,483,648/2,147,483,647 (d'après le premier lien trouvé sur la question, le calcul était de 2^nombresDeBitPossibles-1 si je ne dis pas de bêtises, à une p'tite erreur près).Faudrait tester, mais je pense que ton
INFINITYdevait avoir un drôle de valeur si tu printais bestScore juste après l'avoir set.Je reviens aux tests unitaires, il faut que tu aies une placement à hard coder, dont tu connais le meilleur coup. Vu que c'est un fork, tu peux peut-être le tester dessus.
Et regarder ce que fais ton code.
Merci Larme pour l'idée INT_MAX
: ça fait le taf et c'est bien plus propre et plus pro 
Par ailleurs, j'ai commencé à mettre en place les test unitaires mais je ne percevais pas encore très clairement quels tests pouvaient être véritablement utiles et orientés performance...
Ton idée de plateau codé en dur attendant le meilleur coup connu d'avance, tombe donc à pic : merci là encore
@Céroce & @Larme
La mise en place de tests unitaires à résultats attendus a mis à jour une évidence : le moteur présentait la tare majeure d'être capable d'orienter un choix de déplacement pour un résultat à 3 coups devant (ou +/- selon valeur de la constante ad-hoc) mais était totalement désarmé pour saisir une opportunité à plus courte échéance... Modification faite, s'ajoutant à l'abandon d'INFINITY au profit d'INT_MAX, j'obtiens une IA nettement plus respectable
Merci encore à vous deux