c# - Búsqueda de árboles en Monte Carlo: Implementación para Tic-Tac-Toe

algorithm artificial-intelligence

Question

Edición: Ha aumentado el código fuente completo si desea ver si puede lograr que la IA tenga un mejor desempeño: https://www.dropbox.com/s/ous72hidygbnqv6/MCTS_TTT.rar

Editar: Se busca el espacio de búsqueda y se encuentran los movimientos que resultan en pérdidas. Pero los movimientos que resultan en pérdidas no se visitan muy a menudo debido al algoritmo UCT.

Para aprender sobre MCTS (Monte Carlo Tree Search), he usado el algoritmo para hacer una IA para el clásico juego de tic-tac-toe. He implementado el algoritmo usando el siguiente diseño:

La política del árbol se basa en UCT y la política predeterminada es realizar movimientos aleatorios hasta que el juego termine. Lo que he observado con mi implementación es que la computadora a veces realiza movimientos erróneos porque no puede "ver" que un movimiento en particular resultará en una pérdida directamente.

Por ejemplo: Observe cómo la acción 6 (cuadrado rojo) se valora ligeramente más alto que el cuadrado azul y, por lo tanto, la computadora marca este lugar. Creo que esto se debe a que la política del juego se basa en movimientos aleatorios y, por lo tanto, es muy probable que el humano no ponga un "2" en el cuadro azul. Y si el jugador no pone un 2 en el cuadro azul, la computadora tiene una ganancia garantizada.

Mis preguntas

1) ¿Se trata de un problema conocido con MCTS o es el resultado de una implementación fallida?

2) ¿Cuáles podrían ser las posibles soluciones? Estoy pensando en limitar los movimientos en la fase de selección, pero no estoy seguro :-)

El código para el núcleo MCTS:

    //THE EXECUTING FUNCTION
    public unsafe byte GetBestMove(Game game, int player, TreeView tv)
    {

        //Setup root and initial variables
        Node root = new Node(null, 0, Opponent(player));
        int startPlayer = player;

        helper.CopyBytes(root.state, game.board);

        //four phases: descent, roll-out, update and growth done iteratively X times
        //-----------------------------------------------------------------------------------------------------
        for (int iteration = 0; iteration < 1000; iteration++)
        {
            Node current = Selection(root, game);
            int value = Rollout(current, game, startPlayer);
            Update(current, value);
        }

        //Restore game state and return move with highest value
        helper.CopyBytes(game.board, root.state);

        //Draw tree
        DrawTree(tv, root);

        //return root.children.Aggregate((i1, i2) => i1.visits > i2.visits ? i1 : i2).action;
        return BestChildUCB(root, 0).action;
    }

    //#1. Select a node if 1: we have more valid feasible moves or 2: it is terminal 
    public Node Selection(Node current, Game game)
    {
        while (!game.IsTerminal(current.state))
        {
            List<byte> validMoves = game.GetValidMoves(current.state);

            if (validMoves.Count > current.children.Count)
                return Expand(current, game);
            else
                current = BestChildUCB(current, 1.44);
        }

        return current;
    }

    //#1. Helper
    public Node BestChildUCB(Node current, double C)
    {
        Node bestChild = null;
        double best = double.NegativeInfinity;

        foreach (Node child in current.children)
        {
            double UCB1 = ((double)child.value / (double)child.visits) + C * Math.Sqrt((2.0 * Math.Log((double)current.visits)) / (double)child.visits);

            if (UCB1 > best)
            {
                bestChild = child;
                best = UCB1;
            }
        }

        return bestChild;
    }

    //#2. Expand a node by creating a new move and returning the node
    public Node Expand(Node current, Game game)
    {
        //Copy current state to the game
        helper.CopyBytes(game.board, current.state);

        List<byte> validMoves = game.GetValidMoves(current.state);

        for (int i = 0; i < validMoves.Count; i++)
        {
            //We already have evaluated this move
            if (current.children.Exists(a => a.action == validMoves[i]))
                continue;

            int playerActing = Opponent(current.PlayerTookAction);

            Node node = new Node(current, validMoves[i], playerActing);
            current.children.Add(node);

            //Do the move in the game and save it to the child node
            game.Mark(playerActing, validMoves[i]);
            helper.CopyBytes(node.state, game.board);

            //Return to the previous game state
            helper.CopyBytes(game.board, current.state);

            return node;
        }

        throw new Exception("Error");
    }

    //#3. Roll-out. Simulate a game with a given policy and return the value
    public int Rollout(Node current, Game game, int startPlayer)
    {
        Random r = new Random(1337);
        helper.CopyBytes(game.board, current.state);
        int player = Opponent(current.PlayerTookAction);

        //Do the policy until a winner is found for the first (change?) node added
        while (game.GetWinner() == 0)
        {
            //Random
            List<byte> moves = game.GetValidMoves();
            byte move = moves[r.Next(0, moves.Count)];
            game.Mark(player, move);
            player = Opponent(player);
        }

        if (game.GetWinner() == startPlayer)
            return 1;

        return 0;
    }

    //#4. Update
    public unsafe void Update(Node current, int value)
    {
        do
        {
            current.visits++;
            current.value += value;
            current = current.parent;
        }
        while (current != null);
    }

Answer 1

Creo que tu respuesta no debería ser marcada como aceptada. Para Tic-Tac-Toe, el espacio de búsqueda es relativamente pequeño y la acción óptima debe encontrarse dentro de un número razonable de iteraciones.

Parece que su función de actualización (backpropagation) agrega la misma cantidad de recompensa a los nodos en diferentes niveles de árbol. Esto no es correcto, ya que los estados actuales son diferentes en diferentes niveles de árbol.

Le sugiero que eche un vistazo a la propagación hacia atrás en el método UCT de este ejemplo: http://mcts.ai/code/python.html

Debes actualizar la recompensa total del nodo según la recompensa calculada por el jugador anterior en un nivel específico (node.playerJustMoved en el ejemplo).

Answer 2

Mi primera conjetura es que, de la forma en que funciona su algoritmo, elige el paso que conduce más probablemente a ganar el partido (tiene la mayor cantidad de victorias en endnodes).

Su ejemplo que muestra que la IA ''falla'', por lo tanto no es un ''error'', si estoy en lo correcto. Esta forma de valorar movimientos procede de movimientos aleatorios enemigos. Esta lógica falla, porque es obvio para el jugador qué paso debe tomar para ganar el partido.

Por lo tanto, debe borrar todos los nodos que contengan un próximo nodo con ganancia para el jugador.

Tal vez me equivoque, fue solo una primera suposición ...

Answer 3

Ok, resolví el problema agregando el código:

        //If this move is terminal and the opponent wins, this means we have 
        //previously made a move where the opponent can always find a move to win.. not good
        if (game.GetWinner() == Opponent(startPlayer))
        {
            current.parent.value = int.MinValue;
            return 0;
        }

Creo que el problema fue que el espacio de búsqueda era demasiado pequeño. Esto asegura que incluso si la selección selecciona un movimiento que en realidad es terminal, este movimiento nunca se elige y el recurso se usa para explorar otros movimientos en su lugar :).

Ahora el AI contra AI siempre juega empate y el Ai es imposible de vencer como humano :-)

Answer 4

Por lo tanto, en cualquier heurística basada en el azar es posible que simplemente no busque una muestra representativa del espacio del juego. Por ejemplo, es teóricamente posible que muestre aleatoriamente exactamente la misma secuencia 100 veces, ignorando completamente la rama vecina que pierde. Esto lo diferencia de los algoritmos de búsqueda más típicos que intentan encontrar cada movimiento.

Sin embargo, es mucho más probable que esta sea una implementación fallida. El árbol de juego de la garrapata no es muy grande, ¡tiene alrededor de 9! en el movimiento uno, y reduciéndose rápidamente, por lo que es improbable que la búsqueda en el árbol no busque en cada movimiento un número razonable de iteraciones, y por lo tanto debería encontrar un movimiento óptimo.

Sin su código, realmente no puedo proporcionar más comentarios.

Si fuera a adivinar, diría que quizás esté eligiendo movimientos en función del mayor número de victorias, en lugar de la mayor fracción de victorias, y, por lo tanto, generalmente sesgo la selección hacia los movimientos que se buscaron la mayoría de las veces.