Intelligence artificielle pour puissance 4

Une première idée, je ne sais pas du tout ce qu'elle vaut, il faudra surement en essayer plusieurs avant de trouver la meilleure (tu fais jouer deux ordinateurs l'un contre l'autre et tu regardes ce qu'il se passe)

Pour chaque combinaison possible, tu comptes le nombre d'alignements "complétables", c'est à dire ceux qui peuvent être prolongés jusqu'à 4 dans chaque sens. Par exemple en comptant k^2 points pour un alignement de k jetons, puis en faisant la somme

Avec cette grille :


Pour les rouges : 1+1+1 (vertical) + 9+1 (diagonale gauche) + 1+4 (diagonale droite) = 18


Pour les jaunes : 4+1 (vertical) + 9 (diagonale gauche) + 1 + 1 + 4 (diagonale droite) = 20


En utilisant ces calculs on pourrait donc donner un avantage aux jaunes de 2 points.
Si l'ordinateur est jaune il considérera cette grille avec une valeur +2, sinon avec une valeur -2.
Le but étant bien sûr de maximiser cette valeur et de choisir au final la colonne qui permet d'atteindre ce maximum.

Remarque : pour un même maximum il peut y avoir plusieurs manière d'y arriver, par exemple si n=3, on peut mettre successivement un jeton en A puis en B, et obtenir parfois la même valeur que si on avait joué B puis A, à condition que l'adversaire est bien joué la même chose dans ces deux cas, ce qui est évidemment incertain.
Il serait donc intéressant de ne pas considérer que le maximum, mais de prendre également en compte (à plus ou moins grande échelle) l'ensemble des valeurs qui peuvent être obtenues en jouant telle ou telle colonne afin de choisir au mieux.

Exemple si on a un maximum M que l'on peut obtenir en jouant en A ou en B, on pourrait choisir entre A et B en considérant par exemple la moyenne des valeurs si on joue en A et la moyenne des valeurs si on joue en B. On visera donc toujours le maximum, mais s'assurant une moyenne plus importante.

Il ne s'agit pas vraiment de probabilité.

Dans l'intelligence artificielle, tu dois toujours trouver un moyen d'évaluer la qualité d'une solution. Il faut donc que tu puisses convertir toute une grille en un seul nombre, qui doit te permettre d'évaluer si elle meilleur qu'une autre.

Je t'ai donné un exemple de comment on pourrait obtenir ce nombre, en faisant la somme des k^2 pour chaque joueur, et la différence entre l'adversaire et toi.
Mais ce n'était qu'un exemple, tu peux trouver une autre manière de faire, peut-être plus simple, peut-être meilleur. Mais le principe doit toujours être le même. Il faut pouvoir comparer deux grilles et savoir laquelle est la plus à notre avantage.

Ensuite vient l'algorithme de recherche en lui même, qui va parcourir les différentes grilles possibles, ce que je t'ai proposé est le plus simple, tu considères toutes les solutions possibles et tu ne gardes que la meilleure. D'autres algorithmes sont plus intelligents, il se dirigeront vers une première solution un peu meilleure et par différentes méthodes, se diriger vers une autre solution encore meilleure, jusqu'à obtenir la meilleure, ou au moins une des meilleurs solutions.

Concrètement, il te faut donc deux méthodes indépendantes :

// détermine quelle est la valeur de la grille
double valeur(Grille g);

// trouve la meilleur colonne où jouer à partir de la grille g
int meilleur(Grille g);

Evidemment la deuxième méthode utilisera la première afin de trouver la valeur maximale.

Aaah oui! Je vois mieux maintenant! :D
En fait, dans votre exemple, si l'ordi est jaune, il est dans une position avantageuse puisque la différence est positive. Par contre si l'ordi est rouge, il est désavantagé, il doit donc trouver un moyen de rendre la différence positive ou nulle en essayant de couvrir la colonne où le joueur adversaire a plus de chance de gagner. Et ce moyen là est, dans votre cas, la fonction meilleur() si j'ai bien compris.
Je vais tester ça, et je vous tiendrais au courant. Merci pour les explications.

Pas tout à fait.

Au départ on a une grille, qui est l'état courant du jeu.

Puis l'ordinateur va simuler un ensemble de prochains tours possibles.
Par exemple si on anticipe sur n=3 tours on pourrait avoir une combinaison (5, 2, 6) qui signifie "je joue 5, l'adversaire joue 2, je joue 6".
Ce qui nous intéresse c'est la valeur de la grille après que ces n coups aient été joués.
Si la valeur maximale de la grille est obtenue avec une combinaison (x, y, z), alors l'ordinateur devrait jouer x (cela vient du fait que l'on choisit justement le calcul de la valeur pour ça).

Tout ça c'est le principe de l'intelligence artificielle. Après il y a deux choix à faire :
1) comment calculer la valeur de la grille de manière à avoir le meilleur coup à jouer quand on aura trouvé le maximum
2) comment sélectionner les combinaisons possibles à calculer de manière à trouver le maximum.

Le principe de la force brute, c'est qu'on va faire toutes les combinaisons possibles sans exception. Par exemple sur n=3 tours, on va avoir 7^3 combinaisons à tester que sont :
(1,1,1), (1,1,2) ... (1,1,7), (1,2,1), (1,2, 2) ... (1, 7, 7), (2, 1, 1), ... (7,7,7)

Malheureusement si cette technique est infaillible pour trouver le maximum, elle est coûteuse pour de trop grandes valeurs de n. C'est pour cela que d'autres techniques plus sophistiquées existent, mais dans ton cas la force brute devrait suffire si tu te limites à de petites valeurs de n.