Temps de calcul de l'algorithme Minimax et Alphabeta

Bonsoir ,
J'ai comme projet la conception du jeu MORPION sur un plateau 9x9 avec intelligence artificielle et interface graphique en JAVA .
Pour gagner le joueur doit réussir a aligné 4X ou O .

Les cases du plateau son toutes désactivés sauf celle du milieu , après chaque coup les cases adjacentes deviennent activé ect ...


J'ai tout fais et j'ai implémenté les algorithmes , niveau facile minmax avec profondeur 1 , niveau moyen profondeur 2 et niveau difficile alpha beta profondeur 3 .

Le problème c'est quand j'essaye d'augmenter la profondeur , ça met beaucoup de temps pour que l'IA joue son coup . Si quelqu'un peut m'aider ça serai gentil .
Je peux partager tout mon code .

Oui bah, montre toujours le code au cas où, il est peut-être peu efficace.

Mais bon, au bout d'un moment c'est un problème normal et la raison pour laquelle un ordinateur ne peut pas battre un humain au go : le temps de calcul est trop long.
La solution n'est pas miraculeuse : il faut faire une sélection rapide des coups valables, au lieu de les essayer tous. Au risque de se tromper et d'ignorer un coup qui aurait été gagnant si on l'avait estimé valable.

voici pour alpha beta : http://pastebin.com/Ubq5aVp8
et pour minmax : http://pastebin.com/fiL9Ux6f

Arrête immédiatement de balader des JButton et autres éléments de UI dans tes algos -_-°.

Je suis débutant , c'est tout ce que j'ai pu faire . En plus ça marche ,et j'ai bien dit que le problème était juste si j'augmente la profondeur sa met du temps pour jouer .

Si quelqu'un à un conseil ça serai gentil .

Citation:

---

Envoyé par rpedro0921

c'est tout ce que j'ai pu faire . En plus ça marche ,et j'ai bien dit que le problème était juste si j'augmente la profondeur sa met du temps pour jouer .

---

Et cela arrive, d'abord parce que tu utilises des JButton dans ton algo.

Débutant ou pas, maintenant que je t'ai dit de pas le faire, je vois pas ce qui te gêne pour ne pas le faire. Utilise autre chose qu'un JButton ultra-complexe pour stocker l'état de ton calcul. N'importe quoi sera déjà mieux.

Sérieusement, chaque changement que tu fais su un JButton implique de nombreux calculs. Tu pourrais donc facilement réduire tes temps de calcul d'un facteur 10 à 100 en utilisant des structures de données adaptées plutôt qu'un effet de bord sur les JButton :roll:


Ensuite, il n'y a pas d'avance, une grille de 9x9, c'est 81 cases. Une profondeur de 3 coups pour un joueur, ça donne 5 mouvement dans la parties. Si on se base sur une moyenne de 40 cases accessibles, on a 40^5 situations à analyser et évaluer. Soit 100 millions de situations. Alors oui ça prend du temps et faut apprendre à coder proprement. Ton code est bon à jeter car tu n'a pas fait d'analyse sur comment structurer tes données, t'as tout fais à l'emporte pièces sans te poser de questions.

D'accord merci .