Puissance 4, qui aura la meilleure IA ?

Hum… Faudrait que je convertisse ce que j'avais fait pour un tic-tac-toe vu que la seule différence c'est dans les coups jouables.

Après, les heuristiques ne font pas grande différence dans/face à un negamax passé 2-3 coups de profondeur dans la recherche – j'avais pu tester la chose dans mes TPs de lisp il y a pfff 18 (/19?) ans (bXrdXl!).

PS: si vous cherchez des idées d'IA qui posent un petit peu plus de challenge que ce qu'il y a dans les jeux classiques & simples à deux joueurs (reverso, puissance IV, tic-tac-toe), vous avez aussi les jeux de plateau d'aujourd'hui -> Ricochet Robot, Mr Jack Pocket, …

Bonsoir,

Plusieurs questions et propositions avant que je ne me décide à balancer mon IA :

1. Est-ce que tu prends le java ?
2. Je n'ai pas encore regardé comment le MJ est fait en détail, mais ne serait-il pas plus simple pour tout le monde de communiquer via stdin/stdout uniquement (pas de fichier temporaire) et de ne lancer les programmes des IA qu'une seule fois ? Par exemple comme le pseudo-code que je donne en fin de post ?
3. Il me semble avoir déjà lu que pour le P4, le deuxième joueur était désavantagé. JE pense donc qu'il faut prévoir des matchs aller et retour. ET même si personne n'est avantagé dans des jeux futurs, à mon avis c'est quand même mieux. Ca t'évite d'avoir des choix random
4. Le random, justement, je pense que ça devrait faire partie des choses interdites. Pour que ça soit intéressant et surtout pour qu'on puisse progresser tous ensemble, il faut absolument que les matchs soit reproductibles sans dépendre de l'heure ou de la météo. Pas parce qu'on ne fait pas confiance au MJ, mais bien pour, une fois le concours terminé, rejouer les résultats soi-même chez soi, voir comment les autres on fait, modifier son IA et comprendre comment on aurait pu faire mieux.

Pseudo-code de ma question 2 et explications :

1
2
3
4
5
6
7
8
9

ia1 = exec(......)
ia2 = exec(......)
IA1.print("start\r\n")
while(......)
coup1 = ia1.read()
ia2.print(coup1 +"\r\n")
coup2 = ia2.read()
ia1.print(coup2 + "\r\n")
end while

Bien sûr je fais ici abstraction des vérifications pour savoir si les retours sont valides et si les coups choisis sont légaux.

Avantages pour les joueurs:

• On peut représenter sa grille en interne de la façon qu'on souhaite, et c'est notre propre responsabilité
• Les programmes ne sont pas quittés entre chaque coup, ce qui fait qu'on est pas obligé de stocker des informations dans des fichiers, ni de parser des fichiers. En clair ça fait moins de bouts chiants à coder (parce que s'amuser à parser des fichiers, franchement, c'est presque toujours très chiant) et on peut réellement passer tout son temps uniquement sur l'algorithme de l'IA.
• Vu qu'il n'y a pas de fichiers à traiter nulle part, ça sera beaucoup plus rapide
• Ca sera aussi plus sûr pour toi… tu vois un fopen dans le code, bam, disqualifié, pas de question à se poser si c'est un fichier autorisé ou pas, si ça peut être de la triche ou pas

Très intéressant comme petit jeu.

Je suis d'accord avec QuentinC pour les matchs allez-retour et pour le fait de pouvoir reproduire les matchs.

Une manière de retirer l'aléatoire, ça serrait que tout le monde utilise le même générateur avec la même clé. L'aléatoire peut être utilile dans le cas où on doit choisir entre 2 coups dont on calcule qu'ils ont la même probabilité.

Puissance 4 c'est un peu out of date pour les IAs …

Il y a un algo qui te fais forcément gagner si tu commence … (Si j'ai le temps je le mettrai sur mon github)

En gros tu commence : tu gagne, tu ne commence pas : tu perds x). Donc il n'y a plus beaucoup d’intérêt de faire une compétition …

EDIT : http://www.ce.unipr.it/~gbe/velena.html

@QuentinC

Est-ce que tu prends le java ?

Yep

mais ne serait-il pas plus simple pour tout le monde de communiquer via stdin/stdout

C'était une solution aussi effectivement. Mais débutant en python et peut habitué à la manipulation de process, j'ai joué la carte de la facilité. Après rien n’empêche de s'inspirer du MJ pour son parseur (pour ceux qui prog en python vous pouvez carrément l'importer )

Il me semble avoir déjà lu que pour le P4, le deuxième joueur était désavantagé

C'est vrai. Bonne idée que de faire des matchs Aller Retour

Le random, justement, je pense que ça devrait faire partie des choses interdites

L'humain est-il toujours prévisible ? Plus sérieusement, j'ai proposé un joueur random uniquement parce que j'ai pas codé d'IA, donc ca permettait quand meme de tester le MJ de mon côté et pour vous d'avoir un truc bête et méchant a affronter au début.

… une fois le concours terminé, rejouer les résultats soi-même

C'est aussi pour ca que tout "l'historique" d'une partie est sauvé (grille et dessin). Ca permet d'analyser le match pour débugguer ton algo si besoin.

Pour tout les derniers points, je suis d'accord avec toi. Encore une fois, on touche là à ma faiblesse de niveau en Python, j'ai choisi une solution de simplicité. (Par contre une fois le fichier parsé tu représentes en interne comme tu veux !)

@Choups314

J'ai conscience que le puissance 4 c'est un peu facile. Seulement commencer par là à plusieurs intérêt :

• Pour ma part, c'était un bon exercice d'application
• Le puissance 4 est (universellement ?) connu, pas besoin de faire un poste de 3 kilomètres pour expliquer les règles et aucune zone d'ombre dans ces dernière. C'est idéal pour un premier essai. Et en plus c'est simple à coder pour le MJ !
• Oui, c'est cheaté. Mais on est là pour s'amuser, rien à gagner ! Si tu penses que le défi est trop simple, essai de le faire dans un autre langage ou essai de t'interdire l'algo ultime en prenant d'autres approches ?
• Enfin, c'était aussi pour moi un très bon moyen de prendre la température vis à vis de ce genre d'exercice. Si ce dernier plait, je serais (ou qqun d'autre) plus motivé pour en proposer d'autres (car ca prend du temps à organiser et préparer tout de même). Si au contraire ca ne marche pas, tant pis !

(Et si vraiment ca plait, pour plus tard j'ai d'autres idées de jeu qui n'ont pas forcément de "solution ultime". Tu pourras participer à ce moment si jamais le P4 te motive vraiment pas )

J'adore le concept
C'est juste que le puissance 4 … il y a une solution ultime

En tout cas si tu organise un tel défi pour un autre jeu, je serais ravi de participer

Faudrait interdire l'utilisation de fichier aussi dans l'IA, sinon j'implémente la stratégie gagnante grâce au fichier que l'on peut trouver ici :

http://archive.ics.uci.edu/ml/datasets/Connect-4

Et pour ceux que ça intéresse :

Pour ma part, j'avais fait une implémentation Ocaml du min-max ou de l'alpha-beta il y a un an en speed. Si je retrouve le projet, je mettrais à jour mon post. Mais elle n'était pas très efficace et je n'avais pas eu beaucoup de temps.

Edit :

Voici mon IA en Ocaml (code non retouché :

Et pour le projet en entier :

Bonsoir L'idée est plaisante. As-tu plus ou moins défini un planning ? Deuxième point : JE vois certaines personnes qui seraient intéressées, mais qui disnet que le jeu n'a aucun intérêt car il existe de la littérature qui donne l'algorithme qui gagne à tous les coups. C'est vrai que ça limite l'intérêt du challenge. Alors je propose dès maintenant une adaptation du jeu. Joueur1 joue le mouvement n°1 Joueur2 joue le mouvement n°2, puis le mouvement n°3 Joueur3 joue le mouvement n°4, puis le mouvement n°5 … ET ainsi de suite,2 mouvements à chaque fois pour chaque joueur.

Peut-être qu le jeu est moins intéressant, je n'ai pas testé. Mais au moins, il n'y a pas de littérature sur le sujet.

Autre variante archi-simple à mettre en place côté 'Maitre du jeu' : jouer sur une grille avec 8 colonnes et 6 lignes, au lieu de 7 colonnes.

La première variante déséquilibre beaucoup trop le jeux à mon goût
En revanche, la deuxième variante est plus intéressante (mais il faudrait alors 9 colonnes. Un nombre pair dénaturerait également beaucoup le jeu). Mais bon, il est possible d'adapter Velena pour une telle grille .

Je ne pense pas que changer la taille de la grille fera beaucoup de différence pour les algos type minimax. Ca empêchera juste de reprendre la base de donnée telle quelle.

Pour le coup, j'avais trouvé le challenge pierre papier ciseaux beaucoup plus marrant, à son époque sur le SDZ v3. J'en avais proposé un autre pour un autre jeu un peu dans le même style, le jeu des cow-boys, mais j'avais abandonné parce qu'il n'y avait pas eu assez de participants (pour le PPC, j'avais gagné mais on était seulement 4 ou 5)

«Le jeu a été résolu de façon exacte en 1988, par James D. Allen, et indépendamment par Victor Allis1, à quelques jours d'intervalle (1er et 16 octobre 1988), avec des calculs informatiques. Le premier joueur (celui qui commence la partie) peut s'assurer la victoire s'il joue les coups adéquats.

Le seul premier coup gagnant est celui dans la colonne centrale. Un premier coup dans les colonnes adjacentes permet au second joueur d'obtenir une partie nulle, et un premier coup dans l'une des 4 autres colonnes extérieures permet carrément au second joueur de remporter la victoire (à condition qu'il joue parfaitement).»

Cf. wikipédia

Cf le moteur Velena pour voir l'algo en question

Attention, il faut quand même une grosse config pour exécuter Velena

Il tourne sur une tablette Android sans problèmes
Après tout dépend de ce que l'on entend par grosse config

C'était du troll, 4Mio de RAM c'est très 1990 tu ne trouves pas? ^^' (Regardes en bas de la page que j'ai linké)

Ha ok, je pensais que tu étais sérieux …

Je veux bien être un peu pingre, mais, 4 Mio et un processeur IBM-compatible, je pense que c'est passé en dessous des standards il a a peu près 20 ans

Ca ne changera effectivement rien du tout. Une fois qu'un negamax est implémenté, il marche sur les jeux à deux. La différence, c'est le niveau de profondeur que l'on accepte de mettre, et éventuellement l'heuristique employée pour évaluer les nœuds non gagnants. Et un puissance 4, avec une profondeur de 2 et sans heuristique, cela devient compliqué pour un humain qui joue du tac au tac sans trop réfléchir, et quasi impossible avec une profondeur de 3 et sans heuristique toujours.

Un tic-tac-toe rajoute un peu plus de complexité pour la machine : il y a vite beaucoup plus de coups à évaluer, et il devient nécessaire de restreindre la profondeur de la recherche pour réagir assez vite. Alors du coup, on se dit, facile, "il suffit de limiter le temps de recherche de chaque coup". Sauf que cela va pénaliser les langages de scripts (comparativement aux langages compilés de type C ou C++), ou qu'au final la modélisation du jeu et de son IA va être moins compliquée qu'une recherche sur la parallélisation de l'algorithme.

Bref, sur ce type de jeux, vous allez voir s'opposer des negamax avec élagage alpha-beta pour les plus évolués qui font dans le classicisme. Et si le jeux devient très compliqué, on va commencer à voir apparaitre des BDs de coups (échecs, ou quand il y a une preuve de solution gagnante: velana).

Après on peut interdire les fichiers de config (pour interdire velana donc), mais cela va aussi interdire des approches intéressantes issues du Machine Learning (je pense au Reinforcement Learning qui avait été appliqué avec succès, IIRC, au go et au backgammon).

Bref, le principe est super intéressant, mais proposer des matchs/tournois équilibrés n'est pas si simple.

Je veux bien être un peu pingre, mais, 4 Mio et un processeur IBM-compatible, je pense que c'est passé en dessous des standards il a a peu près 20 ans

En 94 ? Hum … Je crois bien que j'avais 16Mo et un pentium 195 (Mhz)

Au passage, ca pourrait ptet vous intéresser : https://www.coursera.org/course/ggp

On a jusqu'a quand ?

A peu près n'importe quand… mais vu l'engouement global pour ce jeu en particulier…