src/GameAI/Algorithms/MonteCarlo/UCB1Tree.cs
/// <summary>
/// Return the best Transition found after performing in parallel 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="milliseconds">The length of time to run the search.</param>
Return the best Transition found after performing in parallel the specified number of simulations on the game.
Return the best Transition found after performing in parallel the specified number of simulations on the game .
public static Transition ParallelSearch(TGame game, long milliseconds)
        {
            ConcurrentDictionary<long, Node> tree = new ConcurrentDictionary<long, Node>();
            tree.TryAdd(game.Hash, new Node(game.CurrentPlayer));
            Stopwatch sw = new Stopwatch();
            sw.Start();
            Parallel.For(0L, Int64.MaxValue,
                () => new ThreadLocalVars(RandomFactory.Create(), new List<Node>(50)),
                (i, loop, localVars) =>
                {
                    if (sw.ElapsedMilliseconds > milliseconds)
                        loop.Stop();
                    TGame copy = game.DeepCopy();
                    localVars.path.Clear();
                    localVars.path.Add(tree[game.Hash]);
                    while (!copy.IsGameOver())
                    {
                        List<Transition> transitions = copy.GetLegalTransitions();
                        List<Transition> transitionsNoStats = new List<Transition>();
                        foreach (Transition transition in transitions)
                            if (!tree.ContainsKey(transition.Hash))
                                transitionsNoStats.Add(transition);
                        if (transitionsNoStats.Count == 0)
                        {
                            double bestScore = double.MinValue;
                            int parentPlays = localVars.path[localVars.path.Count - 1].plays;
                            double ucb1Score;
                            int indexOfBestTransition = 0;
                            for (int j = 0; j < transitions.Count; j++)
                            {
                                ucb1Score = tree[transitions[j].Hash].ParentUCBScore(parentPlays);
                                if (ucb1Score > bestScore)
                                {
                                    bestScore = ucb1Score;
                                    indexOfBestTransition = j;
                                }
                            }
                            Transition bestTransition = transitions[indexOfBestTransition];
                            copy.Transition(bestTransition);
                            localVars.path.Add(tree[bestTransition.Hash]);
                        }
                        else
                        {
                            copy.Transition(transitionsNoStats.RandomItem(localVars.random));
                            Node n = new Node(copy.CurrentPlayer);
                            if (tree.TryAdd(copy.Hash, n))
                                localVars.path.Add(n);
                            else
                                localVars.path.Add(tree[copy.Hash]);
                            break;
                        }
                    }
                    copy.Rollout();
                    foreach (Node node in localVars.path)
                    {
                        Interlocked.Add(ref node.plays, 1);
                        if (copy.IsWinner(node.player))
                            Interlocked.Add(ref node.wins, 1);
                    }
                    return localVars;
                },
                x => { }
            );
            List<Transition> 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 ParallelSearch ( TGame game , long milliseconds ) { ConcurrentDictionary < long , Node > tree = new ConcurrentDictionary < long , Node > ( ) ; tree . TryAdd ( game . Hash , new Node ( game . CurrentPlayer ) ) ; Stopwatch sw = new Stopwatch ( ) ; sw . Start ( ) ; Parallel . For ( 0L , Int64 . MaxValue , ( ) => new ThreadLocalVars ( RandomFactory . Create ( ) , new List < Node > ( 50 ) ) , ( i , loop , localVars ) => { if ( sw . ElapsedMilliseconds > milliseconds ) loop . Stop ( ) ; TGame copy = game . DeepCopy ( ) ; localVars . path . Clear ( ) ; localVars . path . Add ( tree [ game . Hash ] ) ; while ( ! copy . IsGameOver ( ) ) { List < Transition > transitions = copy . GetLegalTransitions ( ) ; List < Transition > transitionsNoStats = new List < Transition > ( ) ; foreach ( Transition transition in transitions ) if ( ! tree . ContainsKey ( transition . Hash ) ) transitionsNoStats . Add ( transition ) ; if ( transitionsNoStats . Count == 0 ) { double bestScore = double . MinValue ; int parentPlays = localVars . path [ localVars . path . Count - 1 ] . plays ; double ucb1Score ; int indexOfBestTransition = 0 ; for ( int j = 0 ; j < transitions . Count ; j ++ ) { ucb1Score = tree [ transitions [ j ] . Hash ] . ParentUCBScore ( parentPlays ) ; if ( ucb1Score > bestScore ) { bestScore = ucb1Score ; indexOfBestTransition = j ; } } Transition bestTransition = transitions [ indexOfBestTransition ] ; copy . Transition ( bestTransition ) ; localVars . path . Add ( tree [ bestTransition . Hash ] ) ; } else { copy . Transition ( transitionsNoStats . RandomItem ( localVars . random ) ) ; Node n = new Node ( copy . CurrentPlayer ) ; if ( tree . TryAdd ( copy . Hash , n ) ) localVars . path . Add ( n ) ; else localVars . path . Add ( tree [ copy . Hash ] ) ; break ; } } copy . Rollout ( ) ; foreach ( Node node in localVars . path ) { Interlocked . Add ( ref node . plays , 1 ) ; if ( copy . IsWinner ( node . player ) ) Interlocked . Add ( ref node . wins , 1 ) ; } return localVars ; } , x => { } ) ; List < Transition > 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 in parallel the specified number of simulations on the game.
Return the best Transition found after performing in parallel 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 .
milliseconds
long
The length of time to run the search.
The length of time to run the search .