<.
# Task 1: Implement the Expansion phase of MCTS
Open up the file `src/main/scala/mcts/UCT.scala`.
In the `search()` method of the file, you will a comment block identifying the **Expansion** phase of MCTS. You are to implement the remainder of this phase using what you have learnt from the MCTS tutorial.
```scala
// EXPANSION phase of MCTS
// -------------------------------------------------------
if (node.untriedActions.nonEmpty) {
// TODO: Task (1) Implement the following three steps
// First, choose a random action from list of untried actions of the node
// Second, apply it to the state.
// Third, record this action and the resultant state as a child of the node.
}
```
## Hints:
0. **Choose a random action from the node**:
You should be able to access the list of available actions via `GameNode.getAvailableActions`
0. **Apply the action to the state**: You can make use of the `GameState.doAction` method.
0. **Record this action and resultant state as a child of the node**: Make use of the `GameNode.addChild` method.
# Task 2: Implement the Simulation phase of MCTS
Open up the file `src/main/scala/mcts/UCT.scala`.
In the `search()` method of the file, you will a comment block identifying the **Simulation** phase of MCTS. You are to implement the remainder of this phase using what you have learnt from the MCTS tutorial.
```scala
// SIMULATION phase of MCTS
// -------------------------------------------------------
while (state.getAvailableActions.nonEmpty) {
// TODO: Task (2) Implement the following two steps
// First, choose a random action from list of available actions of the state
// Second,apply it to the state.
}
```
## Hints:
0. **Choose a random action from the state**:
Take a look the `GameState` trait in `src/scala/mcts/GameState.scala`. Which of the methods might be useful?
0. **Apply the action to the state**: This is similar to what you did for the expansion phase earlier.
# Task 3: Implement the tree policy using the UCT formula.
Open up the file `src/main/scala/GameNode.scala`.
Look at the method called `selectChild`. This is where you will implement the UCT algorithm.
<img class="img img-responsive" src='image-uct-formula.png' width="300px"></img>
```scala
def selectChild : GameNode = {
// TODO: Task 3 -- Implement the tree policy.
//
// The tree policy is based on the UCT formula.
// Given the current GameNode, calculate the
// UCT values for each of them and return
// the child with the highest value.
// --------------------------------------------
return null;
}
```
## Hints:
0. Each `GameNode` has a list of `children` nodes that you should be selecting from.
0. Created a sorted list of `GameNode` objects in order of their game theoric value (i.e., value from the UCT formula)
0. The explotation term **(Xj)** is the estimated value of a given child node `j` . Consider how the `numberOfWins` and `numberOfVisits` can be used to estimate this.
0. Remember that `n` is the number of times the current (parent) node has been visited in total, while `n_j` is the number of times that the child node has been visited in total.
0. The code snippet below should point you in the right direction
```scala
def selectChild : GameNode = {
val sortedChildren = children.map( node => (node,
??? // Exploitation term
+ ??? // Exploration term
).sortBy(_._2)
return sortedChildren.last;
}
```
# Let's Play
Now here comes the fun part. You do not need to implement any game specific logic (they were provided by the client, remember?) So now you can just test run your MCTS AI and tell Herman you are done!
## Choose a Game
Open up `src/main/scala/Main.scala`.
Choose a game you want to play by appropriately commenting / uncommenting out the appropriate lines.
## Run the Game (and AI!)
In the terminal, simply run:
```
sbt run
```
And you're all set!
]]>