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.