Available nodes

Modifié le 23 oct.

 Stratégie de jeu au Connect 5

Le 5 en ligne est un jeu qui se joue à 2 sur une grille de taille 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èque ncurses.
  • 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 : 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.