Puissance 4

Bonjour,

Je fais le puissance 4 du TP du langage C, je vais essayer de l’améliorer pour y intégrer des notions avancées du C (multithreading, IA avancée qui réflechisse à N coups à l’avance, etc.), le projet peut être suivi ici https://gitlab.com/Meithal/puissance4

Etant un apprenant, les suggestions sont bienvenues

Bravo à toi pour le tp.

Quelques remarques rapides (version actuelle du code).

Au vu des macros {HAUTEUR,LARGEUR}_DAMIER, ton damier est 5x5 ? Il me semblait qu’un damier de puissance 4 est plus large que haut (genre 7x5, à vérifier).

Je n’aime pas la structure case_damier:

• tu stockes une position et un contenu ensemble, ça n’a pas de sens, il faudrait pouvoir manipuler les positions comme des valeurs à part entière et avoir des fonctions pour lire ou écrire le contenu d’un plateau à une position donnée

• je ne comprends pas le rôle du champ index

Au lieu d’avoir une énumération de directions, tu pourrais représenter chaque direction unitaire par un vecteur: (0, -1) pour le SUD, (1, -1) pour SUD_EST, etc. Aujourd’hui ta fonction assigne_curseur est assez compliquée à lire.

Globalement la gestion des "curseurs" avec des pointeurs partout me semble baroque et compliquée, et la façon dont tu gères un tableau de dimension 2 dans un tableau de dimension 1 est compliquée et génère des risques d’erreurs. Faire simple!

struct position;
struct direction;

struct place; /* j'évite "case", c'est un mot clé du langage */
typedef plateau;


bool valide(plateau, struct position);
struct position deplace(struct position, struct direction);

struct place *place(plateau, struct position);

Écrire un symbole dans le plateau, à une position pos:

if (!valide(plateau, pos)) { /* cas d'erreur: position hors du plateau */ }
else { place(plateau, pos)->contenu = symbole; }

Autre exemple de truc trop compliqué:

            for (unsigned i = 0 ; i < 8 ; ++i) {
                if (DRAPEAUX & ((unsigned) 1 << i)) {
                    TACHE = (unsigned) 1 << i;
                    DRAPEAUX ^= (unsigned) 1 << i;
                    break;
                }
            }

(Bon et les non-constantes en majuscules je trouve ça bizarre, mais les goûts et les couleurs…)

Tu définis une constante DERNIER_DRAPEAU (LAST_FLAG pour les gens qui évitent le franglais), et tu fais juste

for (int drapeau = 1; drapeau <<= 1; drapeau <= DERNIER_DRAPEAU)
{
     if (drapeau & drapeaux == 0) continue;
     switch (drapeau) {
         ...
     }
}

Bonne idée pour les drapeaux. Je suis pas très fan des fonctions, en tout cas pour l’instant, j’imagine qu’elles peuvent aider à la lisibilité dans certains endroits, je vais y réfléchir.

tu stockes une position et un contenu ensemble, ça n’a pas de sens, il faudrait pouvoir manipuler les positions comme des valeurs à part entière et avoir des fonctions pour lire ou écrire le contenu d’un plateau à une position donnée

Mon approche permet justement de ne pas avoir de fonction pour ça, enfin on pourrait en faire une qui ressemble plus à une macro.

je ne comprends pas le rôle du champ index

Ca sert à ce qu’une case sache où elle se trouve dans le tableau qui la contient, sans devoir la calculer par sa ligne ou colonne, ou par une soustraction de pointeurs.

Globalement la gestion des "curseurs" avec des pointeurs partout me semble baroque et compliquée

Faire disparaitre le curseur est un objectif à moyen terme

Je suis pas très fan des fonctions, en tout cas pour l’instant, j’imagine qu’elles peuvent aider à la lisibilité dans certains endroits, je vais y réfléchir.

Le code de "assigne_curseur" et la gestion des curseurs est bien trop compliquée. Ça rajoute de l’état dans tes données qu’il faut maintenir avec soin (sinon c’est le bug), et en plus ça veut dire que tu ne peux "explorer" qu’une seule position à la fois dans ton damier ! C’est une restriction qui n’a pas lieu d’être, avec l’interface que je propose ci-dessus (par exemple) tu peux stocker autant de positions que tu veux, où tu veux, les explorer l’une après l’autre ou en simultané….

On dirait que la façon dont tu t’y prends pour coder c’est : essayer d’implémenter un truc, regarder de quelles données supplémentaires tu aurais besoin dans tes structures pour y arriver, et les rajouter. Du coup ça donne des structures de données trop compliquées, un peu baroques. Il vaut mieux commencer à coder en se demandant: quels sont les notions du "domaine du problème" et comment les représenter ? Ensuite seulement, tu te demandes comment faire ce que tu veux à partir de ces notions.

Ici la notion de "position" sur le damier est naturelle et bien pratique pour faire un peu tout, et tu n’as pas de structure de donnée pour la représenter. Tu ne colles pas bien à la nature du problème, et donc tu te compliques la vie et tu écris du code foireux comme assigne_curseur.

Une autre remarque qui n’est pas liée: personellement je trouve que ton union dans struct meilleur est une horreur. Les unions en C sont un excellent moyen de se tirer dans le pied, et on dirait que tu n’attends que ça. Pourquoi diable renverrais-tu un char ou un short pour évaluer les positions d’un puissance 4 ? Je vois deux approches raisonnables:

• Tu écris une fonction pour ce problème, et tu spécialises le type de retour; typedef long score;, ensuite tu utilises score et le tour est joué — si un jour tu veux utiliser float à la place, tu n’auras que le typedef à changer.

• Ou alors tu veux faire de la généricité (ici je ne vois pas trop l’intérêt) et tu fais avec du void* comme tout le monde en C, au lieu d’une union bien crade. Ça veut sans doute dire prendre en paramètre un pointeur de fonction de comparaison des scores, comme dans qsort par exemple.

Mise à jour d’aujourd’hui :

• Ajout de tests unitaires
• Le code respecte le principe de moindre connaissance, jamais plus d’un niveau d’indirection.
• Amélioration d’IA, elle sait la longueur maximale que pourra faire un coup a telle colonne, donc elle evitera de jouer la ou elle pourra pas avoir de ligne gagnante au bout du compte.

Nouvelle mise à jour:

• L’IA peut réfléchir un coup à l’avance
• J’ai enfin trouvé un calcul de voisinnage qui me satisfasse
• L’IA pondère moins les bords de map car les possibilités sont plus restreintes (diagonales capées)

C’est à peu près l’objectif que je me suis fixé sur ce projet, il reste un peu de nettoyage et documentation à faire mais je crois qu’il est fini

Une autre remarque qui n’est pas liée: personellement je trouve que ton union dans struct meilleur est une horreur. Les unions en C sont un excellent moyen de se tirer dans le pied, et on dirait que tu n’attends que ça. Pourquoi diable renverrais-tu un char ou un short pour évaluer les positions d’un puissance 4 ? Je vois deux approches raisonnables:

Le problème quand on fait de l’arithmetique de pointeurs sur des types variables c’est qu’on veut les cast vers des pointeurs de caractères pour avoir des calculs simples, mais en étant des pointeurs vers caractères on ne peut pas les faire comparer des valeurs qui dépassent la capacité du type char, donc j’ai été obligé d’utiliser une union ici.

• L’IA est globalement meilleure
• L’IA affiche pourquoi elle joue à tel endroit
• Elle ne considère que le joueur qui joue après elle, au lieu de tous les joueurs (si il y en a plus de 2)
• Simplifié la fonction de pondération
• Compatibilité avec Visual Studio

En voulant rendre la fonction de calcul de voisinnage plus lisible, je crois que j’ai irrémédiablement rendu le reste de mon code illisible

• Quand l’IA sait qu’elle a perdu, elle affichera un texte en consequence

Je continue à penser que tes structures pour représenter l’environnement autour d’une case (avant curseur, maintenant cibles) ajoutent beaucoup de complexité sans gain très clair. On peut représenter facilement une position dans le damier avec une paire d’entier (struct position { int ligne; int colonne }), et une direction dans le damier avec à nouveau une paire d’entier (struct direction { int dl; int dc }).

Tu écris

static struct case_damier * vers(struct case_damier *orig, enum directions dir) {
    struct damier * damier = damier_depuis_case(orig);
    cibles_t * cibles = cibles_damier(damier);
    int bitmask = bitmask_direction(dir, cibles);
    if (((orig->ligne == damier->bords[BORD_HAUT]) && (bitmask & NORD))
        || ((orig->ligne == damier->bords[BORD_BAS]) && (bitmask & SUD))
        || ((orig->colonne == damier->bords[BORD_GAUCHE]) && (bitmask & OUEST))
        || ((orig->colonne == damier->bords[BORD_DROIT]) && (bitmask & EST)))
        return NULL;

    echiquier_t * echiquier = echiquier_damier(damier);
    return &(*echiquier)[orig->index + direction_delta(dir, cibles)];
}

Mais tu pourrais écrire tout simplement:

static struct position vers(struct position depart, struct direction dir) {
  return { .ligne = depart.ligne + dir.dl; .colonne = depart.colonne + dir.dc; }
}

Pour représenter un ensemble de directions possibles, tu peux te casser les pieds avec un bitmask si tu le souhaites (il faut écrire des fonctions de conversion entre struct direction et enum direction_bit), mais tu peux aussi tout simplement utiliser un tableau de booléens de taille 3x3.

Aujourd’hui ton code est écrit comme si les performances étaient très critiques : à chaque fois tu essaies de choisir une structure de donnée optimisée, même si ça donne du code moins lisible ((struct damier *)((char *)orig - orig->index * sizeof(*orig) - offsetof(struct damier, echiquier))). C’est ce qu’on appelle de l’optimisation prématurée. En plus le code au final n’est sans doute pas plus rapide qu’une version beaucoup plus simple, car tu te retrouves à faire beaucoup d’opérations sur tes structures super-optimisées — compare les deux fonctions que je montre au-dessus, la seconde (plus simple) sera en fait nettement plus rapide que la première.

As-tu essayé d’écrire le code le plus simple et le plus clair possible qui fait ce que tu veux ? Ensuite tu pourras optimiser si tu te rends compte qu’il y a un problème de performance. Pour un problème d’algorithmique comme celui-ci, l’important n’est pas de gagner un facteur constant avec un bitmask à la place d’un petit tableau, c’est d’avoir un code propre et clair qui te permet d’évoluer rapidement tes algorithmes, et de monter en complexité sur l’algorithmique (minimax etc.) au lieu de dépenser ton énergie sur des détails d’implémentation.

Salut,

Le fait que vers retourne NULL en cas de sortie du damier est attendu par de nombreuses routines pour vérifier si on est en dehors du damier. Sinon après chaque appel de ta fonction il faudrait nous même vérifier si le couple .ligne/.colonne est dans les bounds. Je pense que c’est moins fastidieux de juste vérifier NULL. Autrement je pense qu’on pourrait améliorer ta fonction comme ça:

static struct position vers(struct position depart, struct direction dir) {
  size_t ligne = depart.ligne + dir.dl;
  size_t colonne = depart.colonne + dir.dc;
  if(ligne < damier->bords[BORD_HAUT] 
  || ligne > damier->bords[BORD_BAS]
  || colonne < damier->bords[BORD_GAUCHE]
  || colonne > damier->bords[BORD_DROIT])
  {return NULL;}
  return { .ligne = depart.ligne + dir.dl; .colonne = depart.colonne + dir.dc; }
}

Aussi pour tester rapidement les 8 directions autour de la case, il suffit de faire une boucle for a travers une énumération, chaque direction possède un index. Avec une direction qui correspond à une structure, il y aura des aménagements à faire. Par exemple une fonction qui retourne la case pour un x et y donné.

Auparavant chaque case du damier contenait un pointeur sur ses 8 voisins, ça occupait beaucoup de mémoire mais tant pis. Le vrai problème est quand on veut copier le damier pour voir dans le futur (pour l’IA), les pointeurs restent sur les cases de l’ancien damier, on pourrait appeler une pseudo macro qui ferait repointer les voisins sur les bonnes cases, mais j’ai trouvé ça tricoté comme manière de faire. A la place de pointeurs, ce sont des deltas maintenant qui sont stockés, et peuvent être copiés sans soucis. C’est à dire que pour trouver son voisin de droite il faut ajouter 1, celui du haut soustraire la largeur du damier, celui en haut a droite soustraire la largeur et ajouter 1…

En ce qui concerne la macro qui permet de remonter au damier à partir d’une case, le problème c’est que j’ai besoin de connaitre le damier que dans une fonction, et sans cela je devrais passer le damier par référence a tous les endroits qui on besoin d’appeler cette fonction, et que toutes les fonctions qui en ont besoin doivent connaitre le damier, du coup tous mes appels de fonction seront plus longs, pour une seule fonction qui en a vraiment besoin..

C’est vrai que lorsque je change la structure du damier je dois pas oublier de changer cette fonction aussi, sinon ça plante. Idéalement on devrait pouvoir faire un static assert pour s’en prémunir, sinon je trouve ça acceptable et ça m’aide beaucoup je pense…

A la place de pointeurs, ce sont des deltas maintenant qui sont stockés, et peuvent être copiés sans soucis. C’est à dire que pour trouver son voisin de droite il faut ajouter 1, celui du haut soustraire la largeur du damier, celui en haut a droite soustraire la largeur et ajouter 1…

Mais tout cela serait inutile si tu avais un tableau à deux dimensions au lieu d’un tableau unidimensionnel (qui ne sert à rien d’autre que te rendre la vie plus compliquée), ce serait trivial d’obtenir une case à partir de sa position (et la position d’un voisin à partir de ta position).

En ce qui concerne la macro qui permet de remonter au damier à partir d’une case, le problème c’est que j’ai besoin de connaitre le damier que dans une fonction, et sans cela je devrais passer le damier par référence a tous les endroits qui on besoin d’appeler cette fonction, et que toutes les fonctions qui en ont besoin doivent connaitre le damier, du coup tous mes appels de fonction seront plus longs, pour une seule fonction qui en a vraiment besoin..

Ben oui, passe l’argument à chaque fois. C’est nettement plus propre, ça te permet de bien comprendre quelle partie du code a accès au damier (ça permet de mieux raisonner sur le domaine et sur ton API), et de toute façon plein de programmes ont ce genre de besoin (passer un contexte à tout le monde), autant s’habituer.

P.S.: pour le test de sortie du tableau, je pense effectivement que c’est plus propre de tester après vers, parce que le langage C n’est pas assez flexible/expressif pour tester dans vers facilement. Tu utilises NULL dans ta version modifiée, mais ça demande de renvoyer un pointeur et ça rend le code un peu plus fastidieux (il faut gérer la mémoire, etc.). Déjà dans mon premier message j’avais proposé une API avec une fonction bool valide(damier, struct position).

J’ai envoyé des propositions de simplification:

https://gitlab.com/Meithal/puissance4/merge_requests/1

Merci, j’ai merge dans le codebase, et ce fonctionne toujours