Bonjour
 
J'ai donc écrit un programme dons vous trouverais l'histoire dans ce sujet.
 
Les stats des parties automatiques.  
 
Level Black   Level White        Points Black    Point White    Timing   Shotcount      Gain
 
        0                   0                   2300               400           00:00:06       27             White Mat
 
 
        0                    1                   2600              3400          00:10:00      37             Black Mat
 
 
        1                    0                   1800                3700         ~00:00:10    27              whitte Mat
 
 
        1                     1                                                            00:49        29               black Mat
 
 
 
 
 
Vous trouverez les source de ce programme en cliquant ici
 
Mon problème est résolu
Merci au participant, et HFR.
 
 
Quote original.
 
 

C'est plutôt des algos à base de A* min/max en général qu'on implémente pour les échecs, non?

Peut-être mais je vais pas savoir faire du tout.

Ben pourtant, cet algo est basé sur un arbre (donc pas très dur) avec des évaluations de branches par score et "trancher" celles qui auront un mauvais score (= ensemble de coups qui conduiront à une mauvaise situation voire la défaite).
ca me paraît plus simple dans l'implémentation qu'un réseau de neurones (qui, en plus, risque de conduire à des résultats pas top)
2 bons algos :
http://fr.wikipedia.org/wiki/Algorithme_A*
http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta

C'est pas vraiment au niveau des algo que ça coince, c'est sur l'organisation du projet dans sa globalité.
Je suis déjà passé par developpez et j'avais un problème pour initialiser un truc.
De plus de cette initialisation dépend quasiment le reste qui reste la solution optimale et non pas un jeu.
Je pense que si je vais chercher les partie, j'ai pas trouvé encore, dans une bonne base de donnée ça peut donner un truc bien en RdN.
Mais peut-être je me trompe.
Dans ce cas je n'aurais fait qu'une évaluation de la structure de mon réseau.
Parce qu'il existe bien un fonction abstraite jouer aux échecs. Suffit d'apprendre la règle.

Ben les échecs, c'est pas qu'apprendre des règles. C'est aussi apprendre des stratégies, détecter des réseaux de mat. Les grands joueurs ont aussi en tête tout un tas de parties déjà jouées qui leur permettent de détecter une situation similaire et donc de jouer tel coup parce qu'ils savent que dans une autre partie, ça avait conduit à la victoire du joueur (ou pas, du reste, et donc qu'il faut pas jouer ce coup mais un autre).
 
Tous les softs de jeux d'échecs que je connais avaient une BD de parties déjà jouées et utilisait l'algo A* ou alpha-beta pour rechercher dans la BD le meilleur coup. Le niveau de jeu était en fonction du temps qu'on laissait à l'ordi pour jouer son coup : facile, qq secondes, très difficile, plusieurs minutes. Ca permettait donc à l'ordi d'évaluer son arbre plus ou moins profondément et donc de prendre une décision plus ou moins fiable.
 
Peut-être qu'une approche par apprentissage par renforcement( Qlearning) pour conduire à de bons résultats puisqu'on sait que débuter une partie d'échecs en jouant tel coup est bon ou pas (genre, avancer le pion à gauche du roi, découvrant sa diagonale en tout début de partie, c'est pas bon du tout, ou la stratégie du coup du berger qu'il faut savoir contrer pour pas être échec et mat en 3-4 coups)...

 
Ben position de départ, position d'arrivée, et valeur de la pièce.  
 
Mais ça risque de te donner des résultats très fun.  
 
Les réseaux de neurones c'est quelque chose d'assez obscur. Ça marche à peu près pour des petites images de lettres par exemple, mais même pour ça c'est pas le top, les SVM sont plus efficaces il me semble.  
 
J'ai fait un réseau de neurones qui reconnaissait des chiffres en projet d'école d'ingé. Rien que pour ça c'est galère au niveau des paramètres et de l'apprentissage, si tu veux quelques couches avec rétro propagation on faisait tourner ça des nuits entières.  
 
Mon intuition me fait dire que tu vas obtenir quelque chose de ridicule pour un truc aussi compliqué que le jeu d'échecs. Rien que pour apprendre les règles de déplacement il faudrait un réseau énorme je pense.
 
T'as pas idée du temps d'apprentissage, je me souviens d'un chercheur qui avait fait un réseau à 10 couches (ce qui est déja énorme) pour reconnaître des chiffres sur des images genre 25*25 et il faisait tourner ça sur des GPU.

Je te rejoins sur ce que tu dis : les réseaux de neurones pour le jeu d'échecs, ça va conduire... à l'échec (oui, elle était facile ). Phase d'apprentissage trop longue.
 
Pour tout ce qui met en jeu du calculatoire (ie du combinatoire), vaut mieux des algos "classiques" que des réseaux de neurones. Parce que finalement, gagner aux échecs, c'est ni plus ni moins que d'être capable de calculer à chaque fois tous les coups possibles et voir le meilleur. A l'heure actuel, le seul pb est que ce temps de calcul est trop long et qu'on a donc recourt à des algos type A* ou alpha-béta...

 
 
Ca me dit pas si la partie est terminé ça ?    
 
Si non, je note votre insistance pour me faire abandonner mon projet mais je vais un poil persévérer.
J'ai toute fois deux problème, l'alimentation en donnée d'apprentissage, par défaut de base de donnée.
Je me souviens pas du second problème, mis à part l'implémentation de fin_de_partie()..

 
Tu peux détecter le mat ou le pat relativement facilement. Après si t'as envie que ton réseau de neurones le détecte tu rajoutes deux bits en sortie.
 
Les bases de données t'en as plein partout. Commerciales où non mais c'est pas ça qui manque.  
http://www.chessbase.com/newsdetail.asp?newsid=8711  
5 millions de parties ça te suffit ?  

 
Merci, je vais le detecter mais plus ou moins facilement ... Merci.
 
En fait je cherche un base au format text gratuite et surtout en notation algébrique complète.

A* c'est plutôt du pathfinding. Pour les échecs, c'est plus du Minimax, avec élagage Alpha/Beta

Comme l'a dit Rufo si tu tiens absolument à faire de l'apprentissage il vaut mieux faire de l'apprentissage par renforcement.
Les méthodes à la mode et qui se révèlent efficaces pour pas mal de jeux sont les méthodes MCTS (Monte-Carlo Tree Search) et en particulier UCT (Upper Confidence Tree).
 
Ca a l'avantage d'être très facile et rapide à coder.

Merci pour les idées.
 

 
 
Ca donne quoi comme "type de solution" ?

http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta
 
-> un arbre qui représente les coups à jouer avec pour chacun, un "score".

Merci rufo,
 
 
Pour le moment je réfléchis encore à la finalité de ma réflexion.
 
Et je voulais vous demander votre avis sur une idée.
 
Admettons que je choisisse la meilleurs solution pour résoudre les meilleurs parties.
Que ce passe t-il maintenant si j'affronte un tel joueur avec un jeu aléatoire ?

Pour gagner aux échecs, c'est pas avec des coups aléatoires C'est avec une stratégie. Et savoir évaluer si une stratégie est bonne ou mauvaise, c'est être capable de vérifier si l'ensemble des coups qui la composent conduisent à la victoire ou pas. Ca revient donc à parcourir un arbre composé de coups à jouer. On en revient donc aux algos minimax / alpha/beta. Les BD de coups ne sont là que pour faire gagner du temps de calcul (identification de la partie en cours à une situation rencontrée dans une partie en BD et voir quel était le coup que le joueur avait joué et s'il avait gagné).
Mais si t'avais un super ordi, calculer tous les coups possibles et voir ceux qui conduisent à la victoire suffirait. C'est un peut comme le brut force pour trouver un mdp. En général, on n'y va pas au pif, on utilise des dicos pour accélérer le calcul.

Merci rufo, merci beaucoup.  
 
 
Je donne une idée de ce à quoi je pense.
 
Si j'affronte deux joueurs de type "optimale" en fait je tire probablement l'ensemble des meilleurs partie nulle voir un anti jeu.
Une touche d'aléatoire donnerais un certain exotisme au jeu .
 
Et finalement, le réseau de neurone n'est t-il pas un compromis entre un jeux optimal et un jeu aléatoire.
D'ailleurs est-il possible de les combiner ?
 
Voilà.

Je suis pas spécialiste des réseaux de neurones, mais pour moi, leur domaine d'application de prédilection était tout ce qui n'était pas calculable "pile-poil", en gros là où y'a une part d'indéterminisme, un peu de logique flou. C'est bien pour ça que les réseaux de neurones sont adaptés pour tout ce qui touche à la représentation (reconnaissance de forme dans une image où y'a toujours du "bruit" ). A de l'apprentissage aussi quand on est dans un monde où y'a énormément de règles et d’interactions possibles. Les possibilités sont tellement élevées qu'il n'est pas possible d'utiliser un algo à base d'arbre. Par ailleurs, toutes les situations ne se résument pas à des prises de décision basées sur un score bon au mauvais.  
 
Or les échecs, c'est tout le contraire, c'est très déterministe et les règles sont limitées. Mais les humains ne jouent pas forcément le meilleur coup car ils sont limités dans leur puissance de calcul et de prévision à 10, 15, 20 coups d'avance.

Oui, mais la je parle d'affronter la machine contre elle même. Nombre de joueur 0.

 
Tu peux construire une bonne stratégie à partir de coups aléatoires  

Je suis en train de voir que la vitesse de la lumière est relative.
J'ai ré- écris plus de 2k lignes pour implémenter Astart.
 
Ca donne quoi en théorie Astar au echecs ?
 
J'arrive pas à me faire à l'idée. Normalement j'ai un chemin optimal, mais en application, avec moi on sait jamais.
 
 
1000 en fait, et pas des plus symboliques.

Comme Harkonnen et moi après l'avions dit, le mieux pour les échecs, c'est quand même un min-max avec un alpha-beta. Le A* est plus général.

Ok, merci rufo.
 
Pour le moment je m'amuse avec Astar, je pense que les problème sont du même ordre.
Déplacer les piece mesurer les perte et les gain, valider un patrie terminale.
Après c'est que de l'algo. Mais bin, j'ai pas vue bien minimax, et l'élagage Alpha-beta me donne le tournis.

Pourtant, c'est eux les plus efficaces pour le échecs à ma connaissance

Oui ce sont des alpha beta avec des améliorations classiques.
 
Jovalise, prends le temps de bien regarder, implémenter un min-max est vraiment super simple.

Voici les sources Ada de mon implémentation d'un jeu d'échces avec solution algorithmique Astar ; http://80.15.188.151/dev/WChess-0.0.2.tar.gz  
 
C'est pas au poins encore.

Bonjour,
J'utilise Astar donc pour le moment, j'aurais une question relative, est-ce qu'une heuristique récursive vous parait être une bonne approche ?
Je compte calculer la distance entre le jeu courant et le jeu final en rappelant récursivement l'heuristique pour tous les successeurs du jeu courant.
Bon, pas mal, trop vague, mauvaise idée ?
Merci.

Vous auriez vraiment pas des idées pour les heuristiques, parce que vraiment, je me casse les dents.
J'ai bien des idée mais j'aimerais qu'elle soit conforté.
En fait je suis simplement sur une piste, je pense à peser les cases de l'échiquier en pondérant les cases vide et pleine mais je ne sais pas comment, et je n'ai aucune valeur. Je sais jouer au échecs, mais j'ai du mal à définir la règle qui dis que si je suis en échec je dois m'en sortir si je peux. Enfin c'est pas simple.
 
J'ai un autre problème aussi, si je me souvient bien, c'est ma stratégie Astar qui normalement prend un point initial et un point terminal et calcule le chemin.
Alors que là j'ai pas le point terminal.
Je peut néanmoins en donner un sans perdre l'intérêt de mon jeu.
 
S'il vous plaît !
Merci !
 
 
Ah oui, j'ai une autre question plus technique, j'ai voulu lencer une procédure récursive qui compte les mouvement possible sur une partie, la bécane mouline un moment et j'obtien un storage error Ada, plus un message Stack overflow.    
Bref, est-ce qu'il est possible qu'une solution avec Astar soit pas calculable sur un PC avec 1Go de ram et 1Go de swap ?
Merci pour vos réponses.

Déjà ça, enfin, ceci : ça passe pas.
 

Hcost : Float := 0.0;
   begin
 
      declare
         The_White_Successors : Successors_Type := white_Successors(Move);
      begin
 
         if The_White_Successors.Successor /= 0 then
            for I in 1..The_White_Successors.Successor loop
               declare
                  Successors : Successors_Type := black_Successors(The_White_Successors.Plan(I));
               begin
 
                  if Successors.Successor /= 0 then
                     for J in 1..Successors.Successor loop
                        declare
                           White_Echiquier : Echiquier_Type := Successors.Plan(J);
                           The_Successors : access Successors_Type;
                        begin
 
                           for Line in Line_Type loop
                              for Colum in Colum_Type loop
 
                                 if Echiquier.Board(Line, Colum) in BK..BP then
                                    case Echiquier.Board(Line, Colum) is
                                       when BP =>
                                          The_Successors := new Successors_Type;
                                          Pion(Echiquier, Line, Colum, The_Successors.all);
                                          Hcost := Hcost + Float(The_Successors.Successor);
                                       when BK =>
                                          The_Successors := new Successors_Type;
                                          King(Echiquier, Line, Colum, The_Successors.all);
                                          if The_Successors.Successor = 0 then
                                             return 0.0;
                                          else
                                             Hcost := Hcost + Float(The_Successors.Successor);
                                          end if;
                                       when BQ =>
                                          The_Successors := new Successors_Type;
                                          Queen(Echiquier, Line, Colum, The_Successors.all);
                                          Hcost := Hcost + Float(The_Successors.Successor);
                                       when BC =>
                                          The_Successors := new Successors_Type;
                                          Chavalier(Echiquier, Line, Colum, The_Successors.all);
                                          Hcost := Hcost + Float(The_Successors.Successor);
                                       when BV =>
                                          The_Successors := new Successors_Type;
                                          valey(Echiquier, Line, Colum, The_Successors.all);
                                          Hcost := Hcost + Float(The_Successors.Successor);
                                       when BT =>
                                          The_Successors := new Successors_Type;
                                          Tower(Echiquier, Line, Colum, The_Successors.all);
                                          Hcost := Hcost + Float(The_Successors.Successor);
                                       when others =>
                                          null;
                                    end case;
                                 end if;
                              end loop;
                           end loop;
                        end;
                     end loop;
                  end if;
               end;
            end loop;
         end if;
      end;

 
Le processus s'arrête tout seul avant même le premier coup.

Mais qu'est ce que tu fous avec un A* bondieu ? C'est pas du tout adapté à un jeu d'échecs ! Le A* est utilisé principalement pour du pathfinding. Pour les jeux à somme nulle comme les échecs, c'est du minmax, alpha-béta...

Ok, je laisse tomber Astar et j'attaque Minimax.
Des conseils pour la représentation ? Et l'évaluation ?

Fais pas du récursif C'est lent et ça pompe trop de mémoire...

Quelqu'un peut m'expliquer ici en quoi ça consiste en premier s'il vous plaît comment construire l'arbre de jeu ?
Si c'est encore possible ?

Ou me dire quel type d'arbre je dois implémenter ?

Tu dois créer un arbre de solutions.
Jusqu'à une certaine profondeur tu développes tous les noeuds (=décision/coup/position) tout simplement.
Le but est de trouver la meilleure décision parmi l'arbre des solutions avec l'algo de ton choix (minmax, alphabeta, uct, pns, dps ... tout ce que tu veux il y en a des dizaines) la meilleure solution selon tes critères.  
 
C'est vraiment très simple, je suppose que pour minmax la page wikipedia est bien faite.

D'abord merci à tous.
 
J'aurais à la limite voulu savoir comment je dois implémenter une règle telle que l'échec (la fuite, la protection, la lute) ?
Savoir si je doit le calculer dans mes successeur ou si ça se fait après ? Par quelle magie.
Ma question est la même pour le jeu globalement.
 
Après j'insiste sur un argument auquel personne n'a répondu.
Si j'affronte deux machine avec le même algorithme qu'obtiens-je comme résultat avec vos algorithme ?
 
Merci encore pour vos réponses, s'il vous plaît !

J'ai pas compris pourquoi comment le roi vaudrait un beau 0.0 ?
J'ai lu ça dans un doc. Aussi.

Ben parce que le roi peut pas attaquer j'imagine. Et s'il se fait prendre, c'est que t'es mat...
 
Edit : pour ta question d'une partie entre 2 machines, je vois 2 solutions : les blancs commençant, ils ont l'avantage de l'attaque. Si l'algo est "parfait", les blancs ne perdront jamais l'attaque donc les noirs vont perdre où être pat. Si l'algo n'est pas parfait, les noirs peuvent reprendre l'attaque et donc potentiellement gagner ou faire pat. Et toujours si l'algo n'est pas parfait, celui qui a l'attaque peu à tout moment la perdre ou la reprendre.
 
Faut pas perdre de vue un truc très important aux échecs : c'est pas possible de jouer en "symétrique" et se neutraliser puisque tous les pions sont pas en face l'un de l'autre (cavaliers et fous sur des cases différentes de ceux de l'adversaire). Donc la machine 2 ne pourra pas jouer le même coup que la machine 1. Les arbres de décisions des 2 machines seront donc nécessairement différents, à commencer par le fait que la situation elle-même est différente : les blancs comment donc attaquent et vont essayer de conserver l'attaque alors que les noirs vont défendre et essayer de la récupérer...

Un roi ne peut pas se faire prendre.
 
Si non comment il le pourrait si ne vaut pas de point.
 
Comment compte t'on ?