Dans le cadre d'un devoir, je dois programmer un simple jeu d'échecs en Java. Je pensais profiter de l'occasion pour expérimenter la récursivité, et je me demandais s'il y avait un candidat évident aux échecs pour le code récursif?Bon usage de la récursivité dans la programmation des échecs?
Le candidat le plus évident pour moi serait une routine minimax récursive pour rechercher les meilleurs coups. Cela entre aussi dans une grande partie de la théorie derrière les algorithmes de recherche et serait assez cool à mettre en œuvre.
Exemple:
http://www.devshed.com/c/a/Practices/Solving-Problems-with-Recursion/6/
Je pense même, il n'y a pas d'alternative à la minmax récursive (si l'idée est de développer un KI) –
Aussi utile est ce lien expliquant alpha-beta http://www.fierz.ch/strategy1.htm –
Wow, c'est un bon article. Il semble que ce soit une méthode qui serait utilisée différemment à différentes étapes. Peut-être qu'il y aurait une version pour le compagnon, et une version pour un autre but (par exemple, capturer une pièce), chacune avec une profondeur différente. Hmmm ... Fun. – JDelage
Pas d'échecs, mais un casse-tête classique avec figueres d'échecs: http://en.wikipedia.org/wiki/Eight_queens_puzzle
Vous songez à backtracking
Profondeur première recherche est un candidat de choix pour récursivité. Donc, si vous programmez une IA pour le devoir, alors l'algorithme de la tête de l'IA pour essayer de trouver le meilleur coup suivant serait un bon candidat.
Faites attention cependant - vous pouvez manquer de mémoire rapidement. Vous voulez probablement limiter le nombre de coups que l'IA peut avoir.
Oui il y a. Si vous avez une fonction qui évalue "force" d'une certaine position pour dire joueur blanc. Vous pouvez déplacer une pièce et l'appeler récursivement pour évaluer la valeur d'un coup et choisir le meilleur coup.
Vous devriez appeler la même fonction pour le joueur noir, en échangeant des rôles pour les noirs et les blancs, évaluant ainsi le "danger" d'un mouvement adverse.
ensuite à nouveau pour les blancs, etc.
Juste être conscient que vous ne devriez pas aller trop profondément dans les niveaux de récursivité ou il faudra toujours.
Merci. J'ai juste besoin de trouver une bonne logique pour la valeur de chaque mouvement. – JDelage
esprit dynamic programming, comme vous avez plusieurs combinaisons qui conduisent à la même carte, vous devez vous rappeler de mettre en cache les mouvements afin d'éviter de répéter les calculs
Si vous détectez un récursion juste vous conduire à un endroit où vous avez été, juste rompre cet appel. Ceci est connu comme backtracking
Tout ce qui concerne les arbres. –
Un de mes premiers programmes Java (en 1998) était un programme de jeu d'échecs, utilisant un algorithme minimax récursif que Laplace mentionne ci-dessous. C'est certainement un projet intéressant pour apprendre le Java et la récursivité avec. – Jesper
www.m-w.com dit que la récursivité n'est pas un mot anglais valide. Titre édité –