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.

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.