src/GameAI/Algorithms/MonteCarlo/UCB1Tree.cs
/// <summary>
/// Return the best Transition found after performing the specified number of simulations on the game.
/// </summary>
/// <param name="game">The initial gamestate from which to find the best move for the current player.</param>
/// <param name="simulations">The number of simulations to run on the game.</param>
Return the best Transition found after performing the specified number of simulations on the game.
Return the best Transition found after performing the specified number of simulations on the game .
public static Transition Search(TGame game, int simulations)
        {
            Dictionary<long, Node> tree = new Dictionary<long, Node>
            {
                { game.Hash, new Node(game.CurrentPlayer) }
            };
            List<Node> path = new List<Node>();
            IGame copy;
            List<Transition> allTransitions;
            List<Transition> transitionsNoStats;
            Random rng = new Random();
            for (int i = 0; i < simulations; i++)
            {
                copy = game.DeepCopy();
                path.Clear();
                path.Add(tree[game.Hash]);
                while (!copy.IsGameOver())
                {
                    allTransitions = copy.GetLegalTransitions();
                    transitionsNoStats = new List<Transition>();
                    foreach (Transition transition in allTransitions)
                        if (!tree.ContainsKey(transition.Hash))
                            transitionsNoStats.Add(transition);
                    if (transitionsNoStats.Count == 0)
                    {
                        double bestScore = float.MinValue;
                        int parentPlays = path[path.Count - 1].plays;
                        double ucb1Score;
                        int indexOfBestTransition = 0;
                        for (int j = 0; j < allTransitions.Count; j++)
                        {
                            ucb1Score = tree[allTransitions[j].Hash].ParentUCBScore(parentPlays);
                            if (ucb1Score > bestScore)
                            {
                                bestScore = ucb1Score;
                                indexOfBestTransition = j;
                            }
                        }
                        Transition bestTransition = allTransitions[indexOfBestTransition];
                        copy.Transition(bestTransition);
                        path.Add(tree[bestTransition.Hash]);
                    }
                    else
                    {
                        copy.Transition(transitionsNoStats.RandomItem(rng));
                        Node node = new Node(copy.CurrentPlayer);
                        tree.Add(copy.Hash, node);
                        path.Add(node);
                        break;
                    }
                }
                copy.Rollout();
                foreach (Node node in path)
                {
                    node.plays++;
                    if (copy.IsWinner(node.player))
                        node.wins++;
                }
            }
            allTransitions = game.GetLegalTransitions();
            int indexOfBestMoveFound = 0;
            double worstScoreFound = double.MaxValue;
            double score;
            for (int i = 0; i < allTransitions.Count; i++)
            {
                score = tree[allTransitions[i].Hash].CurrentPlayerScore();
                if (score < worstScoreFound)
                {
                    worstScoreFound = score;
                    indexOfBestMoveFound = i;
                }
            }
            return allTransitions[indexOfBestMoveFound];
        }
public static Transition Search ( TGame game , int simulations ) { Dictionary < long , Node > tree = new Dictionary < long , Node > { { game . Hash , new Node ( game . CurrentPlayer ) } } ; List < Node > path = new List < Node > ( ) ; IGame copy ; List < Transition > allTransitions ; List < Transition > transitionsNoStats ; Random rng = new Random ( ) ; for ( int i = 0 ; i < simulations ; i ++ ) { copy = game . DeepCopy ( ) ; path . Clear ( ) ; path . Add ( tree [ game . Hash ] ) ; while ( ! copy . IsGameOver ( ) ) { allTransitions = copy . GetLegalTransitions ( ) ; transitionsNoStats = new List < Transition > ( ) ; foreach ( Transition transition in allTransitions ) if ( ! tree . ContainsKey ( transition . Hash ) ) transitionsNoStats . Add ( transition ) ; if ( transitionsNoStats . Count == 0 ) { double bestScore = float . MinValue ; int parentPlays = path [ path . Count - 1 ] . plays ; double ucb1Score ; int indexOfBestTransition = 0 ; for ( int j = 0 ; j < allTransitions . Count ; j ++ ) { ucb1Score = tree [ allTransitions [ j ] . Hash ] . ParentUCBScore ( parentPlays ) ; if ( ucb1Score > bestScore ) { bestScore = ucb1Score ; indexOfBestTransition = j ; } } Transition bestTransition = allTransitions [ indexOfBestTransition ] ; copy . Transition ( bestTransition ) ; path . Add ( tree [ bestTransition . Hash ] ) ; } else { copy . Transition ( transitionsNoStats . RandomItem ( rng ) ) ; Node node = new Node ( copy . CurrentPlayer ) ; tree . Add ( copy . Hash , node ) ; path . Add ( node ) ; break ; } } copy . Rollout ( ) ; foreach ( Node node in path ) { node . plays ++ ; if ( copy . IsWinner ( node . player ) ) node . wins ++ ; } } allTransitions = game . GetLegalTransitions ( ) ; int indexOfBestMoveFound = 0 ; double worstScoreFound = double . MaxValue ; double score ; for ( int i = 0 ; i < allTransitions . Count ; i ++ ) { score = tree [ allTransitions [ i ] . Hash ] . CurrentPlayerScore ( ) ; if ( score < worstScoreFound ) { worstScoreFound = score ; indexOfBestMoveFound = i ; } } return allTransitions [ indexOfBestMoveFound ] ; }
Return the best Transition found after performing the specified number of simulations on the game.
Return the best Transition found after performing the specified number of simulations on the game .
// SELECTION // EXPANSION // ROLLOUT // BACKPROP // Simulations are over. Pick the best move, then return it //Console.WriteLine("Root: plays-{0} wins-{1} plyr-{2}", tree[game.GetHash()].plays, tree[game.GetHash()].wins, tree[game.GetHash()].player); //Node n = tree[allTransitions[i].Hash]; //Console.WriteLine("Move {0}: plays-{1} wins-{2} plyr-{3}", i, n.plays, n.wins, n.player); // **NOTE** // The best move chosen is the move with gives the // opponent the least number of victories
game
TGame
The initial gamestate from which to find the best move for the current player.
The initial gamestate from which to find the best move for the current player .
simulations
int
The number of simulations to run on the game.
The number of simulations to run on the game .