J'ai ecrit ca il y a peu de temps sur un probleme similaire (mais bien plus petit)

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

Oui, je l'avais d'ailleurs lu en entier.
Mais je pense n'avoir pas tout saisi, d'autant plus que je suis pas super fort en anglais. Mais en gros tu exploites plusieurs propriétés du problèmes pour réduire la tâche de l'IA n'est-ce pas ? Je pense que j'en suis à un stade inférieur : j'essaie de comprendre ce que doit faire mon IA avec son arbre incomplet des parties possibles.

Mais j'avance, j'avance. Je reviendrai poster après avoir testé diverses choses.

Merci de vos aides !

La question a laquelle il faut pouvoir repondre est: quel est l'information minimal qu'il faut pour pouvoir jouer une partie parfaite?

Avoir une liste de toutes les partie possible annote avec "gagnant" ou "perdant" est suffisant (certainement pas minimal) pour repondre a la question. Mais en fait tu n'as pas besoin de toutes les parties possible; mais juste de tous les tableaux possibles. (Deux partie differente peuvent ammener au meme tableau.) En fait, tu n'as pas besoin de tous les tableau possible, juste de tous les tableau ATTEIGNABLE. Certaine configuration ne sont pas atteignable parceque ton IA ne les jouera pas. Tu peux aussi exclure celle la.

Apres il te faut un moyen pour stocker ton information. le plus simple est certainement de stocker toutes l'information dans une table de hashage. Comment generer cette table de hashage est aussi important. Il ne faut certainement pas la generer "en largeur", mais "en profondeur". Si tu ne connais pas la difference, google la question. Le plus tot, tu realisera qu'un coup est gagnant, le plus tot tu peux arrete d'explorer cette branche de l'arbre.

Quand j'ai lu ton article sur ton jeu "cassis", j'avais effectivement envisagé d'investiguer sur les tableaux plutôt que sur les parties. Puis j'avais abandonné, parce que trouver quels tableaux sont atteignables et lesquels ne le sont pas était plus difficile que de trouver quelles parties sont jouables et lesquelles ne le sont pas (les seules conditions étaient que les joueurs jouent chacun leur tour et que la partie s'arrête en cas de puissance 4 ou de tableau plein.

Mais maintenant que je suis un peu dans une impasse avec ma première méthode, je vais devoir revenir en arrière et essayer comme tu dis, en cataloguant les configurations atteignables du jeu. Et puis au moins, là, je vois comment exploiter la symétrie du jeu par rapport à la colonne n°3 ^^

Je reviendrai poster si j'ai des résultats

Il y a beaucoup plus de partie que de tableau. Ca fait exploser la combinatoire beaucoup plus vite de travailler sur les parties.

Je suis d'accord qu'il y a moins de configurations possibles que de chemins possibles, puisque plusieurs chemins différents peuvent mener à une même configuration, tandis que deux configurations naissent forcément de deux chemins différents.

Autre problème : comment construire un tableau selon les règles du puissance4? La seule chose facile à dire est que, le nombre de pièces du joueur qui a commencé est toujours soit égal au nombre de pièces du deuxième joueur, soit de 1 plus grand. Mais sur la seule base de cette constation, on ne peut pas générer un tableau qui reflète une partie possible d'un puissance 4. Pour l'instant, la seule manière que j'ai trouvée pour générer un tel tableau, est de faire jouer la partie, puis de stocker la configuration tout à la fin dans le tableau... C'est justement sur ça que je réfléchis en ce moment (quand je m'ennuie en cours^^) : trouver un algorithme qui génère un tableau qui soit FORCEMENT le reflet d'une configuration possible d'un jeu de puissance 4.

Ah oui, autre chose facile à dire, c'est qu'une case du tableau ne peut jamais être remplie si celle du dessous n'est pas déjà remplie (gravité). Sauf si c'est la dernière^^ Mais ça ne suffit toujours pas.

Bonjour,

Je sais que c'était 2012 mais, les âneries il y en a trop.
Faire tous les cas possibles est trop énorme.
Ensuite, il est inutile d'enregistrer tous les cas possibles ! Vous avez du temps à perdre.
Il faut utiliser l'algorithme Min-Max avec élagage alpha-bêta.
Fonction d'évaluation : 0 j'ai perdu, 1 j'ai gagné par exemple.
PS: Inutile de parcourir toute la grille pour savoir si vous avez perdu ou gagné, regardez juste le dernier jeton posé et posez-vous la question : est-ce que, celui-ci permet de faire un alignement de 4 ?
Jusqu'à une profondeur de 8 ou 10 environ c'est rapide, après ça commence à être long...

Cordialement.

Et aussi, il n'y a pas tant de tableau que ca. Je n'avais pas compter a l'epoque, mais pour une colone il y a moins \sum_{i=0}^6 2^i = 2^7 combinaison. Comme il y a 7 colones, ca donne moins de (2^7)^7 combinaisons. Soit moins 2^49=562T combinaisons. Quand tu comptes les symmetries ca retire un facteur 2.

Et quand tu va prendre en compte le fait qu'il y a autant de pion blanc que noir, ca va retirer BEAUCOUP de combinaison la encore. Ca c'est un peu plus difficile a estimer. Mais sur une grille complete, il y a 2^42=4.3Tcombinaison pour 2 colorer. Mais seulement 42!/((42-21)!21!)=538Gcombinaison qui ont le meme de blanc et noir.

Si on garde le meme ratio de 8 sur la 2 coloration et de 2 par symmetrie. Il reste en gros 32Tcombinaison interessante. Alors c'est beaucoup c'est sur. Mais ce n'est pas infaisable. En particulier, tu peux ne stocker que un coup sur x qui diminue en gros le volume a stocker par un facteur x. Mais tu paye le recalcul au runtime.

Donc je pense qu'en moins de 10TB, tu dois pouvoir arriver a construire un index utilisable. Et c'est quoi les prix aujourd'hui? 8TB c'est $250. Donc avec une machine de moins de $2000, tu peux craquer le probleme. Bon, il faut aussi generer l'index, ce qui peut etre long avec une seule machine, mais tu peux craquer le dernier etage du probleme avec EC2.

Toutes les questions ne sont pas completement regler. Mais ca ma l'air faisable.

Je me permet de up aussi

Le 20 décembre 2015 à 09:05:16 ]Titoune[ a écrit :
Bonjour,

Je sais que c'était 2012 mais, les âneries il y en a trop.
Faire tous les cas possibles est trop énorme.
Ensuite, il est inutile d'enregistrer tous les cas possibles ! Vous avez du temps à perdre.
Il faut utiliser l'algorithme Min-Max avec élagage alpha-bêta.
Fonction d'évaluation : 0 j'ai perdu, 1 j'ai gagné par exemple.
PS: Inutile de parcourir toute la grille pour savoir si vous avez perdu ou gagné, regardez juste le dernier jeton posé et posez-vous la question : est-ce que, celui-ci permet de faire un alignement de 4 ?
Jusqu'à une profondeur de 8 ou 10 environ c'est rapide, après ça commence à être long...

Cordialement.

En même temps, c'est probablement le moyen de plus connu pour résoudre une partie de puissance 4. C'est exactement ce que j'avais fait dans le cadre d'un projet scolaire, et ça marchait plutôt bien (même si je doute qu'il était imbattable, notamment car il est possible de piéger des colonnes et d'avoir 1 chance sur 2 de gagner à la fin. Mais je crois qu'on peut intégrer ce problème à la fonction d'évaluation aussi)

Pour la fonction d'évaluation j'avais quand même fait quelque chose de plus complet que -1, 0 ou 1, mais quelque chose d'assez intuitif

Je ne m'y connais pas vraiment mais je crois que tu as raison, il faudrait cataloguer toutes les parties possibles, cependant je ne crois pas que ton programme doivent à chaque fois explorer toutes les possibilité.
Il "suffirait" que tu enregistre chaque positions comme Gagnante, Perdante ou Neutre.
Une position est gagnante si elle est reliée à au moins une position perdante, une position est perdante si elle est uniquement relié à des positions gagnante et une position est neutre si elle forme un "cycle".
Ton programme doit ensuite toujours choisir une position gagnante.

Ouais c'est ce que j'ai fait pour l'IA de cassis. Je ne stocke dans la base centrale qu'une seule reponse pour chaque etat du jeu. Et je ne garde que les etats du jeu qui sont atteignable compte tenu de la reponse que l'IA fait.
On pourrait ammener ca plus loin et explicitement essayer de ramener le jeu dans une position qui est deja stocke pour minimizer encore plus la taille de l'index.