RETENIR POUR MIEUX TUER

Dans le précédent post sur les bitboards, le moteur a enfin arrêté d'agoniser sur l'allocation d'objets et les boucles de chaînes de caractères. On est passés de plusieurs heures pour 1 seul cours, à moins de 50 minutes pour une semaine entière. En observant les nouvelles logs du moteur, un nouveau problème flagrant s'est montré : le moteur refait des millions de fois exactement les mêmes calculs.

observation

Les mouvements créés par le moteur (le fait de déplacer un cours d'un créneau à un autre) sont commutatifs. C'est l'unique cause de ces répétitions et la transposition est super simple à observer, en voilà un exemple sur 2 mouvements:
Soient 2 cours à replacer dans la semaine,

Mouvement A : déplacer Maths du lundi vers Mercredi, 10h;

Mouvement B : déplacer Physique du mardi vers Vendredi, 14h;

graph TD
        Root["État Initial (Lundi)"] -->|Mv A. Déplacer Maths| StepA["Maths = Mercredi 10h<br><i>(Physique encore Mardi)</i>"]
        Root -->|Mv B. Déplacer Physique| StepB["Physique = Vendredi 14h<br><i>(Maths encore Lundi)</i>"]

        StepA -->|Mv B. Déplacer Physique| FinalState["État Intermédiaire X<br><b>Maths Mercredi + Physique Vendredi</b>"]
        StepB -->|Mv A. Déplacer Maths| FinalState

        style Root fill:#111,stroke:black,color:white
        style StepA fill:white,stroke:black,color:black
        style StepB fill:white,stroke:black,color:black
        style FinalState fill:black,stroke:black,stroke-width:3px,color:#fff

Alors le moteur va parcourir l'arbre en partant de la racine (état initial), s'éloigner via deux branches distinctes, et trouver deux états physiques intermédiaires identiques (état intermédiaire x).
Le moteur ne l'ayant pas retenu, il devra donc à nouveau le calculer.
C'est une transposition à l'origine de la perte de temps massive de willowengine.

l'importance d'une bonne structure de données

C'est un problème que l'on a déjà traité deux fois, d'abord en créant un objet: chaque cours était représenté par une instance de classe avec des propriétés (Start: DateTime, End: Datetime, Teacher: "", Room: "", Group: ""), c'était IMMENSÉMENT lourd (+- 3500 octets/semaine). On a donc implémenté la représentation par bitboards: chaque jour est représenté par un entier de 64 bits non signé, une semaine pèse donc 5*(64/8) = 40 octets (27o de charge utile).
C'est un score très satisfaisant, mais insuffisant : mes logs affichaient en moyenne 80 millions d'état logique d'emploi du temps. Si l'on stockait l'état physique de ces semaines avec notre méthode de bitboards, ça représente environ 19.3Go de mémoire pour un seul calcul (1.7To avec la première méthode). Une telle taille détruit totalement mes projets car j'aurais idéalement aimé avoir une table de transposition assez fine pour entrer dans le cache CPU, et plus tard pouvoir lancer plusieurs calculs parallèles.
Je suis donc retourné voir du côté des moteurs d'échecs, où se trouvait encore une fois la réponse : le hachage zobrist.

hachage zobrist

Cette partie se base sur le rapport a new hashing method with application for game playing de Albert Lindsey Zobrist, 1970, ainsi que a means of enabling position comparison de Bruce Moreland, ~2000. Je ne peux que fortement conseiller d'aller voir ces documents bien que la suite reste compréhensible sans.
Aux échecs, un plateau comporte 64 cases et une douzaine de types de pièces. L'idée de Zobrist permet d'éviter de recalculer le hash de tout l'échiquier après chaque coup, en associant un grand nombre aléatoire de 64 bits (ulong / uint64) à chaque couple [pièce, case].
Dans willow, le principe est le même:

Au démarrage, on pré-calcule une table de nombres aléatoires de 64bits avec une graine constante, pour chaque triplet [cours, jour, créneau].

L'empreinte de la semaine est simplement le résultat de la combinaison de ces nombres avec l'opérateur XOR.

Ce choix repose sur la propriété involutive de XOR (A ^ B ^ B = A).
Appliquer et annuler un déplacement de cours se fait donc avec la même opération et en 1 seule instruction CPU! :

// Déplacer un cours : on applique la clé Zobrist du nouveau créneau
currentHash ^= _zTable[coursIdx, targetDay, targetSlot];

// Pour le retirer (backtracking)
currentHash ^= _zTable[coursIdx, targetDay, targetSlot];
// (exactement la même ligne)

Zéro allocation d'objet, zéro boucle sur les cours, coût O(1) constant.
Le plus important : l'état physique de la semaine ne pèse que 8o (au lieu de 40o).

C'est un résultat agréable, qui ferait tout à fait rentrer une tt dans un cache L3 et certains L2, mais qui peut encore être largement amélioré par un dernier détail: l'utilisation d'une table de transposition ne devient rentable qu'à partir de la depth 2 (quand on autorise le moteur à aller jusqu'à 2 cascades). En pratique, on peut maintenant pousser willowengine jusqu'à la depth 3. La tt est donc active pour les profondeurs uniquement >1.

Considérons qu'à depth 0 (changements directs uniquement), il y ait en moyenne 150 possibilités, alors le nombre d'évaluations maximales à faire serait, pour 1 seul cours:

On peut maintenant estimer le pire poids d'une tt, en depth=3, selon la méthode utilisée:

*mesures inutiles car perte de temps
Bien que dans ce modèle, la taille indiquée corresponde aux clés brutes et que l'empreinte réelle dépend de l'implémentation de la tt, c'est excellent! Dans le pire des cas, on pourrait toujours faire rentrer plusieurs dizaines de tt dans un cache L2/L3 (175 Ko entrent même cache pistache dans les caches L2 récents par coeur). Je pense par la suite contraindre les tt à chaque coeur indépendament, car la taille est assez fine pour se faire une place en L1 sans contention de lock, il faudrait mesurer.

élagage et table de transposition

(partie mise à jour en juillet)*
Maintenant que l'état logique d'une semaine est résumé dans un simple ulong de 8 octets, l'intégration devient triviale. Avant de s'enfoncer plus bas dans l'arbre, le moteur vérifie simplement si cette configuration exacte n'a pas déjà été explorée:

// calcul incrémental du hash Zobrist O(1)
uint64_t ttKey = ctx.runningSeenHash ^ zEvent[eventIdx] ^ zDay[targetDay] ^ zQ[targetQ];

// table de transposition locale au worker (zéro lock)
if (ctx.localTT != nullptr) {
    auto it = ctx.localTT->find(ttKey);
    // si déjà exploré avec une profondeur restante plus grande ou égale:
    if (it != ctx.localTT->end() && it->second >= depthLeft) {
        // on connait déjà cette branche, on peut la tuer.
        ctx.ttHits++;
        return; 
    }
    // garde la profondeur restante 
    (*ctx.localTT)[ttKey] = depthLeft;
}

*code cpp de juillet
On vérifie aussi que la profondeur restante à laquelle on a vu cette branche est au moins plus grande (s'assurer qu'il ne reste bien rien à explorer). Pour sauver le hash probabiliste de la semaine (zobrist) et la profondeur de l'état, on utilise donc une std::unordered_map<uint64, int>.

Résultats

On élague jusqu'à 80% de l'arbre, le calcul de la même semaine est passé de 50 minutes à environ 6 minutes... en depth 3!

Sur des paramètres égaux, (depth 2, week 16feb, maxworkers 32), on est passés de <50 minutes à <3 secondes, c'est absoluement énorme.
Une autre bonne comparaison, c'est sur un cours unique. Il y a encore 4 semaines, le calcul du même cours à paramètres égaux est passé de <5 heures à <3 secondes, soit un solide ~x6000 (sur un seul calcul spécifique).
C'est très encourageant pour la suite.

Document

Le fonctionnement du hachage zobrist et des tables de transpositions dans le moteur est détaillé dans ce document

la suite

Zobrist et la table de transposition ont été pour moi une assez grosse implémentation, le plus dur ayant été de trouver et comprendre les concepts. Evidemment, le nouveau willowengine a passé tous les tests de régression et absolument détruit le benchmark. Les résultats sont les mêmes à la pénalité près. Je compte maintenant m'éloigner un peu du moteur pour nettoyer le projet et automatiser un maximum les actions répétitives. Je n'ai toujours pas trouvé de solution en ce qui concerne les contraintes des enseignants. J'ai aussi pu profiter de la rapidité de cette nouvelle version pour itérer et changer les coefficients de pénalité empiriquement en notant chaque changement proposé par le moteur avec quelques autres étudiants. Il semble sortir de meilleurs résultats, mais ça reste toujours subjectif.

C'est une chouette update!
//pekmi