Conseils pour une IA d'échecs

Voir le sujet précédent Voir le sujet suivant Aller en bas

Conseils pour une IA d'échecs

Message par persalteas le Jeu 11 Oct - 11:21

Salut, je me suis levé ce matin avec des questions très théoriques en tête...


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... Peur ...mais ma moyenne a monté de 10 points :P ), ces conseils pourraient servir a tout programmeur...

Spoiler:
par exemple, je parie une TI que sachiix va dire "je vais essayer", "je vais voir ce que je peux faire", ou quelque chose du genre :D

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 a la suite...

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 a 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écéssite d'analyser une a 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.

A ce niveau, ne restent dans la liste de coups possibles que les attaques sur pièces non protégées où pièces protégées mais de niveau supérieur à la pièce attaquante.

- Eliminer 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 où 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.

- Eliminer 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 a jour a 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 a faire les tests a 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 a 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 a la pièce de grade inférieur (long en temps !)

- Si des pièces peuvent le faire, choisir la pièce de moindre grade, a 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.


PRIORITE DES ACTIONS

Alors, que choisir entre attaquer, protéger une de ses pièces, avancer ?

- Evaluer si attaque envisageable ou pas
- Evaluer si nécéssité 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 a me faire part de vos idées ! Houra

(Bon, pis un de ces jours je tenterai peut-être un jeu d'échecs sait-on jamais...dans au moins 4 mois alors.)



_________________
[Vous devez être inscrit et connecté pour voir cette image]

persalteas
Platinum 2
Platinum 2

Sexe : Masculin
Age : 21
Messages : 2068
Date d'inscription : 30/06/2010
Etudes : PACES (médecine)
Points Forum : 114
Points Concours : 10
Langages :
  • - TI-Basic Z80
  • - xLib
  • - Grammer
  • - TI-Basic Nspire
Calculatrices :
  • - TI-82 Stats.fr
  • - TI-83
  • - TI-83+
  • - TI-84+ SE
  • - TI-86
  • - TI-Nspire
  • - TI-Nspire CX
  • - Casio Collège
  • - Casio Graph

TI-84 Pocket.fr


http://tiemulation.kegtux.org

Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par noelthebest le Jeu 11 Oct - 14:09

À la Fnac j'avais vu un livre, qui se présentait comme la Bible de l'intelligence artificielle, tu sais un livre noir, si tu balades dans le rayon informatique. Il pourrait peut-être t'aider.

je vais voir ce que je peux faire Content

_________________
[Vous devez être inscrit et connecté pour voir cette image]

[Vous devez être inscrit et connecté pour voir cette image]
[Vous devez être inscrit et connecté pour voir cette image]

noelthebest
Platinum 1
Platinum 1

Sexe : Masculin
Age : 19
Messages : 1969
Date d'inscription : 12/03/2011
Etudes : ENS Cachan
Points Forum : 20
Points Concours : 9
Langages :
  • - TI-Basic Z80
  • - ASM TI-83+ / TI-84+
  • - Axe Parser
Calculatrices :
  • - TI-83+.fr
  • - TI-Nspire CX
  • - Casio Collège
  • - Casio Graph

TI-84+ SE


Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par nikitouzz le Jeu 11 Oct - 14:22

euh...

1) je ne dit pas ce genre de truc sans le faire...
2) il y a des bonne IA d'echec en asm qui ne prenne pas 4 minute ce jeu par exemple :

euh je l'ai sur mon ordi mais je ne le trouve plus sur internet, si vous voulez je vous le donne

_________________
[Vous devez être inscrit et connecté pour voir cette image]
Invité née le 0 a aujord'huis 0 ans et a posté 11 messages... je suis derrière vous

2x2x2 : 2.18 secondes / 2x2x2 une main : 21.15 secondes / 2x2x2 yeux bandés : 47.59
3x3x3 : 5.97 secondes / 3x3x3 une main : 49.86 secondes
4x4x4 : 1.49 minutes / 4x4x4 une main : 6.50 minutes
5x5x5 : 4.10 minutes / 5x5x5 une main : 18.02 minutes
6x6x6 : 8.10 minutes
7x7x7 : 16.03 minutes
9x9x9 : 58.26 minutes

3x3x1 : 0.73secondes / 3x3x2 : 30.55secondes / 3x3x3 : 5.97secondes / 3x3x4 : 1.09minutes / 3x3x5 : 1.46minutes / 3x3x6 : 2.06minutes

megaminx : 5.59 minutes / pyraminx : 7.91 secondes / square-one : 1.07

nikitouzz
Platinum 1
Platinum 1

Sexe : Masculin
Age : 21
Messages : 1834
Date d'inscription : 16/01/2011
Points Forum : 7
Points Concours : 6
Langages :
  • - TI-Basic Z80
  • - ASM TI-83+ / TI-84+
  • - Axe Parser
  • - TI-Basic 68K
  • - TI-Basic Nspire
Calculatrices :
  • - TI-73
  • - TI-76.fr
  • - TI-82 Stats.fr
  • - TI-83+
  • - TI-84+
  • - TI-92
  • - TI-Nspire
  • - TI-Nspire CX

TI-84+ SE


Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par linkakro le Jeu 11 Oct - 14:34

Faire un brainstorming des idées de conception n'est pas une mauvaise idée. Ok

Je pense me concentrer d'abord sur les restrictions des règles avant de concevoir une IA.
Je n'ai jamais terminé mon programme du concours 5 tout82.

linkakro
Or 4
Or 4

Sexe : Masculin
Age : 22
Messages : 768
Date d'inscription : 01/07/2010
Etudes : dut geii (elec/info)
Points Forum : 51
Points Concours : 8
Langages :
  • - TI-Basic Z80
  • - ASM TI-82 Stats / TI-83
  • - ASM TI-83+ / TI-84+
Calculatrices :
  • - TI-82 Stats.fr
  • - TI-84 Pocket.fr

TI-84+ SE


Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par Hayleia le Jeu 11 Oct - 17:09

linkakro a écrit:Faire un brainstorming des idées de conception n'est pas une mauvaise idée. [Vous devez être inscrit et connecté pour voir cette image]
Tout à fait, ça peut donner des idées à des gens qui cherchaient un projet et ça les aide à démarrer plus vite Très Content

Hayleia
Or 4
Or 4

Age : 22
Messages : 406
Date d'inscription : 03/08/2012
Points Forum : 45
Points Concours : 4
Langages :
  • - TI-Basic Z80
  • - Axe Parser
Calculatrices :
  • - TI-76.fr
  • - TI-83+
  • - TI-84+ SE
  • - TI-Nspire CX

TI-84+ SE


Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par persalteas le Ven 12 Oct - 11:41

C'est bien pour ça que j'ai posé ces réflexions ici Content

Linkakro tu as fait un jeu d'échecs ? O_o

Si tu l'as bien avancé déjà, ça me tenterait de le finir... J'ai plutôt la flemme d'en commencer un de zéro, mais si j'arrive a comprendre ton code...

tu veux bien ?

@sachiix: fait péter Clin Oeil

_________________
[Vous devez être inscrit et connecté pour voir cette image]

persalteas
Platinum 2
Platinum 2

Sexe : Masculin
Age : 21
Messages : 2068
Date d'inscription : 30/06/2010
Etudes : PACES (médecine)
Points Forum : 114
Points Concours : 10
Langages :
  • - TI-Basic Z80
  • - xLib
  • - Grammer
  • - TI-Basic Nspire
Calculatrices :
  • - TI-82 Stats.fr
  • - TI-83
  • - TI-83+
  • - TI-84+ SE
  • - TI-86
  • - TI-Nspire
  • - TI-Nspire CX
  • - Casio Collège
  • - Casio Graph

TI-84 Pocket.fr


http://tiemulation.kegtux.org

Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par nikitouzz le Ven 12 Oct - 12:21

la je suis au CDI de mon lycee ^^ mais si tu veux ce soir je te le donnerai Content

_________________
[Vous devez être inscrit et connecté pour voir cette image]
Invité née le 0 a aujord'huis 0 ans et a posté 11 messages... je suis derrière vous

2x2x2 : 2.18 secondes / 2x2x2 une main : 21.15 secondes / 2x2x2 yeux bandés : 47.59
3x3x3 : 5.97 secondes / 3x3x3 une main : 49.86 secondes
4x4x4 : 1.49 minutes / 4x4x4 une main : 6.50 minutes
5x5x5 : 4.10 minutes / 5x5x5 une main : 18.02 minutes
6x6x6 : 8.10 minutes
7x7x7 : 16.03 minutes
9x9x9 : 58.26 minutes

3x3x1 : 0.73secondes / 3x3x2 : 30.55secondes / 3x3x3 : 5.97secondes / 3x3x4 : 1.09minutes / 3x3x5 : 1.46minutes / 3x3x6 : 2.06minutes

megaminx : 5.59 minutes / pyraminx : 7.91 secondes / square-one : 1.07

nikitouzz
Platinum 1
Platinum 1

Sexe : Masculin
Age : 21
Messages : 1834
Date d'inscription : 16/01/2011
Points Forum : 7
Points Concours : 6
Langages :
  • - TI-Basic Z80
  • - ASM TI-83+ / TI-84+
  • - Axe Parser
  • - TI-Basic 68K
  • - TI-Basic Nspire
Calculatrices :
  • - TI-73
  • - TI-76.fr
  • - TI-82 Stats.fr
  • - TI-83+
  • - TI-84+
  • - TI-92
  • - TI-Nspire
  • - TI-Nspire CX

TI-84+ SE


Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par persalteas le Ven 12 Oct - 12:58

Parfait ! Clin Oeil

(Si ça se trouve on parle du même)

_________________
[Vous devez être inscrit et connecté pour voir cette image]

persalteas
Platinum 2
Platinum 2

Sexe : Masculin
Age : 21
Messages : 2068
Date d'inscription : 30/06/2010
Etudes : PACES (médecine)
Points Forum : 114
Points Concours : 10
Langages :
  • - TI-Basic Z80
  • - xLib
  • - Grammer
  • - TI-Basic Nspire
Calculatrices :
  • - TI-82 Stats.fr
  • - TI-83
  • - TI-83+
  • - TI-84+ SE
  • - TI-86
  • - TI-Nspire
  • - TI-Nspire CX
  • - Casio Collège
  • - Casio Graph

TI-84 Pocket.fr


http://tiemulation.kegtux.org

Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par linkakro le Ven 12 Oct - 18:30

Je n'ai jamais numérisé mon echec (à l'époque je programmais exclusivement sur calculatrice et papier, pas de câble, ...). Le code papier doit trainer quelque part... mais pas à portée de main. La semaine prochaine je devrais pouvoir le récupérer.
De plus il est à 2 joueurs humains, très lourd, moche à cause de la restriction ti82, et plein de gotos pour économiser des boucles... Et enfin inachevé.
Le projet contenait les déplacements normaux, je ne sais plus pour les roques, les prises en passant et les mises en échec. Je prévoyais les pats et mats mais pas je ne les ai pas réussis.

linkakro
Or 4
Or 4

Sexe : Masculin
Age : 22
Messages : 768
Date d'inscription : 01/07/2010
Etudes : dut geii (elec/info)
Points Forum : 51
Points Concours : 8
Langages :
  • - TI-Basic Z80
  • - ASM TI-82 Stats / TI-83
  • - ASM TI-83+ / TI-84+
Calculatrices :
  • - TI-82 Stats.fr
  • - TI-84 Pocket.fr

TI-84+ SE


Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par persalteas le Sam 13 Oct - 15:03

Ah.

Ben je veux bien quand même si tu le retrouves :P

Tu ne stockais pas tes programmes autrement que sur papier ?

_________________
[Vous devez être inscrit et connecté pour voir cette image]

persalteas
Platinum 2
Platinum 2

Sexe : Masculin
Age : 21
Messages : 2068
Date d'inscription : 30/06/2010
Etudes : PACES (médecine)
Points Forum : 114
Points Concours : 10
Langages :
  • - TI-Basic Z80
  • - xLib
  • - Grammer
  • - TI-Basic Nspire
Calculatrices :
  • - TI-82 Stats.fr
  • - TI-83
  • - TI-83+
  • - TI-84+ SE
  • - TI-86
  • - TI-Nspire
  • - TI-Nspire CX
  • - Casio Collège
  • - Casio Graph

TI-84 Pocket.fr


http://tiemulation.kegtux.org

Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par nikitouzz le Dim 14 Oct - 8:26

ah en faite je me suis tromper mon jeux d'echec est en 2 joueur et pas d'IA.... toute mes excuse

_________________
[Vous devez être inscrit et connecté pour voir cette image]
Invité née le 0 a aujord'huis 0 ans et a posté 11 messages... je suis derrière vous

2x2x2 : 2.18 secondes / 2x2x2 une main : 21.15 secondes / 2x2x2 yeux bandés : 47.59
3x3x3 : 5.97 secondes / 3x3x3 une main : 49.86 secondes
4x4x4 : 1.49 minutes / 4x4x4 une main : 6.50 minutes
5x5x5 : 4.10 minutes / 5x5x5 une main : 18.02 minutes
6x6x6 : 8.10 minutes
7x7x7 : 16.03 minutes
9x9x9 : 58.26 minutes

3x3x1 : 0.73secondes / 3x3x2 : 30.55secondes / 3x3x3 : 5.97secondes / 3x3x4 : 1.09minutes / 3x3x5 : 1.46minutes / 3x3x6 : 2.06minutes

megaminx : 5.59 minutes / pyraminx : 7.91 secondes / square-one : 1.07

nikitouzz
Platinum 1
Platinum 1

Sexe : Masculin
Age : 21
Messages : 1834
Date d'inscription : 16/01/2011
Points Forum : 7
Points Concours : 6
Langages :
  • - TI-Basic Z80
  • - ASM TI-83+ / TI-84+
  • - Axe Parser
  • - TI-Basic 68K
  • - TI-Basic Nspire
Calculatrices :
  • - TI-73
  • - TI-76.fr
  • - TI-82 Stats.fr
  • - TI-83+
  • - TI-84+
  • - TI-92
  • - TI-Nspire
  • - TI-Nspire CX

TI-84+ SE


Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par persalteas le Dim 14 Oct - 16:37

Ben tiens. Tu es excusé, je suis magnanime.

_________________
[Vous devez être inscrit et connecté pour voir cette image]

persalteas
Platinum 2
Platinum 2

Sexe : Masculin
Age : 21
Messages : 2068
Date d'inscription : 30/06/2010
Etudes : PACES (médecine)
Points Forum : 114
Points Concours : 10
Langages :
  • - TI-Basic Z80
  • - xLib
  • - Grammer
  • - TI-Basic Nspire
Calculatrices :
  • - TI-82 Stats.fr
  • - TI-83
  • - TI-83+
  • - TI-84+ SE
  • - TI-86
  • - TI-Nspire
  • - TI-Nspire CX
  • - Casio Collège
  • - Casio Graph

TI-84 Pocket.fr


http://tiemulation.kegtux.org

Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par maxence le Dim 14 Oct - 17:49

Mes idées pour essayer de faire simple quand même, sinon ça devient vraiment trop fastidieux:

Privilégier la défense de tes pièces sur l'attaque des autres: Tu ne pourras pas attaquer longtemps si tes pièces se font "manger" trop vite.

Je sais que cette méthode peut parraitre longue, mais il faudrais que tu verrifie pour chaque pièce si elle est pottentielement attaquable ou non. Si il y en a plusieurs en danger, donner un ordre de priorité à tes pièces pour se protéger. Il faudrais alors faire une liste de toutes les cases sécurisées (y compris des cases ou il y a deja une pièce ennemie) , et voir pour la pièces choisie la ou lesquels sont accessibles.

Puis l'attaque, la il faudrais à la limite se servir d'une liste de cases ennemies attaquables (non protégées) , puis donner un autre de priorité sur les pièces ennemies, par exemple attaquer en priorité les pièces les plus fortes.

bref ce n'est pas très precis mais c'est ce que je ferrais si je voulais faire une IA d'echecs Ok

maxence
Or 4
Or 4

Sexe : Masculin
Age : 20
Messages : 574
Date d'inscription : 26/02/2012
Etudes : 1ere S SI
Points Forum : 17
Points Concours : 0
Langages :
  • - TI-Basic Z80
  • - Axe Parser
Calculatrices :
  • - TI-84+

TI-84+


Revenir en haut Aller en bas

Re: Conseils pour une IA d'échecs

Message par Contenu sponsorisé Aujourd'hui à 6:53


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum