蒙特卡洛搜索在Snake(botzone)中的应用

数据结构课设的任务是botzone平台的snake智障AI的编写,于是写了这篇文章总结。

特点:snake是双人同时选择方向,因此minmax貌似不太可行(不能你一步我一步的下)。而每条蛇最多有3个方向能够选择,因此有9种排列组合。每层遍历9种情况,选择可行方向作为节点,以此向下继续搜索。

踩过的坑:
  • 曾经尝试过限定搜索层数,在到达限定层数时采用评估函数的评判俩条蛇在本局面下的价值,以局面价值的高低来判断输赢,输赢作为reward往上层传播。但是效果并不理想,就是个智障。
  • 我们需要计算的是3个方向的ucb值,并以此来选择bestchild,但是我一开始计算的是9种排列中可行解的ucb,并未计算某一方向的ucb,因此导致,疯狂增加那个不太可能发生的可行解(建立在对方蛇足够蠢的情况下)的权重,最终选择了那个明显不好的方向
  • 选择bestchild的时候,只选择了本方ucb最高的方向,但是对方蛇也要认为走的是最佳走法啊。有点minmax的意思,因此,选择bestchild的时候,要选择由本方ucb值最大的方向和对方ucb值最大的方向构成的可行解。

蒙特卡洛的思想不再赘述,下面是几个重要的函数实现解释:

int uctSearch(State *originstate)
{
    node *root = new node(originstate, nullptr, -1, -1);
    if (root->isTerminal)//对方必死的时候,随意选择一个我方能走的方向
    {
        vector<Action *> actions = getPossibleActions(originstate);
        return (*actions.begin())->self_dir;
    }
    while (getTime() < TIMELIMIT)
    {
        node *child = treePolicy(root);
        int reward = defaultPolicy(child->state);
        backup(child, reward);
    }
    lambda1 = 0;//最后选择时,把ucb公式中的参数置0,只讲胜率作为选择因素
    node *bestchild = getBestChild(root);
    return bestchild->self_dir;
}
vector<Action *> getPossibleActions(State *state)//用于获取9种排列组合中的可行解,即在当前局面下,双方蛇能走的方向的组合排列
{
    vector<Action *> actions;
    for (int i = 0; i < 4; i++)
    {
        if (validDirection(state, 0, i))
        {
            for (int j = 0; j < 4; j++)
            {
                if (validDirection(state, 1, j))
                {
                    point self = point(state->snake[0].begin()->x + dx[i], state->snake[0].begin()->y + dy[i]);
                    point opponent = point(state->snake[1].begin()->x + dx[j], state->snake[1].begin()->y + dy[j]);
                    actions.push_back(new Action(self, opponent, i, j));
                }
            }
        }
    }

    if (!actions.size())//如果对方没有能走的方向,就只考虑自己能走的方向
    {
        for (int i = 0; i < 4; i++)
        {
            if (validDirection(state, 0, i))
            {
                point self = point(state->snake[0].begin()->x + dx[i], state->snake[0].begin()->y + dy[i]);
                point opponent = point(-1, -1);
                actions.push_back(new Action(self, opponent, i, -1));
            }
        }
    }
    return actions;
}
node *getBestChild(node *root)
{
    int self_dir=getDirection(root,0);//本方ucb最高的方向
    int opponent_dir=getDirection(root,1);//对方ucb最高的方向
   
    for(auto child:root->children)
    {
        if(child->self_dir==self_dir&&child->opponent_dir==opponent_dir)return child;
    }
    return nullptr;

}

代码开源在这里

Logo

秉承“创新、开放、协作、共享”的开源价值观,致力于为大规模开源开放协同创新助力赋能,打造创新成果孵化和新时代开发者培养的开源创新生态!支持公有云使用、私有化部署以及软硬一体化私有部署。

更多推荐