下棋和算法(took)因为写过一个五子棋程序，所以被joyfire缠住不放烦死了。给大家说说我的总的思路 joyfire是围棋业余高手，他很喜欢收集有关棋类游戏算法的东西。我是在知道了“深蓝”以后才逐渐投入的。所以我们的思路不同，他总是思考一些目前人工智能解决的不好的问题如何处理，例如所谓“下棋的大局观”或者“教会电脑弃子”等等；我比较愿意先写程序，看看程序到底能有多好，然后慢慢改进。所以就照我的想法写。 简单说我的五子棋程序，算法就是一般的博弈树，用了alpha-beta剪枝（不过其实不用也差不多）。局面评估是：对棋盘每个空的点看：若下在此点将形成什么（如活二、长四等），把它们的威胁值加起来，作为该点的威胁值，记为W。这可以作为考虑下一步的方法。整个棋盘局面评估=Sigma(W(先手方)-a*W(后手方))，其中Sigma是对所有空点求和，a是后手的折扣系数。 大家学过数据结构课的话，就知道上面的思路和那道著名的“三子棋”程序基本类似（比尔盖茨十三岁的时候搞定这个程序的，后来有个电影里还通过这种游戏说服已经具备智能的计算机不要发动全球核战争，因为没有胜利者）。其实大多数算法都是这样的，你可以使用比较牛一点的A*；也可以这个基础上可以加点learning，就是参数的修改了；或者用牛一点的硬件搞一个并行处理（例如深蓝就是两个小型机并行的)；或者找些下棋的高手,把它们的经验都放到一个专家系统里。总之建模而已，只要算法足够好，硬件足够快，任何一种棋类游戏都可以搞定。 当然一些新的算法，例如遗传算法和神经网络，也许比这种传统方式有优势。不过对于下棋，足够了。 像joyfire说的，目前最难的问题是围棋，因为计算量过大，如果用深蓝的方式，下一步棋就需要五千多万年。而且相对于象棋的局部计算化，围棋需要很多“全局进退的感觉”，很多时候是你整盘都在吃子，吃得很爽，最后却输了。 我们需要更多的研究和创新，例如对策学（最简单的就是田忌赛马）。
|
Index下棋和算法(Mar. 23, 2003, by took) |