# Tensor Implementation of Monte-Carlo Tree Search for Model-Based Reinforcement Learning
## 3 Proposed Implementation
### Phase of Selection  
The pseudocode of the phase of selection is given in Algorithm 2, and the flowchart is shown in Figure 2. During one iteration of MCTS, each tree is traversed to find the leaf node. Let the \(L\)-step trajectory consists of combinations of traversed nodes and edges (actions) in-order, then we can write trajectory as \(\tau=[(ID_{0},a_{0}),(ID_{1},a_{1}),(ID_{2},a_{2}),\cdots,(ID_{L-1},a_{L-1})]\). Tensor \(I\) holds IDs of traversed nodes and tensor \(A\) indices of selected actions chosen by the PUCT method. Both tensors have size \(C_{N}\times C_{T}\). \(C_{N}\) is the number of simulations increased by one because the first ID and action in trajectory belong to the root of a tree. Each tree has its trajectory stored in one column whose index corresponds to a particular tree. Therefore, the number of columns is \(C_{T}\). Vector \(\vec{l}\) stores the indices of the last elements of each trajectory. Information stored in all three tensors are used in the next phases. Each trajectory starts from the root. Root indices (IDs) are inserted into the zero row of tensor \(I\) (Algorithm 2, line 4). Indices of active trajectories are stored in vector \(\vec{i_{N}}\). In other words, vector \(\vec{i_{N}}\) remembers indices of trees that are still active in the phase of selection. At the beginning of each selection phase, vector is filled by vector of all tree indices because each tree takes a part in the selection phase. The loop of the selection phase starts with condition \(\vec{i_{N}}\
eq\emptyset\). Condition checks whether the vector of active trajectories is empty. If there is no active trajectory, the phase of selection is finished. Otherwise, IDs of nodes in active trajectories are assigned to vector \(\vec{i}\) by indexing via the current step and vector \(\vec{i_{N}}\) in the tensor \(I\) (Algorithm 2, line 8). Computing of the PUCT method (Equation (1)) for current nodes is fully executed by tensor operations of adding, multiplying, dividing, etc. The method returns vector of selected actions of current nodes. Indices of the last items in active trajectories are updated (Algorithm 2, line 11). The IDs of the nodes accessed using the actions \(\vec{a}\) in current nodes \(\vec{i}\) are obtained from tensor \(E\). As we mentioned before, if there is no children node for combination \(((ID,a))\), \(0\) is returned instead. Obtained IDs and possible zero indices are inserted into a new row of the tensor \(I\). For simplicity's sake, let the number of trees \(C_{T}=4\), number of active trajectories \(|\vec{i_{N}}|=3\), indices of active trajectories \(\vec{i_{N}}=[0,1,3]\), node IDs \(\vec{i}=[5,7,8]\), selected actions \(\vec{a}=[3,1,0]\) and IDs of children nodes \(E(\vec{i},\vec{a})=[E(5,3)=15,E(7,1)=0,E(8,0)=21]=[15,0,21]\). Since \(I(step,\vec{i_{N}})=[15,0,21]\), updated row of the tensor is \(I(step)=[15,0,0,21]\). \(I(step,0)=15\) and \(I(step,3)=21\) indicate active trajectories. \(I(step,1)=0\) represents inactive trajectory. This trajectory has been terminated in the current step because the node with \(ID=7\) has no children, e.g., \(E(7,1)=0\). \(I(step,2)=0\) represents a trajectory that was already inactive. Finally, we update the indices of nonzero values from the current row of \(I\). If there is no nonzero value, the phase of selection is completed. On the other hand, if there is at least one nonzero value (active trajectory), the next phase of the MCTS simulation begins.