Recherche par différence temporelle dans l'ordinateur Go

L'apprentissage par différence temporelle est l'une des solutions les plus efficaces et les plus largement appliquées au problème de l'apprentissage par renforcement ; il a été utilisé pour atteindre un niveau de jeu de maître aux échecs, aux dames et au backgammon. L'idée principale est de mettre à jour une fonction de valeur à partir d'épisodes d'expérience réelle, en faisant du bootstrap à partir d'estimations de valeurs futures, et en utilisant l'approximation de la fonction de valeur pour généraliser entre des états apparentés. La recherche arborescente de Monte-Carlo est un algorithme récent de recherche haute performance, qui a été utilisé pour atteindre un niveau de jeu de maître au Go. L'idée principale est d'utiliser le résultat moyen d'épisodes simulés d'expérience pour évaluer chaque état dans un arbre de recherche. Nous présentons une nouvelle approche de la recherche haute performance dans les processus de décision de Markov et les jeux à deux joueurs. Notre méthode, la recherche par différence temporelle, combine l'apprentissage par différence temporelle et la recherche par simulation. Comme la recherche arborescente de Monte-Carlo, la fonction de valeur est mise à jour à partir de l'expérience simulée, mais comme l'apprentissage par différence temporelle, elle utilise l'approximation de la fonction de valeur et le bootstrapping pour généraliser efficacement entre des états apparentés. Nous appliquons la recherche par différence temporelle au jeu de Go 9×9, en utilisant un million de caractéristiques binaires correspondant à des motifs simples de pierres. Sans arbre de recherche explicite, notre approche surpasse une recherche arborescente de Monte-Carlo non améliorée avec le même nombre de simulations. Combiné à une simple recherche alpha-bêta, notre programme a également surpassé tous les programmes de recherche et d'apprentissage automatique traditionnels (pré-Monte-Carlo) sur le serveur de Go de l'ordinateur 9×9.