## 4 Monte Carlo Q-Value Function
### Best-First Simulation Policy  
Simulation policy uses a default policy to play a game quickly. After that, MCTS propagates back the simulation results. The default policy is typically domain dependent. As there is no value like \(Q(\vec{\theta}^{t},\vec{a})\) for guiding the action selection, uniformly choosing available actions is a common scheme.  
However, the heuristic knowledge of the problem can be involved into the default policy to strengthen simulation. [PERSON] (1966) discusses some factors that influence simulation performance. In this paper, we extend the rollout phase by incorporating domain knowledge into playouts, which are called heavy playouts ([PERSON] et al., 2016). If it is not the last time step, the algorithm recursively calls for the Rollout function. Then it returns the best immediate reward (\(immR\)) and backpropagates the value obtained and updates \(N(\overrightarrow{\theta})\) and \(N(\overrightarrow{\theta},\overrightarrow{a})\). This Best-First Simulation Policy (BPSP) returns the promising node first to ensure that the heuristic value is admissible or a guaranteed overestimation. The detail is shown in Algorithm 3.  
Especially we would like to note that the selectBestA() function selects the best action combining an idea of reinforcement learning and the history heuristic. Reinforcement learning (RL) reinforces the actions that make success. The history heuristic assumes that an action good in one position may be good in another. Joint actions, which acquire the highest simulating value, will be given more chances in the later simulation. Concretely, we keep an average accumulated value \(v(\overrightarrow{a})\) of each joint action in a playout. Apart from \(v(\overrightarrow{a})\), a separate visit of each action \(n_{i}\) and total visits of all actions, \(n\) in the simulation phase is also stored. An action is selected by a softmax function with inputs \(z=v(\overrightarrow{a})\cdot\frac{n_{i}}{n}\). This implies that the larger \(z\) will correspond to a larger probability. If it is at an initial state or the chance of nodes are equal, a random legal action will be selected. For example, if a problem has nine joint actions, in the start of a simulation phase, an action is selected through this softmax function. After the simulation ends, its accumulated value to the terminal is recorded and the visit number increases by one. In another simulation phase, the statistics are reused, which we call the history heuristic.  
```
Input: joint action-observation history \(\vec{\theta}\), time step \(t\) Output: the optimal reward of rollout
1:if\((isLastTimeStep)\)then
2:\(immRbest\leftarrow-\infty\)
3:for all\(\vec{a}\in A\)do
4:\(immR\leftarrow\) ComputeImmR(\(\vec{a}\))
5:\(N(\vec{\theta},\vec{a})\gets N(\vec{\theta},\vec{a})+1\)
6:\(immRbest\leftarrow\max(immR,immRbest)\)
7:\(N(\vec{\theta})\gets N(\vec{\theta})+1\)
8:return \(immRbest\)
9:else
10:for all\(\vec{a}\in A\)do
11:\(bestA\leftarrow\) selectBestA(\(\vec{a}\))
12:\(immR\leftarrow\) ComputeImmR(\(bestA\))
13:for all\(\vec{\phi}\in O\)do
14:\(\vec{\theta}^{\prime}\leftarrow(\vec{\theta},bestA,\vec{\phi})\)
15:\(\mathit{futR}\,+\,=\,\,\gamma\cdot P(\vec{\theta}^{\prime})\cdot\mathrm{ Rollout}(\vec{\theta}^{\prime},t+1)\)
16:\(N(\vec{\theta})\gets N(\vec{\theta})+1,N(\vec{\theta},bestA)\gets N (\vec{\theta},bestA)+1\)
17:return \(immR+\mathit{futR}\)
```  
**Algorithm 3**Rollout(\(\vec{\theta},t\))