Salut,

J'ai créé un topic il y a quelques semaines pour proposer un concours d'IA dont le juge eût été le puissance 4. On m'a tout de suite fait remarquer que c'était un mauvais départageur, puisque puissance 4 a été "résolu" depuis longtemps.

J'ai donc créé un petit puissance 4 (avec la librairie SDL) et une "ia" qui va avec. Ma première ia n'avais pas la prétention de résoudre le jeu. En gros, elle jouait un grand nombre de parties virtuelles (typiquement, 200 parties par colonne de départ) puis, à la fin, regardait quel était la colonne de départ qui offrait le meilleur ratio parties gagnantes/parties perdantes. Pour jouer ses parties virtuelles, cette ia se contentait simplement de ne pas faire de coups stupides, c'est-à-dire qu'elle :
- ne ratait jamais d'occasion de gagner au tour suivant
- si la condition précédente n'était pas remplie, elle ne ratait jamais d'occasion d'empecher de gagner l'adversaire au tour suivant
- enfin, si ni l'ia ni le joueur ne pouvait gagner au tour suivant, elle jouait au hasard dans une colonne libre.

Avec cette ia, j'ai obtenu des résultats encourageants.
Elle poutre ma petite soeur^^
Elle me bat régulièrement, mais je la bat plus souvent qu'elle me bat.
À noter qu'elle conclue systématique, et à partir de 20 parties virtuelles par colonnes déjà (ce qui correspond à un temps de calcul de quelques centièmes de secondes), que le meilleur premier coup est celui au milieu.

Mais voilà : maintenant je me demande comment résoudre le jeu.

Je ne vois qu'une solution : "cataloguer" l'ensemble des parties possibles. On pourrait les représenter par un arbre complet (et gigantesque) dans lequel l'ordinateur n'aurait "qu'à " prendre l'embranchement le plus avantageux à chaque fois qu'il joue. Il jouerait donc de manière parfaite, n'est-ce pas?
Seulement, construire un tel arbre, puis le stocker dans un fichier de données, est beaucoup trop gourmand en mémoire. Et à chaque fois que l'ia joue, elle devrait pourtant :
1) se situer dans l'arbre
2) scanner l'ensemble des embranchements accessibles et en déduire lequel est le plus avantageux.
Cet arbre serait donc non seulement long à construire, mais encore à utiliser !

Comment font les programmes qui jouent parfaitement à puissance 4? D'après ce que j'ai lu, ils se cantonnent à un catalogue de 60'000 entrées de jeu environ. Mais comment jouent-ils ensuite ?

Ah encore une chose intéressante sur mon ia "aléatoire".

Lorsque je fais jouer l'ordinateur contre lui même, et que je fixe le niveau d'ia du joueur 1 à une certaine valeur, et que je fais varier celui du joueur 2, j'observe que jusqu'à un certain point, il est utile d'augmenter le nombre de parties virtuelles (de la même manière que quand on fait un sondage, en augmentant l'échantillon statistique on se rapproche des valeurs réelles), mais au delà d'une valeur (environ 200 parties virtuelles par colonne), l'ia ne devient pas plus forte. Ainsi, sur 100 parties, la répartition victoires/défaites entre un ordi qui a un niveau 200 et un autre un niveau 1000 est d'environ 50/50 ....

C'est comme si mon ia "aléatoire" possédait un pouvoir de résolution maximum, une asymptote, et qu'elle ne peut pas, comme je m'y attendais, approcher indéfiniment de la partie parfaite, au fur et à mesure que j'augmente l'échantillonnage.

À noter que j'ai testé plusieurs manières de compter les victoires de parties virtuelles. J'ai introduit une sorte de pondération.
La valeur d'une victoire est inversément proportionnelle à l'avancement de la partie virtuelle en cours (plus la victoire a lieu tôt, plus elle a de poids).
Au final, comme je l'ai dit, l'ia choisit la colonne dont le ratio (somme des valeurs de victoires) / (somme des valeurs de défaites) est le plus élevé

Mon topic, en lien avec ce sujet

https://www.jeuxvideo.com/forums/1-47-43101-1-0-1-0-c-ansi-argh-mon-fichier-explose.htm

si tu comprends quelque chose aux idées de dnob700...

Salut a toi,

Tu peux vouloir lire ca que j'ai ecrit sur la resolution de cassis [1]. La cle de la resolution de puissance 4 est de comprendre que brute force est realiste de nos jours.

Il n'y a pas beaucoup de solution au probleme. Chaque colonne est de taille 6, il n'y a que deux couleurs et elles occupent les positions les plus basses de la colonnes. Donc si la colonne a x piece, il y a 2^x combinaison. Chaque colonne est de taille 6, donc il y a 2^0+2^1+2^2+...+2^6 = 2^7 combinaison par colonne. Il y a 7 colonnes, donc 2^49 tableau possible. Ca fait en 2^9 tera combinaisons.

Ca a l'air beaucoup comme ca, mais en fait c'est pas tant que ca parceque ce compte contient des solutions "incorrect". Ce compte se moque des symetries. Ce compte suppose que le nombre de piece de chaque couleur est arbitraire, alors qu'il reste egal (ou la difference est de 1). Ce compte suppose que la partie continue apres que l'on ai trouve une solution gagante. Ce compte suppose aussi que l'IA explore toutes les solution meme quand elle en a trouve une gagnante. En pratique le compte est BEAUCOUP plus petit. Donc si tu as un systeme avec un peu de memoire, tu peux tout explorer sans difficulte.

Une fois que tu as une map entiere du probleme sur disque. Le probleme est beaucoup plus facil car il te suffit de constituer une bibliotheque d'ouverture (comme aux echec) pour stocker ce qu'il faut faire dans les X premiers coups. Tu n'as besoin que de stocker en gros 7^(X/2) possibilite. (Le 7 viens du nombre de colonne, le X/2 viens du fait, que pour les coups de l'IA, il n'y a qu'un choix possible.) Donc tu peux stocker explicitement les 16 premiers coups pour 7^8 = 5.7 Million de combinaisons.

Ensuite, tu brute force le reste du probleme au runtime quand tu y arrives. C'est pas completement evident a calculer, mais ce qui reste n'est pas si gros. Mais c'est certainement plus petit que 2^9 tera diviser par 5.7 million. Soit quelques millions, ca se re-calcul bien au runtime.

Et ca c'est l'approche de base sans reflechir a la structure du probleme.

J'espere que cela t'aide,

Erik

[1] http://erik.deblan.org/blog/index.php?article11/the-best-ai-for-cassis

J'ai déjà écrit sur papier mon algorithme de constitution de la map entière du problème. Je vais essayer de le tester dès que j'aurai un ordinateur qui arrive à faire tourner codeblocks sous la main^^ (c'est cool les pauses à la campagne, ça laisse le temps d'écrire sur le forum et de réfléchir aux problèmes)

Je suis tout à fait d'accord avec toi sur le fait qu'on peut éliminer beaucoup de chemins à notre arbre (entre le fait que les règles du puissance 4 doivent toujours être respectées et la symétrie qui divise (quasiment) par 2 la taille de l'arbre).

Je vais donc essayer de générer cette map, comme tu dis.

Par contre je te comprend plus ici : "Ensuite, tu brute force le reste du probleme au runtime quand tu y arrives."
==> brute-forcer au runtime veut dire quoi pour toi ? utiliser une ia comme celle que j'ai déjà bricolée ? (d'ailleurs, aucune idée de pourquoi l'augmentation de l'efficacité de cette ia n'augment pas linéairement avec le nombre d'itérations, mais semble s'écraser asymptotiquement sur une efficacité bien en-deçà de l'efficacité type "partie parfaite" ? )

Merci pour vos réponses

(Par contre, j'ai juste jeté un coup d'oeil à ton lien concernant Cassis, et j'ai peur de pas avoir le niveau de programmation/de maths pour tout comprendre^^ Mais je m'y replonge plus tard )

Il arrive parfois qu'une approche à base d'arbre de décisions suffise pour avoir une IA qui tient la route sans pour autant connaitre les règles pour gagner.

http://fr.wikipedia.org/wrg/wiki/Arbre_de_d%C3%A9cision

brute force est le nom de l'algorithme qui essaye toute les solutions. Une fois que tu as une bibliotheque d'ouverture qui t'amene au debut du jeu (que tu constuis auprealable), finir le jeu est facil parcequ'il n'y a plus tant de combinaison que ca.

NFG, OP parles de resoudre exactement puissance 4.

Je sais pas ce que ça donne pour le puissance 4 mais un algo qui marche bien dans ce genre de jeu tour par tour c'est le minmax:
http://en.wikipedia.org/wiki/Minimax
Lis la partie Combinatorial game theory

hyrulink2, OP est interesser a la resolution exacte du puissance 4. Donc une heuristique ne lui sert a rien. Utilise minimax pour calculer l'optimal est la meme chose que brute force dont on parle depuis le debut du topic.

Je suis de retour...

Alors là j'ai réussi (facile, vous allez me dire, mais j'en ai bavé) à créer un programme qui me stocke dans un fichier texte toutes les parties possibles, pour un nombre de coup spécifiés.

J'ai plusieurs problèmes pour exploiter ceci.

Mais avant tout, pour que vous voyiez de quoi je parle, voici comment le programme note une partie sur mon fichier text, c'est un exemple d'une partie stupide mais simple :

w3026415

Cela veut dire que le joueur ayant commencé la partie a gagné (d'où le "w"), et que la partie s'est déroulée comme suit (les colonnes sont numérotées de 0 à 6) :
joueur 1 joue dans colonne 3
joueur 2 joue dans colonne 0
joueur 1 joue dans colonne 2
.
.
.
joueur 1 joue dans colonne 5
fin de la partie.
(de toute façon, le "w" ou le "l" au début des séquences (won et lost) délimitent le début de chaque partie)

Avant d'exposer mes problèmes, voici comment fonctionne mon algorithme d'écriture de parties, en gros :

- Il parcourt toutes les branches de l'arbre des parties du puissance 4 (le début est schématisé sur l'image )

- à chaque noeud de l'arbre, on check si la partie est gagnée, perdue, ou nulle. Le cas échéant, on note le résultat, suivi de la "coordonnée" de la branche sur laquelle on se trouve (cette coordonnée est une suite de nombres qui représentent les embranchements choisis depuis le départ jusque là où l'on se trouve).

Evidemment, on peut spécifier la "profondeur" de l'examen. Par exemple, je peux dire au programme que je ne veux pas qu'il examine plus loin que le 8ème coup, le 8ème "étage" de branches.

• • • *Premier problème : tirer profit de la symétrie****

Le jeu est symétrique par rapport à la colonne numéro 3.Le puissance 4 ne fait pas de différence entre la partie w3026415 et la partie w3640261. Ces deux parties sont le miroir l'une de l'autre. En fait, on peut facilement, sur la base d'une partie quelconque, écrire sa partie miroir, en utilisant le fait que la colonne miroir de la colonne N est la colonne 3 + (3-N). Ainsi en appliquant l'opérateur "miroir" à tous les coups d'une partie, on obtient sa partie miroir.

Jusqu'ici rien de bien difficile.

Mais mon problème, c'est que n'arrive pas à exploiter cette capacité potentielle à réduire de moitié le nombre de parties gagnantes (ou perdantes) à rechercher.
En effet imaginons que pour chaque partie gagnée ou perdue, je fasse également écrire sur le fichier sa partie miroir.
Maintenant, pour tirer profit de ce que je viens de faire, il faut que l'algorithme ignore efficacement toutes les parties miroires qui ont déjà été écrites. Si pour cela on doit vérifier, avant d'écrire chaque partie, si elle n'est pas déjà écrite, alors c'est une perte de temps plus qu'autre chose. Je ne vois pas de moyen efficace de dire à mon algorithme qu'il n'a pas besoin de réecrire les parties miroires (et pire encore, il voudra écrire le miroir des parties miroires déjà écrites, c'est à dire les parties "sources" !).

Bref, cette histoire de symétrie est pour l'instant plus un frein qu'un accélérateur...

• • • *Second problème : qu'est-ce qu'une bonne ouverture?****

J'imagine que vouloir décrire toutes les parties possibles, avec une profondeur de 42 tours (il y a 42 emplacements sur un plateau de puissance 4) n'est pas très réaliste. Sur wikipédia, et ici même, j'ai lu que les programmes qui jouent parfaitement à puissance 4 utilise un catalogue des meilleurs ouvertures. Mais comment savoir ce qu'est une bonne ouverture sans posséder le catalogue des parties complètes??? Cela m'échappe complètement. Comment peut-on dire d'une configuration donnée du jeu que c'est une bonne configuration pour un joueur donné ? Je peux le faire intuitivement, mais pas le quantifier de manière à le mettre sous forme de code.

Bref, pour l'instant, voici ma seule idée pour tirer profit de mon algorithme :

Créer une base de donnée de toutes les parties possibles avec une profondeur donnée, je pense que entre 10 et 15 est raisonnable, ca devrait engendrer un fichier de l'ordre de la dizaine de Mo. En fait, on peut même diviser ce fichier en sept fichiers : un pour le premier coup joué dans la colonne 0, un pour le premier coup joué dans la colonne 1, etc ...

Ensuite, l'IA, à chaque coup qu'elle joue, efface purement et simplement les lignes du fichier qui sont caduques, qui ne correspondent pas aux branches atteignables depuis cette position (on ne peut pas revenir dans le temps). Puis elle regarde, pour chaque branche qui s'offre à elle, laquelle offre le plus de victoire, ou le meilleur ratio victoire/défaites, ou encore le moins de défaites, suivant le mode de l'IA.

Mais lorsque le jeu dépasse la profondeur prévue (entre 10 et 15 coups), alors on est obligé de repasser l'IA en mode "statistique aléatoire" (voir mon premier post) ... Bref, ce n'est pas satisfaisant.

Qu'en pensez-vous ? (si vous avez eu le courage de tout lire^^)

Si j'arrive à créer une IA qui joue parfaitement à puissance 4, elle portera le nom de mon sauveur, qui est, j'en suis certain, parmi vous

Si c'est une sauveuse ça va aussi.

Ce n'est pas parce que tu as un catalogue de bonnes ouvertures que tu n'as pas eu a generer et ponderer toutes les ouvertures auparavant. Je vois trois facteurs de ponderation ici en rapide intuition qui pourraient etre interessant (si j'ai bien compris le probleme) :

- La distance HW minimum entre le coup N+1 et l'etage gagnant le plus proche
- La distance HL minimum entre le coup N + 1 et l'etage perdant le plus proche
- Le prorata (densite) des parties gagnantes sur les parties perdants implique par le coup N+1

Exemple : Supposons que l'un des fils de N soit tres proches de la solution (entendons plus proche que tous les autres fils) MAIS qu'il implique aussi de nombreuses parties perdantes pour ton IA. Pire l'une des parties perdante est plus proche que ta partie gagnante ! Tu en deduis que cette branche est certes proche d'un denouement mais aussi tres risquee.

Tout ces quantificateurs "Tres", "pas beaucoup" sont evidemment des allusions a comparer tous les fils entre eux. Je ne suis pas sur de savoir comment integrer fidelement le prorata des parties gagnantes dans l'histoire mais la bonne idee pour les ouvertures est l'idee du min max de toute facon avec les distances citees ci-dessus.
A chaque coup tu dois calculer d = HW - HL et t'assurer de prendre par exemple le fils qui a la distance d maximum. En cas d'egalite pourquoi pas ne pas comparer ensuite les branches qui ont une densite de parties gagnantes plus grande que les autres (par exemple).

Je vois tout à fait ce que tu veux dire. Mais comment affirmer que mon ia jouerait de manière parfaite ? Je devrais quantifier la valeur d'une configuration d'après la valeur des configurations adjacentes (N+1), alors qu'il existe des tas et des tas de configurations plus profondes?

J'ai du mal à concevoir par quel miracle mathématique cela me garantit que le meilleur choix vis-à-vis du coup N+1 est également le meilleur choix vis-à-vis du coup FINAL.

Ou alors j'ai mal compris ce que tu veux dire par "étage gagnant" (ou perdant). Est-ce que tu veux dire "étage entièrement gagnant" ? Un noeud dont tous les fils mènent à la victoire, et uniquement la victoire ?

Maintenant que je l'écris, ça m'a l'air bien^^. Mais je doute que ce genre d'étages se manifeste avant des grandes profondeurs. Et là je viens de faire tourner mon ordi 1h (C'est un ordi assez puissant), et ma simulation avec une profondeur de 12 n'a pas abouti . J'ai stoppé alors qu'il avait développé 70Mo de chemins gagnants (et je lui ai meme pas fait écrire les chemins perdants).

Par contre, avec une profondeur 8, le fichier texte est généré en 1 ou 2 secondes. Avec une profondeur 10, ça commence à être long (3 minute environs) et le fichier texte pèse 3Mo...

Bon, j'ai déjà trouvé une IA qui joue parfaitement sur 8 tours^^...

(Donc en fait, pour rectifier, je vois pas tout à fait ce que tu veux dire, contrairement à ce qu'affirmes ma première phrase^^)

Ce que je veux dire c'est que dans un arbre genere par un algorithme A* (puisque c'est ca dont on parle) il faut ponderer chaque noeud pour savoir lequel vaut mieux qu'un ordre grosso modo. Je te propose de ponderer chaque noeud par ces trois facteurs (en fait seulement deux puisque l'un est la difference des distances).

Oui ces distances ne peuvent se faire qu'apres avoir genere, etayer l'arbre car tu ne peux pas savoir a combien d'etages d'un noeud est la solution la plus rapide.

Apres est-ce que cette ponderation pas sur... comme j'ai dit il est bien de privilegier aussi la densite de parties gagnantes dans les etages enfants d'un noeud... histoire de pas se retrouver avec une solution rapide mais quasi unique qui pourrait etre tres facilement dejouee par le joueur et alors faire indubitablement perdre la partie.

Je ne suis pas expert dans le domaine. les fonctions heuristiques sont toujours des choix importants dans le parcours d'un arbre en IA.

Mais justement je ne veux pas aborder le problème de manière heuristique ; je veux résoudre le puissance 4 de manière exacte. Et je ne comprend pas comment ceux qui l'ont fait ont réussi, car je ne comprend pas comment on peut résoudre le puissance 4 sans avoir, à un moment où un autre, possédé la masse gigantesque d'information correspondant à l'arbre des possibilités complet de toutes les parties possibles du puissance 4.

(je suis Triple14)

Soit je ne te comprends pas soit c'est toi qui ne comprend pas trop ce que tu veux. Je precise que cette phrase n'est pas ironique du tout.

Il n'y a pas une maniere exacte puisqu'il n'y a pas qu'un seul choix possible a chaque iteration menant a une etat de victoire (ou alors je n'ai pas compris votre probleme). C'est pour cela qu'a un moment ou a un autre il faut bien faire parler une heuristique pour ponderer tout ca.

tu n'as pas besoin de toute les partie, tu as seulement besoin de pouvoir identifier pour une partie gagnante atteignable un coup qui mene a une autre partie gagnante. Il pourrait y avoir plusieurs coup gagnant, mais tu n'as besoin de n'en connaitre qu'un seul.

tbop2 : non je n'ai pas vraiment compris ce que je veux, dans la mesure où je n'ai pas compris tout court comment m'en sortir^^

godrik : tu veux dire qu'il faut faire en sorte de toujours rester sur une branche d'où part au moins une autre branche gagnante ?

Plus j'y réfléchis, et moins je comprend ce problème^^