JAVA黑白棋之学习感悟

        前言
        这是我来到蓝杰之后的第一个学习感悟，阶段成果也是我第一个觉得小有成就的作品，不在于所用的知识有多么高深，而在与这是第一个凝结了失败、努力、成功这样颇有曲折经历的项目，使我收获颇多。
         下面切入正题，当学完做画板之后，面临的一个选择就是做五子棋或者黑白棋，虽然对于我而言，五子棋要比黑白棋在行的多，但由于考虑到机器搜索的代价，我便毫不犹豫地选择了制作黑白棋的小游戏，毕竟不是我去对弈，而是要“教”机器如何对弈。
至于我所谓的搜索代价，便是对机器而言，所面临的需要搜索的节点数。不妨拿黑白棋和五子棋做个对比。首先，黑白棋的棋盘是8*8的，而五子棋的棋盘是15*15的，就这个层面讲，无论是空间上还是时间上，对五子棋落子的搜索的代价都要比黑白棋要高；其次，黑白棋每轮下子的位置是有要求的，这便进一步减少了节点的数量，而五子棋则理论上可以下在棋盘上的任何一个空位（当然是有特殊情况的，比如你不能眼睁睁地看着别人出杀招）；再者，基于上面两点，五子棋较黑白棋来讲，电脑是更难发起有效进攻的。
        当然，黑白棋也有难以处理的地方，比如每下一步，不仅改变了自己棋子的状态，同时也会改变棋盘上对方棋子的状态，那么在深搜的过程中，便不能像五子棋那样先是尝试一个位置，然后深搜，最后再把尝试的痕迹抹掉，这样只用一个二维数组就可以了，而由于黑白棋中对翻转的棋子进行还原是很麻烦的，所以在深搜的过程中，便只能不断new一个二维数组，然后再传递翻转后的棋盘，这样便增大了额外的内存开销。
        版本经历
        老爸曾在我和他谈想进蓝杰的时候教育过我：“学习是好事，但千万不要好高骛远”，起初我听过龙哥安排我做黑白棋的计划之后，便陷入了无限的憧憬之中，幻想着自己的黑白棋会多么多么厉害（至少要打败某某的黑白棋程序，并且让某某打败不了我的程序，有点小邪恶- -!……），但却只是一味的想象，甚至连个框架都没有做出来，一上午都显得很毛躁。在龙哥的警醒下，我下午终于开始先投入精力至少把框架做出来，原来想象中的简单的事情其实也并不是那么简单，但至少当晚磕磕绊绊地把双人模式的雏形已经搞出来了，至少走棋的模块是没有问题了。
        接下来便是对界面的美化和人机算法进行研究了。界面美化其实也不算重点，有了仿WIN7画板的经历之后，对Swing组件还是有了一定的了解和应用能力的，因此界面应该不会是大问题。也正如龙哥所说，如果做黑白棋，不把人机算法好好研究一番，是没有意思的，因此，接下来的主要任务便是拿下人机算法模块。
        由于有了前面李众力的经验，我还算很快就把一个简单的BOT操作的模块写出来了，就是依赖格子的权值，尽可能地先占角和边，而尽量不去碰“C位”（两条边上的与角相邻的的格子）和“星位”(除了C位的另一个和角相邻的位置)。
        有了这个思想，很容易想到，如果我的BOT能够再往下看一步该多好，因为如果BOT走了一步棋，而Player下一步走了角或者边上的其他有利位置，那么我的BOT不就亏了么，于是在原有的基础上，又堆砌了一些代码来判断下一步Player可能走的地方。就这样，v1.0就成型了。
        但是后来经测试发现，如果只用权值去判断到底走哪里好是很吃亏的，因为我很轻松就把它下赢了，这时便试图去找一些更好地判断方法。
        也许是有点急功近利的心态吧，找到的一些比较高深的资料和论文自己根本没心思看下去（写到这里，又联想到了龙哥的一句话：“你要想赶进度，我一天让你做一个项目都可以，但关键是你要去想怎么把这个项目做精致，你要用心去观察细节，学会把软件做得精致一些。”），后来便找了一个也是大概同龄的学生写的一个用C语言做黑白棋的报告，他是用行动力（就是每轮能够下子的位置的总数）来作为对棋局评估的标准的，而且还说这样棋力还不错，我一想这个挺好的，于是便把思想拿来用了，用了大概半天的时间把这个模块写完，并和之前的程序融合到了一起，v2.0便成型了。
        然而好景不长，这样做出的程序依然很傻，到了晚上在蓝杰测试的时候，我格外沮丧。这时胡zong开始语重心长地教育我：“哦，你的意思就是说你现在这个黑白棋就相当于3岁的小孩子撒，智力还很低，但你可以每天让它涨一点撒，我们不多算，你就一个月让它长一岁，你算算，等到你大四毕业，我靠，它得多……所以你只要不放弃就行，是不？”
        听完胡zong的，我便静下心来了，晚上回去之后便开始研究起一个中科大学生（柏爱俊）写的关于黑白棋算法研究的一个论文，同时又开始研究起玄黄整理版的黑白棋对弈策略指南。事后反思的时候，研究这两个东西才是真正奠定了我的程序的黑白棋算法的基础，给了我颇多的启示。首先，单由点权去判定每个点的优劣是绝对行不通的，因为你即使让对方只剩一颗棋子，他也有可能最后将局面反败为胜，而且每个点的优劣也是依具体情况而定的；其次，做人机算法，就要充分发挥机器的优势——快速而精准的暴力，因而在时间允许的范围内，让机器多想一点总比少想一点要好；再者，印证了我之前对极大极小搜索理论的一些想法，确立了用深搜的形式去暴力各种可能情况的算法，并限定深搜的层数。
        有了上面的感悟，第二天我便把v2.0的人机算法模块抹掉，重新开始以递归的形式去描述我的算法，经过一天的努力，v3.0终于调试成功了。
        后一天的早晨我便迫不及待地让龙哥玩上一把，毕竟如果能赢龙哥还是会很高兴的，(*^__^*)。结果龙哥一开始有时候走得太快了，于是便马失前蹄，被我的程序意外地占了更多优势，但后来仔细行棋的话，还是可以比较容易地拿下我的BOT的。虽然听完龙哥说我的这个程序还是满厉害的，但我还是有些不知足，毕竟还是让龙哥比较轻松地赢了的。
        在后续完善v3.0的过程中，我发现限定深搜的层数有时并不是那么理想，因为如果每层只有很少的节点，那么实际上还是有充足的时间搜索更多步的，何乐而不为呢？于是我便把限定搜索层数改成了限定搜索节点数，这样便使程序能够更加有效地利用有限的时间了。
        同时，在和别人下的过程中，还发现了对于最终棋局的判定是不宜只着眼于位置的。因为即使你占得位置再好，最后子数少也是明显不行的。于是便改变了双方都无子可下时的对棋局的评估函数，这时便着眼于子数的优势了。
        周六的晚上，我便又开始依照那篇论文的指导思想开始研究剪枝优化的博弈树搜索，也即α-β搜索，由于有了前面MIN-MAX搜索代码的基础，在晚上比较晚的时候我便比较容易地写完了α-β搜索的代码，v4.0便研发成功了，同时这时一个可喜的战果便是，我的白棋赢了百度应用上面日文版的那个黑白棋的黑棋（因为这个版本被龙哥评为比较厉害的版本，所以会比较高兴），尽管我的黑棋赢不了它的白棋……同时我抱着侥幸的心理挑战了一下百度应用的聪明黑白棋，结果毫不犹豫地战败了……
        周日的时候，我便在QQ上面开始用我的程序进行实战了，大概能到70%的胜率吧，而且还下赢过2000多分的。欣喜之余，我发现有些时候我的BOT会很傻，尤其是最后几步，有时对手能接连让我停步好多次，然后战胜我。后来直到晚上很晚的时候，我突然意识到了我对α-β搜索中有一方pass的处理是有BUG的，到周一中午的时候，我终于把这个BUG修复了，但我发现反倒赢不了之前的日文版的黑白棋了（BUG+BUG也许会减轻BUG的影响，但当消除一个BUG时，另一个BUG的问题就暴漏地很明显了……），这时我才更加意识到了评估函数的重要性，便又仔细修改了评估函数的值，重新又赢下了日文版，而且这次黑棋也能赢下它的白棋，我便把这个版本记作了v4.5，但我依然赢不下聪明黑白棋。
        于是我便又有些沮丧，开始寄希望于网上的资料，结果把从一个外国的论文上找下的一个权值表用上之后，反倒BOT变傻了。吃晚饭回来后，我便仔细分析了一下权值表，觉得它这个权值的分布还是有道理的，同时又结合了我的一些实战的经验以及我原创并修改的权值表，对摘过来的外国的权值表上的一些值的影响进行了削弱，并将一些权值的影响进行了加强，并依现在的权值表，对最终的线性合并评估值的常数比例进行了适当的修改，之后我便拿这个程序又抱着侥幸的心理去打聪明黑白棋，这次居然完成了我一周以来梦寐以求的心愿——终于将其打败了O(∩_∩)O！之后便把这个加强之后版本命名为v4.7。
        所谓有目标才能有动力，有动力才能有成功，现在百度应用上比较厉害的黑白棋已经被我的BOT战胜了，希望我还能有更多地动力继续将论文上的历史表和置换表的知识融入到我的程序之中，让我的BOT变得更聪明，加油哈！
        后记
        此篇仅作一个阶段性的感悟的汇总和留念，具体的开发JAVA黑白棋过程中应用到的各种算法，我还在汇总之中，相信不久就能成文了。
        另附我开发的v4.7的黑白棋程序，大家疲劳之时可以娱乐一番，如果有什么建议和指导，还望大家不吝赐教O(∩_∩)O~。

        P.S.由于我没有标记谁下在了哪里，所以有可能有时电脑走完子之后并不能引起我们的视觉注意，但是从当前持子那个位置可以看出来是该谁接着下了，这个问题我会在之后的版本予以修正和改善，我对因此给各位在游戏中带来的不便表示歉意，谢谢各位对我的谅解和支持。

评论

4 楼 雨花石-runningman 2014-11-21  

为什么没有代码？好坑。

3 楼 cutejuan 2011-12-28  

其实想参考一下你的代码  可是没有。不过你做的黑白棋不错哈

2 楼 linrulong2005 2011-08-30  

算法盲表示惭愧，楼上是个胖子

1 楼 freewxy 2011-08-30  

哎，现在都写不出个黑白子来