【技术分享】象棋对弈程序的设计

碧俐千仞 · 发表于 2015-1-16 22:52:46

电脑与玩家下象棋，围棋，五子棋，斗地主，三国杀等等，我们称之为人机博弈。下面以象棋为例，说说人机博弈程序的基本思想。
幻灯片1.jpg

这种对弈程序主要涉及到3个方面，分别是走法产生、估值算法和搜索技术。
幻灯片4.jpg

走法产生就是遍历当前局面的所有可行走法。
幻灯片5.jpg

上面的程序描述了红卒的走法。只要遍历每一种棋子的走法，通过AddMove添加到列表之中，走法表便形成了。
幻灯片8.jpg

了解走法产生后，就要介绍下估值算法了，总之就是评估一个局面好坏的算法。这里介绍三种评估方法，其一是计算棋子的价值，其二是计算棋子的灵活性（棋子有没有被挡住），其三是计算棋子的关系（有没有威胁到对方棋子），将这几种方法结合起来，就可以得出较好的估值结果了。
幻灯片9.jpg

有了走法产生和估值，就能够产生一颗博弈树，接下来就要了解怎样找到一个最好的走法了。
幻灯片15.jpg

可以用下面的图来解释极大极小值算法，这是一个两层的博弈树，c1的估值是8，c2的估值是10。假如程序走红方，现在在B1局面，轮到黑方下棋，最坏的情况就是黑方走到c1局面，因为这时候局面对红方的估值最小。所以B1的估值是c1，c2，c3的最小值，也就是8，B2和B3同理，得出的估值分别是5和10。假如现在在局面A，轮到红方走，那自然要走一步对自己最有利的，于是选择了B3。
幻灯片17.jpg

如下图所示，当程序计算到c4的时候，得出c4是7，因为B2取的是下面节点的最小值，所以B2 <= 7，而B1 = 8，所以在A局面到B1，B2，B3局面选择时，就不可能选择B2了。这时候C5和C6就可以不用计算了，直接抛弃，有点像减掉一棵树的枝叶，称为剪枝，这是对搜索算法的一种优化。
幻灯片19.jpg

完成了，了解了这一思想，你便也了解了五子棋、围棋、斗地主、三国杀等等人机博弈程序的思路了。
幻灯片20.jpg

永樂壹條鞭 · 发表于 2015-1-16 23:04:05

这是一门学文

首席统帅大将军 · 发表于 2015-1-16 23:16:37

路过看看！

悍匪的门牙 · 发表于 2015-1-16 23:47:21

学习了，赞

我亦、飘零久 · 发表于 2015-1-17 00:35:57

作为一个java 搬砖工，觉得这个比较难啊

我亦、飘零久 · 发表于 2015-1-17 00:36:42

21分钟。。可学不会

漫不经心 · 发表于 2015-1-17 00:53:32

路过看看

漫不经心 · 发表于 2015-1-17 00:53:47

帮陈琳磨墨，漫不经心得罪曹操，花 3 枚金币减罪.

霸王项羽 · 发表于 2015-1-17 01:42:30

看看...............

知天命逆天难 · 发表于 2015-1-17 01:44:25

路过..............

小七同学 · 发表于 2015-1-17 09:05:50

的撒旦撒旦撒大撒的

焰之扉 · 发表于 2015-1-17 09:07:38

看看，支持一下

青色天空 · 发表于 2015-1-17 09:24:53

路过看看

今夜来看雪 · 发表于 2015-1-17 11:22:16

小手一抖，金币带走
- 本文出自中华MOD网，原文地址：http://www.1mod.org/thread-130043-1-1.html

三善昵 · 发表于 2015-1-17 13:45:01

路过看看

大撒旦法 · 发表于 2015-1-17 15:47:19

++++++++++++++++++++

422 · 发表于 2015-1-17 19:36:11

支持一下

		自动登录	找回密码
密码			立即加入

【技术分享】象棋对弈程序的设计

相关帖子

站长推荐 /2