Discussion :

[amathlog]

Bonsoir à tous !
Je vous expose mon problème, en espérant que quelques irréductibles travaillent encore en Pascal et n'ont pas encore tous migré vers le C/C++.
Tout d'abord, le fait que je code en Pascal vient que c'est le seul langage qui est disponible pour l'option info en maths spé dans mon lycée. Du coup, vu que j'ai bien plus manipulé le pascal que le C, j'ai décidé de continuer dans cette voie(mon prof pouvant en plus m'aider).

Peut être que vous le savez, mais les secondes années de classe préparatoire doivent rendre un dossier sur lequel ils ont travaillé toute l'année et qu'ils doivent présenter devant un jury.
J'ai choisi de travailler sur un puissance 4, et plus précisément sur la partie IA du puissance 4. Le puissance 4 étant un bon compromis difficulté/intérêt. Je n'ai en effet que peu de temps à m'y consacrer et viser plus haut aurait sans doute compromis mes chances de réussite !

Mon programme est dorénavant fini, ou presque. Il me reste des améliorations à apporter et c'est pour cela que je mobilise votre aide !
En effet, mon IA joue et arrive à me battre de temps en temps. Mais je la trouve très très mal optimisée.
Je m'explique :
-Son plus gros défaut reste que dans certains cas, où elle peut aligner 4 jetons verticalement en 2 coups alors que moi en 1 coup je peux gagner, elle va chercher ce coup et ne va pas tenter de bloquer le mien =>victoire facile
-L'autre soucis est le coup banal qui consiste à aligner 3 jetons au milieu pour pouvoir gagner soit en posant un jeton à droite ou à gauche. Je pense l'avoir contré, du moins en partie, en forçant l'ordinateur à poser un jeton dans une colonne au hasard (au lieu de toujours jouer dans la 1ère colonne)

Je pense que ce le problème majeur vient de ma fonction d'évaluation. Elle n'est finalement pas très poussée. Pour un coup qui aligne 1 jeton c'est 1 point, 2:10 points, 3:100 points et 4:1000 points
Je fais la somme de tous les scores pour chaque jeton de ma grille et soustrait au score de chaque jeton de la grille pour mon adversaire.
Après un algorithme min_max se charge de prendre soit le score le plus bas si c'est au tour de l'humain de jouer ou le plus haut si c'est à l'IA de jouer.

C'est assez long à expliquer mais je pense que cet algorithme est très connu du coup j'espère que vous comprendrez.

Je ne sais pas comment modifier mon programme de tel sorte que le 1er problème soit résolu... Si vous avez besoin de mon code source, je peux vous le fournir, je l'ai annoté de façon à ce qu'on puisse s'y retrouver facilement.

En tout cas je vous remercie d'avance pour votre aide et bonne soirée !

[Roland Chastain]

Bienvenue !

Il me semble que tu ferais bien en effet de montrer ce que tu as fait, afin qu'on puisse s'en faire une idée précise.

En te lisant je crois comprendre que l'évaluation ne prend en compte que le résultat immédiat du coup à jouer. Si tel est le cas, s'il n'y a pas de prévision au-delà de la prochaine position, le jeu de l'ordinateur ne peut être que faible.

Si tu en es réduit à faire jouer l'ordinateur au hasard pour augmenter ses chances de victoire, c'est qu'il y a quelque chose qui ne va pas !

[Invité]

Bonjour,

En ce qui concerne l'algorithme, peut-être quelques idées vous paraîtront-elles dignes d'intérêt ici. Bonne continuation.

Cordialement. Gilles

[Mendahor]

-Son plus gros défaut reste que dans certains cas, où elle peut aligner 4 jetons verticalement en 2 coups alors que moi en 1 coup je peux gagner, elle va chercher ce coup et ne va pas tenter de bloquer le mien =>victoire facile

Affecter un score négatif sur un coup qui empêche l'autre d'aligner 4 jetons ?

-L'autre soucis est le coup banal qui consiste à aligner 3 jetons au milieu pour pouvoir gagner soit en posant un jeton à droite ou à gauche. Je pense l'avoir contré, du moins en partie, en forçant l'ordinateur à poser un jeton dans une colonne au hasard (au lieu de toujours jouer dans la 1ère colonne)

De mémoire du temps ou je jouais, je ne jouais jamais mon premier coup dans la 1ère colonne. Toujours celle du milieu si c'est toi qui ouvre ou qu'elle est libre, et toujours une immédiatement a côté si l'adversaire ouvre au milieu.

[amathlog]

Merci d'abord pour vos réponses !
Après réflexion, je pense que le principal défaut de mon algorithme vient du fait que je ne l'arrête pas dès qu'un coup aligne 4 jetons, il continue à tourner.
Je vous laisse mon code source et je vais voir comment je peux intégrer un arret de mon algo si une situation 4 jetons alignés est présente.

Merci

[Paul TOTH]

pour ce genre de problème tu dois obligatoirement anticiper les coups suivants. Tu ne peux pas te contenter de l'état actuel du tableau.

1) quel est le "score" du tableau si je place un jeton en colonne X
2) quel est le "score" du tableau si mon adversaire joue alors en colonne Y

et tu peux continuer cette évaluation jusqu'à une profondeur d'analyse donnée pour limiter le temps de calcul...encore que sur un P4 ce temps est fini puisqu'on utilise un jeton à chaque tour.

avec ce principe, tu sais que si le joueur place 3 jetons à l'horizontal tu as perdu deux coups plus tard. Le programme ne laissera donc jamais le jouer atteindre cet état (sauf s'il n'a pas le choix et alors il sait qui a déjà perdu si le joueur ne fait pas de connerie)...tu peux alors ajouter un commentaire "ça sent le roussi"...ou "mauvais coup" si le jour ne profite pas de ça chance de gagner.

[amathlog]

Je comprends mais j'ai déjà une fonction d'évaluation qui va jusqu'à 2 tours plus loin, cependant cette fonction ne s'arrête pas lorsque il remarque que 4 jetons sont alignés il peut même aligner 5 jetons et pourtant il ne va pas jouer la. Donc je pense tester en plus le nombre de jetons alignés dans cette fonction en plus de donner un score au tableau.
Mais pour le moment je ne peux pas accéder à mon ordinateur, je vous recontacte lorsque que j'aurais quelques résultats

[Gouyon]

Je n'ai pas vraiment regardé ton programme mais as tu pensé à utiliser un algorithme min-max avec réduction alpha-beta
voir http://fearyourself.developpez.com/t...l/sdl/morpion/

[Roland Chastain]

Mais pour le moment je ne peux pas accéder à mon ordinateur, je vous recontacte lorsque que j'aurais quelques résultats

Veux-tu des conseils ou n'en veux-tu pas ?

cependant cette fonction ne s'arrête pas lorsque il remarque que 4 jetons sont alignés

Dans ce cas qu'est-ce qui te fait dire qu'il le "remarque" ?