Tic-Tac-Toe AI: Comment faire l'arbre?

Question

J'ai un énorme bloc qui essaie de comprendre les "arbres" tout en créant un bot Tic-Tac-Toe. Je comprends le concept, mais je n'arrive pas à les implémenter. Quelqu'un peut-il me montrer un exemple de la façon dont un arbre devrait être généré pour un tel cas? Ou un bon tutoriel sur la génération d'arbres? Je suppose que la partie la plus difficile génère des arbres partiels. Je sais comment implémenter générer un arbre entier, mais pas des parties de celui-ci.

Answer 1

Imaginez qu'à tout moment dans un tableau tac-tac-toe, chaque mouvement possible est une branche. L'état actuel du tableau est la racine. Un mouvement est une branche. Maintenant faites semblant (un à la fois), que chaque branche devient l'état actuel. Chaque mouvement possible devient une nouvelle branche. La feuille de l'arbre est quand le dernier mouvement est fait et la planche est pleine. La raison pour laquelle vous devez avoir un arbre, c'est qu'une fois qu'il est construit, vous devez déterminer quelle branche a le plus de feuilles qui sont des scénarios 'WIN'. Vous construisez la branche de tous les résultats possibles, additionnez le nombre total de WIN, puis effectuez le mouvement qui a la chance de se terminer avec le plus de victoires.

Faire quelque chose comme arbre ceci:

class Node { 
public: 
    std::list<Node> m_branches; 
    BoardState m_board; 
    int m_winCount; 
} 

std::list<Node> tree; 

Maintenant, vous itérer la liste des branches de l'arbre, et pour chaque branche, itérer à travers ses branches. Cela peut être fait avec une fonction récursive:

int recursiveTreeWalk(std::list<Node>& partialTree) 
{ 

    for each branch in tree 
     if node has no branches 
      calculate win 1/0; 
     else 
      recursiveTreeWalk(branch); 

    partialTree.m_winCount = sum of branch wins; 
} 

// initial call 
recursiveTreeWalk(tree) 

Très pseudo-code.

Answer 2

Je ne pense pas que vous ayez besoin de garder un arbre en mémoire. Il vous suffit de mettre en œuvre une fonction récursive qui fonctionne quelque chose comme:

Move getBestMove(Board state, boolean myTurn) 

Ensuite, vous RECURSE simplement jusqu'à ce que vous avez atteint un gagnant, perdant ou dessiner l'état.

La pile d'appel ressemblerait à un arbre si vous la dessiniez sur papier. Vous devriez retourner le coup qui mène à un nœud auquel l'adversaire perd (certainement/très probablement) (même s'il joue également en utilisant getBestMove)

Pour un espace-état aussi petit que le tic-tac-toe pourrait simplement faire une table de consultation complète avec les meilleurs coups! :-)

Answer 3

Si vous voulez générer l'arbre en mémoire (ce qui est nécessaire), peut-être un algorithme comme le suivant pourrait être utilisé (pseudo-code):

GenTree(State s): 
    T <- empty tree // T is a tree of States 
    SetRoot(T, s) 

    ForEach (s' in Successors(s)): 
    AddChild(T, GenTree(s')) 

    return T 

// Call it 
GenTree(currentMove) 

où

Successors(s) // returns a list of successor states of s 
AddChild(p, n) // adds n to the list of p's children 

Answer 4

vous trouverez peut-être cet article CodeProject intéressant:

Solve Tic Tac Toe with the MiniMax algorithm

C'est en C#, mais ce ne sera pas un problème pour l'adapter en C++.

Cet article a été aussi une bonne lecture pour moi quand j'ai essayé de mettre en œuvre mon premier jeu Tic-Tac Toe en C++:

Minimax Explained