Bonjour,
Je veux réaliser un jeu PUISSANCE 4 en C++. Pour cela je cherche un algorithme pour avoir des idées pour écrire mon propore algorithme.
Merci de m'avance
Lui
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
[IA] Algorithme jeu PUISSANCE 4
Bonjour,
Je veux réaliser un jeu PUISSANCE 4 en C++. Pour cela je cherche un algorithme pour avoir des idées pour écrire mon propore algorithme.
Merci de m'avance
Lui
Bonjour,
A quoi doit servir l'algorithme que tu recherches ? Tu veux simuler un joueur ?
Bonjour,
Les idées sont sur cette page !
__________________
- Premièrement, il faudra réfléchir;
- Deuxièment, chercher;
- Finalement, poser son problème en le décrivant correctement.
Oui, sur cette page, je trouve quelques idées. mais la je cherche la façon de réaliser l'algorithme quand on remplace les joueurs par la machine.Envoyé par paronyme
Merci
Bonjour,
ce que tu souhaites c'est donc de créer une IA (Intelligence Artificielle).
Tu peux regarder cette discussion qui te donne certaines pistes.
Dans le cas du puissance 4 une recherche exhaustive apporte de très bon résultats.
Merci
Deja je viens d'aprendre quelques chose : IA https://intelligence-artificielle.developpez.com
Je vais faire un tour sur ce lien, j'espère que j'aurai ce que je cherche
Lui
La technique la plus commune dans une situation telle que celle du Puissance 4 est la suivante :
imaginons-nous au milieu de la partie, tu as les pions du joueur à telles et telles cases, ceux de l'ordi à telles et telles cases. La technique consiste à lister, à partir de cette situation, toutes les situations qu'entraineraient de jouer tel ou tel coup, et ainsi de suite. Tu obtiendras donc un arbre de "situations" de ton jeu.
Cette technique est très exposée sur internet. Tu trouveras facilement des docouments.
Tu peux regarder ce que fearyourself a fait pour son morpion, c'est le même principe : http://fearyourself.developpez.com/t...l/sdl/morpion/
Et pour un puissance 4 n*m (hauteur*largeur très grand)?
Dans ce cas, soit tu disposes d'une machine très puissante auquel cas tu peux te permettre d'explorer la plupart des coups possibles, voir tous, soit tu as une machine "normale", et tu dois "trier".
Ca consiste à s'arrêter à une certaine profondeur -> tu construis l'arbre mais ne va pas au bout de chaque "branche". Par exemple, on peut s'arrêter dès que l'on voit que la situation n'est pas bénéfique du tout. On peut aussi construire toutes les branches jusqu'à une certaine profondeur P. Il s'agit donc de "simuler" tous les P coups suivants possibles. Ensuite, on choisit "le" meilleur (qui n'est pas toujours unique).
Dans la plupart des jeux de ce genre, quand tu augmentes le niveau de difficulté de l'ordinateur (adversaire), cela augmente souvent son temps de réflexion. S'il applique un algo comme celui décrit plus haut, cela revient "simplement" à augmenter la profondeur. Il est normal que s'il "voit plus loin dans le jeu", il saura mieux prévoir et ainsi jouer un coup bien meilleur pour lui, car il sera meilleur sur le long terme (grâce à la profondeur) et non pas sur le court terme (dans le puissance 4, cela lui ferait par exemple aligner 3 pions, mais l'entrainerait 2 ou 3 coups plus loin à la défaite car il n'avait pas exploré assez en profondeur les situations qu'entraineraient son coup).
Bonjour,
Il faut bien regarder la façon dont tu joues au puissance 4 :
- tu mets les pions par le haut dans une colonne !!!
- donc il n'y a que "largeur" possibilité à chaque étape
Alp te décrit ce que j'appelle la recherche exhaustive qui se représente sous forme d'arbres.
Et on appelle comment la méthode qui s'arrête à une profondeur donnée ? Elle n'est plus exhaustive
Les algos classiques pour l'exploration partielle d'un arbre sont le Min-Max et ses raffinements comme l'Alpha-Beta. Leur efficacité dépend beaucoup de la qualité de la fonction d'évaluation utilisée (la fonction qui affecte un score à une position donnée).
--
Jedaï
Le problème n'est plus le même, dans un cas déterminer le meilleur coup est simple, car on joue celui qui fait gagner la partie en explorant toutes les possibilités. Fonction d'évaluation : Je gagne/je perds
Dans le deuxième comment détermine t on qu'un coup est meilleur que l'autre? Il faut à chaque instant pouvoir dire qui est le plus avantagé.
Avez vous une bonne fonction d'évaluation pour le P4?
HA... Tu penses qu'il y a autant de coup possible sur un plateau de 4*1 que 4*4 (L*H) par exemple, et donc que la complexité du problème n'est que fonction de la largeur?Il faut bien regarder la façon dont tu joues au puissance 4 :
- tu mets les pions par le haut dans une colonne !!!
- donc il n'y a que "largeur" possibilité à chaque étape
Bonjour,
alors :
- 1 - Pour la fonction de recherche du meilleur coup, tu ne regardes pas qu'un seul coup à l'avance, sinon elle ne va pas t'apporter beaucoup d'information. Quand tu joues, tu essaies de calculer plusieurs coups à l'avances, afin de créer une tactique pour gagner. Il faut donc parcourir l'arbre de recherche sur une profondeur N, donc N coups à l'avance.
- 2 - Pour le nombre de coups possible par tour : tu ne peux mettre un pion qu'en le glissant par le haut du plateau dans une colonne. Donc tu as "Largeur" colonnes possible pour glisser un pion. Tu n'as pas plus de choix possibles à chaque tour.
Oui, mais peu importe la profondeur, il faut être capable de Déterminer à un momment qui à l'avantage dans telle ou telle position, sinon comment savoir quelle coup jouer???
Tu peux essayer de voir 500 coups à l'avance si tu es incapable de choisir les bons, ça ne sert à rien.
Donc comment fait on pour choisir les bons coup au P4? La tactique on la construit à partir de quoi?
Oui, et? je n'ai jamais nié cela, mais si tu veux dire par là qu'il ne faut prendre en compte que la largeur pour calculer la taille de l'arbre: non.- 2 - Pour le nombre de coups possible par tour : tu ne peux mettre un pion qu'en le glissant par le haut du plateau dans une colonne. Donc tu as "Largeur" colonnes possible pour glisser un pion. Tu n'as pas plus de choix possibles à chaque tour.
Bonsoir,
La hauteur de ton arbre est le nombre de coups que tu vas calculer à l'avance.
Le nombre de fils pour chaque noeuds de l'arbre est le nombre de possibilité à chaque étape du jeu, soit la largeur.
Bonjour,
Là ce que tu souhaites typiquement c'est une fonction d'évaluation du jeu, comme les probabilités de gagner au poker.
Donc j'aurai tendance compter le nombre de pions alignés.
Je m'explique :
- si ton adversaire a quatre pions alignés, tu mets la solution à 0 (ou -infini) car tu as perdu
- si c'est toi qui en a quatre aligné, solution à l'infini, afin d'être sûr de garder cette solution.
- Si ni toi ni l'adversaire n'avez gagné, tu comptes le nombre de séries de trois pions alignés pouvant encore être complétés (celle bloquées sont bien sûr à ignorer). Ce nombre de pions alginés doit être multiplié par un fort coefficient (100 par exemple) et additionné à la solution.
- ensuite tu fais de même avec les séries de deux pions et un coeffficient plus faible (10 par exemple) et de même pour un pion (coef 1).
C'est une méthode basique qui te donnera une solution correcte si elle est employé dans le cas d'un calcul exhaustif des solutions.
Mais il doit exister pour chaque type de jeu, une formulation mathématique de la technique (comme pour le rubicube, les dames, ...).
Oui ! enfin quelqun qui à compris qu'il de servait a rien de calculer mais il faut refléchir a point !
imaginons que l'adversaire a 3 pions alligné, il ne sert a rien de calculer les 500 prochains coups il faut le bloquer dessuite !
d'autres part au echecs il ne sert a rien de calculer les 20 000 suivants (surtout en début de partie) car rien ne garantis que la personne en face ne trouvera pas le moyen de faire une variante du mat de legal coups difficile a contrer au niveau algorithmique car on sacrifie la dame (pièce maitresse apres le roi) au benefice d'un mat en un coup avec une pièce subalterne ensuite !
Le but etant, plutot, de ne pas prendre de trop mauvaises solutions que l'on peux calculer avec seulement 10 à 20 coups (loi de parreto : 20 % de choix déterminent 80% des actions) le reste des calculs n'etant pas nésséssaires car trop difficile à prédire avec certitude.
meme les grands joueurs sont difficilement capables de voir avec certitude plus de 80 ou 100 coups. Tout en sachant que tous ne construisent pas d'arbre dans leur tetes. Il connaissent et définissent en cour de partie des "cases stratègiques à prendre" et a tenir et connaissent parfaitement la meilleure utilisation des mouvements de leurs pièces. Par exemple la tour gagne en puissance dans la ligne des pions enemis. Ou encore, les fous servent a maitriser les cavaliers adverses.
Bref il faut calculer tous les coups oui mais il faut le faire en vérifiant que l'on ne vas pas tomber dans un piège (mat de legal). Le truc etant de vérifier avec des formules spécialisés tout comportement suspect et domageables.
Ceci etant dit la "brute force" et un des meilleurs atout de l'informatique et ne pas s'en servire serait abérhent
Dernière modification par doccpu ; 12/03/2008 à 00h10.
1. Sauf dans le cas ou l'IA peut gagner immédiatement la partie.
2. S'il y a plusieurs moyens de bloquer l'adversaire, l'IA choisit lequel ?
etc.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager