Accueil
Ce midi, on discutait avec Sébastien du fait que le min-max, ça risque d'être plus que chaud à faire. Quelque soit la manière avec laquelle on aborde le problème, il y a des choses qui coincent :
- en traitant tous les coups possibles, on a un min-max qui fonctionne parfaitement, mais avec un temps d'exécution délirant (de l'exponentiel méchant
)
- en mettant un alpha-beta en place, les calculs d'IA ne mettront plus que 154 fois l'âge de l'univers à s'exécuter, au lieu de 4662.
- pour ne pas traiter tous les coups possibles, et donc avoir une complexité "raisonnable", je vois deux possibilités :
+ construire une abstraction de la carte donnant les relations de distance entre les groupes et points clés de la carte (on peut partir d'une triangulation de Delaunay par ex), et exécuter le min-max dessus. En faisant ça, on réduit grandement le nombre de coups réalisables, mais on va y perdre des plumes : une évaluation (forcément) à moitié fausse dès le départ, sera totalement fausse ou presque au second coup, et ça ira de pire en pire... Il s'ajoute à cela le caractère plus ou moins continu des actions effectuées. Par exemple, on ne peut pas dire qu'un groupe va soit avancer de 5 cases, soit rester sur place. Il peut aussi bouger de 1, 2, etc... Il faut aussi tenir compte des attaques à n vs 1... Bref, on fera des prédictions, mais elles seront fausses. Et dans tous les cas, le fait de devoir modifier le graphe à chaque noeud de l'arbre d'exploration (pour prendre en compte les déplacements, attaques, etc) coûterait cher.
+ on peut choisir de travailler sur les cases directement, mais en diminuant radicalement les possibilités d'action. Il s'agirait de dire par exemple que si un groupe a 3 ennemis dans son champ d'action, alors il peut soit les attaquer (d'une seule manière), soit rester sur place, soit fuir (d'une seule manière aussi). Ça nous fait donc 5 coups possibles par groupe, ce qui reste à peu près raisonnable, mais quand même élevé quand on multiplie ça par le nombre de groupes. Il est donc clair que là aussi, on ne peut pas faire de folies dans le choix de la profondeur. Problème : on aurait une IA sachant combattre contre elle même (forcément, quand les deux pnj sont aussi bêtes l'un que l'autre...), mais faisant des prédictions à 100% fausses dès le départ face à un humain (et aussi plus que limitée stratégiquement parlant).
Dans tous ces cas, je ne vois pas comment utiliser le min-max efficacement si on évalue plus que les conséquences directes de son propre coup. C'est gênant, vu que tout l'intérêt du min-max par en fumée.
Quand je relis l'énoncé sur sujet de TER, je vois :
" L'IA dans les jeux de stratégie historique est fondamentale. L'objectif de ce TER est d'étudier l'impact des algorithmes min-max (avec alpha-beta pruning) dans ces jeux."
Par contre, le prof ne nous a jamais dit qu'il voulait du min-max particulièrement. J'ai même l'impression que c'est sans importance pour lui. Comme vous l'avez compris, je suis plutôt d'avis de lui demander des précisions
- en traitant tous les coups possibles, on a un min-max qui fonctionne parfaitement, mais avec un temps d'exécution délirant (de l'exponentiel méchant
)- en mettant un alpha-beta en place, les calculs d'IA ne mettront plus que 154 fois l'âge de l'univers à s'exécuter, au lieu de 4662.
- pour ne pas traiter tous les coups possibles, et donc avoir une complexité "raisonnable", je vois deux possibilités :
+ construire une abstraction de la carte donnant les relations de distance entre les groupes et points clés de la carte (on peut partir d'une triangulation de Delaunay par ex), et exécuter le min-max dessus. En faisant ça, on réduit grandement le nombre de coups réalisables, mais on va y perdre des plumes : une évaluation (forcément) à moitié fausse dès le départ, sera totalement fausse ou presque au second coup, et ça ira de pire en pire... Il s'ajoute à cela le caractère plus ou moins continu des actions effectuées. Par exemple, on ne peut pas dire qu'un groupe va soit avancer de 5 cases, soit rester sur place. Il peut aussi bouger de 1, 2, etc... Il faut aussi tenir compte des attaques à n vs 1... Bref, on fera des prédictions, mais elles seront fausses. Et dans tous les cas, le fait de devoir modifier le graphe à chaque noeud de l'arbre d'exploration (pour prendre en compte les déplacements, attaques, etc) coûterait cher.
+ on peut choisir de travailler sur les cases directement, mais en diminuant radicalement les possibilités d'action. Il s'agirait de dire par exemple que si un groupe a 3 ennemis dans son champ d'action, alors il peut soit les attaquer (d'une seule manière), soit rester sur place, soit fuir (d'une seule manière aussi). Ça nous fait donc 5 coups possibles par groupe, ce qui reste à peu près raisonnable, mais quand même élevé quand on multiplie ça par le nombre de groupes. Il est donc clair que là aussi, on ne peut pas faire de folies dans le choix de la profondeur. Problème : on aurait une IA sachant combattre contre elle même (forcément, quand les deux pnj sont aussi bêtes l'un que l'autre...
), mais faisant des prédictions à 100% fausses dès le départ face à un humain (et aussi plus que limitée stratégiquement parlant).Dans tous ces cas, je ne vois pas comment utiliser le min-max efficacement si on évalue plus que les conséquences directes de son propre coup. C'est gênant, vu que tout l'intérêt du min-max par en fumée.
Quand je relis l'énoncé sur sujet de TER, je vois :
" L'IA dans les jeux de stratégie historique est fondamentale. L'objectif de ce TER est d'étudier l'impact des algorithmes min-max (avec alpha-beta pruning) dans ces jeux."
Par contre, le prof ne nous a jamais dit qu'il voulait du min-max particulièrement. J'ai même l'impression que c'est sans importance pour lui. Comme vous l'avez compris, je suis plutôt d'avis de lui demander des précisions
