Récursivité et algorithme

Bonjour,

J'essaie de programmer un jeu de dames avec des règles spéciales, où le joueur doit faire un maximum de prises au cours de son tour.
Voici ce que j'aimerais arriver à faire : si le programme voit qu'il y a une ou plusieurs prises possibles, il demande à l'utilisateur de choisir entre tous les parcours possibles celui qu'il préfère, mais seuls les parcours qui prennent le plus de pions à l'adversaire sont retenus (et affichés).

Je ne sais pas comment partir pour faire une fonction de ce genre. J'avais pensé à une fonction récursive, mais je ne sais pas comment la construire et quoi lui faire renvoyer. :arf:

Quelqu'un a-t-il une idée s'il-vous-plait?


But : Si on numérote les abscisses du damier de A à J et et les ordonnées de 1 à 10, on devrait proposer à l'utilisateur de choisir entre plusieurs combinaisons, par exemple (pour 2 prises):

Code:

---

1 2 3

-choix 1 : A1 --> C3 -->A5 -choix 2 : A1 --> C3 -->E5 -choix 2 : E3 --> G5 -->E7

---

La difficulté est dans le fait qu'à partir d'une position de départ ou d'une position intermédiaire, on peut avoir plusieurs ramifications, et je ne vois pas comment stocker tout ça dans un tableau.

Les positions des pièces sont stockées dans un tableau [10][10]. Ce tableau représente le damier. Par exemple tableau[3][5] représente la case D6. tableau[3][5]=0 si c'est une case vide, 1 s'il y a un pion blanc dessus, etc.

J'ai déjà plusieurs fonctions qui :
- calculent le nombre maximal de prises pour une pièce donnée.
- calculent les choix offerts pour une et une seule prise (par exemple, si un pion peut manger en avant à gauche et à droite, renverra 2, mais ne regarde pas si d'autres prises sont possibles ensuite).

Si quelqu'un a une idée il est le très bienvenu :)

Merci d'avance!

il faudrait que tu regardes de plus près la programmation par contraintes... voire les domaines finis afin de maximiser le nombre de pions capturés

(langage prolog conseillé)


sinon regardes les arbres alpha-beta... mais cela revient à te refaire l'unification et le backtrack à la main :?

Citation:

---

La difficulté est dans le fait qu'à partir d'une position de départ ou d'une position intermédiaire, on peut avoir plusieurs ramifications, et je ne vois pas comment stocker tout ça dans un tableau.

---

C'est peut-être parce qu'un tableau n'est pas la meilleure des solutions ?

Si j'ai bien suivit, tu veux, pour chaque piece, avoir la liste complete des "coups" possible, m'est avis que là, tu as un chouette arbre en perspective.

Prend un pion. Il a x coup possibles (x pouvant être égal à zero). Dans ton arbre chaque noeud va être la position d'un pion, et chaque noeud fils une position directement atteignable, juste après le mouvement précédent (attention, un pion éliminé au premier coup ne doit plus faire partie du calcul de pour le coup suivant, sinon tu risques de boucler et d'avoir des résultats abérants).

Une fois ton arbre construit, Si tu veux seulement les coups "interessant", tu prend seulement les branches avec une profondeur supérieure à ce que tu définit comme "interessant", genre tous les arbres ayant une profondeur de deux.
Et là, tu as toutes tes solutions.

--
Rakken

Comme l'a suggéré gorgonite je serai partisant de regarder du coté de min max puis d'alpha-béta.

Le problème avec ces approches, c'est qu'elle ne sont pas réalisables completement : devant le nombre exponentiel de solutions, tu ne pourras à la fois pas les explorer toutes et tu ne pourras pas non plus toutes les stoquer. La seule chose que ton algorithme peut faire, c'est s'éfforcer de te pousser vers une configuration qui va maximiser le nombre de prises mais pas te pousser à toujours obtenir la solution qui va maximiser le nombre de pions pris (comme tu n'es pas tout seul à jouer, tu ne peux pas forcer les choix de ton adversaire).

Citation:

---

Envoyé par zerakain

Je ne sais pas comment partir pour faire une fonction de ce genre. J'avais pensé à une fonction récursive, mais je ne sais pas comment la construire et quoi lui faire renvoyer. :arf:

---

Je dirais... rien ! :mrgreen:

Du moins en type de retour. Ta fonction qui "calcule le nombre maximal de prises pour une pièce donnée" doit d'une façon ou d'une autre (boucle ou récursion) parcourrir les prises possible donc ça fait une base. Il en faudrait une version modifiée qui prend en argument une liste de listes de prises (ou une liste d'une structure qui serve à stocker une pièce et une liste de mouvements pour elle) et une pièce. Elle parcourt toutes les prises possibles pour la pièce et stocke les séquences correspondantes dans la liste passée en paramètre. Pour ne pas trop mettre de séquences inutiles on n'ajoute une série de prise que quand il n'est plus possible d'en faire d'autres (donc au moment où on revient en arrière pour passer à d'autres possibilités).

C'est la liste passée en paramètre qui fait office de valeur de retour. Il ne reste qu'a créer la liste, boucler sur les pions puis éliminer toutes les séries de prises trop petites, ce qui nous donne en fait un type de retour possible : le maximum rencontré qui servira à l'élagage final et peut aussi être passé en paramètre pour pas ajouter une séquence alors que l'on a déjà trouvé plus long (c'est de là que doit venir la référence à l'alpha-béta).

La liste pourrait aussi être une table de hash avec pour clef le pion concerné et en valeur la liste de ses prises possibles (donc encore une liste). Pour ne pas élaguer tu peux aussi commencer par passer sur tous les pions pour avoir le maximum dès le début (je parie que ça ne va pas se sentir :mrgreen:).


Ca nous donne les coups possibles. Suivant l'utilisation que tu en fais tu voudras peut-être faire de la liste/table de hash une forêt (une liste d'arbre). Ce serait plus propre pour montrer le variations possibles. Dans ce cas on pourrait avoir en racine le pion concerné et aux feuilles les mouvements. Le type de retour devient le sous-arbre des prises à partir de la position donnée (avec en paramètre les coordonnées actuelles du pion et aussi le plateau de jeu si ce n'est pas une variable globale). Là pour le coup ça va vraiment être de la récurrence :

Code:

---

1 2 3 4 5 6 7

créer le noeud des coordonnées courrantes boucler sur les prises possibles jouer le coup ajouter en fils le résultat de l'appel récursif défaire le coup renvoyer le noeud courrant

---

On pourrait aussi passer en paramètre le numéro du coup (donc la profondeur dans l'arbre) et le maximum trouvé jusque là. Si au moment de renvoyer le noeud courrant celui-ci n'a pas de fils (pas de prise à faire ou pas assez de prises à faire) et que la profondeur est inférieure au max alors on ne renvoit rien.

Après au choix on part en connaissant le maximum ou on élague après coup. Au fond je trouve que c'est plus élégant avec une arbre.


Hum hum hum... je crois que je me suis un brin emporté moi :oops: Alors résolution pour cette année, faire des posts plus courts.

Ou je n'ai pas compris, ou il n'est pas en train de chercher le meilleur coup possible, il est simplement en train de chercher les coups legaux. En effet aux dames on est oblige de prendre quand on peut et on est oblige de faire le plus de prises possibles (pour moi ce n'est pas une regle additionnelle, c'est une regle de base).

Dans ce genre de contextes, il vaut se rendre compte qu'on parcours des arbres, mais qu'on ne les construit jamais.

Donc il te faut une fonction qui prend une description de la position actuelle et un pion et qui retourne le nombre de prises possible. Pour se faire, elle va regarder les 4 coups en prise, les simuler successivement s'ils sont valides, s'appeler recursivement sur la position modifiee, et retourner 1 de plus que le maximum retourne par un des appels recursifs. A adapter pour les dames. A adapter aussi s'il faut retourner aussi la liste des mouvements correspondant aux maxima.