中国象棋软件引擎审局揭秘系列1
编者注：fenon，原名应为叶剑锋，棋海无涯界面作者，曾获世界奥林匹克大赛第四名。
中国象棋软件的点滴
从2004年, 走在世界的前列, 编写象棋软件开始, 到2006年, 学习研究并改写全新的引擎, 已经是三年多的时间,。这三年, 是一个技术/思维从粗糙到成熟的过程, 获益良多。 这段时间写了很多文章, 转载在各大网站/论坛上, 可惜已经如风中的铃声, 消失在时间中, 现在摘录的一些, 作为一种回忆, 保存起来。
在编写象棋软件的期间, 得到象棋世家创始人Poor的帮助, 得到朋友raylau和face的支持, 谢谢他们。在编写象棋软件的期间, 认识了纵马奔流, 象棋奇兵, 棋天大圣, 还有现在的新起之秀象棋旋风, 天机, 象眼, 是他们让我在一次又一次的自我挑战中,不断完善自己. 回想起自己所编写的软件战胜旧一代棋软巨头的时候, 我也明白我的程序, 总有一天也会被淘汰, 消失在人们的眼中, 这是历史发展的必然, 自然会有更好更新的软件, 出现在人们眼前。感谢所有为中国象棋软件做出努力的人们, 愿棋软常青。
2006.12.4 08:20 作者：fenon
人工智能系列--nullmove
Nullmove 实战剖析
int attackpieces = (side==RED?(Rattackpieces) : (Battackpieces));
int nulldepth = CtrlNullEx ? 4 : 3;
if (CtrlNullmove
&& !NullVerify <BR> && !InChk<BR> && !mate_threat <BR> && attackpieces > 0<BR> && !avoid_donull<BR> && depth>=2<BR> && (depth-nulldepth<=0 || zEval(side, ply, 0)>=beta)
&& do_null) <BR> { // 控制nullmove的危险程度
null_score = -zSearch(-beta, -beta + 1, 1 - side, depth -
nulldepth, ply + 1, false/*do_null = false*/);
if (null_score >= beta)
{
{
bool verifyok = false;
// null-move verify
if (depth < nulldepth)
verifyok = true;
else
{
NullVerify = true;
if (zSearch(beta-1, beta, side,
depth-nulldepth+1, ply, false) >= beta)
verifyok = true;
NullVerify = false;
///*
if (verifyok) {
StoreHash();
}
//*/
}
if (verifyok)
return (null_score);
}
}
else if (null_score == -vMate + ply + nulldepth)
mate_threat = 1;
}
nullmove是一种有损剪枝, 会带来一些不准确的结果, 所以控制nullmove的危险程度是很有必要的
在何种条件下可以进行nullmove? 我的实现算法中, 采取了以下几种限制
1. 攻击子>0
2. depth>=2 最后一层直接剪掉是非常危险的
3. 不被将军
4. 上一层已经做了nullmove, 本层就不再做了
5. 当校验nullmove是否正确时,不再使用nullmove
6. 当同样的盘面,以前曾经使用过nullmove,并且发现被对方杀死时(参考crafty)
7. 层数比nulldepth要大, 或者优势很大时 (参考fruit)
8. avoid_donull发生在如果保存在hash表中有记录,但是却不能返回结果时
其中7是相当好的一种限制条件, 比通过子力的多少来进行限制有效得多
因为nullmove的危险性, 需要测试nullmove结果是否正确, 通过统计, 子力多的时候, 基本不会出现verify失败的结果,
这多少也印证了crafty中, 采用子力多少进行nullmove限制的原因
nullmove的verify是通过层数多一层的搜索来校验的方法来校验, 所以
depth小于nulldepth时,可以认为不需要校验
(考虑这个时候计算的结果跟nullmove搜索结果的比较)
nullmove搜索的结果可以保存重用(参考crafty)
这里对象眼nullmove的实现, 提几点建议
if (Search.bNullMove
&& !bNoNull <BR> && !mvsLast.bcCheck <BR> && Tree.pos.NullMoveOkay()<BR> && nDepth>1<BR> && (nDepth-NULL_DEPTH-1<=0 ||
Tree.pos.Evaluate(vlAlpha, vlBeta)>=vlBeta)
)
{
Tree.pos.MakeMove(0);
vl = -SearchFull(Tree, -vlBeta, 1 - vlBeta, nDepth
- NULL_DEPTH - 1, NO_NULL);
Tree.pos.UndoMakeMove();
if (vl >= vlBeta)
{
if (Tree.pos.NullMoveSafe() ||
nDepth<=NULL_DEPTH || SearchFull(Tree, vlBeta - 1, vlBeta, nDepth -
NULL_DEPTH, NO_NULL) >= vlBeta)
{
return FAIL_SOFT ? vl : vlBeta;
}
}
else if (vl == nThisPly + 2 - MATE_VALUE)
{
bMateThreat = TRUE;
}
}
其中的关键是(nDepth-NULL_DEPTH-1<=0 || Tree.pos.Evaluate(vlAlpha,
vlBeta)>=vlBeta), 这样可以避免很多危险的情况, 使用了nullmove启发剪枝！
作者：fenon 看不懂:),,,,,,,,,,, 这个真看不懂
页:
[1]