Arbre de recherche : quel algo conseiller ?

Bonjour,

Je suis en train de développer une réussite et j'ai développé une option qui permet au programme de résoudre tout seul la réussite.
Mon problème est que le nombre de combinaisons semble tellement énorme, que le traitement est très très long...

J'ai fait une procédure récursive qui calcule toutes les positions des cartes et ça fonctionne pas mal.
Ensuite, j'ai fait une variante en multithreading qui permet de calculer plusieurs branches en parallèle, ça fonctionne encore mieux...

Comme je me retrouve avec un arbre à plusieures branches (comme aux échecs), je voudrais savoir quel est le meilleur algo à utiliser pour résoudre mon problème... J'ai souvent entendu parler de MiniMax et autres AlphaBeta, mais je ne sais pas le mettre en application ni déterminer si l'une de ces méthodes serait appropriée.

Merci pour vos lumières.
Cédric

Pour infos, le principe du jeu est le suivant :
- j'étale mes 52 cartes (mélangées) sur 4 lignes de 13 colonnes
- j'enlève les As pour me retrouver avec 4 trous
- pour jouer il suffit de combler l'un des trous avec une carte de valeur
supérieure (v+1) (et de même couleur) que la carte précédent le trou.
ex : j'ai un 3 de coeur suivi d'un trou, je peux donc y placer le 4 de coeur
- les 2 ne peuvent se placer qu'en colonne 1 (puisqu'il n'y a plus d'as) mais sur n'importe laquelle
- la partie est gagnée lorsque toutes les cartes sont ordonnées
- la partie est perdue lorsque tous les trous sont précédés de Rois

Euh... si vous aviez juste quelques pistes pour m'orienter ou des URLs, ça me conviendrait ... 8)

cédric

MinMax, Alpha/Beta ca fonctionne dans les cas ou il y un opposant dont il faut aussi evaluer la reaction probable. Il est peu vraissemblable que ce soit applicable dans ton cas.

Je suis pas sur d'avoir compris quel est exactement ta question.

Pour eviter de parcourir des possibilites qui ne different que par l'ordre par lequel on est arrive a une position, tu peux essayer de memoriser celles que tu as deja vue.

Merci pour ta réponse et pour ta précision sur les algos minmax, je ne savais pas qu'il fallait un opposant...

En fait tu as répondu exactement à ma question :

Je cherchais à savoir s'il y avait un moyen de réduire les possiblités à évaluer... c'est une bonne idée que tu me proposes là mais encore faut-il que je puisse la mettre en place...

Tu mémoriserais toutes les positions vues ? ça me paraît énorme...

a+
Cédric

Envoyé par cedico

Tu mémoriserais toutes les positions vues ? ça me paraît énorme...

Je ne sais pas si je memoriserais toutes les positions vues. J'analyserais le probleme pour voir si c'est possible. Je n'ai aucune idee de la proportion des 52!/4! positions possibles qui sont atteignables a partir d'une position de depart, j'ai pas du tout reflechi a ca, je t'ai simplement donne une technique tres generale pour eviter de refaire des calculs deja faits: memoriser le resultat.

Ton problème n'est autre que le traditionnel problème de recherche du plus court chemin dans un graphe. dans le sens ou ton jeux de départ n'est autre q'un noeud parmis les noeuds possibles (configurations possibles du jeu), à partir de chaque noeud tu peut atteindre d'autres noeuds (les différents coups à jouer représentent les étiquettes des arcs). tu cherches donc à trouver un chemin qui va du noeud départ au plus proche noeud solution (où le plus proche possible).

pour cela y'a les algorithme de RO du plus court chemin (les heuristiques tel que Algorithme A*, recherche tabou ....)

Bonne chance!

Merci beaucoup pour vos réponses.
Ca me donne déjà une bonne direction à suivre...

a+

Bon j'ai regardé un peu sur le net, mais j'ai pas trouvé grand chose de pratique, juste beaucoup de théorique....
Auriez-vous quelques liens sous la main où ils expliquent comment implémenter l'algo A* avec un cas simple ou un cas d'école ?

Hello

Tu as déjà fait ce genre d'algo à l'école toi ? Tu as de la chance

Un article sympa ici :
http://blog.lalex.com/archives/200309/49-traduction-article-sur-pathfinding.html

En espérant qu'il puisse t'aider

EKA+

Tu as déjà fait ce genre d'algo à l'école toi ? Tu as de la chance

Ok..., façon de parler ;-)

Super, ton article, je n'ai pas encore eu le temps de lire complètement mais je vais m'y atteler...

D'autre part, suite à un de tes mails d'hier, en recherchant des infos sur l'algo A*, je suis tombé sur les problèmes du voyageur de commerce et du taquin...
Comme ces 2 problèmes traitent d'un problèmatique qui consiste à avancer de cases en cases adjacentes pour trouver le chemin le plus court, es-tu sûr que je puisse appliquer cet algo pour mon jeu ?
En fait, je ne vois pas vraiment la similitude (si ce n'est de trouver la plus courte série de cartes pour aboutir à la solution) ... car pour ma part, j'ai à chaque fois, 4 cartes à poser itérativement, jusqu'à ce que le jeu soient complètement ordonné en couleurs.

Cédric