haroldsultan/mcts

Python Implementations of Monte Carlo Tree Search

MCTS

Python Implementations of Monte Carlo Tree Search for experimentation.

Monte Carlo tree search (MCTS) is a newly emerging and promising algorithm in the AI literature. See http://pubs.doc.ic.ac.uk/survey-mcts-methods/survey-mcts-methods.pdf for a survey on MCTS.

This code is a toy implementation to play with the algorithm. While MCTS can apply to many settings, in the code we apply it to a pretty simple but nonetheless interesting state.

The State is a game where you have NUM_TURNS and at turn i you can make a choice from an integeter [-2,2,3,-3]*(NUM_TURNS+1-i). So for example in a game of 4 turns, on turn for turn 1 you can can choose from [-8,8,12,-12], and on turn 2 you can choose from [-6,6,9,-9]. At each turn the choosen number is accumulated into a aggregation value. The goal of the game is for the accumulated value to be as close to 0 as possible.

The game may not be very interesting but it allows one to study MCTS which is. Some features of the simple game by design are that moves do not commute, and early mistakes are more costly.

USAGE: python mcts.py --num_sims 10000 --levels 8

num_sims is the number of simulations to perform, and levels is the number of times to use MCTS to pick a best child

In a 10 turn game here is an optimal solution [-20, 27, -16, 14, 18, -15, -8, 6, -4, -2]

Here is a suboptimal solution that you may end up with a local plateau on for example [20, -18, -16, 14, 12, -10, -8, 6, 4, -3]

mcts's Issues

Adding a new game

Hey,

I want to have a 2-player game where they take turns. In the beginning there are 114 possible actions and they decrease by 1 every time a player makes a move. The game is played for 10 turns (that's the terminal state). I have my own function for the reward.

Here is a sample game tree:

START- available actions to both players -> [1,2,3,4,5,6....112,113,114]
Player 1 - takes action 5 -> [5,0,0,0,0,0,0,0,0,0] -remove action 5 from available actions
Player 2 - takes action 32->[5,0,0,0,0,32,0,0,0,0] - remove action 32 from the available actions
Player 1- takes action 97 ->[5,97,0,0,0,32,0,0,0,0] - remove action 97 from the available actions
Player 2 takes action 56 -> [5,97,0,0,0,32,56,0,0,0] - remove action 56 from the available actions
....
Final (example) game state after each player makes 5 actions -> [5,97,3,5,1,32,56,87,101,8]
First 5 entries present the actions taken by Player1, second 5 entries present the actions taken by Player 2

Finally, I apply a reward function to this vector [5,97,3,5,1,32,56,87,101,8]

My python skill is really bad. I hope you can help with this.

maybe not a good example

this is a interesting example.
but i think mcts is find a acceptable result in computational budget limit。
i try to exhaustive results,it get better result in less time.
maybe replace [2,-2,3,-3] to trick nums will be more convincing,i try it,but failed。

The UCB algorithm is a little different from the paper

According to the paper A Survey of Monte Carlo Tree Search Methods, the UCB function should look like this.

And here is the pseudo-code about the implementation.

The coefficient 2 should be outsize of the log. And this line of code is a little different from the paper https://github.com/haroldsultan/MCTS/blob/master/mcts.py#L115 .

Rewards not according to criteria

Hi,

Thank you for your awesome code (mcts.py).
However, I think the algorithm is not working according to the policy network. For example, in the link you gave, under section 2.1, it is stated that it aims to find the policy that yields the highest reward.
When I ran the algorithm, the nodes/child selected were not the highest rewards. The root child selected also did not have the highest reward. Does this mean that the policy network is not optimized, and therefore, did not choose the best action/search?

E.g. as follows:
level 0
Num Children: 4
(0, Node; children: 4; visits: 354; reward: 295.106667)
(1, Node; children: 4; visits: 928; reward: 826.746667) <--- This was selected by the algorithim
(2, Node; children: 4; visits: 582; reward: 504.422222)
(3, Node; children: 4; visits: 933; reward: 831.537778) <--- Shouldn't this be selected?
Best Child: Value: 20; Moves: [20]

The input parameters I ran was 10000 loops and 8 levels.

Thank you once again for your help. Hope to hear from you soon.

James

time series with MCTS

This is the most easy and comprehensive implementation of MCTS I have found so far.
Can you show how to build an MCTS for time series prediction with out-of sample forecasting as well.
I cannot find this anywhere. I want to predict the stock market, which is the biggest game of all. :-D

The possible moves would be MOVES=[1, 0, -1] - I think!