Un jeu en tour par tour en Flash

Ce jeu fait partie de la saga des Graphes. Voir les liens dans le menu à droite pour plus de détails

Le résultat

Fichier Flash :

Images

Passez votre souris par dessus une image pour l'afficher.

Version α

Capture de C-Graphe

Version β

Capture de C-Graphe

Fond retenu

Le fond de l'application est généré dynamiquement à l'aide de bruit de Perlin. Il n'y a donc pas de fichiers image comme pour les autres jeux.

Explications

Règle du jeu

C-Graphe est un jeu :

Opposant deux joueurs ou deux équipes (ou seul contre un ordinateur « intelligent »)
Dans lequel les joueurs ou équipes jouent à tour de rôle
Dont tous les éléments sont connus (jeu à information complète)
Où le hasard n'intervient pas pendant le déroulement du jeu

Il s'agit en conséquence d'un jeu de stratégie combinatoire abstrait, qui se joue sur un graphe avec deux noeuds spéciaux (les extremités) et qui oppose deux joueurs (dénommés Coupheur et Paintre).
Pendant son tour, Paintre colore un trait existant.
Pendant son tour, Coupheur supprime un trait existant.

Si Coupheur réussit à séparer le graphe en deux graphes distincts (chacun contenant une extremité), alors Coupheur gagne.

Si Paintre réussit à connecter les deux extremités par des arêtes colorées, il remporte le jeu.

A propos du concept

Ce jeu est directement inspiré d'un jeu de graphe : «Shannon Switching Game». Le jeu est le même, les deux joueurs se prénommant dans la version originale Short et Cut.

L'intelligence artificielle

Le problème du jeu était de créer une intelligence qui ne soit ni imbattable, ni complètement crédule

Mathématiquement, il existe des algorithmes qui permettrait d'assurer la victoire à l'ordinateur : je renverrais le lecteur curieux vers ce PDF, ou vers l'article d'IBM An implemented graph algorithm for winning shannon switching game. Cependant, l'interêt de jouer contre un ordinateur imbattable est extrêmement restreint, de même que de jouer contre un ordinateur incohérent avec ses précédentes actions.

Face à ce dilemme, j'ai choisi d'imiter le comportement humain, et voici donc un résumé de la façon qu'à votre PC de comprendre le jeu.
Basiquement, l'ordinateur calcule une liste de chemins et joue l'arête qui est présente dans le plus de chemins.
Ce comportement est bien entendu plus raffiné, puisqu'il fait en sorte de pondérer chque arête en fonction de la taille du chemin et de quelques autres paramètres, tels que le nombre de coups déjà joués « dans la zone ».
Cette IA calcule tous les chemins possibles dans la carte, en faisant bien évidemment en sorte de ne pas prendre de doublons ou de chemins inutiles (ainsi, faire une boucle est complètement inutile, de même que repasser par une arête déjà utilisée dans le chemin).
Une fois cette liste de chemins déterminées, toutes les arêtes sont examinées et pondérées en fonction de l'inverse de la taille du chemin. Une chemin qui comprend trois arête affectera chaque arête d'un coefficient 1/3, qui s'ajoutera à tous les autres chemins qui passent par là. Si une arête du chemin a déjà été jouée, elle ne compte pas dans la taille : autrement dit, un chemin de taille 5 qui contient 2 traits joués par Paintre ajoutera aux trois autres lignes un coefficient d'un tiers.
Enfin, l'ordinateur récupére dans la liste des arêtes celle qui a le plus gros coefficient, et la joue.

Après plusieurs tests, il s'est avéré que l'IA la plus réactive et dont les comportements étaient les plus intéressants était celle que j'avais affectueusement nommée la carrée.
Celle-ci, au lieu de donner à chaque arete l'inverse de la taille du chemin, affectait l'inverse du carré de la taille du chemin : 1/9 pour un chemin de taille 3. Cela permettait de minimiser au maximum les chemins trop longs pour être envisagés, puisque le poids d'un chemin décroit au carré.

Sur cette idée de base s'ajoutent plusieursconcepts, tels que la détermination des arêtes inutiles, e.g la structure ----------o----------- qui est proprement injouable : jouer un trait d'un côté forcera l'autre joueur à couper le second coté, n'amenant rien au jeu. Des cas plus complexes sont aussi envisagés, afin de minimiser au maximum les incohérences et les tours "stupides".

Vous pouvez voir l'intelligence artificielle à l'oeuvre en activant le mode DEBUG (mettez la valeur correspondante dans le fichier Const.as). Vous trouverez aussi des swf en mode débug dans toutes les versions de sauvegarde précédant la 8.
Ce mode affiche le poids de chaque arête ainsi que les arêtes "non utilisables".

Téléchargement

Dernière version :

Voir le fichier SWF, et le code.

Sauvegardes

Les sauvegardes sont réalisées sur une base plus ou moins régulière, lorsque le code a été amélioré significativement depuis la sauvegarde précedente.
Dans le cas de C-Graphe, le code a été développé de façon sporadique sur plusieurs mois, d'où les intervalles entre sauvegardes. Chaque sauvegarde contient une version swf du jeu tel qu'il était à l'époque.

Historique des versions

Démarrage du codage : 10/10/08
Version α : 20/10/08 (Testeurs : Damien, Patrick, Amélie, Clément, Damien, Clotilde, Etienne P.)
Version β : 1/02/09 (Testeurs : XHTML_Boy, Jean Martin, MyGB, Morgan, M.A, Yannish, Sylvain, Geoffrey, Nico, Etienne V.)
Version RC-1 : 8/02/09 (Testeurs : Tefandil, Laurie, Membres du SDZ)
Version anglaise : traduction par Yannish (1/03/09)

Le code

À propos du code

Le code est réparti en classes claires et nettes.
L'ensemble du fichier représente moins de 10ko !

Afin d'éviter l'engorgement du serveur, le code a été décentralisé sur une page externe.