Je tente depuis quelques jours de créer un jeu de dames sur python (sans interface graphique pour le moment, chaque chose en son temps) dans le but par la suite de tenter de créer une IA basée sur l'algorithme minmax par la suite.
Cependant, je rencontre un problème dans une fonction qui me servirait à établir les pions jouables par un jour, sachant que la règle aux dames stipule que seuls les pions (et les dames) pouvant prendre un maximum de pions (et de dames) ont le droit d'être joué par un joueur.
Pour faire cette fonction, je me suis lancé dans l'obscur domaine de la récursivité, qui est assez compliqué à comprendre quand on a pas fait MP spé info...
L'objectif de cette fonction serait de me renvoyer une liste comprenant le pion étudié, puis tous les chemins qu'il peut prendre avec le nombre de pion prenable associé à chaque chemin. Voici la fonction dont je parle, sachant que le cas de la dame n'est pas encore traité car je compte le calquer sur le cas du pion :
Et voici l'ensemble de mon programme pour le moment, sachant que le dernière fonction n'est pour le moment pas aboutie, je préfère d'abord être sûr de ce que me renvoie ma fonction obliger_manger^^:
# coding = utf-8
import numpy as np
# -------------------- CLASSES DU JEU DE DAMES --------------------------
class damier():
def __init__(self):
"""Les cases vides sont symbolisées par des 0."""
self.plateau = np.zeros((10,10), dtype = int)
self.coordonneesX = [i for i in range(10)]
self.coordonneesY = [i for i in range(10)]
class pion():
def __init__(self, damier, couleur, position):
"""La variable couleur vaut 1 ou -1, et position est un couple de variables."""
self.couleur = couleur
self.position = position
self.damier = damier
self.damier.plateau[self.position[0]][self.position[1]] = self.couleur
self.etat = True
def classe(self):
return('pion')
def retirer(self):
"""C'est relativement évident."""
self.damier.plateau[self.position[0]][self.position[1]] = 0
self.etat = False
def placer(self, coordonnees):
"""Ca reste relativement évident."""
self.position = coordonnees
self.damier.plateau[self.position[0]][self.position[1]] = self.couleur
self.etat = True
def deplacer_droite(self, coordonnees):
"""La donnée coordonnees est un couple de variables.
Pour déplacer un pion, on détermine la droite ou la gauche dans le sens de l'avancée du pion."""
if self.etat == False:
return("Le pion n'est pas sur le plateau.")
if np.sign(self.couleur) == 1:
if (coordonnees[0] == self.position[0] - 1) and (coordonnees[1] == self.position[1] + 1) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
self.retirer()
self.placer(coordonnees)
else:
print("Mouvement impossible.")
else:
if (coordonnees[0] == self.position[0] + 1) and (coordonnees[1] == self.position[1] - 1) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
self.retirer()
self.placer(coordonnees)
else:
print("Mouvement impossible.")
def deplacer_gauche(self, coordonnees):
"""Voir les remarques précédentes."""
if self.etat == False:
return("Le pion n'est pas sur le plateau.")
if np.sign(self.couleur) == 1:
if (coordonnees[0] == self.position[0] - 1) and (coordonnees[1] == self.position[1] - 1) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
self.retirer()
self.placer(coordonnees)
else:
print("Mouvement impossible.")
else:
if (coordonnees[0] == self.position[0] + 1) and (coordonnees[1] == self.position[1] + 1) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
self.retirer()
self.placer(coordonnees)
else:
print("Mouvement impossible.")
def possibilite_manger(self, pion):
"""On regarde si le pion peut en manger un autre."""
if self.etat == False:
return False
if np.sign(pion.couleur) != np.sign(self.couleur) :
if pion.position[0] == self.position[0] + 1 and pion.position[1] == self.position[1] + 1 and self.damier.plateau[pion.position[0] + 1, pion.position[1] + 1] == 0:
return True
elif pion.position[0] == self.position[0] + 1 and pion.position[1] == self.position[1] - 1 and self.damier.plateau[pion.position[0] + 1, pion.position[1] - 1] == 0:
return True
elif pion.position[0] == self.position[0] - 1 and pion.position[1] == self.position[1] - 1 and self.damier.plateau[pion.position[0] - 1, pion.position[1] - 1] == 0:
return True
elif pion.position[0] == self.position[0] - 1 and pion.position[1] == self.position[1] + 1 and self.damier.plateau[pion.position[0] - 1, pion.position[1] - 1] == 0:
return True
return False
def manger(self, pion):
"""On mange le pion."""
if self.possibilite_manger(pion) == False:
return("Mouvement impossible.")
if np.sign(pion.couleur) != np.sign(self.couleur) :
if pion.position[0] == self.position[0] + 1 and pion.position[1] == self.position[1] + 1 and self.damier.plateau[pion.position[0] + 1, pion.position[1] + 1] == 0:
self.retirer()
self.placer((pion.position[0] + 1, pion.position[1] + 1))
pion.retirer()
elif pion.position[0] == self.position[0] + 1 and pion.position[1] == self.position[1] - 1 and self.damier.plateau[pion.position[0] + 1, pion.position[1] - 1] == 0:
self.retirer()
self.placer((pion.position[0] + 1, pion.position[1] - 1))
pion.retirer()
elif pion.position[0] == self.position[0] - 1 and pion.position[1] == self.position[1] - 1 and self.damier.plateau[pion.position[0] - 1, pion.position[1] - 1] == 0:
self.retirer()
self.placer((pion.position[0] - 1, pion.position[1] - 1))
pion.retirer()
elif pion.position[0] == self.position[0] - 1 and pion.position[1] == self.position[1] + 1 and self.damier.plateau[pion.position[0] - 1, pion.position[1] - 1] == 0:
self.retirer()
self.placer((pion.position[0] - 1, pion.position[1] + 1))
pion.retirer()
class dame(pion):
def classe(self):
return('dame')
def deplacer_droite(self, coordonnees):
"""La donnée coordonnees est un couple de variables.
Pour déplacer une dame, on détermine la droite ou la gauche dans le sens de l'avancée du pion.
Une dame blanche vaut 2, une dame noire vaut -2."""
if self.etat == False:
return("La dame n'est pas sur le plateau.")
if np.sign(self.couleur) == 1:
i = self.position[0] - 9
while (self.position[0] - i) >= 0 and (self.position[1] + i) <= 10:
if (coordonnees[0] == self.position[0] - i) and (coordonnees[1] == self.position[1] + i) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
self.retirer()
self.placer(coordonnees)
break
i += 1
else:
i = self.position[0] - 9
while (self.position[0] - i) >= 0 and (self.position[1] - i) >= 0:
if (coordonnees[0] == self.position[0] - i) and (coordonnees[1] == self.position[1] - i) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
self.retirer()
self.placer(coordonnees)
break
i += 1
if self.position != coordonnees:
print("Mouvement impossible.")
def deplacer_gauche(self, coordonnees):
"""La donnée coordonnees est un couple de variables.
Pour déplacer une dame, on détermine la droite ou la gauche dans le sens de l'avancée du pion."""
if self.etat == False:
return("La dame n'est pas sur le plateau.")
if np.sign(self.couleur) == 1:
i = self.position[0] - 9
while (self.position[0] - i) >= 0 and (self.position[1] - i) >= 0:
if (coordonnees[0] == self.position[0] - i) and (coordonnees[1] == self.position[1] - i) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
self.retirer()
self.placer(coordonnees)
break
i += 1
else:
i = self.position[0] - 9
while (self.position[0] - i) >= 0 and (self.position[1] + i) <= 10:
if (coordonnees[0] == self.position[0] - i) and (coordonnees[1] == self.position[1] + i) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
self.retirer()
self.placer(coordonnees)
break
i += 1
if self.position != coordonnees:
print("Mouvement impossible.")
def possibilite_manger(self, pion, coordonnees):
"""On regarde si la dame peut en manger un pion."""
if self.etat == False:
return False
if np.sign(pion.couleur) != np.sign(self.couleur) and self.damier.plateau[coordonnees[0],coordonnees[1]] == 0:
i = self.position[0] - 9
while (self.position[0] - i) >= 0 and (self.position[1] - i) >= 0:
if pion.position[0] == self.position[0] + i and pion.position[1] == self.position[1] + i:
if i >= 0:
if coordonnees[0] > pion.position[0] and coordonnees[1] > pion.position[1]:
return True
elif coordonnees[0] < pion.position[0] and coordonnees[1] < pion.position[1]:
return True
elif pion.position[0] == self.position[0] + i and pion.position[1] == self.position[1] - i:
if i >= 0:
if coordonnees[0] > pion.position[0] and coordonnees[1] < pion.position[1]:
return True
elif coordonnees[0] < pion.position[0] and coordonnees[1] > pion.position[1]:
return True
i += 1
return False
def manger(self, pion, coordonnees):
"""On mange le pion."""
if self.possibilite_manger(pion, coordonnees) == False:
return("Mouvement impossible")
if np.sign(pion.couleur) != np.sign(self.couleur) and self.damier.plateau[coordonnees[0],coordonnees[1]] == 0:
i = self.position[0] - 9
while (self.position[0] - i) >= 0 and (self.position[1] - i) >= 0:
if pion.position[0] == self.position[0] + i and pion.position[1] == self.position[1] + i:
self.retirer()
self.placer((coordonnees[0], coordonnees[1]))
pion.retirer()
elif pion.position[0] == self.position[0] + i and pion.position[1] == self.position[1] - i:
self.retirer()
self.placer((coordonnees[0], coordonnees[1]))
pion.retirer()
i += 1
# -------------------- VARIABLES ET LISTES ------------------------------
damier = damier()
liste_pions = []
liste_dames = []
# -------------------- FONCTIONS ET REGLES ------------------------------
def init_partie(damier, liste_pions):
"""Mise en place des pions pour le début de la partie."""
for x in damier.coordonneesX:
for y in damier.coordonneesY:
if (x%2 != y%2) and x < 4:
liste_pions.append(pion(damier, -1, (x,y)))
elif (x%2 != y%2) and x > 5:
liste_pions.append(pion(damier, 1, (x,y)))
def pion_vers_dame(damier, liste_pions, liste_dames):
"""On vérifie tous les pions, et on change ceux qui sont à dame."""
for pion in liste_pions:
if pion.couleur == 1 and pion.position[0] == 0:
pion.retirer()
liste_dames.append(dame(damier, 2, (pion.position[0],pion.position[1])))
liste_pions.remove(pion)
if pion.couleur == -1 and pion.position[0] == 9:
pion.retirer()
liste_dames.append(dame(damier, -2, (pion.position[0],pion.position[1])))
liste_pions.remove(pion)
def fin_partie(liste_pions, liste_dames):
"""La partie se termine lorsqu'il ne reste plus qu'une couleur en jeu."""
try:
for pion in liste_pions:
if pion.couleur != liste_pions[0].couleur:
return False
for dame in liste_dames:
if dame.couleur != liste_pions[0].couleur:
return False
return True
except:
for dame in liste_dames:
if dame.couleur != liste_dames[0].couleur:
return False
return True
def obliger_manger(Pion, indice):
"""On indique tous les pions pouvant en manger d'autres."""
if Pion.classe() == 'pion':
liste_cibles = []
for cible in liste_pions:
nouvelle_position = Pion.position
if Pion.possibilite_manger(cible) == True:
liste_cibles.append(cible)
indice += 1
if Pion.position[0] > cible.position[0] and Pion.position[1] > cible.position[1]:
nouvelle_position = [cible.position[0] - 1, cible.position[1] - 1]
elif Pion.position[0] > cible.position[0] and Pion.position[1] < cible.position[1]:
nouvelle_position = [cible.position[0] - 1, cible.position[1] + 1]
elif Pion.position[0] < cible.position[0] and Pion.position[1] < cible.position[1]:
nouvelle_position = [cible.position[0] + 1, cible.position[1] + 1]
elif Pion.position[0] < cible.position[0] and Pion.position[1] > cible.position[1]:
nouvelle_position = [cible.position[0] + 1, cible.position[1] - 1]
if nouvelle_position == Pion.position:
break
nouveau_pion = pion(damier, Pion.couleur, nouvelle_position)
if len(obliger_manger(nouveau_pion, indice)[1]) != 0:
liste_cibles.append(obliger_manger(nouveau_pion, indice)[1])
liste_cibles.append(indice)
nouveau_pion.retirer()
return([Pion, liste_cibles])
else:
pass
def tour_joueur(damier, liste_pions, liste_dames):
"""Le joueur joue les blancs."""
liste_pions_jouables = []
for pion in liste_pions:
if pion.couleur == 1:
if liste_pions_jouables == []:
liste_pions_jouables.append(obliger_manger(pion, 0))
else:
if obliger_manger(pion, 0)[1] == liste_pions_jouables[0][1]:
liste_pions_jouables.append(obliger_manger(pion, 0))
elif obliger_manger(pion, 0)[1] > liste_pions_jouables[0][1]:
liste_pions_jouables = []
liste_pions_jouables.append(obliger_manger(pion, 0))
for dame in liste_pions:
if dame.couleur == 1:
if liste_pions_jouables == []:
liste_pions_jouables.append(obliger_manger(dame, 0))
else:
if obliger_manger(dame, 0)[1] == liste_pions_jouables[0][1]:
liste_pions_jouables.append(obliger_manger(dame, 0))
elif obliger_manger(dame, 0)[1] > liste_pions_jouables[0][1]:
liste_pions_jouables = []
liste_pions_jouables.append(obliger_manger(dame, 0))
for pion in liste_pions_jouables:
if pion.classe() == 'pion':
print("Vous pouvez jouer le pion situé aux coordonnees {} ; {}".format(pion[0].position[0] + 1, pion[0].position[1] + 1))
if pion.classe() == 'dame':
print("\nVous pouvez jouer la dame situé aux coordonnees {} ; {}".format(pion[0].position[0] + 1, pion[0].position[1] + 1))
drapeau = 0
while drapeau == 0:
input("\nEntrez les coordonnees du pion ou de la dame que vous voulez déplacer. Exemple : (3,2).\n", coordonnees_jouees)
coordonnees_jouees[0] -= 1
coordonnees_jouees[1] -= 1
for pion in liste_pions_jouables:
if pion[0].position == coordonnees_jouees:
pion_selectionne = pion
drapeau = 1
if drapeau == 0:
print("Le pion ou la dame sélectionné n'est pas jouable.")
Merci d'avance si vous pouvez m'aider, ça fait plusieurs jours que j'essaie de corriger cette fonction et je n'y arrive vraiment pas !
Curieux, quelqu'un m'avait posé le problème (ou qqchose de très proche) en début d'année, voici à quoi j'étais arrivé :
import sys
N = 10
def saut(lig, col, dl, dc, blancs, damier):
return (0 <= lig + dl < N and 0 <= col + dc < N
and (lig + dl // 2, col + dc // 2) in blancs
and (lig + dl, col + dc) not in blancs
and damier[lig + dl][col + dc] != 'x')
def f(lig, col, blancs, damier):
sauts = [((lig + dl, col + dc), (lig + dl // 2, col + dc // 2))
for (dl, dc) in ((-2, 2), (-2, -2), (2, -2), (2, 2))
if saut(lig, col, dl, dc, blancs, damier)]
if not sauts:
return 0
L = []
for (moi, blanc) in sauts:
damier[lig][col] = '.'
i, j = moi
damier[i][j] = 'x'
blancs.discard(blanc)
L.append(f(i, j, blancs, damier))
blancs.add(blanc)
damier[lig][col] = 'x'
damier[i][j] = '.'
return 1 + max(L)
def couleur(damier, coul):
couleurs = set()
for i in range(N):
for j in range(N):
if damier[i][j] == coul:
couleurs.add((i, j))
return couleurs
def main(damier):
damier = [list(ligne) for ligne in damier.split()]
blancs = couleur(damier, 'o')
noirs = couleur(damier, 'x')
if not noirs:
return 0
return max(f(lig, col, blancs, damier) for (lig, col) in noirs)
damier = (""""\
..........
........o.
.......x..
..o.o.o...
..........
....o.....
...x......
..........
..........
..........""")
print(main(damier))
Effectivement ça peut se faire récursivement. L'idée de base est simple : tu regardes les sauts que tu peux faire (ligne 12), tu lances récursivement (ligne 23) ta fonction pour chacun des sauts (ligne 18) et tu prends le max (ligne 27 et 44). Faut juste faire gaffe à remettre le plateau en état (lignes 24-25-26) quand on termine la fonction récursive. Celui qui joue (moi) a les noir (pions x).
Peut-être que le code ci-dessus pourra t'être utile.
Si on part d'un pion en (i, j), on peut parcourir son voisinage pour en sortir une liste des pions à prendre. Puis pour chaque pions à prendre, on peut "simuler" la prise du pion, se retrouver à une nouvelle position (i', j') et recommencer tant que la liste de pions à prendre n'est pas vide.
Première étape, parcourir le voisinage de (i, j) pour sortir une liste de (pion à prendre, nouvelle position, les prises suivantes).
A cette étape, les prises suivantes est une liste vide.
Si cette liste est vide, on a fini et on retourne []
Sinon, on itère sur les éléments de la liste et à chaque itération:
on retire le pion à prendre
on s'appelle soit même avec la nouvelle position (et le damier étant global).
on récupère une liste que l'on range dans les prises suivantes
on se remet le pion qui a été pris,
on replace le pion en (i, j)
et on recommence avec le pion suivant.
A la fin, on obtient une liste qui ressemble plutôt à un arbre puisqu'à chaque pion à prendre est associée "les prises suivantes" plus ou moins profond.
Reste à choisir le chemin le plus long... et peut être optimiser l'algorithme pour éviter de tout balayer.
Ce que je raconte là est un algorithme. Çà s'écrit d'abord en français. On le teste un peu sur quelques exemples pour s'assurer qu'on n'a rien oublié. Et quand on a l'impression que çà tient la route, on peut le coder pour voir si il vole.
Perso je fais pas de fonction récursive, j'itère sur une liste que je remplis au fur et à mesure. La dernière entrée est forcément le plus long chemin.
"il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"
PascalOrtiz, ton programme est intéressant, mais comment ensuite peux-tu retrouver le chemin entier ? Car j'ai l'impression que ton programme ne renvoie que le pion de plus grand indice (sauf erreur de ma part, car l'écriture de ton code est assez compacte et concise, du coup je peine un peu à le comprendre car je n'ai pas un niveau si avancé^^)
mps, c'est globalement ce que je fais dans mon code, notamment l'idée de l'arbre, c'est ce que je fais aussi, cependant je rencontre 2 difficultés :
Je ne sais pas comment faire pour faire retomber ma variable "indice" à 0 quand je passe sur une autre branche de l'arbre, ce qui fait que mon programme me renvoie mon arbre avec un indice qui ne fait que croître, et je ne sais pas où dire au programme de fixer la variable indice à 0 car l'appel récursif empêchera alors de faire grimper cet indice pour les branches plus longues.
Je ne sais pas non plus, encore pour des raisons de récursivité, comment réussir à renvoyer une liste de la forme [[pion1, pion2, 2], [pion3, 1]], où pion1 et pion2 représentent un chemin de prises et pion3 un autre, car mon programme me renvoie plutôt [pion1, 1, [pion2, 2], pion3, 2], ce qui rend le parcours de l'arbre plus compliqué ensuite.
josmiley a écrit:
Perso je fais pas de fonction récursive, j'itère sur une liste que je remplis au fur et à mesure. La dernière entrée est forcément le plus long chemin.
Que veux-tu dire par là ? Car je ne vois pas comment mettre ça en oeuvre avec plusieurs chemins possibles. Si il y a une solution qui exclut la récursivité, je suis preneur !
Merci pour votre aide !
- Edité par BouloukaouzeOulouzek 3 mai 2020 à 17:39:05
[position de depart, position pion adverse pris, position suivante, position pion adverse pris, position suivante, ... , position pion adverse pris, position finale]
au début chaque chemin n'est que la position d'un pion.
chemins = [[(2.4)],[chemin autre pion],...[chemin dernier pion]]
pour chaque chemin de la liste chemins, tu lis la dernière position de ton pion(soit chemin[-1]) et tu ajoutes à chemins le chemin actuel étendu des pions adverses pris et des nouvelles positions de ton pion.
par exemple ton pion en (2,4) peut prendre le pion adverse en (1,5) et se retrouvera alors en (0,6)
chemins vaudra
[[(2.4)],...,[(2,4),(1,5),(0,6)]]
ton pion peut aussi prendre en (3,5) et se retrouvera en (4,6)
mps, c'est globalement ce que je fais dans mon code, notamment l'idée de l'arbre, c'est ce que je fais aussi, cependant je rencontre 2 difficultés.
Honnêtement, je ne comprends pas votre code. A quoi sert l'indice? Pourquoi tester tous les pions (au lieu de ceux qui sont dans le voisinage de la position)? A quoi doit ressembler l'arbre qui remonte?
Après, çà regarde s'il est possible de manger le pion, mais çà n'a pas l'air de le manger.
C'est pour çà qu'il faut essayer d'écrire les choses en français avant de coder.
Sinon, on va le lire en se demandant ce qu'il fait. Sûr qu'on fait çà avec un certain à priori et que si on n'y retrouve pas trop ce qu'on cherche assez vite... car on ne peut pas y passer des heures... Cà ne va pas être facile de vous aider.
Je ne vois pas trop l'intérêt de cet indice: il donne le niveau de ce qu'on va ajouter dans l'arbre mais après, il faudra quand même le parcourir pour sortir la branche la plus profonde.
et si la structure de l'arbre qui se construit à chaque itération n'est pas décrit. On sait pas trop ce qu'on veut ni à quoi çà va bien pouvoir servir.
PascalOrtiz, ton programme est intéressant, mais comment ensuite peux-tu retrouver le chemin entier ? Car j'ai l'impression que ton programme ne renvoie que le pion de plus grand indice
Il faut adapter le code pour récupérer un plus long chemin. J'ai essayé de le faire, le problème c'est qu'initialement le problème était pas prévu pour ça. Voici ce que ça donne, je te garantie pas que ce soit juste mais au moins tu as l'idée :
import sys
# taille du damier
N = 10
def saut(lig, col, dl, dc, blancs, damier):
return (0 <= lig + dl < N and 0 <= col + dc < N
and (lig + dl // 2, col + dc // 2) in blancs
and (lig + dl, col + dc) not in blancs
and damier[lig + dl][col + dc] != 'x')
def f(lig, col, blancs, damier):
sauts = [((lig + dl, col + dc), (lig + dl // 2, col + dc // 2))
for (dl, dc) in ((-2, 2), (-2, -2), (2, -2), (2, 2))
if saut(lig, col, dl, dc, blancs, damier)]
if not sauts:
return (0, [])
M=0
for (moi, blanc) in sauts:
damier[lig][col] = '.'
i, j = moi
damier[i][j] = 'x'
blancs.discard(blanc)
maxi, path=f(i, j, blancs, damier)
if maxi>M:
M=maxi
maxi_path=path
edge=(moi, (lig, col))
blancs.add(blanc)
damier[lig][col] = 'x'
damier[i][j] = '.'
if M==0:
moi, blanc=sauts[0]
return 1, [(moi, (lig, col))]
maxi_path=maxi_path+[edge]
return len(maxi_path), maxi_path
def couleur(damier, coul):
couleurs = set()
for i in range(N):
for j in range(N):
if damier[i][j] == coul:
couleurs.add((i, j))
return couleurs
def main(damier):
damier = [list(ligne) for ligne in damier.split()]
print(*damier, sep='\n')
blancs = couleur(damier, 'o')
noirs = couleur(damier, 'x')
N, path=max(f(lig, col, blancs, damier) for (lig, col) in noirs)
return N, [z[::-1] for z in path[::-1]]
damier = ("""\
.x........
..o.....o.
.x.....x..
..o.o.o...
...x......
..o.o..x..
.o...o....
..o.o.o...
...o......
....x.....""")
print(*main(damier), sep='\n')
Les indices sont (ligne, colonne) et commencent à 0. Autrement dit, tu pars de (2,7) tu manges un blanc et tu arrives en (4,5) et de là tu manges encore un blanc et tu arrives en (2, 3), etc. Fais des tests pour vérifier.
La fonction récursive f renvoie un tuple (N, path) où N est le nombre maximal de prises à partir de la position noire (lig, col) et path est un chemin réalisant une prise de N pions blancs.
EDIT : le principe est très simple : je regarde chaque case blanche voisine que je peux manger depuis la position (lig, col), je demande à la fonction récursive de me dire, une fois que j'ai mangé le pion blanc en question, combien je mangerais de nouveaux pions blancs. Ensuite, je prends la combinaison qui rapporte le plus et je la prolonge par la prise depuis (lig, col) du pion blanc qui rapporte le plus. Ce n'est pas une récursivité compliquée. Fin du EDIT
Tu peux aussi certainement l'écrire itérativement et probablement de manière plus efficace que ci-dessus. L'idée d'une pile comme josmiley l'a proposé est exactement ce qu'il faut. Chaque fois que tu empiles c'est que tu manges un blanc, chaque fois que tu dépiles, c'est tu as regardé toutes les possibilités de manger un éventuel voisin blanc et que tu reviens là où tu étais avant avoir mangé le dernier pion blanc. Tu dois surveiller la longueur de ta pile, quand elle est de longueur maximale comme te l'as dit josmiley, la suite des éléments de la pile te donne une combinaison qui récupère le maximum de pions. Je trouve ça moins facile à écrire, surtout pour gérer «proprement» cette longueur maximale.
mps, effectivement l'indice ne servait à rien, je l'ai retiré.
PascalOrtiz, en m'inspirant du fonctionnement de ton code, je suis arrivé à une solution, et tout fonctionne bien !
Merci pour votre aide ! Je vais maintenant m'attaquer aux règles pour les dames...
[Récursivité]Jeu de dames en python
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
"il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"
Découverte Python Doc Tkinter Les chaînes de caractères
"il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"
"il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"
"il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"
Découverte Python Doc Tkinter Les chaînes de caractères