Partie 2: Améliorations et encore plus de blabla !
Nous en étions restés à la construction d’une structure d’arbre de recherche basique utilisant une recherche de possibilité basée sur un équilibre l’exploration, de score et de chance (MCTS: Monte Carlo Tree Search). Dans cette deuxième partie, je vais montrer les améliorations que j’ai trouvées pour la méthode de base.
Notre petit programme fonctionne tout à fait tel quel, mais en le programmant la première fois, j’ai remarqué des points d’amélioration.
On rappelle notre programme principal :
Node root(nullptr, gameState);
do {
//chercher la meilleure feuille
Node* child = root;
while(child->get_move_count() != 0) {
if(child->children.size() < child->state->child->get_move_count()) {
//node peut encore être développée
child = child->expand_children();
break;
}
child = child->get_best_child_UCT();
}
if(child->get_move_count() != 0) {
//can expand
double score = child->rollout();
child->backpropagate(score);
}
} while (on a du temps);
IGame_State* bestMove = root->get_best_child_UCB(); //use UCB
Fermeture de branches
Pour commencer, on n’élimine jamais de branche quand elles sont complètement explorées.
Imaginez qu’on utilise notre petit programme pour un TicTacToe: 9 cases donc 9 coups en tout (profondeur maximum de l’arbre… 9, Bravo !).
Si on laisse une seconde à notre petit programme, on va rapidement faire le tour des possibilités, l’arbre sera entièrement exploré en une fraction du temps et on va alors faire des tours dans le vide, en descendant au fond de l’arbre (if(child->get_move_count() != 0) sera toujours false, on a épuisé les possibilités).
Si on a une seconde à tuer, pourquoi pas. Tant qu’on y est on limite le temps de recherche à 15 minutes pour la pause café et on en parle plus. Dans ce cas extrême, on obtiendra des scores et un nombre de visites très grand, tous vers le même chemin (au moins le choix du chemin est clair !).
De mon côté, je préfèrerais profiter du temps restant pour faire autre chose. On va donc mettre en place un système de fermeture de Node quand elles ne peuvent plus avoir d’enfants.
Fermeture de nœuds
On ajoute la méthode is_fully_explored dans notre classe Node:
bool Node::is_fully_explored() {
//true if this node is fully explored
return _children.size() == _state->get_move_count();
}
Cette méthode nous dira simplement que toutes les possibilités de cette Node ont été explorées. Cependant, elle n’indique rien concernant les enfants de notre Node, qui pourrait bien n’être pas du tout explorés.
La solution évidente est de vérifier chaque enfant récursivement, mais ça ne serait pas très efficace.
On va plutôt sacrifier un peu de mémoire et ajouter un membre _isClosed a notre class Node.
_isClosed sera mis a jour dans l’étape de backpropagation (c’est là qu’on va fermer les nodes, on doit remonter l’arbre de toutes manières, autant en profiter).
Tout d’abord, on ajoute _isClosed = _state.get_move_count() == 0; dans le constructeur de Node.
Les nodes sans enfants seront les premières à être indiquées comme fermées (Ajoutez également une méthode bool Node::is_closed() pour plus tard).
On va aussi ajouter un membre _closedChildrenCount pour garder en mémoire le nombre d’enfants fermés de cette node (rajouter _closedChildrenCount = 0 dans le constructeur).
Au moment de la backpropagation, on va remonter l’information de fermeture et mettre à jour le parent, qui sera responsable qu’il est bien fermé :
void Node::backpropagate (score) {
//incremente le nombre de visites et score
_nombreDeVisites += 1;
_score += score;
//Verifier si on a encore des enfants ouverts
if(_isClosed) {
_closedChildrenCount += 1; //un de nos enfants s'est déclaré fermé
if(this->is_fully_explored() and _closedChildrenCount == this->children.size()) {
//Tous les enfants explorés et fermés
if(dynamic_cast<Node*>(_parent) != nullptr) {
//Forcer le parent a vérifier si il doit fermer
_parent->_isClosed = true;
//propager au parent si il existe
_parent->backpropagate(score);
}
return; //prevent a recheck of parent validity
}
else {
//a child is closed but some remain open for exploration
_isClosed = false;
}
}
if(dynamic_cast<Node*>(_parent) != nullptr) {
//propager au parent si il existe
_parent->backpropagate(score);
}
}
On cherche ici à remonter l’information de fermeture en mettant la variable _isClosed du parent a true quand on ferme une node.
Le parent se chargera lui-même de repasser _isClosed a false s’il a encore des enfants non fermés.
Il ne nous reste plus qu’à rajouter une condition en plus du temps écoulé pour quitter la boucle de recherche de solutions quand on a exploré toutes les possibilités.
C’est assez simple, il suffit de tester si le membre _isClosed de la Node root est true (} while (on a du temps and not root->is_closed()); ).
Cette simple modification permet un usage plus sensé des ressources, et gagner du temps de traitement pour autre chose (ou faire plus de café).
élimination des nodes fermées
Il ne faut pas oublier d’éliminer les Nodes marquées comme fermée dans la fonction get_best_child_UCT, sinon notre fermeture de branches ne sert à rien.
Rollout - Expand
Lors de mes tests, j’ai remarqué qu’une des étapes qui nous consomme le plus de temps est la partie état de jeux gérée par une classe dérivant de IGame_State.
En soi, on ne peut rien y faire, un état de jeu peut être très lourd à calculer, et leur optimisation n’est pas vraiment dans le cadre de ce billet de blog.
On va ici essayer d’appeler cette fonction moins souvent. Notre étape de Rollout (déroulement aléatoire de coups jusqu’à un état final) réalise la plupart de ces appels, et on n’en fait pratiquement rien.
L’idée est d’étendre l’arbre de recherche en même temps qu’on effectue la phase de rollout pour calculer nos coups une seule fois et économiser le maximum de temps de traitement.
Expand
Pour garder une certaine souplesse d’utilisation, je vais conserver la fonction existante et en créer une nouvelle :
void Node::rollout_expand () {
Node* currentNode = this;
while(currentNode->_sate->get_move_count() > 0) {
//Créer une nouvelle node
Node* nextNode = new Node(currentNode, currentNode->_state->do_move(
//index a choisir
) );
//ajouter node comme enfant de celle ci
currentNode->_children.push_back(nextNode);
//recommencer !
currentNode = nextNode;
}
//propager le score de l'état final
this->backpropagate(
currentNode->_state->get_score()
);
}
Une fonction pas bien différente donc, mais qui nous économise pas mal de temps de calcul.
Quelques problèmes cependant :
- Le score backpropagé sera le même pour chaque node ajoutée pendant l’étape de rollout.
- On obtient un arbre avec des branches très longues, dont la base se développe au fur et à mesure.
Remettre les scores a leur place
Chaque nouvelle node de la phase de rollout aura un nombre de visites fixé à 0. On va simplement modifier notre fonction backpropagate et ajouter une condition sur le score propagé :
//incrémenter le score, comme avant
_score += score;
if(_nombreDeVisites == 0) {
//ajouter le score de cette node au score total a backpropager
score += _state->get_score();
}
//incrémenter les visites
_nombreDeVisites += 1;
On obtient des scores assez proches de notre situation pre rollout-expand.. Il restera toujours un biais cependant : avec ce type de recherche, on n’arrive pas aux mêmes scores, car les nodes créées sont éliminées de l’exploration durant la phase de rollout, et leur score ne remonte forcément qu’une seule fois.
Exploration en longueur
Celle-ci est un peu plus complexe. On va commencer par regrouper la recherche d’une feuille dans une fonction.
Node* find_leaf() {
Node* child = root;
while(child->get_move_count() != 0) {
if(child->children.size() < child->state->child->get_move_count()) {
//node peut encore être développée
return child->expand_children();
}
child = child->get_best_child_UCT();
}
return nullptr; //atteint le bout de l'arbre sans avoir trouvé de feuille a étendre, ca ne devrait pas arriver avec notre élimination de branches.
}
Node root(nullptr, gameState);
do {
//chercher la meilleure feuille
Node* child = find_leaf();
if(child == nullptr)
break; //erreur: sortie de boucle
if(child->get_move_count() != 0) {
//can expand
double score = child->rollout();
child->backpropagate(score);
}
} while (on a du temps and not root->is_closed());
IGame_State* bestMove = root->get_best_child_UCB(); //use UCB
On peut ensuite modifier cette fonction pour y ajouter une possibilité de “saut” si une node enfant a des enfants non explorés et c’est gagné ! Pour le saut, je fais un jet aléatoire entre 0 et le nombre d’enfants non explorés, et saute la node en cours si le tirage est > au nombre d’enfants explorés :
Node* find_leaf() {
Node* child = root;
while(child->get_move_count() != 0) {
if(child->children.size() < child->state->child->get_move_count()) {
//node peut encore être développée
var tirage = randInt(0, child->_state->get_move_count());
if(tirage < child->children.size())
return child->expand_children();
//continue to search
}
child = child->get_best_child_UCT();
}
return nullptr; //atteint le bout de l'arbre sans avoir trouvé de feuille a étendre, ca ne devrait pas arriver avec notre élimination de branches.
}
On obtient une métrique assez naturelle qui favorise le saut de nodes quand on a déjà bien exploré l’arbre.
Graph ?
//todo !
-> hash
-> tout les states dans une map<hash, state>
-> multiple parents Backprop se fait depuis chaque parent, le score augmente donc beaucoup pour chaque noeuds dans le graph