强化学习系列（十一）--探索蒙特卡洛树搜索（MCTS）及其在大语言模型中的应用

 #! create children
        if self.node_type is Node_Type.USER_QUESTION:
            # A1: Propose an one-step thought.
            if not self.disable_a1:
                do_action_generate_ost_step()

            # A2: Propose the remaining thought steps
            do_action_generate_direct_answers()

            # A3: Propose next sub-question along with its answer.
            do_action_generate_subquestions()

            # A5: Rephrase the question/sub-question.
            if not self.disable_a5:
                do_action_generate_rephrased_user_question()

        elif self.node_type is Node_Type.REPHRASED_USER_QUESTION:
            # A1: Propose an one-step thought.
            if not self.disable_a1:
                do_action_generate_ost_step()

            # A2: Propose the remaining thought steps
            do_action_generate_direct_answers()

            # A3: Propose next sub-question along with its answer.
            do_action_generate_subquestions()
        elif self.node_type is Node_Type.DIRECT_ANSWER:
            raise ValueError("DIRECT_ANSWER node cannot create children!!")
        elif self.node_type is Node_Type.SUBQUESTION:
            # A1: Propose an one-step thought.
            if not self.disable_a1:
                do_action_generate_ost_step()

            # A2: Propose the remaining thought steps
            do_action_generate_direct_answers()

            # A3: Propose next sub-question along with its answer.
            do_action_generate_subquestions()

            # A4: Answer the sub-question again.
            do_action_generate_re_subanswers()
        elif self.node_type is Node_Type.RE_SUBANSWER:
            # A1: Propose an one-step thought.
            if not self.disable_a1:
                do_action_generate_ost_step()

            # A2: Propose the remaining thought steps
            do_action_generate_direct_answers()

            # A3: Propose next sub-question along with its answer.
            do_action_generate_subquestions()
        elif self.node_type is Node_Type.OST_STEP:
            # A1: Propose an one-step thought.
            if not self.disable_a1:
                do_action_generate_ost_step()

            # A2: Propose the remaining thought steps
            do_action_generate_direct_answers()

### Instruction:
There are 15 trees in the grove. Grove workers will plant trees in the grove today. After they are done, there will be 21 trees. How many trees did the grove workers plant today?

### Response:
Let's think step by step.
Step 1: Identify the initial number of trees. The problem states there are 15 trees in the grove.
Step 2: Identify the final number of trees. The problem states there will be 21 trees after the workers are done planting.
Step 3: Subtract the initial number of trees from the final number of trees to find out how many trees were planted.
Step 4: Therefore, the grove workers planted 21 (final number of trees) - 15 (initial number of trees) = 6 trees today.
Step 5: The answer is 6.

### Instruction:
Olivia has $23. She bought five bagels for $3 each. How much money does she have left?

### Response:
Let's think step by step. Olivia had 23 dollars. 
5 bagels for 3 dollars each will be 5 x 3 = 15 dollars. 
So she has 23 - 15 dollars left. 23 - 15 is 8. 
The answer is: 8.

Given a question, please decompose it into sub-questions. For each sub-question, please answer it in a complete sentence, ending with "The answer is <a numeric answer>". When the original question is answerable, please start the subquestion with "Now we can answer the question: <original question>".

Question 1: Given a list of conditions, please answer the question. Condition 1: Four years ago, Kody's age was half of Mohamed's age. Condition 2: Mohamed is currently twice as old as 30 years. Question: What is Kody's current age?
Question 1.1: How old is Mohamed currently?
Answer 1.1: Mohamed is twice as old as 30 years, which means he is 30 * 2 = 60 years old.
Question 1.2: What was Kody's age four years ago, given that it was half of Mohamed's age at that time?
Answer 1.2: Four years ago, Mohamed was 60 - 4 = 56 years old, so Kody was half of that, which is 56 / 2 = 28 years old.
Question 1.3: Now we can answer the question: How old is Kody?
Answer 1.3: Kody is currently 28 + 4 = 32 years old. The answer is 32.

Original Question: There are 15 trees in the grove. Grove workers will plant trees in the grove today. After they are done, there will be 21 trees. How many trees did the grove workers plant today?
Rephrased Question: Given a list of conditions, please answer the question. 
Condition 1: Initially, there are 15 trees in the grove. 
Condition 2: Grove workers will add more trees to the grove today. 
Condition 3: After planting, the total number of trees in the grove will increase to 21. 
Question: How many trees did the grove workers plant today?

for i in (pbar := trange(args.num_rollouts, disable=True, position=0)):
        # mcts蒙特卡洛树：do num_rollouts次rollout，构建搜索树
        rollout_node = mcts_searcher.do_rollout(root_node, i)
        model_rollout_nodes.append(rollout_node)
        # search出最优路径
        _, best_solution, _, chosen_node, all_solution_nodes, all_solutions = stochastic_find_best_solution(
            root_node, generator.evaluator, enable_potential_score=args.enable_potential_score
        )
        model_solutions.append(best_solution)
        model_all_solutions.append(all_solutions)

       def do_rollout(self, root_node: MCTS_Node, rollout_id: int):
        "Make the tree one layer better. (Train for one iteration.)"
        # select: 选择树节点
        path_1 = self._select(root_node, rollout_id)
        leaf = path_1[-1]
        # expand: 扩展节点
        self._expand(leaf, rollout_id)
        # simulate: 从扩展后的节点开始进行随机模拟，只到得到答案
        path_2 = self._simulate(leaf, rollout_id)
        # backpropagate：选择的路径反向传播，更新节点信息
        self._backpropagate(path_1 + path_2)
        try:
            return path_2[-1]
        except:
            return path_1[-1]

def stochastic_find_best_solution(
    root_node,
    evaluator,
    enable_potential_score,
):
    # todo: what strategy do we use to select best node?
    """The function finds the best solution from the solution nodes in the MCTS tree.
    Return: top answer, top solution, confidence of the top answer, the corresponding node of the answer, all solution nodes
    """
    # 有效的solution_node: in SUBQUESTION type or DIRECT_ANSWER type or OST_STEP type,也就是叶子节点或者A1
    solution_nodes = find_valid_solution_nodes(root_node)

    if len(solution_nodes) == 0:
        return None, None
    # 提取node的答案
    def extract_solution_from_node(node):
        if node.node_type is Node_Type.SUBQUESTION:
            return node.subanswer
        elif node.node_type is Node_Type.DIRECT_ANSWER:
            return node.direct_answer
        else:
            return None
    # 提取solution_nodes的答案，也就是每条路径的最终答案
    solutions = [extract_solution_from_node(node) for node in solution_nodes]
    
    # 统计每个solutoin_node的分数
    def calculate_potential_score_for_solution_node(node):
        # 根据规则把最终答案提取出来
        model_answer = evaluator.extract_answer_from_model_completion(extract_solution_from_node(node))
        potential_answers_history = node.potential_answers_history  # {depth -> [potential answers]}
        assert potential_answers_history[node.depth] is None
        
        # 这段代码是计算solution_node在树中每一层的得分depth_score
        #（potential_answers_history记录的是node的所有祖先节点产生的potential_answers。
        #如果path中节点高比例得到的answer和solution_node的answer相等，分数高），
        # 最后将每层的depth_score相乘作为最终potential_score 。
        potential_score = 1
        for depth, depth_potential_answers in potential_answers_history.items():
            if depth < node.depth:
                depth_score = sum(
                    evaluator.check_answers_equiv(dpa, model_answer) for dpa in depth_potential_answers
                ) / len(depth_potential_answers)
                potential_score *= depth_score

        node.set_potential_score(potential_score)
        return potential_score

    prior_weights = (
        [calculate_potential_score_for_solution_node(node) for node in solution_nodes]
        if enable_potential_score
        else None
    )
    # 统计分数最高的答案和path
    top_answer, top_completion, top_completion_id, top_confidence = evaluator.stochastic_find_most_confident_answer(
        completions=solutions, prior_weights=prior_weights
    )
    return top_answer, top_completion, top_confidence, solution_nodes[top_completion_id], solution_nodes, solutions