src/GameAI/Algorithms/MonteCarlo/UCB1Tree.cs
/// <summary>
/// Return the best Transition found after running the UCB1 Tree algorithm for the specified length of time.
/// </summary>
/// <param name="game">The initial gamestate from which to find the best move for the current player.</param>
/// <param name="milliseconds">The length of time the algorithm will run.</param>
Return the best Transition found after running the UCB1 Tree algorithm for the specified length of time.
Return the best Transition found after running the UCB1 Tree algorithm for the specified length of time .
public static Transition Search(TGame game, long milliseconds)
        {
            Dictionary<long, Node> tree = new Dictionary<long, Node>
            {
                { game.Hash, new Node(game.CurrentPlayer) }
            };
            List<Node> path = new List<Node>();
            TGame copy;
            List<Transition> allTransitions;
            List<Transition> transitionsNoStats;
            Random rng = new Random();
            Stopwatch sw = new Stopwatch();
            sw.Start();
            while (sw.ElapsedMilliseconds < milliseconds)
            {
                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 , long milliseconds ) { Dictionary < long , Node > tree = new Dictionary < long , Node > { { game . Hash , new Node ( game . CurrentPlayer ) } } ; List < Node > path = new List < Node > ( ) ; TGame copy ; List < Transition > allTransitions ; List < Transition > transitionsNoStats ; Random rng = new Random ( ) ; Stopwatch sw = new Stopwatch ( ) ; sw . Start ( ) ; while ( sw . ElapsedMilliseconds < milliseconds ) { 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 running the UCB1 Tree algorithm for the specified length of time.
Return the best Transition found after running the UCB1 Tree algorithm for the specified length of time .
// 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 .
milliseconds
long
The length of time the algorithm will run.
The length of time the algorithm will run .