Discussion :

[timtima]

Bonjour,
je travaille sur un projet de Puissaance 4,
la grille a 7 colonnes et 7 lignes.
le jeu a une nouvelle option: les joueurs peuvent tourner la grille avec des angles de 90°,180°,270°.
c'est pour celà que je n 'arrive pas a trouvé les heuristiques de machine , pour machine vs homme.
aider moi SVP je dois bientôt rendre mon projet !!! merci !!!

[PRomu@ld]

Quel est déjà l'algorithme que tu utilises ? minmax , alphabeta , autre ?

aider moi SVP je dois bientôt rendre mon projet !!!

Nous n'y sommes pour rien !

[ToTo13]

Bonjour,

le puissance 4 est un "petit" jeu ne demandant pas une intelligence artificielle surpuissante. En général une simple recherche exhaustive permet de battre n'importe quel joueur.

Est ce que tu as essayé une recherche exhaustive en ajoutant la possibilité de faire des rotations ?

[timtima]

Quel est déjà l'algorithme que tu utilises ? minmax , alphabeta , autre ?

l'algorithme alphabeta.

Est ce que tu as essayé une recherche exhaustive en ajoutant la possibilité de faire des rotations ?

Non


je n'ai rien fait pour le moment, je sais comment marche ce algorithme mais je ne sais pas comment l'appliquer a un jeu, j'ai déjà vu un code source d'une version de puissance 4. Et Tourner la grille me rend encore plus

[fremen167]

Bonjour,

le jeu a une nouvelle option: les joueurs peuvent tourner la grille avec des angles de 90°,180°,270°.

Est-ce que la gravité continue de s'appliquer ? Je veux dire, si tu tournes par exemple de 90°, les pions tombent-il vers le bas ?

Et le joueur qui fait tourner le jeu peut-il également placer un pion ? Avant ou après la rotation ?

[alex_pi]

Pour chaque position, tu as 7 coups possible. Donc pour les 4 rotations, ça te fait, à chaque tours, 28 possiblités. Si tu fais un parcours exhaustif sur 4 coups, ça te fait 614 656 possibilités, ce qui me semble parfaitement raisonnable (même les 17 210 368 de possibilités pour un coup de plus sont raisonnables et les 481 890 304 pour 6 coups ne sont pas inenvisageables, surtout avec un bon backtracking), et je pense qu'aucun être humain n'aura la moindre chance de jouer face à ça. Bref, je n'ai pas l'impression que ce soit exactement un domaine où la recherche d'optimisation est valorisante :-)

[acx01b]

salut

au puissance 4 quand la partie va bientôt se finir il faut absolument prévoir plus que les 6 coups suivant pour gagner

[fremen167]

salut

au puissance 4 quand la partie va bientôt se finir il faut absolument prévoir plus que les 6 coups suivant pour gagner

Oui, mais :
1) il y a des coups qu'il est facile d'éliminer (il suffit de savoir compter, et de connaître la notion de parité et à priori, c'est pas le point faible d'un PC )

2) avec les rotations en plus, je crois que ça change vraiment la nature du jeux.

Je suis tout-à-fait d'accord avec Alex-pi pour dire qu'il sera très difficile à un humain de voir aussi profond. S'il peut le faire, ça voudrait dire (cf. 1) que par des méthodes de comptage, il arrive à déterminer le caractère gagnant d'une position. Le principe même de l'alphabeta, c'est qu'il faut avoir une bonne heuristique au niveau de profondeur maximum.

D'où mes questions sur les règles précises, car sans elles, je ne vois pas comment définir une fonction heuristique !

[timtima]

Est-ce que la gravité continue de s'appliquer ? Je veux dire, si tu tournes par exemple de 90°, les pions tombent-il vers le bas ?

oui la gravité continue de s'appliqué et les pions tombent vers le bas

Et le joueur qui fait tourner le jeu peut-il également placer un pion ? Avant ou après la rotation ?

le joueur ne peut pas tourner la grille et jouer, soit il joue , soit il tourne la grille

[timtima]

SVP aidez moi je susi bloquée, etje dois rendre mon projet dans 4jours!

[fremen167]

Bonjour Timtima,

Mais de ton côté, où en es-tu ? Tu demandais comment appliquer l'aplphabeta à un jeu. Mais en fait, cet algorithme est fait pour ça !

Le principe est dérivé de celui du minimax, qui consiste à dire :
quand je joue, je choisi le meilleur coup, qui correspond à un maximum de ma fonction d'évaluation pour tous les coups possibles ;
quand mon adversaire joue, son meilleur coup correspond à un minimum de la même fonction.
En principe, tu as 7 coups possibles (1 par colonne), et là tu ajoutes 3 rotations, soit dix coups maximum possibles par niveau.
Tu dois fixer la profondeur maximum de parcours de l'arbre des possibilités. Dès que tu arrives à cette profondeur, il faut évaluer la position : c'est là qu'intervient la fonction heuristique.

Tu peux commencer par programmer ton minimax en laissant des fonctions à coder (fonction d'évaluation notamment). Dans le même temps, il faut que tu essayes de jouer à ce jeux (même avec un papier et un crayon, mais le mieux est de jouer avec quelqu'un) pour voir quelles sont les bonnes tactiques. Ca devrait te permettre d'affiner ta vision du jeu et d'élaborer une heuristique pertinente.

[timtima]

Mais de ton côté, où en es-tu ? Tu demandais comment appliquer l'aplphabeta à un jeu. Mais en fait, cet algorithme est fait pour ça !

ok

de mon côté je sais qu'il ya 10 coups possibles par niveau.
le pb est que je ne sais pas comment déterminé cette fonction d'évaluation. et je sais comment marche l'agorithme alpha bêta.
vous me proposer de dérouler le jeu jusqu'a la fin avec tout les cas possibles :trop galère

Tu dois fixer la profondeur maximum de parcours de l'arbre des possibilités.

pour un ordinateur amateur la profondeur sera de 3 bien de 5 et fort de 7.

Dès que tu arrives à cette profondeur, il faut évaluer la position : c'est là qu'intervient la fonction heuristique.

je ne sais pas comment le faire.

Dans le même temps, il faut que tu essayes de jouer à ce jeux (même avec un papier et un crayon, mais le mieux est de jouer avec quelqu'un) pour voir quelles sont les bonnes tactiques. Ca devrait te permettre d'affiner ta vision du jeu et d'élaborer une heuristique pertinente.

je joue a ce jeux chaaque 30mn!

[fremen167]

vous me proposer de dérouler le jeu jusqu'a la fin avec tout les cas possibles :trop galère

Non, juste d'y jouer pour essayer de déterminer une logique de jeu.

Tu écris que tu y joues tout le temps... ça donne quoi ?

Par contre, as-tu regardé ici ?

Ca devrait beaucoup t'aider !

Je n'y ai pas encore joué, mais il y a au moins un problème que tu devras aborder : la possibilité d'un "nul" comme aux échecs, par répétition de rotations (mais ça doit être rare, car les rotations ne sont à priori pas réversibles, au sens où 1 rotation +90° suivie d'une rotation -90° a bien peu de chances d'aboutir à la position initiale !).

[fremen167]

Bon, j'ai joué un peu et je vois se dégager au moins un semblant de règle : ne faire une rotation que si :
1) c'est un coup gagnant direct (ça, c'est facile à évaluer )
2) ou si c'est le seul moyen d'empêcher un coup gagnant direct de l'adversaire.

Ca veut dire que si tu n'as pas atteint la profondeur maximum, tu évalues les rotation mais tu ne leur accordes une valeur que si tu es dans un des deux cas indiqués ci-dessus (et tu ne parcours pas d'arbre en dessous).

En effet, la rotation permet à l'adversaire de placer un pion de plus, et lui donne un avantage considérable.

Après, il y a les heuristiques propres au puissance 4 :
- construire des lignes et des diagonales,
- encore mieux, une ligne et une diagonale de 3 pion dont la fin est consituée de deux cases l'une au dessus de l'autre,
- jouer les extérieurs plutôt que les intérieurs, globalement essayer d'envelopper l'adversaire.

La fonction peut accorder des points :
- à une ligne, colonne, diagonale (3 mieux que 2, et bien sûr avec la place de finir) ;
- privilégier les lignes / diagonales du bas sur celle du haut ;
- considérer également comme ligne / diagonale des pion alignés avec un trou au milieu...

Tu peux également dépasser la profondeur maxi que tu as fixée dans les cas où il y a des coups forcés pour l'un des joueurs, même si avec la règle des rotations, il faudra évaluer le coup "forcé" (qui empêche de finir une ligne) mais aussi les rotations. De toutes façons, évaluer la position après rotation quand tu atteins la profondeur maxi.

Pour l'instant, c'est tout ce que je vois

Ce qui serait bien, c'est que tu commences à implémenter et que tu expérimentes. Un méthode peut consister à définir des constantes pour pondérer les différentes configurations que tu évalues dans ta fonction.

Puis tu affiches le déroulement avec à chaque fois position / évaluation, pour voir si ça te paraît bon.

C'est là que tu pourras voir s'il manque un truc important dans ta fonction, et tu pourras nous poser des questions plus précises