Answers.Body: <h1>Unexplored children</h1>
  <p>If a node has any unexplored children you have to select one of them, before computing UCB values and selecting the best one. Alternatively you could return <code>+inf</code> as the UCB value for nodes without any visits.</p>
  <p>If you want to completely remove any bias towards the first move, you can also consider selecting a random unexplored one, instead of the first one. This is not that important though.</p>
  <h1>Storing the game state</h1>
  <p>For the game state you have two options:</p>
  <ul>
  <li>store the game state in each node</li>
  <li>compute the game state from scratch each time while selecting down the tree</li>
  </ul>
  <p>This is a memory/compute tradeoff, depending on how large the board representation is and how expensive playing a move are both of them can make sense.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-10T22:11:03.467Z
Answers.LastActivityDate: 2023-02-15T13:33:15.263Z
Answers.LastEditDate: 2023-02-15T13:33:15.263Z
Answers.UserDisplayName: KarelPeeters
Body: <p>I am trying to implement MCTS for a custom word game I am working on. I feel like I have got all the pieces of code needed, but the algorithm seems to always return the first available move (first child of provided root note). I feel like this has something to do with the selection phase, as none of the children will have any visits after being created. Below is some of my code used in my implementation:</p>
  <p>Node class containing game state, children/parent, visits/wins and functions for MCTS phases:</p>
  <pre><code>class MCTSNode {
      // Node stuff
      parent: MCTSNode | null;
      children: MCTSNode[];
  
      // Gamestate stuff
      /*
          I chose not to include this here as it is not important for the problem
      */
  
      // Stats
      visits: number;
      wins: number;
  
      constructor(parent: MCTSNode | null) {
          /*
              Here I set all the gamestate stuff
          */
          this.parent = parent;
          this.children = [];
          this.visits = 0;
          this.wins = 0;
      }
  
      private getAvailablePlays(): Play[] {
          /*
              Returns an array of legal plays
          */
      }
  
      private play(play: Play): MCTSNode {
          /*
              Returns the resulting child node if a certain play is applied to the current node
          */
      }
  
      private getUCB1(biasParam: number = 2) {
          return this.wins / this.visits + Math.sqrt((biasParam * Math.log(this.parent!.visits)) / this.visits);
      }
  
      private winner() {
          /*
              Returns winner of current node(game state) 
              null if game is not finished yet
              &quot;&quot; if game is draw
              &quot;ai&quot; if ai wins, &quot;player&quot; if player wins
          */
      }
  
      select(): MCTSNode {
          // implement logic to select a child node based on UCB1
          let node: MCTSNode = this;
          while (node.children.length &gt; 0) {
              let bestNode = node.children[0];
              let bestUCB1 = -Infinity;
              for (let child of node.children) {
                  let childUCB1 = child.getUCB1();
                  if (childUCB1 &gt; bestUCB1) {
                      bestNode = child;
                      bestUCB1 = childUCB1;
                  }
              }
              node = bestNode!;
          }
          return node;
      }
  
      expand() {
          // Expand current node by adding all available child states(nodes) to children
          const availablePlays = this.getAvailablePlays();
          for (const play of availablePlays) {
              const child = this.play(play);
              this.children.push(child);
          }
      }
  
      simulate() {
          // implement logic to simulate a game from this node and return the score
          let currNode: MCTSNode = this;
          let winner = currNode.winner();
  
          while (winner === null) {
              let plays = currNode.getAvailablePlays();
              let play = plays[Math.floor(Math.random() * plays.length)];
              currNode = currNode.play(play);
              winner = currNode.winner();
          }
          return winner;
      }
  
      backpropagate(winner: string) {
          // implement logic to backpropagate the score to the parent nodes
          let currNode: MCTSNode | null = this;
          while (currNode !== null) {
              currNode.visits += 1;
              // Parent's choice (currNode.turn is either &quot;ai&quot; or &quot;player&quot;)
              if (currNode.turn === winner) {
                  currNode.wins += 1;
              }
              currNode = currNode.parent;
          }
      }
  }
  
  </code></pre>
  <p>MCTS Function that should return the most promising child node of root based on <em>robust</em> or <em>max</em> policy:</p>
  <pre><code>const mcts = (root: MCTSNode, rounds: number = 100, policy: string = &quot;robust&quot;) =&gt; {
      for (let i = 0; i &lt; rounds; i++) {
          let node = root.select();
  
          node.expand();
  
          const winner = node.simulate();
  
          node.backpropagate(winner);
      }
  
      let max = 0;
      let bestNode: MCTSNode | null = null;
      for (let child of root.children) {
          if (policy === &quot;robust&quot; &amp;&amp; child.visits &gt; max) {
              max = child.visits;
              bestNode = child;
          }
          if (policy === &quot;max&quot; &amp;&amp; child.wins &gt; max) {
              max = child.wins;
              bestNode = child;
          }
      }
      return bestNode;
  };
  </code></pre>
  <p>I am mainly wondering if the <strong>select</strong> and <strong>mcts</strong> functions are implemented correctly. Furthermore I am currently storing the game state in each node. Is this a bad idea with regards to efficiency/memory?</p>
  
Tags: <monte-carlo-tree-search><upper-confidence-bound><javascript>
Title: MCTS: How to select children when none of them are visited?
UserDisplayName: nikord
ThreadText: # MCTS: How to select children when none of them are visited?
  
  (Asked by: username_0 on 2023-02-10)
  
  I am trying to implement MCTS for a custom word game I am working on. I feel like I have got all the pieces of code needed, but the algorithm seems to always return the first available move (first child of provided root note). I feel like this has something to do with the selection phase, as none of the children will have any visits after being created. Below is some of my code used in my implementation:
  Node class containing game state, children/parent, visits/wins and functions for MCTS phases:
  class MCTSNode {
      // Node stuff
      parent: MCTSNode | null;
      children: MCTSNode[];
  
      // Gamestate stuff
      /*
          I chose not to include this here as it is not important for the problem
      */
  
      // Stats
      visits: number;
      wins: number;
  
      constructor(parent: MCTSNode | null) {
          /*
              Here I set all the gamestate stuff
          */
          this.parent = parent;
          this.children = [];
          this.visits = 0;
          this.wins = 0;
      }
  
      private getAvailablePlays(): Play[] {
          /*
              Returns an array of legal plays
          */
      }
  
      private play(play: Play): MCTSNode {
          /*
              Returns the resulting child node if a certain play is applied to the current node
          */
      }
  
      private getUCB1(biasParam: number = 2) {
          return this.wins / this.visits + Math.sqrt((biasParam * Math.log(this.parent!.visits)) / this.visits);
      }
  
      private winner() {
          /*
              Returns winner of current node(game state) 
              null if game is not finished yet
              "" if game is draw
              "ai" if ai wins, "player" if player wins
          */
      }
  
      select(): MCTSNode {
          // implement logic to select a child node based on UCB1
          let node: MCTSNode = this;
          while (node.children.length > 0) {
              let bestNode = node.children[0];
              let bestUCB1 = -Infinity;
              for (let child of node.children) {
                  let childUCB1 = child.getUCB1();
                  if (childUCB1 > bestUCB1) {
                      bestNode = child;
                      bestUCB1 = childUCB1;
                  }
              }
              node = bestNode!;
          }
          return node;
      }
  
      expand() {
          // Expand current node by adding all available child states(nodes) to children
          const availablePlays = this.getAvailablePlays();
          for (const play of availablePlays) {
              const child = this.play(play);
              this.children.push(child);
          }
      }
  
      simulate() {
          // implement logic to simulate a game from this node and return the score
          let currNode: MCTSNode = this;
          let winner = currNode.winner();
  
          while (winner === null) {
              let plays = currNode.getAvailablePlays();
              let play = plays[Math.floor(Math.random() * plays.length)];
              currNode = currNode.play(play);
              winner = currNode.winner();
          }
          return winner;
      }
  
      backpropagate(winner: string) {
          // implement logic to backpropagate the score to the parent nodes
          let currNode: MCTSNode | null = this;
          while (currNode !== null) {
              currNode.visits += 1;
              // Parent's choice (currNode.turn is either "ai" or "player")
              if (currNode.turn === winner) {
                  currNode.wins += 1;
              }
              currNode = currNode.parent;
          }
      }
  }
  
  
  MCTS Function that should return the most promising child node of root based on robust or max policy:
  const mcts = (root: MCTSNode, rounds: number = 100, policy: string = "robust") => {
      for (let i = 0; i < rounds; i++) {
          let node = root.select();
  
          node.expand();
  
          const winner = node.simulate();
  
          node.backpropagate(winner);
      }
  
      let max = 0;
      let bestNode: MCTSNode | null = null;
      for (let child of root.children) {
          if (policy === "robust" && child.visits > max) {
              max = child.visits;
              bestNode = child;
          }
          if (policy === "max" && child.wins > max) {
              max = child.wins;
              bestNode = child;
          }
      }
      return bestNode;
  };
  
  I am mainly wondering if the select and mcts functions are implemented correctly. Furthermore I am currently storing the game state in each node. Is this a bad idea with regards to efficiency/memory?
  
  **Tags:** monte-carlo-tree-search, upper-confidence-bound, javascript
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-02-10. Score: 1
  
  # Unexplored children
  
  If a node has any unexplored children you have to select one of them, before computing UCB values and selecting the best one. Alternatively you could return `+inf` as the UCB value for nodes without any visits.
  
  If you want to completely remove any bias towards the first move, you can also consider selecting a random unexplored one, instead of the first one. This is not that important though.
  
  # Storing the game state
  
  For the game state you have two options:
  
  * store the game state in each node
  * compute the game state from scratch each time while selecting down the tree
  
  This is a memory/compute tradeoff, depending on how large the board representation is and how expensive playing a move are both of them can make sense.
  
  
  ---
  
  