VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 6698|回复: 12

【原创教程】VB AI 中国象棋之二——棋子、棋盘和走法的表示以及规则的实现

[复制链接]
 楼主| 发表于 2010-2-15 10:29:02 | 显示全部楼层 |阅读模式
本帖最后由 VBProFan 于 2010-2-15 15:09 编辑

别说是人机对弈,即使是人人对弈,利用电脑作为输入输出设备,也需要在内部建立棋子和棋盘的表示。我们知道,中国象棋里双方各有7种棋子,除了兵5个、老头1个外,其余都是2个。棋盘是10行9列的。因此很容易想到这样来表示棋子:
  1. Public Enum udtChessType
  2.   c_None
  3.   c_BlackRook
  4.   c_BlackKnight
  5.   c_BlackBishop
  6.   c_BlackHousecarl
  7.   c_BlackKing
  8.   c_BlackPawn
  9.   c_BlackCannon
  10.   c_RedPawn
  11.   c_RedCannon
  12.   c_RedRook
  13.   c_RedKnight
  14.   c_RedBishop
  15.   c_RedHousecarl
  16.   c_RedKing
  17. End Enum
复制代码
这样来表示棋盘:
  1. Private mChessBoard(1 To 9, 1 To 10) As udtChessType
复制代码
mChessBoard(2, 7) = c_BlackRook 表示在坐标(2, 7)处有一个黑车,mChessBoard(8, 3) = c_None 表示在坐标(8, 3)处没有任何棋子。
这样来表示一个走法:

  1. Private Type udtChessMove
  2.   ChessType As udtChessType '表明是什么棋子
  3.   FromI     As Byte '起始位置
  4.   FromJ     As Byte '起始位置
  5.   ToI       As Byte '走到什么位置
  6.   ToJ       As Byte '走到什么位置
  7. End Type
复制代码
判断走法是否合法的函数也很容易想出:
  1. Private Function IsValidMove(ByVal ChessType As udtChessType , _
  2.                              ByVal FromI As Integer, _
  3.                              ByVal FromJ As Integer, _
  4.                              ByVal ToI As Integer, _
  5.                              ByVal ToJ As Integer) As Boolean
复制代码
根据棋子的类型扫描棋盘二维数组 mChessBoard(1 To 9, 1 To 10)来判断走法是否合法。首先所有棋子都不能吃己方的棋子,其次看看是否车炮走直线、马走日、相走田、兵不能回头且过河才能横走、老头和士不能出九宫、别马脚、塞相眼、炮要隔一子吃子。
在判断马和相的走法时,由于目标格的横纵坐标是在原格的基础上+/- 1~2,因此当马、相在靠近边界时访问 mChessBoard 会下标越界,所以要首先判断是否x在1~9,y在1~10的范围内,如果超出,则直接判走法非法,不用再访问 mChessBoard 了。
至于怎么判断在同一直线、日、田就很简单了吧,源、目标格的横(纵)坐标相同则在同一直(横)线上,横、纵坐标分别相差2就是走田字,判断横、纵坐标分别相差1的位置有没有棋子就知道相眼是否被塞等等。



思考题:
以上都是很自然想到的表示法,但越容易想到的方法其效率往往也越低。如果是人人对弈这么一点小小的差距(最多1ms)无伤大雅,但AI程序每步棋要搜索几十万甚至几百万个节点,对于频繁调用的部分的一点小小的改进都会使最后获得可观的效应。如何重新设计棋子、棋盘和走法的表示法能提高效率呢?

评分

参与人数 1威望 +20 收起 理由
410023425 + 20 原创内容 辛苦

查看全部评分

本帖被以下淘专辑推荐:

  • · 效率|主题: 44, 订阅: 2
发表于 2010-2-16 00:05:27 | 显示全部楼层
先沙发,思考题我暂时不会……

节点数据结构设计是个重要问题,我的那个摇方块搜索算法的节点设计我估计就不太好……还有数学家玩的单人纸牌,我甚至设计了个Hash来判断是否重复,而且为了优化速度,还改成了线性Hash,只改动几个数时计算很快……
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-2-16 11:33:32 | 显示全部楼层
提示:
1. 在 CPU 的指令中,四则运算和大小比较比较慢,什么比较快?
2. 我们为了赢得时间,常常用另一种资源去和它交换,什么可以换时间?
回复 支持 反对

使用道具 举报

发表于 2010-2-16 12:13:54 | 显示全部楼层
时空互换...时空特警...异次元骇客
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-2-16 14:06:33 | 显示全部楼层
恭喜老汉答对了第二问,但具体怎么换呢?第一问的答案又是什么呢?
回复 支持 反对

使用道具 举报

发表于 2010-2-16 15:35:20 | 显示全部楼层
哦,看太快漏了第一个. 我猜是bit
回复 支持 反对

使用道具 举报

发表于 2010-2-16 15:42:30 | 显示全部楼层
1. 在 CPU 的指令中,四则运算和大小比较比较慢,什么比较快?
泡饭你这个也不太对吧,要说速度的话And,Or,Xor肯定比四则运算快一些,加减法也比乘除法快,但是现代CPU来说And,Or,Xor比加减法快就说不过去了,两者速度几乎相等……而且(整数)乘除法也慢不到哪里去,大概是一半的速度吧(我也说不上)……为什么慢那是因为VB的问题,四则运算的时候VB会自动插入错误检测代码,And,Or,Xor不会……你把所有高级优化选项全部打开可能就会快一些……
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-2-16 17:42:27 | 显示全部楼层
哦,看太快漏了第一个. 我猜是bit
download 发表于 2010-2-16 15:35


正确。
严格来说,第二问老汉答得不正确,时空互换...时空特警...异次元骇客里的“空”指的是物理学中的三维空间,而不是计算机的内存空间。。。
回复 支持 反对

使用道具 举报

发表于 2010-2-16 17:53:24 | 显示全部楼层
7# acme_pjz
一般来说add比idiv快11倍,但是编译器也会优化,例如除以固定值,
便会用imul+shr/l来代替,速度快不少,与加减几乎没区别
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-2-16 18:40:09 | 显示全部楼层

公布答案

本帖最后由 VBProFan 于 2010-2-16 18:42 编辑

除了狂用位运算和空间换时间外,还要注意使用字(节)对齐。首先看棋盘,中国象棋的棋盘是 9*10 的,如果补成 16*16 不仅能补充整数个字节方便位运算,而且在判断是否在棋盘内时,就不必使用这么慢的方法:
Private Function IsValidIJ(ByVal i As Integer, ByVal j As Integer) As Boolean
  IsValidIJ = CBool(i >= 1 And i <= 9 And j >= 1 And j <= 10)
End Function
而可以使用:
Public ccInBoard As Variant
  ccInBoard = Array( _
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, _
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, _
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, _
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, _
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, _
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
Public Function IN_BOARD(ByVal sq As Integer) As Boolean
  IN_BOARD = CBool(ccInBoard(sq) <> 0)
End Function
这种空间换时间的方法了。



而且 16*16 的棋盘还有N个好处,刚好用一个字节来表示棋子在棋盘中的位置,高4位表示第几行,低4位表示第几列,用 And 运算加上移位就可以得到其横纵坐标了;一个走法就可以用一个16位整数来表示,高8位表示走法的终点,低8位表示走法的起点:
'获得走法的起点
Public Function SRC(ByVal mv As Long) As Long
  SRC = mv And &HFF '低8位
End Function
'获得走法的终点
Public Function DST(ByVal mv As Integer) As Byte
' CopyMemory DST, ByVal (VarPtr(mv) + 1), 1 '高8位
  DST = (mv And &HFF00&) \ &H100
End Function
由于一个走法用一个数来表示,后面的走法生成器表示走法和 Hash 表的建立都非常方便,直接将这个数字作为键值就可以了,如果是之前的FromI,FromJ,ToI,ToJ方法,还得自己组合成一个数字才能使用 Hash 表。可能你会说,一个走法用一个数来表示,规则判断和走法描述会用到它的横纵坐标,此时还不是要自己分解?其实不然,规则判断我们不再比较坐标的相对关系,也使用了空间换时间的做法,而走法描述非AI的核心部分,而且占用时间非常少,只在根节点处调用。
车的规则判断:
'是否在同一行
Public Function SAME_RANK(sqSrc As Integer, sqDst As Integer) As Boolean
  SAME_RANK = ((sqSrc Xor sqDst) And &HF0) = 0
End Function
'是否在同一列
Public Function SAME_FILE(sqSrc As Integer, sqDst As Integer) As Boolean
  SAME_FILE = ((sqSrc Xor sqDst) And &HF) = 0
End Function
这种位运算就比
  If FromI <> ToI And FromJ <> ToJ Then '斜行
    IsRookValidMove = False
  End If
快多了。

上面已经列出了一个判断棋子是否在棋盘中的数组,这里再列出一个判断棋子是否在九宫的数组:
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

这都是典型的空间换时间的做法,但是值!只占用一次这么点空间,但是每生成一个节点都要调用走法生成器,而走法生成又必须调用规则判断。每走一步棋都要对规则进行上百万次的判断!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2019-8-19 22:06

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表