Tic-Tac-Toe AI: ¿Cómo hacer el árbol?

Question

Estoy teniendo un gran problema tratando de entender "árboles" mientras hago un bot de Tic-Tac-Toe. Entiendo el concepto, pero no me puedo imaginar para implementarlos.

¿Alguien me puede mostrar un ejemplo de cómo se debe generar un árbol para este caso? ¿O un buen tutorial sobre la generación de árboles? Supongo que la parte difícil es generar árboles parciales. Sé cómo implementar la generación de un árbol completo, pero no partes de él.

Answer 1

Imagine que en cualquier punto de un tablero de tres en raya, cada movimiento posible es una rama. El estado actual de la placa es la raíz. Un movimiento es una rama. Ahora pretenda (uno a la vez), que cada rama se convierta en el estado actual. Cada movimiento posible se convierte en una nueva rama. La hoja del árbol es cuando se realiza el último movimiento y el tablero está lleno.

La razón por la que necesita tener un árbol, es que una vez que está construido, necesita averiguar qué rama tiene la mayor cantidad de hojas que son escenarios 'GANAR'. Cree la rama de todos los resultados posibles, sume la cantidad total de WIN y luego haga la jugada que tenga la oportunidad de obtener la mayor cantidad de ganancias.

Hacer el árbol de algo como esto:

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

std::list<Node> tree; 

Ahora, iterar a través de la lista de las ramas en el árbol, y para cada rama, iterar a través de sus ramas. Esto se puede hacer con una función recursiva:

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) 

Muy pseudocódigo.

Answer 2

No creo que necesite mantener un árbol en la memoria. Sólo hay que poner en práctica una función recursiva que funciona algo así como:

Move getBestMove(Board state, boolean myTurn) 

Entonces sólo tiene que Recurse hasta que haya alcanzado una serie, perder o dibujar-estado.

La pila de llamadas con el tiempo se vería como un árbol si la dibujara en papel. Debería devolver el movimiento que conduce a un nodo en el cual el oponente (definitivamente/más probable) pierde (aunque también juega usando getBestMove)

Para un espacio de estado tan pequeño como tres en raya, sin embargo, ¡simplemente podría hacer una tabla de búsqueda completa con las mejores jugadas! :-)

Answer 3

Si desea generar el árbol en la memoria (que no es necesario), tal vez un algoritmo como la siguiente podría ser utilizado (pseudo-código):

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) 

donde

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

Answer 4

Es posible encontrar este artículo CodeProject interesante:

Solve Tic Tac Toe with the MiniMax algorithm

Está en C#, pero no será ningún problema adaptarlo en C++.

Este artículo fue también una buena lectura para mí cuando traté de poner en práctica mi primer juego de Tic-Tac-Toe en C++:

Minimax Explained