Rapport du projet d'algorithmique : Jeu Othello
Analyse des problématiques algorithmiques du jeu
Classification de l'analyse
- 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.
Résultante de l'analyse
Cela a conduit à l'élaboration d'une liste de fonctionnalités à implanter et d'un planning de leurs implantations.
Les directives architecturales
Pas de "tripotage" direct des structures de données (c'est indécent :p)
- Implantation de fonctions outils : get_*, set_*, print_*, print_all_*, dbg_mvprintw, 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).
"Small is beautiful" :
- 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.
Ne pas réinventer la roue :
- Utilisation de bibliothèques pour gérer l'affichage dans un terminal: ncurses;
- 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).
Style du code de l’implantation :
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.
Fonctionnalités implantées :
- Affichage de l'othellier et des pions;
- Saisie d'un coup;
- Détection des conditions de fin de jeu : othellier plein ou plus de coups jouables pour un des deux joueurs;
- Boucle de jeu complète;
- Retournement des pions après un coup;
- Jeu pour deux joueurs humains.
Fonctionnalités à implanter :
- Listes des coups jouables;
- Redéfinir plus proprement certains types de donnés;
- Implantation de la fonctionnalité de retour en arrière dans la liste des coups joués;
- IA (AI en anglais) MiniMax;
- Graphical User Interface aka GUI avec SDL.
Problèmes rencontrés :
- Gestion du tableau à deux dimensions : retour de fonctions conjointement avec passage par adresse, donc des chevauchements mémoires et autres bizarreries (le même objet était retourné deux fois par les fonctions …)
- 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,
Remplacement par implantation d'une version itérative de l’algorithme.
Au total, “perte” de temps proche de 3 cours de 3h.