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="simulations">The number of simulations to run on the game.</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, int simulations)
        {
            ConcurrentDictionary<long, Node> tree = new ConcurrentDictionary<long, Node>();
            tree.TryAdd(game.Hash, new Node(game.CurrentPlayer));
            Parallel.For(0, simulations,
                () => new ThreadLocalVars(RandomFactory.Create(), new List<Node>(50)),
                (i, loop, localVars) =>
                {
                    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 node = new Node(copy.CurrentPlayer);
                            if (tree.TryAdd(copy.Hash, node))
                                localVars.path.Add(node);
                            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 , int simulations ) { ConcurrentDictionary < long , Node > tree = new ConcurrentDictionary < long , Node > ( ) ; tree . TryAdd ( game . Hash , new Node ( game . CurrentPlayer ) ) ; Parallel . For ( 0 , simulations , ( ) => new ThreadLocalVars ( RandomFactory . Create ( ) , new List < Node > ( 50 ) ) , ( i , loop , localVars ) => { 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 node = new Node ( copy . CurrentPlayer ) ; if ( tree . TryAdd ( copy . Hash , node ) ) localVars . path . Add ( node ) ; 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 .
simulations
int
The number of simulations to run on the game.
The number of simulations to run on the game .