fr:cs:rapport_de_projet_d_algorithmique

Ceci est une ancienne révision du document !


Soutenance et rapport du projet d'algorithmique : Jeu Othello

  • Descendante ou “top-down”;
  • Diviser pour mieux régner :

Découpage des problématiques algorithmiques en sous-problèmes dit simples autant au niveau complexité (on parle de la notation “big O” ici) que difficulté d'implantation. Une approche fonctionnelle a été choisie pour l'effectuer.

Cela a conduit à l'élaboration d'une liste de fonctionnalités à implanter et d'un planning de leurs implantations.

  • Implantation de fonctions outils : get_*, set_*, print_*, print_all_*, dbg_printf, etc.
  • Indépendance de l'implantation par rapport aux définitions des structures;
  • Séparation claire entre le modèle de données et leurs présentations (architecture proche du MVC).
  • Création de modules de compilation par fonctionnalités : User Interface aka UI (entrées/sorties du terminal, affichage de l'othellier, affichage des pions, etc.), liste chaînée, AI, etc.
  • N'exporter que les fonctions strictement nécessaires;
  • Définitions et déclarations de fonctions simples et compactes pour couvrir une fonctionnalité. Faire une et une chose, et le faire bien;
  • Création d'une librairie partagée et statique des fonctions et des structures de données du jeu;
  • Pas de sur-ingénierie : couvrir les fonctionnalités demandées sans penser à une hypothétique future fonctionnalité qui tue la mort.
  • Utilisation de bibliothèques pour gérer l'affichage dans un terminal;
  • Réutilisation de code disponible en ligne couvrant une fonctionnalité de base demandée mieux que je ne l'implanterai : liste chaînée du noyau Linux portée en espace utilisateur, etc.
  • Réutilisation du système de construction (à base de Makefile) déjà implanté lors d'autres cours et amélioré (50% Gabriel / 50% modifications personnelles).

Calqué sur le style de Kernighan and Ritchie aka K&R avec de légères modifications sur le placement des parenthèses pour les déclarations de fonctions.

indent est votre ami.

  • Affichage de l'othellier et des pions;
  • Saisie d'un coup;
  • Détection des conditions de fin de jeu : othellier plein ou plus de oups jouables pour les deux joueurs;
  • Boucle de jeu complète;
  • Retournement des pions après un coup;
  • Listes des coups jouables;
  • Jeu pour deux joueurs humains.
  1. Définir plus proprement certains types de donnés;
  2. Implantation de la fonctionnalité de retour en arrière dans la liste des coups joués;
  3. IA (AI en anglais) MiniMax;
  4. Graphical User Interface aka GUI avec SDL.

Fonction d'exploration depuis un coup d'origine pour établir :

  • la liste des pions à retourner;
  • la liste des coups jouables pour un joueur.

Problèmes avec l'implantation récursive de l'algorithme, “perte” de temps proche de 3 cours de 3h.
Remplacement par implantation d'une version itérative de l’algorithme.

  • fr/cs/rapport_de_projet_d_algorithmique.1493917259.txt.gz
  • Dernière modification : il y a 3 ans
  • (modification externe)