by Dans la continuité de ma démarche de déménagement des topics intéressants d'Espace-TI, en voilà un que j'avais écrit un matin ou j'avais fait des rêves d'intello.
Je me demandais quels paramètres étaient les plus importants à prendre en compte pour faire un IA de jeu d'échecs.
Bien que je n'aie pas l'intention directe de programmer un jeu d'échecs là maintenant ( je fais moins d'une heure de progra par semaine en ce moment...mais ma moyenne a monté de 10 points
), ces conseils pourraient servir a tout programmeur...Bref, bien entendu, je n'ai jamais fait encore une telle IA, et ce que je raconte est peut être faux, si vous avez des idées postez-les à la suite... (surtout si VOUS avez déjà fait une IA d'échecs...)
Donc comme critères principaux, en partant du principe que l'IA ne réfléchit pas à plus d'un tour à l'avance, voici mon raisonnement:
Pour l'instant, je ne me suis pas soucié :
- ni du temps que pourrait prendre l'IA à réfléchir. Je connais une IA d'échecs en ASM qui met 4 minutes par tour...
- ni de la stratégie pour mettre le Roi adverse en Mat : juste éliminer des pièces en préservant les siennes
1) Attaquer une pièce
- Pour chaque pièce, évaluer chaque position qu'elle peut prendre au prochain tour, retenir toutes les positions permettant de prendre une pièce ennemie (ça fait beaucoup)
- Pour chaque pièce ennemie ainsi susceptible d'être prise, évaluer si elle est protégée où non:
Ceci nécessite d'analyser une à une toutes les pièces ennemies pour voir leur rapport avec la pièce concernée.
Si cette pièce est protégée et de niveau inférieur ou égal à la pièce qui attaque, éliminer cette proposition de la liste.
À ce niveau, ne restent dans la liste de coups possibles que les attaques sur pièces non protégées ou pièces protégées mais de niveau supérieur à la pièce attaquante.
- Éliminer de la liste des coups possibles ceux qui mettraient le roi en échec
- Garder dans la liste uniquement les attaques visant les pièces de plus haut grade
- Privilégier l'attaque sur une pièce non protégée
- Si deux pièces peuvent faire cette attaque, envoyer celle de plus faible niveau
Il est bien entendu possible qu'aucune attaque ne soit envisageable ou censée. Dans ce cas, faire autre chose qu'attaquer.
2) Déplacer ses pièces
Pour savoir quelles pièces avancer, il faut se baser soit sur une prévision d'attaque au coup suivant, soit sur une politique de libération du terrain, c'est à dire avancer ses pièces au maximum pour coincer l'autre derrière des barrières. Donc:
- Pour chaque pièce, vérifier si elle peut avancer.
- Éliminer les positions ou la pièce avancerait en étant non protégée et se ferait prendre inutilement par l'adversaire en utilisant la database (voir paragraphe plus loin)
- Dans celles qui peuvent avancer, vérifier pour chaque position qu'elles peuvent adopter s'il n'y a pas une pièce non protégée ou de grade supérieur à attaquer au tour suivant (pour gagner du temps, je pense qui serait préférable d'avoir une matrice ou une base de Data en tout cas, mise à jour à chaque tour selon les pièces qui ont bougé, qui dit tout de suite si la pièce est protégée ou non. Cela épargne d'avoir à faire les tests à chaque pièce.)
- si il y a, retenir le coup permettant d'attaquer la pièce adverse la plus gradée, ceci par la pièce la moins gradée possible, en tenant compte des protections.
- s'il n'y a pas, chercher à avancer des pièces selon un ordre (auquel je n'ai pas encore réfléchi) qui permettrait d'occuper le plus d'espace sur le plateau.
3) Protéger une pièce
On peut aussi choisir de déplacer une pièce pour en protéger une autre, avant même de la déplacer pour "occuper l'espace" (selon moi, l'ordre des priorités donne privilège à la protection...)
- Vérifier la liste des pièces non protégées
- Privilégier la pièce non protégée de plus haut grade
- Parmi les pièces qui peuvent bouger, vérifier quelles pièces pourraient atteindre une position permettant de protéger cette pièce de plus haut grade, si aucune, passer à la pièce de grade inférieur (long en temps !)
- Si des pièces peuvent le faire, choisir la pièce de moindre grade, à une position où elle même serait protégée
LA DATABASE DES PROTECTIONS
Chaque pièce adverse doit être référencée comme protégée OUI ou NON, ça, c'est simple.
Ensuite, chaque case du plateau doit être référencée du point de vue du joueur IA comme:
- Protégée par une de ses pièces où non (est-ce que si je me déplace là bas je suis protégé)
- Potentiellement attaquée par une pièce adverse OUI ou NON
- Permettant d'attaquer une pièce adverse au prochain tour OUI ou NON
Cette database doit être mise à jour a chaque fois qu'une pièce bouge, ainsi, elle ne prend pas de temps à s'actualiser, et simplifie les calculs.
PRIORITÉ DES ACTIONS
Alors, que choisir entre attaquer, protéger une de ses pièces, avancer ?
- Évaluer si attaque envisageable ou pas
- Évaluer si nécessité de protéger une pièce
- Si les deux sont OUI, je ne sais pas encore comment faire pour choisir... Si une des deux est NON, choisir l'autre.
- Si les deux sont NON, choisir d'avancer une pièce soit pour attaquer au coup suivant soit pour occuper la place...
Notez qu'il est possible d'enregistrer en mémoire un coup: exemple
- Si la pièce finalement retenue pour bouger se retrouve a une place qui n'est pas protégée, enregistrer ce coup dans une variable pour forcer le tour suivant à déplacer une pièce pour la protéger. (choix "protection" obligatoire)
- Si une pièce est avancée car on a repéré une pièce de haut grade prenable au coup suivant, forcer son attaque (choix "attaque" obligatoire).
BREF, je vous laisse sur ces considérations, j'essaierai de penser à des trucs moins tordus la nuit prochaine, n'hésitez pas à me faire part de vos idées !
(Bon, pis un de ces jours je tenterai peut-être un jeu d'échecs sait-on jamais...dans au moins 4 mois alors.)
