摘要：计算机博弈的基本思想，可以确定一个计算机博弈程序由以下五个部分构成：1．某种在机器中表示棋局的方法，选用一种合适的方法记录棋局，能够让程序知道博弈的状态。2.产生合法走法的规则，它的作用是用来生成整棵博弈树，即处于博弈树的任何一个节点位置上，应该能够运用该机制生成这个节点的所有儿子节点，也就是接下来的所有合法走步，使博弈公正地进行，并可判断人类对手是否乱走。3．从所有合法的走法中选择最佳的走法的技术。4.一种评估局面优劣的方法，用以同上面的技术配合做出智能的选择。5.一个界面，有了它，这个程序才能用。这五个部分相互配合运转起来，就可以实现计算机博弈程序。对博弈程序运行的界面部分将不再介绍，主要介绍博弈系统的棋盘表示、走法生成。
1棋盘的表示
棋盘表示主要探讨的是使用什么数据结构来表示棋盘上的信息。通常与具体的棋类知识密切相关。一般用一个二维数组来描述棋盘及其上棋子信息。例如，可以用一个15×15大小的二维数组来表示五子棋的棋盘，如图2.1所示：
图1五子棋的表示数组
为棋类游戏的状态设计一种数据结构往往要考虑三个方面的问题:1、占用的空间数量2、操作速度3、使用方便与否。紧凑的数据表示会赢得空间上的优势，并且往往也伴随着时间上的优势。对于五子棋来说，需要记住棋盘中哪个位置有黑子，哪个位置有白子以及哪个位置是空点，从而让计算机知道棋盘局势状态。棋盘中哪个子先下，哪个后下也需要表示出来。因此使用堆栈的结构存储棋子及坐标，即先下的子放在栈的低端，后下的放在高端，保持其顺序。通过访问栈，可以得到下棋的顺序。下棋的双方每下一子，棋盘的状态都会发生变化。进栈操作就可将一方下的棋子存入堆栈中，得到新的棋盘状态，出栈操作退出一子，即可恢复到前一棋盘状态。
2着法生成
走法产生是指将一个局面的所有可能的走法罗列出来的那一个模块，也就是告诉其他部分下一步可以往哪里走的模块[3]。
不同棋类的游戏规则不同使得走法产生的复杂程度也有很大的区别。走法产生的复杂度与棋类游戏中双方棋子的种类，各种棋子走法的规则密切相关，通常种类及规则越多，走法产生的实现就越复杂。以中国象棋为例，比如兵需要注意的是不可以后退并一次只能前进一步；象只可以走田字，这就需检查与这个象相关联的象位上是否有自己的棋，并且要检查其间的象眼上是否有棋子[书]。假定象棋游戏中轮到红方走棋，要列举出红方所有合乎规则的走法。首先要扫描棋盘，如果某个位置上是一个红方棋子，则根据该棋子的类型找出该棋子的所有可走位。例如该棋子是象，先检查该棋子周围与该棋子横纵坐标差的绝对值均为2的位置是否落在己方半边棋盘上，如某个点超出己方半边棋盘，将其去除。检查剩下的位置上是否有己方棋子，如有将其去除。检查剩下的位置方向上与该棋子横纵坐标差的绝对值均为1的象眼上是否有棋子，如有将其去除。剩下的位置即是合法走步。其它的棋子也要经历各自的判断程序最后找出所有合法的走步。
在五子棋的对弈程序中，五子棋的棋盘上任意的空白点都是合法的落子点。这样在五子棋的走法模块当中只要扫描棋盘，寻找所有的空白，就可以罗列出所有符合规则的下一步落子点。
走法产生是博弈程序中一个相当复杂而且耗费运算时间的方面。不过，通过良好的数据结构，可以显著地提高生成的速度。在进行走法生成的时候，往往伴随着搜索进行。对于一个局面的所有直接后继，可以选择一次产生一种走法然后搜索之；也可以选择一次产生其所有走法然后搜索之。剪枝算法的存在，可能使得不用产生全部走法就能够完成搜索。剪枝算法的剪枝效率很大程度上依赖于节点的排列顺序，一次产生所有节点后再以某种方法调整其排列顺序往往会使搜索效率大大提高。在实际的博弈程序中，绝大部分都是一次产生一个局面的全部走法，然后调整其搜索顺序。
结论：
主要介绍了棋类博弈中棋盘及棋子表示。对于棋盘和棋子的表示，还有多种其他的表示方法，但是其本质都是一样的，即使用一维或二维数组进行表示建模；走法的生成，即罗列出所有可能的走法，然后根据走法规则选择可以落子的棋盘位置。
参考文献
[1]谷蓉.计算机围棋博弈系统的若干问题研究[D].清华大学.2003
[2]王骄，王涛等.中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J].东北大学学报.2005,10
[3]莫建文.机器自学习博弈策略研究与实现[D].广西师范大学.2002.
论文作者:张倩 钟毓笛 黄瑞麒 穆文敏
论文发表刊物:《知识-力量》2019年11月52期
论文发表时间:2019/11/27
标签：棋盘论文; 棋子论文; 位置论文; 程序论文; 棋类论文; 节点论文; 计算机论文; 《知识-力量》2019年11月52期论文;