La disposition des jetons pour le logiciel peut être très simplement stockée dans un tableau 7*7, avec une valeur pour les jetons de chaque joueur plus la case "vide". Vu la faible taille du terrain de jeu, il est probablement inutile de rechercher des systèmes de numérotation exotiques (comme aux dames ou au checkers par exemple).
Par contre, il est préférable que le joueur humain donne ses coups uniquement par le numéro de la colonne, la gravité faisant le reste. Cela réduit considérablement la taille des routines de test de légalité des coups.
Ce type de jeu de réflexion est généralement le terrain de prédilection des algorithmes à arbre de recherche style mini-max ou alpha-béta. Ces méthodes dépendent fortement de la qualité de la fonction d'évaluation et de la profondeur de la recherche, mais elles ne se prêtent pas très bien à une application simple des méthodes d'apprentissage. En effet, je suppose qu'on se situe dans le cas d'un apprentissage par renforcement, où l'on ne connaît pas la stratégie optimale, et où la seule donnée en entrée est la victoire ou la défaite.
Dans le cadre des algorithmes mini-max et apparentés, le seul apprentissage possible, c'est le réglage de la fonction d'évaluation. Or il est difficile de déterminer avec précision quel(s) coup(s) a(ont) assuré la victoire : je n'ai aucune idée pour implémenter un algorithme de rétro-propagation des poids dans le cadre du puissance 4.
Il serait plus intéressant du point de vue de l'apprentissage d'utiliser un algorithme jouant au coup par coup, mais qui apprendrait à identifier les configurations dangeureuses et / ou gagnantes, et qui essaierait de les éviter / jouer autant que possible. Si des coups paraissent équivalents, alors on en joue un au hasard (recuit simulé). Au bout d'un grand nombre de parties avec des joueurs intelligents (ou des IA avec des algorithmes qui comprennent beaucoup de règles), il serait intéressant de comparer la base de données des coups appris avec les règles couramment admises. La référence la plus complète que j'ai pu trouver en la matière est la thèse de Mr Allis ou spécifiquement pour le jeu puissance 4, ici.
Donc, l'algorithme proposé comporterait:
Il est évident que certaines configurations peuvent mener aux 2 résultats , c'est pourquoi on affecte une valeur à chacun de ces config : chaque victoire incrémente la valeur de la configuration de +V, chaque défaite la diminue de D. Les configurations qui mènent sûrement à la victoire seront donc toujours positives, et vice-versa.
|
|
|||||
|
|
|
|
à savoir les alignements de 2 pièces ennemies (si elles sont non bloquées : voir les blancs ici),
|
|
|
|
|||
|
|
|
|
|
ou de 3 pièces ennemies (si l'alignement est bloqué d'un côté).
S'il n'y a pas coup forcé par l'adversaire (cause de danger immédiat), alors on recherche dans la base de données des coups gagnants s'il n'y a pas eu une situation analogue (par symétrie). Sinon, on cherche à allonger tout alignement de jeton susceptible d'atteindre la longueur 4 (on ne va pas se bloquer tout de même). On essaie aussi d'éviter les configurations perdantes.
La valeur estimée du coup est obtenue en sommant la valeur du coup d'après la base de donnée avec les alignements qu'on obtenient ainsi. Si plusieurs coups sont possibles, alors on choisit au hasard parmis les coups légaux.
Si l'adversaire a des alignements dangereux (cf ci-dessus), on utilise la même méthode, mais restreinte aux coups évitant la défaite certaine.
Cette méthode d'apprentissage est très robuste : elle apprend à déjouer / utiliser les combinaisons dangereuses quel que soit le style de l'opposant.Il faut juste que l'adversaire ne perde pas volontairement les parties, car cela fausserait la qualité de la base.
En revanche, cette méthode est très lente, mais vu l'objectif énoncé (trouver de nouvelles règles, de nouvelles stratégies), c'est indispensable. On peut influencer sur la direction d'apprentissage en changeant les valeurs relatives des paramètres : si on veut favoriser la découverte de combinaisons inconnues, alors il faut diminuer les valeurs de la base de données par rapport à l'évaluation positionnelle (alignements). Si on veut augmenter le nombre de victoires / nulles, il suffit au contraire d'augmenter l'importance des coups passés, voire augmenter la profondeur de la mémoire.