Algorithme Negamax Alpha Beta

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 o:) , 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 ;)

Mots clés:

Réponses

  • CéroceCéroce Membre, Modérateur
    24 mars modifié #2

    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... :/

  • LarmeLarme Membre
    24 mars modifié #4

    Vite fait, mais :

    for (Move *moveEnCours in [self PossibleMovesForSide:otherSide board:board]) (ligne 25)
    

    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 :)

    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...

    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.

    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...

    C'est l'appel récursif dans 'NegamaxForSide' qui permet de descendre dans l'arbre des coups possibles Joueur, IA, Joueur,...

    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 ?

    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)

    Tu ne réécris pas side, donc à chaque fois c'est le même dans tes boucles, non ?

    C'est le paramètre 'otherside' passé à la méthode NegamaxForSide qui assure le changement de camp à chaque nouvel appel récursif

    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).

    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 ...

  • LarmeLarme Membre
    25 mars modifié #7

    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 INFINITY et ton test à valeur de 100k, utilises plutôt INT_MAX.
    Le truc, c'est que ton INFINITY, c'est HUGE_VALF, donc 1e50f.
    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 INFINITY devait avoir un drôle de valeur si tu printais bestScore juste après l'avoir set.

  • LarmeLarme Membre

    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 B)
    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 :)

Connectez-vous ou Inscrivez-vous pour répondre.