FAIRE ENTRER UNE SEMAINE DANS 215 BITS

Avant d'avancer dans les posts, je pense utile de revenir sur quelques décisions qui ont fait du moteur ce qu'il est aujourd'hui. Si dans le post précédent j'ai pu dire que "le calcul a donc été relativement rapide (<50 mins pour 1 semaine), [...]", c'est parce que je me suis vite heurté à un mur classique sur un bnb: l'explosion combinatoire.
Mon approche naïve et évidente a été de créer des objets avec une heure de début, une de fin, et de parcourir les listes avec des for pour vérifier si le prof ou la salle est occupé ou non. C'est une approche fonctionnelle, mais c'est bien tout / sur les centaines des ressources et les millions de comparaisons à faire, mon processeur passait tout son temps à allouer des objets en mémoire et comparer des chaînes de caractères, bref ça allait pas.

les moteurs d'échec

En creusant du côté des moteurs d'échecs (stockfish et deep blue), on se rend vite compte qu'on ne jette pas des millions de cycles à allouer des objets - on utilise simplement des bitboards. Un équiquier contient 64 cases, on associe chaque bit d'un entier non signé de 64 bits (uint64) une case, puis on place par exemple un 1 si le fou blanc est sur la case, un 0 sinon. De cette façon on peut déterminer si une pièce attaque ou bloque une autre uniquement avec des op logiques AND, ridiculement peu couteuses (en 1 cycle = 0.2ns en 5ghz, même si ce n'est pas une façon de résumer la latence, débit, microarchitecture, cache et fréquence, une opération bitwise remplace une boucle de comparaison et évite des allocations. Très largement rentable). On peut tout à fait appliquer ça dans willowengine!

faire rentrer une semaine dans 215 bits

En PeiP, il y a des cours du lundi au vendredi, de 8h à 18h45. La conversion est plutôt simple, on coupe chaque jour en 43 * 15 minutes, et on le place dans un uint64 dont chaque bit représente 15 minutes, 0 si libre et 1 si occupé. Chaque ressource (groupe, enseignant, salle) est donc décrite par 43 bits/jour, 215 bits/semaine.

Cette approche permet donc d'effectuer tous les calculs et comparaisons liées à l'emplacement temporel des ressources extrêmement rapidement. On consomme 99.2% de mémoire en moins, on a plus besoin d'attendre les allés retours en RAM (<300 cycles = 60ns contre +- 5ns en L3).

utiliser les masques

On a donc créé un masque pour chaque ressource. Un exemple simple est un cours d'1h30, représenté par 6 bits à '1' ('0b111111'). Selon sa position dans la semaine, on déplace cette valeur dans le masque voulu. Une journée avec un seul cours d'1h30 à 9h sera donc représentée par 0000111111000000000000000000000000000000000. Cette représentation rend très efficace les actions utilisées par le moteur:

Tester un conflit

prof_bits & cours_mask) != 0  // (AND) l'enseignant a déjà un cours.

// *le code est simplifié pour rester lisible, la vraie condition est:
(u[GmIdx(g, day)] & mask) != 0  // l'enseignant a déjà un cours.

Poser un cours

groupe_bits |= cours_mask  // (OR)

Annuler un cours (backtrack)

groupe_bits &= ~cours_mask  // (AND NOT)

*le code réel est disponible dans la carte du moteur.

Document

Le fonctionnement des bitboards dans le moteur est détaillé dans ce document

La suite

Les résultats de cette implémentation ont permis au moteur de finir une semaine en un temps raisonnable (<50mins avec les parametres depth 2, week 16feb, maxworkers 32; contre >5 heures POUR UN SEUL COURS avant bitboards). Le test de regression du dernier post est prêt, je m'occupe maintenant de la tt (qui viendra probablement avec un hachage zobrist)

Voilà pour les bitboards!
//pekmi