基于牛角棋的博弈电路系统设计
1．2．2 招法的形式化描述
用
表示红蓝3枚棋子在第n步时的棋位，第n步时刻的棋位向量的形式化描述为状态Sn：
式中qn+1为第n+1时刻的招法。
由于红子走子方向不受限制，可上可下，可横走，只能走向空位，不得跳跃。所以红方棋子可以表述为：
蓝方的棋子走棋方向受到限制，只能上不能下，可以横走，只能走向空位，不得跳跃。故蓝方的两枚棋子可以描述为：
1．2．3 预置表招法生成
预置表可看作一个可快速检索到满足某些简单条件的、预先生成的招法列表的知识库。
对照图2棋盘的编码方式，参照牛角棋的规则，一种预置招法表的设计方案如图3所示。本文引用地址：http://www.eepw.com.cn/article/175910.htm
preTable是三维的预置表，其中的两个高维度分别代表了2个条件：
(1)棋子的颜色是什么；
(2)棋子处在什么位置上。
在明确上述两个条件的具体值之后，就可以获得全部可行着法的列表。由于预置表是频繁访问的数据，所以，预置表占用的空间不应太大，而且执行时应以能够载入内存为宜，所以针对具体棋类还须因地制宜地采用一些技巧。
1．3 搜索控制
在解决机器博弈问题中，搜索是机器博弈的核心，他控制着系统各个模块的调用，他效率的高低直接影响搜索的速度，是决定整个博弈系统棋力高低的首要因素。
首先，他调用招法生成模块，对当前局面产生所有可能的招法并将产生的招法保存到招法列表中。然后，判断当前局面是否有获胜方，如果有获胜方返回当前局面的估值；否则再判断是否是叶子节点，如果是叶子节点，调用估值模块对当前局面进行估值并将其返回；如果不是叶子节点则按照当前招法走一步棋并且调用自身将刚生成的节点展开，此过程一直持续下去直到分出胜负或者搜索到叶子节点。接着，按照走法将当前局面撤销，退到没有走棋时的局面。然后判断是否需要剪枝。以上过程反复执行，将庞大的博弈树一层一层展开以搜索最佳招法，并将其输出。
在NiosⅡ系统中，使用递归调用的方式来实现搜索算法，使用负极大值算法(Negamax algorithm)，并且采用固定深度的深度优先搜索，同时配合α-β剪枝技术来搜索最佳招法。
1．4 局面评估
对叶子结点所对应的局面打分是估值函数的职责，通过对局面的量化值来表示局面的好坏，而博弈树的其他节点的值则通过算法从叶子节点返回得到。函数的输入是待评估的函数，输出是一个数值。
博弈树的叶子结点是需要调用估值函数加以估值的结点。而博弈树的中间结点和根节点的分值，均可利用极大极小原理从叶子节点的取值倒推出来。除了残局阶段，搜索树中的大部分叶子结点，都是未分胜负的结点，需要估值函数对该局面做出评价，并以数值的形式反映优劣程度。一般地，将所有特征的取值的加权和作为估值函数值。局面p的估值函数V(p)，一般形式如下：
式中：fi表示特征；wi表示权值。
需要注意到是，对于负极大值算法中叶子节点的估值必须对那一方走棋敏感，评估模块设置使能信号，在搜索状态机发出评估使能信号后，评估模块立即对当前局面进行评估并在一定的延时后返回局面的评估值。如果评估使能信号无效，评估模块的输出保持在高阻态，不对局面进行评估。
评论