基于C++进行四子棋实验【100011959】

# 四子棋实验报告 ## 实验概述 1.实现了使用UCT算法的四子棋对战AI 2.对算法的性能进行了分析并做出对应优化 3.最终版本采用：使用UCT算法+系统调用优化+随机优化 4.在QJ和本地分别对给出的50个dll分别采用先、后手进行测试，QJ胜率94%，本地胜率97%。 ## 实验原理:UCT算法 在算法的选择上,有 a-β 剪枝和蒙特卡洛两种算法。 a-β 剪枝算法需要先给定一个对四子棋局面的评估函数，但在本次实验当中，四子棋并不是所有的地方都可以落子，因此人工给出估价函数是-一个比较困难的事情。而蒙特卡洛方法采用的是多次模拟、选取胜率最大节点的方法，并不需要关于四子棋的知识。UCT算法是对蒙特卡洛方法的扩展，引入了信心上界来对局面进行评估:  算法流程： ```c++ Point* UTC::utcRoutine(float time_limit) { //为了使算法每次执产的随机数都不同 srand((unsigned)time(NULL)); clock_t start_clock = clock(); int round = 0; int cnt=0; cerr<<"before while..."<<endl; while (USED_TREE_NODE<upper_Used&&round<ONE_ROUND_COUNTS) { //判断是否还要继续循环：未超时且实现开辟的树节点尚未使完 //为了减少clock()函数引发的系统调次数，每运2048次再进次时间判断 round++; if(round>=ONE_ROUND_COUNTS){ round=0; cnt++; if(!inTimeLimit(start_clock, time_limit)){ break; } } resetBoard();//初始化 auto node = treePolicy();//选择要扩展的节点 float score = defautPolicy();//模拟并得到本次模拟的收益 backUp(node, score);//回溯更新 } int y=decideSolution(); int x=board[top[y]-1][y]==Board::empty?(top[y]-1):(top[y]-2); //返回个point类，为本次落的地点 return new Point(x,y); } ``` 代码实现 1.将算法封装在了UCT类当中，对外部提供接口 Point* utcRoutine( float time_limit = DEFAULT_TIME_LIMIT); 返回一个Point类，为本次落子的地点 2.在类内部避免了内存泄漏问题。 3.由于每走一步搜索都要调用一次UCT，因此在uct.cpp中申请局部变量用于存放uct树的节点，等到整个函数运行结束时统一释放这些空间，这样可以省去很多重复申请、释放内存的工作。 ## 实验数据分析与优化 #### uct局面评估优化  ```c int score = count == 1? WIN_ACCELERATE: 1; ``` 如果只走一步就达到必胜局，那么这局得到的分数会更高。  #### uct系统调用优化  #### uct策略进一步优化  ```c float UTC::getLamda(int line){ //第line列的value放到(1+getLamda(line))倍 return max((float)(0),((float)abs(2-(line-lastY))/2)*LAMDA); } ```  部分本地测试结果：  #### 调整C的大小 C在UCT的信心_上界估计函数当中对策略起到调节作用: C较小时倾向于保守，即选取平均值较高的节点作为较好的结果; C较大时倾向于探索，即考虑探索次数较少的节点。 在本次实验当中，C1表示在最终选择时的C, C2表示搜索过程当中的C。经过测试，如果只考虑正确率，发现C1越高正确率越低，C1=0时正确率最高。推测原因在于: C1控制的是最终节点选.择上倾向于稳健(0)还是探索(1) 。而每一步的搜索时间只有3S，并不是一个充分大的数，也就是说，信心上界算法的第二项是不能被忽略的; C1越大越有可能在最终落子的时候倾向于探索，这样就存在一定可能是C1选择了那些没有被充分探索，而且实际上效果并不好的节点。 对于C2来说，经过测试C2=0.7或0.3时 正确率都较高。C2表示:在对-一个节点的搜索过程中如何对节点进行评价。我们可以看到C2=0.3/0.7时并没有明显区别，C2=1是正确率稍低但是并不明显，但是当C2=0时正确率非常低。推测原因在于: C2控制的是搜索过程当中的节点评价策略，如果在搜索过程当中过分保守(C2=0) 则有很多节点无法搜到，就会较明显地影响对局面的判断。 #### 版本最终选择 将不同的参数进行调整，在网络上再次进行评测，结果如下(去掉调试输出)：  根据测试效果，最终提交版本当中选择了策略号为16的AI(用户名：Connect4_4，测试编号1325) ## 实验总结 1.通过本次实验更加了解UTC算法，理解ab-剪枝算法和UTC算法的不同之处 2.在算法思路等方面得到了较多帮助，感谢！ ​ 1.代码结构和思路 ​ 2.对局面评估的优化：使用局面评估参数增加必胜/必败局面的评价 ​ 3.减少系统调用次数 3.本次实验代码量较大，在oop、树结构个debug能力等方面都有较大提升，例如： ​ 1.编写单测可以在后期减少很多工作量 ​ 2.尽可能少在函数内部修改全局变量、包括类当中的成员变量也在尽量少的函数当中进行修改。尤其是本次实验当中的UCT类需要记录当前下棋者是谁、当前局面等，如果不知道自己调用的函数对其进行了修改、会容易出现问题。