Boucles for imbriquées

Version imprimable

Bonsoir,
je suis en train de programmer un jeu de morpion qui va de la taille 3*3 a 30*30.
Dans un soucis d’optimisation, j'ai complètement changé mon ia. Je suis passé de l’idée de minimax (qui marchais très bien, mais pas encore suffisamment optimisé ) a une idée de for imbriqués.
Voici mon idée actuelle (en résumé) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 ia{ Déclaration des variables profondeur maximale de recherche : ici 3 (mais dépendra de la dimension du plateau de jeu) On connais deja la liste des cases vides donc jouables for (i=0; i<NbCasesVides; i++) //pour toutes les cases vides du plateau, { JouerCoup(i); verifFini(...); ... AnnulerCoup(...); AnnuleVerifFini(...); } Si on ne peut pas gagner en jouant 1 case (pour le joueur), alors on continue la recherche en testant 2 cases (pour le joueur et l'adversaire) for (j=0; j<NbCasesVides; j++) //pour toutes les cases vides du plateau, { for (i=0; i<NbCasesVides; i++) //pour toutes les cases vides du plateau, { if(i!=j)//si on choisit une case pas deja testée, alors { JouerCoup(j); JouerCoup(i); verifFini(...); AnnulerCoup(...); AnnulerCoup(...); AnnuleVerifFini(...); }}} Si on ne peux pas gagner en jouant 2 cases(pour le joueur et l'adversaire), alors on continue la recherche en testant 3 cases (joueur - adversaire - joueur) for (m=0; m<NbCasesVides; m++) //pour toutes les cases vides du plateau, pour O { for (j=0; j<NbCasesVides; j++) //pour toutes les cases vides du plateau, pour X { for (i=m+1; i<NbCasesVides; i++) //pour toutes les cases vides du plateau, pour O mis plus grand que m sinon deja testée { if((i!=j)&&(j!=m))//si on choisit une case pas deja testée, alors { JouerCoup(m);// ia teste m pour lui JouerCoup(j);// ia teste j pour lui JouerCoup(i);// ia teste i pour l'adversaire verifFini(...); AnnulerCoup(...); AnnulerCoup(...); AnnulerCoup(...); AnnuleVerifFini(...); } } } } On joue la case choisie. }
Mon problème est le suivant :
1. Il est fortement possible que je soit obligé d'aller plus loin que 3 cases testées : (joueur - adversaire - joueur - adversaire)
2. Mon code se répète (à l'intérieur des boucles for). Mais je n'arrive pas à faire une fonction récurrente qui accumule le nombre de for et ne reprends pas une valeur deja testée
3. Si je teste 4 cases avec les variables i, j,m, n, (avec m>i et n>j) il faut aussi que i!=j, (i!=m), i!=n, j!=m, (j!=n), m!=n avant de jouer.
4. Si je teste 5 cases avec les variables i, j,m,n,r (avec r>m>i et n>j) il faut aussi que i!=j, (i!=m), i!=n,( i!=r), j!=m,( j!=n),j!=r, m!=n, (m!=r), n!=r avant de jouer.

Je vous serais très reconnaissant de bien vouloir m'aider.

Bonjour

Citation:

Envoyé par chamludo

je suis en train de programmer un jeu de morpion qui va de la taille 3*3 a 30*30.

Parle-t-on du même morpion ? Celui avec les X et les O et il faut en aligner 3 ? Dans ce cas j'ai du mal à imaginer comment jouer sur un 30x30...

Citation:

Envoyé par chamludo

Mon problème est le suivant :
1. Il est fortement possible que je soit obligé d'aller plus loin que 3 cases testées : (joueur - adversaire - joueur - adversaire)
2. Mon code se répète (à l'intérieur des boucles for). Mais je n'arrive pas à faire une fonction récurrente qui accumule le nombre de for et ne reprends pas une valeur deja testée
3. Si je teste 4 cases avec les variables i, j,m, n, (avec m>i et n>j) il faut aussi que i!=j, (i!=m), i!=n, j!=m, (j!=n), m!=n avant de jouer.
4. Si je teste 5 cases avec les variables i, j,m,n,r (avec r>m>i et n>j) il faut aussi que i!=j, (i!=m), i!=n,( i!=r), j!=m,( j!=n),j!=r, m!=n, (m!=r), n!=r avant de jouer.

Je pense que cette réflexion sur les soucis engendrés par ton IA devrait t'amener à la conclusion que celle-ci n'est pas bonne. Elle veut faire trop de trucs à la fois et le fait mal.

Voici comment je verrais ton IA
Code:

1 2 3 4 5 6 7 8 9 10 int ia(int joueur /* 1 ou 2 */, int but /* +1 pour gagner, -1 pour perdu */, int prof) { for (i=0; i < nbCases; i++) { if (caseNonVide(i)) continue; jouerCoup(i); verifFini(but); if (prof < PROF_MAX && ia(3 - joueur /* 3 - 1 = 2 et 3 - 2 = 1 */, -1 * but /* -1 * -1 = 1 et -1 * 1 = -1 */, prof+1) == but) return but; annulerCoup(i); } return 0; }
Bon c'est pas vraiment finalisé comme algo mais ce que je cherche à montrer, c'est que l'IA doit représenter un seul joueur à la fois. Mais en s'appelant récursivement en changeant chaque fois de joueur, elle peut simuler une partie complète (comme quelqu'un qui joue contre lui-même). Et si elle arrvie à une situation ou un de ses coups entraine tous les coups en réponse perdants, alors elle a trouvé le coup gagnant qu'il faut jouer (et on peut faire le raisonnement inverse)...

25/07/2019, 19h12
chamludo

Merci d'avoir pris la peine de me repondre
25/07/2019, 20h18
chamludo

Je vais essayer de t'expliquer un peu plus.
On parle bien du même morpion avec des O et des X sur un quadrillage 3*3 et il faut aligner 3 jetons pour gagner. Ca tu lavais bien compris
Je fais une version graphique avec la sdl, mes jetons mesurent 200px soit un damier de 600*600px.
Du coup, je me sus dis que l'on pouvais aussi jouer sur une grande feuille de papier avec plus de 9 cases.
j'ai comme dimensions possible des diviseurs de 60o cad 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 25, 30 cases.
Donc on peux, si on veut jouer sur une feuille 5*15 cases.Dans cette feuille, aligner 3 jetons est immédiat (et pas intéressant), donc on décide d'en aligner 4 ou 5 ou même plus.

J'avais fait une version avec le minimax qui fonctionnait très bien en dimension 3*3, mais qui ramait sur un plus grand plateau de jeu.
En fait, une profondeur 4 (2jetons chacun) est suffisante pour 3*3.
Sur une plateau 10*5, tester les 4 coups suivant coutent environ : 50*50*50*50 = 6.250.000 essais ce qui est beaucoup. En realite moins de coup car c'est (50-nbjetondejajoués)*(49-nbjetondejajoués)*(48-nbjetondejajoués)*(47-nbjetondejajoués), ce qui n'est pas negligeable.
En plus sur 5*10, on n’aligne pas 3 jetons mais au moins 4 donc il faut une profondeur plus importante pour avoir une chance d'obtenir un alignement (au moins prof=6). D'où un nombre important de cas à traiter en plus.

Du coup j'ai fais plusieurs optimisations. En supposant que la profondeur de base soit 4 (1-2-3-4)ordi-adversaire-ordi-adv
1. Je teste une profondeur de 4 jusqu'à ce que quelqu'un gagne avant (ou pas). L'adversaire peut gagner au rang 4 ou 2 et l'ordi au rang 3 ou 1. Si l'ordi gagne au rang 3 alors on ne teste que jusqu'a la profondeur 3 par la suite, ce qui permet de réduire le nombre de cas et ainsi de suite si quelqu'un obtient un alignement au bout de 1, 2 ,ou jetons.

2. si l"ordi est O et que le jeu est
O X O
X _ O
_ _ _
si O joue les cases n°4 et 8 alors O gagne. Mais ce n'est pas utile de tester les cases 8 puis 4 car c'est la même combinaison. Donc j'avais fait un minimax avec des bouclex ne parcourant pas toutes les cases possibles mais seulement supérieure à celle 2 cases testées avant et cela marchait assez bien (idee que je veux reprendre avec les boucle for et le k=i+1->fin)

3. Cette amélioration, je n'ai pas réussi à la programmer, c'est pour cela que je changé de méthode
Voici quelle était mon idée.
Si en testant les cases 4 puis 8 l'ordi gagne, alors on est a une profondeur de 3 et on a "gagné un étage".
Mais a-t-il gagné car il a joué 2 et 8 ou juste la case 8 ?Du coup, j testait uniquement une profondeur de 1 avec seulement la case 8 et je regardais s'il avait gagné, ce qui ici serait le cas. donc on serait à une profondeur de 1 et plus de 3 avec un gain de recherche considérable. Seulement , je n'ai pas réussi à faire cette modification. De plus si sur un grand plateau 5*0 ou autre, on teste les cases 1-2-3-4-5 et que l'ordi gagne, en fait sa combinaison gagnante est 1-3-5.Le 5 fait gagner. Seul ou avec le 3 ou avec le 3 et le 1? Donc il fallait tester les permutations de la combinaison gagnante. de toute facon, si le 1 faisait gagner tout seul, mon ia l’aurait trouvé mais beaucoup, beaucoup plus tard et ce ne serait pas optimisé.

En fait jusqu'à présent je faisais une recherche en profondeur que j'essayer de réduire.

D'où l’idée de faire une recherche en largeur. Pouvoir gagner en jouant un seul jeton(for i) ou alors s'apercevoir que l'on perd au bout du 2eme jeton posé (for i(for j) avec i!=j) permet un gain beaucoup plus rapide. Mais que l'on teste un 3eme jeton, il y a 3 boucles for et plus de cas à exclure : for i (for j (for k avec i !=j et k>i et k!=j)).

C'est pour cela que je cherche un e fonction, surement récurrente qui puisse me le faire.
En imaginant une profondeur de 3, je peux dans ma fonction écrire mes 3 for imbriqués et les cas d'exclusion, c'est facile
Avec une profondeur de 8, je vais avoir 8 for imbriqué et beaucoup de cas d'exclusion, ce qui est moins long à écrire.

L’étape suivante serait de pouvoir jouer à 3 joueurs sur des grand plateau 10*10.

Voila, j’espère que tu comprendras en gros mon cheminement et que je n'ai pas encore été trop long à lire.

Bonjour,

Ici, tu cherches à déterminer le meilleur coup en force butant sur n coups.

Comme tu l'as remarqué, la complexité est exponentielle (c-à-d que pour tester à n coup l'ordre de grandeur va être k^n, ce qui devient rapidement énorme). Si tu veux bel et bien procéder comme suit, tu dois donc ruser.

Une méthode classique est de ne tester que les coups pertinents. Par exemple sur ton cas précis, si tout tes pions sont en bas à droite du damier, il sera probablement inutile de tester les coups en haut à gauche, ce sera forcément des mauvais coups (enfin, j'en ai l'intuition).

A haut niveau, l'algorithme marche comme ça:
Code:

1 2 3 4 5 6 7 pour i allant de 0 à DEPTH | moves_set <- genereCoups() | pour_tout coup c dans moves_set | | c.score = evaluate(c) | moves_set = prune(moves_set, NUMBER_TO_KEEP) // On garde uniquement les NUMBER_TO_KEEP (ex 1.000 meilleurs coups). On "coupe" des branche de l'arbre des possibilités. return get_best_move(moves_set)
Ce type d'approche est une heuristique, c'est très courant pour ce type de problème. Par exemple, regarde du côté de l'algorithme de Monté Carlo.

Avec des heuristiques, tu n'es pas garanti d'avoir la meilleure solution mais tu as beaucoup de chances de l'avoir quand même ou tout du moins d'avoir une solution quasi-optimale. Le principal intérêt de cette approche est que tu n'as besoin de tester moins que DEPTH*NUMBER_TO_KEEP² coups. Par exemple en gardant 1000 branches et en voyant à 100 coups à l'avance (!) tu n'as besoin de tester que moins de 100*1000² = 10^8 coups, ce qui reste raisonnable et complétement ridicule par rapport à la force brute qui t'aurait donné un truc en puissance 100.

Cela dit, sur ce cas particulier tu dois pouvoir trouver un coup parmi les meilleurs sans avoir besoin de tester plusieurs coups à l'avance. Une idée peut être un truc dans ce style (je suppose que tu dois aligner 4 jetons, on peut trouver des choses similaires sinon)
Code:

1 2 3 4 5 critère_1 = nb_4_a_la_suite('X') - nb_4_a_la_suite('O') critère_2 = nb_3_parmi_4('X') - nb_3_parmi_4('O') // On regarde combien de fois on à 3 'X' et 1 case vide qui permettront de faire un puissance 4 au prochain tour - la même chose pour l'ennemi critère_3 = nb_2_parmi_4('X') - nb_2_parmi_4('O') // On regarde combien de fois on à 2 'X' et 2 cases vides qui permettront de faire un puissance 3 au prochain tour - la même chose pour l'ennemi critère_4 = nb_1_parmi_4('X') - nb_1_parmi_4('O') // On regarde combien de fois on à 1 'X' et 3 cases vides qui permettront de faire un puissance 2 au prochain tour - la même chose pour l'ennemi
Le meilleur coup est alors celui qui maximise le critère 1, en cas d'égalité, le critère 2, en cas d'égalité, le critère 3 et ainsi de suite.

Intuitivement je pense que ça doit marcher mais je n'ai pas testé donc je ne suis pas sûr.

Tu dois pouvoir te passer d'une heuristique ici mais c'est quelque chose de très utile et je trouve rigolo à faire, donc ça peut être intéressant de regarder quand même pour des problèmes plus complexes ou ce sera la seule/meilleure approche.

Si tu as des questions n'hésite pas.

Bonne journée