Stratégie de jeu au Connect 5
Le 5 en ligne est un jeu qui se joue à 2 sur une grille de taille
Le projet se décompose en plusieurs étapes. La première est la création du jeu pour que deux personnes puissent s'affronter. Puis, vous ajouterez une ou plusieurs stratégies de jeu pour pouvoir jouer seul. Enfin, vous ferez jouer vos stratégies les unes contre les autres.
NxN. À tour de rôle, les joueurs posent un pion de leur
couleur jusqu'à ce qu'un joueur réussisse à aligner 5 pions de sa
couleur. Ce joueur a alors gagné la partie.
Remarque : rien dans le sujet ne spécifie que
les pions soient soumis à des mouvements quelconques
(potentiellement la gravité) après avoir été posés. Par contre,
l'ensemble des pions doit toujours former un ensemble connexe.
Le projet se décompose en plusieurs étapes. La première est la création du jeu pour que deux personnes puissent s'affronter. Puis, vous ajouterez une ou plusieurs stratégies de jeu pour pouvoir jouer seul. Enfin, vous ferez jouer vos stratégies les unes contre les autres.
Jouer seul
-
Préparation
Vous devez définir des types de données pour gérer la grille, les coups, les joueurs. -
Afficher une grille de jeu
La grille de jeu, avec les pions posés, doit être affichée dans le terminal à l'aide la bibliothèquencurses. -
Joueur contre joueur
La première version de votre programme permettra à deux joueurs de s'affronter. Vous devrez être capable d'appliquer un coup à une grille, pour les deux joueurs. Un coup correspond au placement d'un pion d'un joueur à une position donnée sur la grille. -
Détection des fins de parties
Votre programme doit être en mesure de détecter quand la partie est terminée. Deux cas de figures : soit un joueur à réussi à aligner 5 de ses pions, soit la grille est pleine et il y a match nul (ou alors le joueur gagnant est celui qui a le plus de lignes de 4).
Gagner contre l'ordinateur
Stratégie aléatoire
Avec ces éléments, votre programme est capable de faire jouer deux personnes l'une contre l'autre. Maintenant, vous allez introduire un joueur virtuel qui se contentera de joueur aléatoirement. Pour cela le programme cherchera la liste des coups possibles. Il choisira ensuite au hasard dans cette liste un coup, et le jouera. Il ne devrait alors pas être trop dur de gagner contre l'ordinateur.Stratégie min-max
Maintenant que vous pouvez jouer contre l'ordinateur, vous allez ajouter une nouvelle stratégie : la stratégie min-max. Vous devrez être capable évaluer un état de jeu (pions joués), et ainsi savoir si pour un joueur donné, un état est plus favorable qu'un autre. Choisir la meilleure évaluation pourra permettre à l'ordinateur de prendre une meilleure décision qu'avec l'algorithme aléatoire. L'inconvénient de la stratégie précédente est qu'il n'y a aucune anticipation. Pour corriger ce défaut, vous appliquerez l'algorithme min-max qui exploitera pleinement votre fonction d'évaluation. Pour cela, vous aurez besoin de pouvoir annuler un coup joué. Votre programme offrira la possibilité de choisir un niveau de difficulté pour le joueur affrontant l'ordinateur.Élagage alpha-beta
L'algorithme min-max a un coût important qui peut diminuer en appliquant la technique de l'élagage alpha-beta. Elle permet de réduire le nombre d'évaluation et donc d'augmenter le nombre de coups prévus par l'ordinateur pour un même temps de réaction. Il peut être envisageable d'ajouter cette technique à la stratégie précédente pour augmenter sa vitesse.
Évaluer son IA
Pour connaître la qualité de votre IA, rien de tel qu'un match entre
ordinateurs. Vous pouvez essayer d'affronter une autre équipe. Pour
cela, il suffit de remplacer les lectures des coups depuis l'entrée
standard et les écritures des coups vers la sortie standard par des
lectures ou écritures dans des fifos (tubes nommés).
Pour simplifier, les fifos sont des fichiers qui bloquent une écriture tant qu'il n'y a pas de lecture et inversement. Vous devez donc remplacer les lectures de coups depuis l'entrée standard, par une lecture depuis une fifo. Cette même fifo servant de sortie pour les coups effectués par l'autre programme et donc remplaçant chez lui l'écriture vers la sortie standard. Une deuxième fifo sera nécessaire pour la communication inverse.
Les remplacements se font simplement :
Pour simplifier, les fifos sont des fichiers qui bloquent une écriture tant qu'il n'y a pas de lecture et inversement. Vous devez donc remplacer les lectures de coups depuis l'entrée standard, par une lecture depuis une fifo. Cette même fifo servant de sortie pour les coups effectués par l'autre programme et donc remplaçant chez lui l'écriture vers la sortie standard. Une deuxième fifo sera nécessaire pour la communication inverse.
Les remplacements se font simplement :
printf
devient fprintf, scanf
devient fscanf, getchar
devient fgetc.
Bibliothèque nCurses
Afin d'afficher des informations dans un terminal avec un peu de
style, il est demandé de passer à travers la
bibliothèque ncurses.
La plupart des questions quant à cette bibliothèque peut être répondue
dans
le howto
accessible en ligne, ainsi que
sur sa
version PDF.
Les exemples de programme donnés dans le howto sont disponibles
à l'adresse
suivante sous la forme d'une archive
.tar.gz.
A titre d'exemple et pour simple référence, voici le code du "Hello
World" donné dans le HOWTO, très légèrement modifié :
#include <ncurses.h>
#include <stdlib.h>
int main(void)
{
initscr(); /* Start curses mode */
mvprintw(LINES/2,COLS/2,
"Hello World !!!"); /* Print Hello World */
refresh(); /* Print it on to the real screen */
getch(); /* Wait for user input */
endwin(); /* End curses mode */
return(EXIT_SUCCESS);
}
Contact
Pour toute information complémentaire, contacter : Samier Medjiag, et
Cyril Bordage, présent aux séances d'encadrement le vendredi
après-midi.