Jeu d'échecs pour VG5000

[joaopa]

Bonjour,

voici une petite capture d'écran pour mon jeu d'échecs pour VG5000 . Les pièces sont dessinées. Le moteur du jeu est terminé. Il reste à coupler le moteur avec l'échiquier (facile). Pour l'instant, les parties sont répétitives. Je prévois une petite bibliothèque d'ouverture pour varier les parties. Il y a 6 niveaux de jeu. Les 4 premiers sont trop faciles à mon goût. Le 5 et surtout le 6 sont corrects. Le temps de réflexion pour le 6 est d'environ 2 minutes, ce qui est correct pour le jeu.

Il y a aussi un niveau d'analyse de situation.

J'espère le terminer ce mois-ci.

[fneck]

Ca ne doit pas être facile de programmer un moteur pour jeu d'échec.
Tu l'as fait en Basic?

[Markerror]

Super, ça manquait vraiment sur notre machine ! Je suppose que tu ne t'es pas amusé à faire ça en Basic .

Tu utilises 16kb ou plus pour le jeu ? Tu es parti d'un moteur maison ?

[6502man]

Un moteur de jeux d’échecs sa doit être sympa à programmer

Est ce que l'on peut en savoir un peu plus sur l'algo général

[Carl]

Bravo joaopa....
J'ai hâte de tester cette nouveauté
Carl

[joaopa]

Pour le moteur, je n'ai pas réinventé la roue. Je me suis inspiré du remarquable programme http://home.hccnet.nl/h.g.muller/max-src2.html. Malheureusement ce programme utilise la récursivité. J'ai donc regardé le code source du célèbre Sargon pour voir comment on faisait de la récursivité en assembleur http://www.andreadrian.de/schach/sargon.asm.

Aussi bien sur Sargon et sur Micromax, l'idée vraiment astucieuse est de considérer non pas un échiquier de 8x8 mais de l'augmenter. Ca permet facilement de supprimer des déplacements invalides. Chaque case de l'échiquier contient un entier. Les bits de cet entier codent la couleur, le type de la pièce présente dans cette case, ainsi que les informations supplémentaires pour les coups particuliers tels que la prise en passant ou le roque.

La méthode pour déterminer le meilleur coup est juste un arbre mini-max, en fait nega-max. C'est l'algo classique dans ce genre de problème (dames, go, sudoku...)
Le nombre de position vérifiée dans cet arbre détermine le niveau de jeu.

Evidemment, je programme en assembleur. Sinon, ce serait infiniment trop lent. Tester le jeu en basic sur Alice pour voir ce que cela donne en basic (présent sur le site de Daniel)

Mon but est de faire tenir le tout sans ram supplémentaire (mes conditions de travail en 1985 ). Pour sauver de la mémoire, j'utilise l'idée de Markerror qui est de définir les caractères graphiques dans un loader. Ceci me fait gagner plus d'un kilo de ram

[Markerror]

Bonjour Joaopa,

Merci pour ces explications très intéressantes. Ca serait pour moi une bonne idée de faire aussi une version 32kb, je suppose que cela te permettrait d'avoir une bibliothèque d'ouvertures plus conséquentes et aussi éventuellement d'augmenter la profondeur de ton arbre de recherche (mais bon, là, ça risquerait de tomber dans les travers des jeux d'échecs sur les sasfépus, à savoir le temps de réponse se comptant en dizaines de minutes ).

[Daniel]

La méthode pour déterminer le meilleur coup est juste un arbre mini-max, en fait nega-max. C'est l'algo classique dans ce genre de problème (dames, go, sudoku...)

Oui pour échecs, dames, sudoku. Mais pour le go le nombre de combinaisons est trop élevé pour cette technique. Les meilleurs programmes de go actuels utilisent des algorithmes de type Monte-Carlo. En particulier l'un des meilleurs, Crazy Stone (6-dan), qui a récemment battu un joueur professionnel avec un handicap de 4 pierres.
http://remi.coulom.free.fr/CrazyStone/
http://entcog.c.ooco.jp/entcog/densei/d ... n-2nd.html

[Dominique]

Félicitations !

J'avais trouvé sur une revue brésilienne de l'époque un minimax avec élagage alpha-beta entièrement écrit en basic.
Je vais essayer de le retrouver.

[DataPro]

Félicitations !

[Totor le Butor]

Euh... question de newbee....qu'elle est le principe d'un algo mini-max et monte carlo

[Dominique]

Le minimax consiste, en gros, pour l'ordinateur qui te considère un très bon joueur, a te laisser la pire de tes meilleures
réponses.
Ex :
L'ordinateur peut jouer 1 , 2 ou 3

S'il joue 1 et que tu réponds A (ta meilleure réponse) ton tableau de jeu vaudra disons 15 Pts
S'il joue 2 et que tu réponds B (ta meilleure réponse) ton tableau de jeu vaudra disons 10 Pts
S'il joue 3 et que tu réponds C (ta meilleure réponse) ton tableau de jeu vaudra disons 20 Pts

Donc il minimisera ta maxi réponse et jouera 2

Comme l'ordi analysera chacune des réponses à tes réponses tu comprends que le nombre de coups à analyser augmente
rapidement.

C'est ça grosso modo pour minimax.
Pour Monte Carlo, je ne connais pas et j'aimerai connaitre.

[Daniel]

Monte-Carlo : https://interstices.info/jcms/c_43860/l ... onte-carlo

[Totor le Butor]

Merci Dominique pour tes explications très clairs mais si je vois bien le principe et l'explosion combinatoire qui suit je me demande sur quelles critères il compte le nombre de points pour chaque mouvement, peut-être une réponse dans le lien de Daniel.

Merci Daniel pour le lien, ça à l'air bien expliqué je me plonge dedans .

[__sam__]

Ahlala, ca me rapelle les vieux cours d'I.A. que j'ai eu il y a longtemps en école d'ingé.

En général tu associe au jeu une fonction qui évalue la qualité de la situation obtenue. Par exemple pour les échecs ca peut être une somme pondérée de la différences du nombre de reines/fous/tours/pions sur le plateau. On peut (et on doit aussi) tenir compte des positions des pièces sur le plateau pour faire en sorte que la fonction d'évaluation puisse faire la différence entre une bonne et une mauvaise configuration de jeu.

L'aspect récursif et la combinatoire résultante est obtenue lorsque le programme essaye de deviner quel sera ton meilleur coup en retour de son choix possible. En gros il inverse la situation et se ramène à la situation précédente. Moralement cela revient à énumérer toutes les combinaisons de jeux obtenues à une profondeur de N coups. Cela croit très très vite: si seulement 2 coups sont possible à chaque niveau tu as 2^N combinaisons et donc de plateau final à énumérer. A chaque fois que l'on augmente la profondeur (N) de 1 coup le temps de calcul double. Avec 10 coups de profondeur on a déjà 1024 combinaisons à évaluer. En pratique cela croit beaucoup plus vite car il y a bien plus que 2 coups possibles à chaque tour.

Quelques infos complémentaires: http://fr.wikipedia.org/wiki/Algorithme_minimax