人智大作业-四子棋实验报告

题目大意

带重力的四子棋(连成4个(横竖斜)胜利)

大致算法

预测:朴素搜索

通过判定一个必胜态的后继状态存在对手必败态,一个必败态后继状态必须全是对手必胜态。实现搜索算法,搜索深度可以达到6层左右。

朴素搜索只能对于短期一定必胜、必败的状态进行判断,故可用于

  1. 蒙特卡罗树新增一个节点时,如果该节点胜负短期可判,则不使用随机游走,而直接将固定胜率\败率100%返回
  2. 决策时跑预测防止出现一些蒙特卡洛故意走向一个必败态的情况

估值:随机下子

估计一个局面的情况可以通过随机下子的方式,双方随机在可能的位置等概率下子,判断最后谁胜,将随机下子次数增加可以非常“不准确”的估计出当前局面对谁有优势

决策:蒙特卡洛搜索树

对于上述算法,在短期无法判断局面的时候很难决策如何下子,因此使用信心上限树算法(UCT).

     $$I_j = X_j + \sqrt{\frac{2ln(n)}{T_j(n)}}$$

通过上面的式子得出决策树上每一个位置的信心上限[latex]I_j[\latex],其中n表示总的尝试次数,

    \[$T_j$\]

表示第j个状态(及其子状态)尝试次数。

显然,每次尝试I值最大的状态可以平衡所有状态的最小尝试次数以及对较优状态的多次尝试。

程序表现

与样例程序进行对抗,分数大约在30/200分左右。

一些细节

  1. 蒙特卡洛树的决策最好选择访问次数最多的而非期望权值最大的那一个,因为蒙特卡洛每次都会拓展期望权值L最大的那一个,并有一定概率使其变小。换句话说,蒙特卡洛的决策在某种意义下就是平衡L值得过程,所以L值并不能代表一个状态的优劣
  2. 比较神奇的是有些时候迭代次数较多的程序表现没有迭代次数较少的程序,可能是因为常数没有调好……
  3. 曾经尝试在随机游走的时候加入深度较小的特判,使得双方“稍微”有一点智能,但是发现这样会导致结果基本是平局
  4. 最开始程序使用new分配内存,然而Compete程序多次调用会出现segmentation fault,单独调用无误,改为预先分配就没有问题了。不知道是否和电脑的垃圾回收机制有关系。

原创文章地址:【人智大作业-四子棋实验报告】,转载时请注明出处mhy12345.xyz

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.