Saltar al contenido

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

Este grupo de trabajo ha pasado horas buscando la respuesta a tus búsquedas, te compartimos la resolución y esperamos que resulte de gran apoyo.

Solución:

Imagina que en cualquier punto de un tablero de tic-tac-toe, cada movimiento posible es una rama. El estado actual de la placa es la raíz. Un movimiento es una rama. Ahora imagina (una a la vez) que cada rama se convierte en el estado actual. Cada posible movimiento 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 más hojas que son escenarios ‘GANADORES’. Construye la rama de todos los resultados posibles, suma el número total de WIN y luego realiza el movimiento que tiene la posibilidad de terminar con la mayor cantidad de victorias.

Haz que el árbol sea algo como esto:

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


std::list< Node > tree;

Ahora, itera a través de la lista de ramas en el árbol, y para cada rama, itera 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.

No creo que necesites mantener un árbol en la memoria. Simplemente necesita implementar una función recursiva que funcione de la siguiente manera:

Move getBestMove(Board state, boolean myTurn)

Luego, simplemente recurre hasta que haya alcanzado un estado ganador, perdedor o empate.

Con el tiempo, la pila de llamadas se vería como un árbol si la dibujara en papel. Debes devolver el movimiento que lleva a un nodo en el que el oponente (definitivamente / probablemente) pierde (aunque también juega usando getBestMove)

Sin embargo, para un espacio de estado tan pequeño como tic-tac-toe, ¡simplemente podría hacer una tabla de búsqueda completa con los mejores movimientos! 🙂

Puede encontrar interesante este artículo del proyecto de código:

Resuelva Tic Tac Toe con el algoritmo MiniMax

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

Este artículo también fue una buena lectura para mí cuando intenté implementar mi primer juego Tic-Tac-Toe en C ++:

Minimax explicado

valoraciones y reseñas

Si te animas, eres capaz de dejar una sección acerca de qué te ha parecido este tutorial.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *