S'agit-il d'un algorithme Q-Learning ou simplement de la force brute?

Question

J'ai joué avec un algorithme qui apprend à jouer Tictactoe. Le pseudocode de base est:

repeat many thousand times {
  repeat until game is over {
    if(board layout is unknown or exploring) {
      move randomly
    } else {
      move in location which historically gives highest reward
    }
  }

  for each step in the game {
    determine board layout for current step
    if(board layout is unknown) {
      add board layout to memory
    }
    update reward for board layout based on game outcome
  }
}

now play a human and win :-)

Exploration: Au début, l'algorithme explore de manière agressive, ce qui réduit linéairement. Après avoir dit mille matchs, il n'explore que dans 10% des mouvements. Tous les autres mouvements sont basés sur l'exploitation des récompenses précédentes.

Récompenses: Si le jeu a abouti à une victoire, alors attribuez 10 points. Si le jeu a entraîné un match nul, 0 points, sinon -5 points. En fait, ces récompenses peuvent être "réglées", de sorte que si le jeu était plus court et qu'il a été gagné, attribuez plus de points ou s'il était plus long, récompense moins de points. De cette façon, l'algorithme préfère la victoire rapidement. Cela signifie qu'il apprend à gagner le plus tôt possible, plutôt que de viser à gagner plus tard. C'est important pour que cela ne manque pas de gagner immédiatement - s'il manquait un tel mouvement, l'adversaire serait probablement a) déménager là-bas pour éviter de laisser l'IA gagner la prochaine fois, et b) penser que l'algorithme était stupide car il a raté un "évident " gagner.

Cet algorithme apprend en effet, donc je peux le classer comme un algorithme d'apprentissage de machine.

Je pense, mais je ne suis pas sûr, qu'il s'agit d'un algorithme d'apprentissage renforcé. Cependant, selon https://www.cse.unsw.edu.au/~cs9417ml/rl1/tdlearning.html Ce n'est pas l'apprentissage de la différence temporelle, car il n'estime pas les récompenses jusqu'à la fin, et il devrait estimer la récompense au fur et à mesure. Cela pourrait signifier que ce n'est pas un apprentissage renforcé.

Question 1: Puis-je affirmer avec succès que j'estime la récompense en fonction de l'histoire, tout en prétendant que l'algorithme est un apprentissage renforcé ou même un Q-Learning?

Question 2: Si je remplace la recherche de récompense qui est basée sur la disposition de la carte, par un réseau de neurones, où la disposition de la carte est l'entrée et la récompense est la sortie, l'algorithme pourrait-il être considéré comme un apprentissage en renforcement profond?

Question 3: Je ne pense pas avoir un taux d'apprentissage ou un facteur de remise. Est-ce important?

J'ai remarqué que l'algorithme est assez inutile à moins que je ne l'entraîne avec au moins chaque mouvement qu'un adversaire essaie. Donc, d'une certaine manière, il a l'impression d'utiliser la force brute plutôt que de vraiment "apprendre". Cela me fait me demander si l'apprentissage automatique Tictactoe apprend vraiment. Je suis d'accord que l'utilisation d'un réseau neuronal pour apprendre la reconnaissance d'image peut être classé comme apprentissage car lorsqu'il voit une image inconnue, il est capable de dire sa classification. Mais cela est tout à fait inutile pour des jeux comme Tictactoe où les dispositions de plaques similaires sont totalement indépendantes (l'une peut conduire à une victoire, l'autre peut entraîner une perte). Alors...

Question 4: Les algorithmes Tictactoe peuvent-ils être classés comme un véritable apprentissage plutôt que comme une simple force brute?

Mise à jour: En ce qui concerne les récompenses ... lorsque l'algorithme décide où aller, cela fait la récompense pour chaque position comme suit:

var total = winRewards + drawRewards + lossRewards;
move.reward = (100*(winRewards/total)) + (10*(drawRewards/total)) + (-1*(lossRewards/total));

Je divise par le nombre total de points (pour chaque mouvement), car sinon il semble apprendre qu'un endroit est génial et n'en donne pas une chance. De cette façon, nous élaborons le ratio gagnant, quelle que soit la fréquence à laquelle il a été joué. Il est normalisé par rapport aux autres.

Le code est disponible ici: https://github.com/maxant/tictactoe/blob/master/ai.js

MISE À JOUR # 2: J'ai depuis compris que cet algorithme ne peut pas être classé comme utilisant Brute Force car il n'apprend pas autant de jeux avant de devenir un expert. Détails ici: http://blog.maxant.co.uk/pebble/2018/04/11/1523468336936.html