Version imprimable
Salut,
J'essaie de faire un morpion.
C'est facile tant que le PC ne doit pas jouer.
Comment le faire jouer au bon endroit sans faire 100 lignes de codes, figées, mais en le faisant réfléchir (par rapport aux autres cases).
J'ai déjà fait un truc, mais il est impossible à battre (toutes les combinaisons possibles sont analysées...
Je suis pas un connaisseur, j'ai juste lus un truc dessus(je faisait des recherches sur l'algo MIN-MAX).
Quand tu dis que toutes les combinaisons possibles sont analysées, tu fais un arbre je supose?
si c'est le cas, il te suffit de ne pas parcourir l'arbre en entier mais 3, 4(estimation minimaliste, ça peut être 100 ou 1000)niveau de ton arbre et plus tu reduit le nombre, plus le PC est facile a battre.
Je laisse le soin au connaisseur de me corriger. :wink:
-Magic-
En fait j'ai jamais fait d'algorythmes, donc, je programme à vue et je ne connais aucun terme.
EN GROS, JE FAIS CA:
Un tableau avec des valeurs selon le joueur (1 pour le joueur 1 et 100 pour le joueur 2), je fais la somme de ces valeurs.
1. Je regarde si je peux gagner (2 de mes cases alignées), je gagne.
2. Ensuite, je verifie si il y a une somme qui correspond à deux cases de même couleur alignées (pour l'autre joueur) , je prends la case qui reste, j'empèche de gagner.
3. Enfin, je joue la première case libre si je n'ai pas encore joué.
Je sais que c'est pas bien, mais j'ai pas eu de formation dans ce domaine, je suis automaticien, et pas informaticien :lol:
Par contre j'ai trouvé un exemple sur le site indiqué dans l'annonce [Cours et tutoriels] de Delphi-fan
Moi aussi :wink: mais je dérive dans l'info depuis séptembre.Citation:
Envoyé par Jérôme PRAT
Autrement là :arrow: http://recursivite.free.fr/chap_IX_1.htm tu a un exemple(avec explication) de jeu du morpion, j'ai pas pas tous lu, mais peut-être que ça pourrra t'aider.
-Magic-
En fait, c'est de celui là que je voulais parler, je suis en trais de télécharger le cours...
J'ai migré vers l'informatique depuis le mois de novembre, mais là, c'est pour moi...
L'exemple du cours utilise la récursivité, autrement dit si elle n'est pas affinée une méthode du genre "force brute" pour analyser toutes les solutions.
Cela est acceptable pour des jeux assez simples où il ne doit pas y avoir de phénomène dit "d'explosion combinatoire" : dans un jeu comme les échecs notamment, on ne peut faire étudier au PC toutes les solutions possibles que ce soit par des méthodes itératives ou récursives (car des milliers d'années de calcul seraient nécessaires !) .
Donc, il ne faut pas hésiter à rechercher -même dans les domaines qui se prêtent à la récursivité- des heuristiques (= méthodes permettant d'éliminer l'étude de certaines positions) .
:arrow: Dans l'exemple du morpion, (mais on peut l'appliquer aussi au jeu Othello par exemple ... ) , une simplification évidente consiste à rechercher d'éventuelles symétries (axiales ou centrales). Dès lors, si une position est le reflet par symétrie d'une position déjà envisagée, il est inutile d'explorer cette branche, et donc le temps de calcul s'en trouve optimisé .......
A+
Pour couper les branches inutiles dans un arbre des possibilités, j'avais utilisé l'algo SSS* pour un jeu d'échec en LISP.
Je ne me souviens plus de cet algo, mais il tient en 15 ligne et n'est pas récursif....
Bonjour a tous,
J'avais fait un morpion dit intelligent en turbo pascal, il utilisait la méthode qu'a décrit Jérôme PRAT, il marchait bien mais j’avais quand même trouvé le moyen pour qu’il perde. En effet, l’inconvénient, c’est que une fois qu’il a perdu, il en déduit rien sur sa façon de jouer. Donc si tu trouves le moyen de le piéger une fois, tu pourras toujours refaire cette méthode et tu gagneras a coup sur.
Une autre idée que j’avais eue était de générer un historique des parties perdues. Donc quand l’ordinateur joue, voici la méthode qu’il doit alors appliquer
1. Il regarde si il peut gagner.
2. Il regarde si il n’a pas déjà joué une partie similaire qu’il aurait perdue. (Prendre en compte toutes les rotations possible et symétrie) Si il est a l’avant dernier coup sur son ancienne partie, alors il ne rejoue pas se qu’il a déjà joué.
3. Ensuite, il regarde si il peu empêcher l’autre de gagner
4. Puis il joue à la première case restante.
Voili voila, je ne sais pas si ça fait avancer le chmilblique mais bon…
A bientôt
Ok je sais je suis en peu en retard sur le sujet, mais si ca t'intéresse j'ai fait un programme qui joue au démineur tout seul (pou faire 40 secondes en expert c'est pratique).
C'est en delphi et les sources sont pas encore tt a fait au point et pas très claires, mais je peu te les envoyer si tu veux...
A+