{"id":223,"date":"2022-03-21T03:37:07","date_gmt":"2022-03-20T19:37:07","guid":{"rendered":"http:\/\/139.224.63.49\/?p=223"},"modified":"2022-03-21T03:37:07","modified_gmt":"2022-03-20T19:37:07","slug":"%e7%94%a8monte-carlo-tree-search%e6%9d%a5%e8%a7%a3%e5%86%b3%e5%80%92%e6%b0%b4%e9%97%ae%e9%a2%98%ef%bc%88water-sort-puzzle%ef%bc%89","status":"publish","type":"post","link":"http:\/\/iamnear.top\/?p=223","title":{"rendered":"\u7528Monte Carlo tree search\u6765\u89e3\u51b3\u5012\u6c34\u95ee\u9898\uff08Water Sort Puzzle\uff09"},"content":{"rendered":"\n<p><a href=\"https:\/\/ai-boson.github.io\/mcts\/\">https:\/\/ai-boson.github.io\/mcts\/<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Monte_Carlo_tree_search\">https:\/\/en.wikipedia.org\/wiki\/Monte_Carlo_tree_search<\/a><\/p>\n\n\n\n<p>\u4e4b\u524d\u6211\u6ca1\u4e86\u89e3\u8fc7\u535a\u5f08\u6811\uff0c\u8499\u7279\u5361\u6d1b\u641c\u7d22\u65b9\u9762\u7684\u77e5\u8bc6\u3002\u5f53\u65f6\u6211\u89c9\u5f97\u8fd9\u4e2a\u95ee\u9898\u4f3c\u4e4e\u5206\u652f\u4e0d\u591a\u7684\u6837\u5b50\uff0c\u5c31\u76f4\u63a5bfs\u66b4\u529b\u641c\u7d22\uff0c\u7ed3\u679c\u641c\u523030\u5c42\u5de6\u53f3\u5c31\u7206\u5185\u5b58\u4e86\uff0860g+\u7684\u5185\u5b58\uff09\u3002\u5373\u4f7f\u6211\u52a0\u5165\u4e86\u4e00\u4e9b\u57fa\u4e8e\u8bc4\u5206\u7684\u526a\u679d\u548c\u6392\u5e8f\uff0c\u8fd8\u662f\u65e0\u6cd5\u7a81\u783435\u5c42\u3002<\/p>\n\n\n\n<p>\u73b0\u5728\u7528\u4e86mcts\u65b9\u6cd5\uff0c\u771f\u7684\u662famazing\uff01\uff01\uff01<\/p>\n\n\n\n<p>\u8fd9\u91cc\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0cwater sort puzzle \u76f8\u6bd4\u8f83\u4e8e\u5176\u4ed6\u6e38\u620f\uff0c\u6bd4\u5982\u4e94\u5b50\u68cb\u7b49\u7b49\uff0c\u5b58\u5728\u5faa\u73af\u641c\u7d22\u7684\u95ee\u9898\u3002\u6240\u4ee5\u5982\u679c\u4e0d\u52a0\u9650\u5236\uff0c\u53ef\u80fd\u4f1a\u5bfc\u81f4rollout\u9677\u5165\u5f88\u957f\u65f6\u95f4\u7684\u5faa\u73af\u3002\u6240\u4ee5\u6211\u5728rollout\u52a0\u5165\u4e86set\u6765\u9632\u6b62\u5faa\u73af\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import numpy as np \nfrom collections import defaultdict\nfrom copy import copy,deepcopy\n\nclass State():\n\tdef __init__(self,state):\n\t\tself.state = state \n\t\tassert isinstance(self.state,list)\n\t\tfor item in state:\n\t\t\tassert isinstance(item,list)\n\t\tself.num_of_container = len(self.state)\n\t\tcnt = 0\n\t\tfor item in state:\n\t\t\tcnt += len(item)\n\t\tassert cnt%4==0\n\t\tself.num_of_color = cnt\/\/4\n\n\tdef __eq__(self,other):\n\t\tif not isinstance(other,State):\n\t\t\treturn False\n\t\treturn self.state==other.state\n\n\tdef __hash__(self):\n\t\tr = 0\n\t\tfor container in self.state:\n\t\t\tfor color in container:\n\t\t\t\tr += hash(color)*37\n\t\treturn r\n\n\t@staticmethod\n\tdef same_color_in_container(container):\n\t\tif len(container)==0:\n\t\t\treturn True \n\t\tcolor = container&#91;0]\n\t\tfor i in range(1,len(container)):\n\t\t\tif container&#91;i]!=color:\n\t\t\t\treturn False\n\t\treturn True\n\n\tdef __check(self,from_idx,to_idx):\n\t\tif from_idx&lt;0 or from_idx>=self.num_of_container or to_idx&lt;0 or to_idx>=self.num_of_container or from_idx==to_idx:\n\t\t\treturn False\n\t\tfv = self.state&#91;from_idx]\n\t\ttv = self.state&#91;to_idx]\n\t\tif len(fv)==0:\n\t\t\treturn False\n\t\tif len(tv)==4:\n\t\t\treturn False\n\t\tif len(tv)>0 and tv&#91;-1]!=fv&#91;-1]:\n\t\t\treturn False\n\t\tif len(fv)==4 and fv&#91;0]==fv&#91;1]==fv&#91;2]==fv&#91;3]:\n\t\t\treturn False\n\t\tif len(tv)==0 and State.same_color_in_container(fv):\n\t\t\treturn False\n\t\treturn True\n\n\tdef get_legal_actions(self):\n\t\tactions = &#91;]\n\t\tfor i in range(self.num_of_container):\n\t\t\tfor j in range(self.num_of_container):\n\t\t\t\tif self.__check(i,j):\n\t\t\t\t\tactions.append((i,j))\n\t\treturn actions\n\n\tdef move(self,action):\n\t\tret = deepcopy(self)\n\t\tfrom_idx = action&#91;0]\n\t\tto_idx = action&#91;1]\n\t\tfv = ret.state&#91;from_idx]\n\t\ttv = ret.state&#91;to_idx]\n\t\tc = fv&#91;-1]\n\t\tcnt = 1\n\t\ti = len(fv)-2\n\t\twhile i>=0 and fv&#91;i]==c:\n\t\t\ti -= 1\n\t\t\tcnt += 1 \n\t\tcnt = min(cnt,4-len(tv))\n\t\tfor i in range(cnt):\n\t\t\tfv.pop()\n\t\t\ttv.append(c)\n\t\treturn ret\n\n\tdef game_result(self):\n\t\tfor v in self.state:\n\t\t\tif len(v)==0:\n\t\t\t\tcontinue\n\t\t\tif len(v)&lt;4:\n\t\t\t\treturn -1\n\t\t\tfor i in range(3):\n\t\t\t\tif v&#91;i]!=v&#91;i+1]:\n\t\t\t\t\treturn -1\n\t\treturn 1\n\n\tdef is_game_over(self):\n\t\treturn len(self.get_legal_actions())==0\n\n\tdef __str__(self):\n\t\ts = ''\n\t\tfor item in self.state:\n\t\t\ts += str(item)+'\\n'\n\t\treturn s\n\n\n\n\nclass MonteCarloTreeSearchNode():\n\tdef __init__(self,state,parent=None,parent_action=None):\n\t\tself.state = state\n\t\tself.parent = parent\n\t\tself.parent_action = parent_action\n\t\tself.children = &#91;]\n\t\tself._number_of_visits = 0\n\t\tself._results = defaultdict(int)\n\t\tself._results&#91;1] = 0\n\t\tself._results&#91;-1] = 0\n\t\tself._untried_actions = None\n\t\tself._untried_actions = self.untried_actions()\n\t\treturn\n\n\tdef __str__(self):\n\t\ts = str(self.state)\n\t\ts += 'num_of_vis={}\\n'.format(self._number_of_visits)\n\t\ts += 'wins={} loss={}\\n'.format(self._results&#91;1],self._results&#91;-1])\n\t\treturn s\n\n\tdef untried_actions(self):\n\t\tself._untried_actions = self.state.get_legal_actions()\n\t\treturn self._untried_actions\n\n\tdef q(self):\n\t\twins = self._results&#91;1]\n\t\tloses = self._results&#91;-1]\n\t\treturn wins-loses\n\n\tdef n(self):\n\t\treturn self._number_of_visits\n\n\tdef expand(self):\n\t\taction = self._untried_actions.pop()\n\t\tnext_state = self.state.move(action)\n\t\tchild_node = MonteCarloTreeSearchNode(next_state,parent=self,parent_action=action)\n\t\tself.children.append(child_node)\n\t\treturn child_node\n\n\tdef is_terminal_node(self):\n\t\treturn self.state.is_game_over()\n\n\tdef rollout(self):\n\t\tcurrent_rollout_state = self.state\n\t\tvisited_state = set()\n\t\tvisited_state.add(current_rollout_state)\n\t\t#max_iter = 100\n\t\t#iter_cnt = 0\n\t\twhile not current_rollout_state.is_game_over():\n\t\t\tpossible_moves = current_rollout_state.get_legal_actions()\n\t\t\tpossible_states = &#91;current_rollout_state.move(a) for a in possible_moves]\n\n\t\t\tfor i in range(len(possible_states)-1,-1,-1):\n\t\t\t\tif possible_states&#91;i] in visited_state:\n\t\t\t\t\tpossible_states.pop(i)\n\t\t\tif len(possible_states)==0:\n\t\t\t\treturn -1\n\t\t\tcurrent_rollout_state = possible_states&#91;np.random.randint(len(possible_states))]\n\t\t\tvisited_state.add(current_rollout_state)\n\t\treturn current_rollout_state.game_result()\n\n\tdef backpropagate(self,result):\n\t\tself._number_of_visits += 1\n\t\tself._results&#91;result] += 1\n\t\tif self.parent:\n\t\t\tself.parent.backpropagate(result)\n\n\tdef is_fully_expanded(self):\n\t\treturn len(self._untried_actions)==0\n\n\tdef best_child(self,c_param=0.1):\n\t    choices_weights = &#91;(c.q() \/ c.n()) + c_param * np.sqrt((2 * np.log(self.n()) \/ c.n())) for c in self.children]\n\t    return self.children&#91;np.argmax(choices_weights)]\n\n\tdef rollout_policy(self,possible_moves):\n\t\treturn possible_moves&#91;np.random.randint(len(possible_moves))]\n\n\tdef _tree_policy(self):\n\t\tcurrent_node = self\n\t\twhile not current_node.is_terminal_node():\n\t\t\tif not current_node.is_fully_expanded():\n\t\t\t\treturn current_node.expand()\n\t\t\telse:\n\t\t\t\tcurrent_node = current_node.best_child()\n\t\treturn current_node\n\n\tdef best_action(self):\n\t\tsimulation_no = 100\n\t\tfor i in range(simulation_no):\n\t\t\tv = self._tree_policy()\n\t\t\treward = v.rollout()\n\t\t\tv.backpropagate(reward)\n\t\treturn self.best_child(c_param=0.)\n\nif __name__=='__main__':\n\t\n\tinitial_state = State(&#91;&#91;],&#91;],&#91;4,3,2,1],&#91;2,6,1,5],&#91;1,8,6,7],&#91;4,9,2,7],&#91;10,5,3,4],&#91;10,7,4,10],&#91;9,8,11,3],&#91;5,12,3,9],&#91;11,6,5,12],&#91;12,11,2,6],&#91;10,9,12,1],&#91;11,8,8,7]])\n\troot = MonteCarloTreeSearchNode(state = initial_state)\n\tround = 0\n\twhile True:\n\t\tprint('rount:{}'.format(round))\n\t\tround += 1\n\t\tprint(root)\n\t\tif root.is_terminal_node():\n\t\t\tbreak\n\t\tselected_node = root.best_action()\n\t\troot = selected_node\n\t\t<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/ai-boson.github.io\/mcts\/ https:\/\/en.wikipe&hellip; <a href=\"http:\/\/iamnear.top\/?p=223\" class=\"more-link read-more\" rel=\"bookmark\">\u7ee7\u7eed\u9605\u8bfb <span class=\"screen-reader-text\">\u7528Monte Carlo tree search\u6765\u89e3\u51b3\u5012\u6c34\u95ee\u9898\uff08Water Sort Puzzle\uff09<\/span><i class=\"fa fa-arrow-right\"><\/i><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":{"0":"post-223","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"hentry","6":"category-uncategorized","7":"h-entry","9":"h-as-article"},"_links":{"self":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/223","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=223"}],"version-history":[{"count":1,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/223\/revisions"}],"predecessor-version":[{"id":224,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/223\/revisions\/224"}],"wp:attachment":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=223"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}