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

蒙特卡洛搜索在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
2