Salut,
 
Après avoir fait un petit jeu de dominos en JS, j'ai envie de me concentrer sur un jeu plus classique : les échecs.
 
J'abandonne le JS pour le C# et une appli EXE, histoire d'avoir une plus grande rapidité de traîtement vu ce que je veux faire, et surtout, un modèle objet qui tiens la route.
 
Jusqu'à présent, j'ai modélisé :
- L'échiquier (Array de 64 lignes, avec un modulo 8 et des divisions entières je devrais être capable de me balader dedans sans problème)
- Les pièces et leurs mouvements possible (un objet "abstract" nommé pièce dont hérite chaque type de pièce qui comporte notamment en interne les mouvements possibles et quelques infos (sauter par dessus les autres pièces, mouvement possible seulement au premier tour, mouvement possible seulement une fois -roque-, etc.)
 
Maintenant que la base du programme connaît les règles de bases, je veux faire le moteur AI.
 
Deux solutions s'offraient à moi, une "AI qui apprends", et une "AI qui choisi le meilleur choix parmi X".
La première solution consisterait à enregistrer toutes les parties que le jeu a fait, et comparer le jeu en cours avec un jeu déjà joué, afin de choisir parmi les scénarios déjà vus celui qui lui donne le plus de chances de prendre l'avantage. Cette solution est chiante, car il faudrait jouer des heures et des heures contre un ordinateur complètement débile avant qu'il commence à jouer correctement. Et à coup sûr, les fin de parties seraient catastrophiques de nullité.
 
La seconde consiste à définir un nombre de "coups futurs" à simuler, et avant chaque mouvement, le PC calcule ce que donnerait au bout de X coup chaque mouvement de chaque pièce, afin de retenir le coup qui offre les meilleures perspectives. Avec X suffisament évolué, ça doit donner une AI capable de rivaliser avec Deep Blue (et des coups qui durent 2 jours je temps de tout simuler )
 
Je pense retenir la seconde solution étant donné qu'elle est à priori plus simple, et me semble offrir un meilleur niveau de jeu.
 
Par contre, à mon avis ça demande pas mal d'optimisation... Parceque pour chaque "coup", faut que je recopie énormément de choses en mémoire !
C'est à dire que si je veux juste simuler le prochain coup :
 
pour chaque piece de mon jeu
  pour chaque mouvement possible de ma piece
    je recopie l'échiquier et les pièces dans un coin
    je fais le mouvement dans cette copie
    pour chaque piece du jeu adverse
      pour chaque mouvement possible de sa piece
        je recopie l'échiquier dans un coin
        je fais le mouvement
        <éventuellement je fais mon appel récursif ici>  
        je regarde si c'est bien ou pas
      fin pour
    fin pour
  fin pour
fin pour
 
Sauf qu'on se rends bien compte que potentiellement, je peux avoir pas loin d'une centaine de tests (et copies) pour un seul niveau et 100^100, ça commence à devenir critique dès le second niveau de récursivité !
 
Y'a moyen d'améliorer ça ?
 
De plus, les 10 premiers coup d'une partie sont plus ou moins machinaux. Du moins,on n'a pas besoin de réfléchir deux heures. Là, ça va être l'inverse pour le PC : au départ, avec les 32 pièces, la PC va pleurer tout ce qu'il peut pour bouger un pion. Arrivé vers la fin de la partie, il va mettre 1 ms pour élaborer un plan avec les 100 prochains coups pour te mettre mat...
 
Du coup, je me tâte : dois-je mixer les deux méthodes : la première tant que les coups sont connus, et pour les coups inconnus qui sont arrivés à une bonne conclusion, et quand l'AI est à cours de coups connus (ou de coups qui l'ont fait gagner), passe à la seconde méthode (ainsi, le PC n'a plus à faire de longs calculs au début du jeu)

Quelques remarques:
- ton AI doit obligatoirement connaitre les ouvertures ( pas toutes ça sert a rien mais disons les principales et leurs variantes) parce que sinon les débuts de parties ressembleront a rien. Par exemple sur D2D4 si l'ordi réponds H7H5 perso j'arrête de jouer
- ton AI doit obligatoirement connaitre les finales: ça sert à rien de calculer 30 millions de possibilités quand la situation est perdante ( genre Roi+Fou contre Roi+2tour)
- le "je regarde si c'est bien ou pas" je sais pas si tu as réfléchi mais c'est pour moi le point le plus difficile. L'évaluation d'une position c'est ultra-subjectif ( à mon sens) alors à code

pour moi ça va être bateau le "je regarde si c'est bien ou pas" :
 
je pense affecter des points à mes pièces :
 
pion = 1 point
...
roi = 1000 points (comme ça si j'ai moins de mille, je sais que je me suis pris un échec et qu'il ne faut pas jouer à ça)
 
et en gros, à chaque évaluation, en fonction des pions pris/perdu, j'ai une balance, et je compte prendre celui qui, après cumul des coups prochain, a la balance la plus élevée.
 
je suis d'accord que sur 3 ou 4 coups d'avance, c'est pas forcément génial, mais disons que ça évite au PC de jouer de façon totalement débile. au moins contre un débutant ça fait illusion

http://forum.hardware.fr/hardwaref [...] 1762-1.htm

pour les finales, en effet, faudra que je me pense sur le sujet. mais à la base, il suffit que je joueur propose un match null, et le PC peut accepter si dans les "n" tours prochain il ne trouve pas une moyen de mettre mat le joueur. ça permet de pas trop me faire chier à énumérer les cas nuls.
 
sinon, pour les ouvertures, la solution de l'apprentissage devrait d'elle-même permettre au PC de pas jouer comme un blaireau, à moins que tout le monde fasse comme toi et capitule quand le PC fait n'importe quoi en effet, au départ, le PC risque de se prendre pas mal de raclées, le temps d'apprendre un peu. et lui, il va tenter bêtement de reproduire le jeu de son adversaire lors de ses branlées les plus cuisantes, et donc, avec ce système, il devrait développer un style de jeu proche du joueur.

j'avais pas lu ce lien
 
par contre, moi j'ai pas fait d'études d'ingé, et les algo "min-max" "truc muche machin chose", ça me par le pas du tout. moi je ne sais exprimer un algo qu'avec des mots en français, du coup je panne rien au topic m'enfin je vais quand même le lire ce soir

le site mentionné t'aidera alors  
http://jeudechecs.ifrance.com/echecs.htm
http://jeudechecs.ifrance.com/login.htm

pas d'accord. Il n'y a pas que les pièces à prendre en compte mais aussi leur position sur l'echiquier leur champ d'action tout ça.
Et puis je peux très bien sacrifier 3 pièces pour mater au 4eme coup...

d'où le besoin que j'ai pour optimiser la profondeur de recherche du prochain coup dans un temps moindre.
 
si je peux calculer les 10 prochains coups, alors je peux dire de façon relativement sûr que le coup qui apporte le meilleur score va mettre mon jeu dans un état le plus intéressant. Evidement, pour avoir un jeu infaillible il faudrait pouvoir prévoir les 100 prochains coups, mais là faut pas trop y compter

10 coups ça me paraît énorme. Pour 100 n'y pense même pas, c'est beaucoup plus que la durée moyenne d'une partie et si on arrivait à une telle profondeur, on aurait sans doute résolu le jeu, c'est à dire avoir une séquence de coups infaillible avec les blancs (voire avec les noirs pour faire nul).
 
Le plus difficile c'est d'avoir une fonction d'évaluation d'une position qui soit de bonne qualité, après pour la recherche tu utilises l'alpha-beta (il y a plein de variantes qui optimisent mais pour commencer je pense que c'est déjà suffisant si t'es pas 2200 elo ).

moi, je suis même pas 10 elo, je connais que les règles (et encore, pas bien )

Sinon tant qu'a être dans l'IA pourquoi ne pas essayer de mettre en oeuvre soit un réseau neuronal ce qui répond tout a fait a ta première solution soit un algo génétique pourra peut etre aller plus vite que d'explorer sequentiellement toutes les possibilités. Ca te donnera peut etre pas LA meilleur solution a tout les coups mais une très bonne solution dans des délais nettement inférieur (si ton algo est bien foutu )

La plupart de ces algos ont déjà été essayés, et la seule manière qui donne des résultats, c'est l'élagage de l'arbre de recherche par alpha-beta.
Les meilleurs programmes pour PC calculent plusieurs centaines de milliers de coups par seconde, et atteignent la dizaine de coups de profondeur en milieu de partie en moins d'une minute. Les ordinateurs dédiés comme Deep Blue, quand à eux, évaluent plus d'une dizaine de millions de coups/sec et les algos peuvent atteindre jusqu'à 30 coup de profondeur. Il faut ça pour battre un grand maître international.

C'était mon projet de fin d'étude pour le DUT
 
En vrac :
 - AlphaBeta : très compréhensible même pour un bac +2 fait une recherche sur MinMax d'abords pour comprendre le principe puis enchaîne sur AlphaBeta (c'est une optimisation de MinMax).
 - Pour économiser de la mémoire : conserve unqiuement une liste de piece avec leurs positions
 - Pour la fonction d'évaluation : Le principe des points sur chaque pièce est limité par le fait qu'un sacrifice de la reine peut faire gagner la partie ou te mettre dans une position trèx confortable mais comme elle te fait perdre beaucoup de points ton prog ne le verra pas.
 - A chaque fois que tu évalues une position conserve sa note quelque part, ça t'évitera de refaire 2 fois le même boulot.

archangel > tu viens de me donner une super idée...
 
a la base, pour chaque coup, je pensais tenter de calculer les X prochains coup, et en retenir un au pif parmi les meilleurs.
 
sauf que mise à par vers la fin quand il n'y a plus beaucoup de pieces, c'est un réel cauchemare pour le CPU et la mémoire, car je reteste des coups que j'ai déjà fait en permanance...
 
du coup... l'idée géniale serait de décider de calculer mettons les 2 prochains coups, et je stocke l'intégralité des coups testés en mémoire.
après, en fonction du coup réellement effectué, il suffit de ne récupérer que la partie du coup qui a été effectivement jouée. ainsi, je peux recalculer les é prochains coups du prochain coup, ce qui donne 3 coups d'avance calculés.
 
bon, ça marche moyen étant donné que plus l'arbre se ramifie, et plus le calcul des coups suivants des bouts de branche sera long... m'enfin ça doit gagner quand même pas mal de temps.
 
a ça on ajoute un critère bête et stupide genre je ne refais les calculs que des 50% qui m'ont offert le moins bon score (ben oui, les coups d'avance qui me donnent un bon score, ça sert pas à grand chose de les recalculer, à priori c'est eux qui donnent le meilleur résultat...)
 
seul hic, c'est que si le jeu détecte qu'en 2 coups il te met matte, mais qu'en 12 coups il te prend un pion et te met matte, il va préférer prendre le pion avant, puisque le score final est meilleur

T'ain c'est chiant de recopier des objets en C#
 
Y'a moins pire que la solution que j'ai adopté ?
 

 
Je vous raconte pas ce que ça donné avec les objets hérités
 
Un exemple de mon code actuel... V'là le bordel