[求助]调试程序-付费问答-看雪-安全社区|安全招聘|kanxue.com

[旧帖] [求助]调试程序 0.00雪花

发表于: 2011-4-30 18:28 914

[旧帖] [求助]调试程序 0.00雪花

woshiyu

2011-4-30 18:28

914

#include <time.h>
#include <string.h>
#include <assert.h>

#include "ucci.h"
#include "Search.h"

static const unsigned int nAdaptive_R = 3;
static const unsigned int nVerified_R = 3;
static const unsigned int BusyCounterMask = 4095;
static const unsigned int BitAttackPieces = 0xF87EF87E; //11111000011111101111100001111110 兵兵兵兵兵士士象象马马炮炮车车将卒卒卒卒卒士士相相马马炮炮车车帅

CSearch::CSearch(void)
{
// 初始化空着
StepRecords[0] = 0;

bPruning = 1 ; // 允许使用NullMove
nSelectivity = 0; // 选择性系数，通常有0,1,2,3四个级别
Debug = 0; // bDegug = 0, 输出简明扼要的搜索信息
SelectMask = 0;
nStyle = 1;
Ponder = 0;
bStopThinking = 0;
QhMode = 0;
bBatch = 0;
StyleShift = 5;
bUseOpeningBook = 0;
NaturalBouts = 120;
nBanMoveNum = 0;

// 初始化Hash表，分配21+1=22级Hash表，64MB
m_Hash.NewHashTable(22, 12);
m_Hash.ClearHashTable();

// 初始化历史表
UpdateHistoryRecord( 0 );
}

CSearch::~CSearch(void)
{
m_Hash.DeleteHashTable();
}

// 判断移动是否为禁着
int CSearch::IsBanMove(CChessMove move)
{
int m;
for(m=0; m<nBanMoveNum; m++)
{
if( move == BanMoveList[m] )
return true;
}
return 0;
}

//深度迭代搜索
int CSearch::MainSearch(int nDepth, long nProperTimer, long nLimitTimer)
{
// 初始化一些有用的变量
int w, MoveStr, score=0;
nPvLineNum = PvLine[0] = 0;

// 这些变量用于测试搜索树性能的各种参数
nNullMoveNodes = nNullMoveCuts = 0;
nHashMoves = nHashCuts = 0;
nAlphaNodes = nPvNodes = nBetaNodes = 0;
nTreeNodes = nLeafNodes = nQuiescNodes = 0;
m_Hash.nCollision = m_Hash.nHashAlpha = m_Hash.nHashExact = m_Hash.nHashBeta = 0;
nTreeHashHit = nLeafHashHit = 0;
nCheckEvasions = 0;
nZugzwang = 0;
nCapCuts = nCapMoves = 0;
for(w=0; w<MaxKiller; w++)
nKillerCuts[w] = nKillerNodes[w] = 0;
nCheckCounts = nNonCheckCounts = 0;
// 这些变量用于测试搜索树性能的各种参数

//一、分配搜索时间
StartTimer = clock();
nMinTimer = StartTimer + unsigned int(nProperTimer*0.618f);
nMaxTimer = unsigned int(nProperTimer*1.618f);
if(nMaxTimer > nLimitTimer)
nMaxTimer = nLimitTimer;
nMaxTimer += StartTimer;
bStopThinking = 0;

//二、输出当前局面
fen.BoardToFen(Board, Player, nNonCapNum, nCurrentStep, StepRecords);
fprintf(OutFile, "info BoardToFen: %s\n", fen.FenStr);
fflush(OutFile);

//三、在开局库中进行搜索
CChessMove BookMove;
if(bUseOpeningBook && m_Hash.ProbeOpeningBook(BookMove, Player))
{
nPvLineNum = 1;
PvLine[0] = BookMove;
score = BookMove >> 16;
MoveStr = Coord( BookMove );

fprintf(OutFile, "info depth 0 score %d pv %.4s\n", score, &MoveStr);
fflush(OutFile);
fprintf(OutFile, "bestmove %.4s\n", &MoveStr);
fflush(OutFile);

return score;
}

//四、若对方被将军，返回吃将帅的走法、终止搜索。
// 主搜索例程中有将军检测，不会出现这样的局面，主要针对特殊局面。
if( w = Checked(1-Player) )
{
score = WINSCORE;
MoveStr = Coord( (w << 8) | Piece[(2-Player)<<4] );
fprintf(OutFile, "info depth 0 score %d pv %.4s\n", score, &MoveStr);
fflush(OutFile);
fprintf(OutFile, "nobestmove\n");
fflush(OutFile);

return score;
}

//五、迭代加深搜索
nStartStep = nCurrentStep; // 开始搜索时的半回合数。

for(w=1; w<=nDepth; w++)
{
MaxDepth = w;
nFirstLayerMoves = 0;

// alpha-beta搜索
score = RootSearch(MaxDepth, -WINSCORE, WINSCORE);

// 无法解将或者只有一个合理的应着，立即停止搜索
if( nFirstLayerMoves <= 1 )
break;

// 若强行终止思考，停止搜索
if(bStopThinking)
break;

// 无后台思考时，若时间已经达到规定时间的一半，再搜索一层的时间可能不够，停止搜索。
if(!Ponder && clock()>nMinTimer)
break;

// 在规定的深度内，遇到杀棋，停止思考。
if(score<-MATEVALUE || score>MATEVALUE)
break;
}

//六、返回搜索结果
// 若有合法的移动，输出 bestmove %.4s 和 ponder %.4s  以及详细的搜索信息。
PopupInfo(MaxDepth, score, 1);
if( nPvLineNum )
{
MoveStr = Coord(PvLine[0]);
fprintf(OutFile, "bestmove %.4s", &MoveStr);
if(Ponder && nPvLineNum>1)
{
MoveStr = Coord(PvLine[1]);
fprintf(OutFile, " ponder %.4s", &MoveStr);
}
fprintf(OutFile, "\n");
fflush(OutFile);
}
// 出现循环，不存在合法的移动，返回score。意味着结束游戏。
else
{
fprintf(OutFile, "depth %d score %d\n", MaxDepth, score);
fflush(OutFile);
fprintf(OutFile, "nobestmove\n");
fflush(OutFile);
}
//fprintf(OutFile, "\n\n");
//fflush(OutFile);

//七、清除Hash表和历史启发表
StartTimer = clock() - StartTimer;
m_Hash.ClearHashTable( 2 );
SaveMoves("SearchInfo.txt");
UpdateHistoryRecord( 4 );
nBanMoveNum = 0;

return(score);
}

// 第一层的搜索算法
int CSearch::RootSearch(int depth, int alpha, int beta)
{
nTreeNodes ++; // 统计树枝节点

int score;
int w, way, nCaptured;

const int  ply = nCurrentStep - nStartStep;                      // 获取当前的回合数
const unsigned int nNonCaptured = nNonCapNum;
const int nChecked = (StepRecords[nCurrentStep-1] & 0xFF000000) >> 24; // 从走法队列(全局变量)中获取(我方)将军标志

CChessMove ThisMove, BestMove = 0; // 初始化为空着。若形成困闭，可以返回此空着。
CChessMove HashMove = 0; // HashMove
CKillerMove SubKillerTab;
SubKillerTab.MoveNum = 0;

int HashFlag = HashAlpha; // Hash标志
int nBestValue = ply-WINSCORE; // 搜索窗口返回的极小极大值
nFirstLayerMoves = 0;

//一、和棋裁剪：敌我双方均不存在任何能够过河攻击的棋子
if(!(BitPieces & BitAttackPieces))
return m_Evalue.Evaluation(Player);

//二、Hash探察，depth=127，故而永远不会命中(除了将军局面)，只是为了得到HashMove。
int nHashValue = m_Hash.ProbeHash(HashMove, alpha, beta, 127, ply, Player);

//三、HashMove启发算法
if(nHashValue == INT_MAX && !IsBanMove(HashMove) )
{
nHashMoves ++;
ThisMove = HashMove;

assert(Board[ThisMove & 0xFF]!=16 && Board[ThisMove & 0xFF]!=32); // 不应该出现，否则有错误，通过将军检测，提前一步过滤调这类走法
MovePiece( ThisMove );
if(Checked(1-Player)) // 我方被将军，下一步对方走，无法挽救，返回失败的分数.免除一层搜索
score = ply+1-WINSCORE; // 对方胜利，我方走了一步臭棋。如双王照面等，多是自己送上门的将军(应该统计一下，这样的移动历史得分应该很低，如何减少无效的运算)
else
{
StepRecords[nCurrentStep-1] |= Checking(Player) << 24; // 对方被将军，传送到下一层
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha); // HashMove不允许使用“空着裁减”或“历史裁减”
}
UndoMove(); // 恢复移动，恢复移动方，恢复一切
nNonCapNum = nNonCaptured; // 恢复原来的无杀子棋步数目

// Fail-Soft Alpha-Beta MainSearch（Hash和MTDf必须的方法）
// 采用全窗口搜索时，第一层永远不会产生beta截断
if( score >= beta ) // Beta剪枝
{
nHashCuts ++;

if( HistoryRecord[ThisMove] > 64000 ) // 流出余地：65535-64000=1535
UpdateHistoryRecord(1);
HistoryRecord[ThisMove] += depth*depth;

m_Hash.RecordHash(ThisMove, score, HashBeta, depth, ply, Player);
return score;
}

if(score > nBestValue)
{
nBestValue = score;
BestMove = ThisMove;

if( score > alpha ) // 缩小窗口。
{
alpha = score;
HashFlag = HashPv;

// 记录第一层的走法
m_Hash.RecordHash(BestMove, nBestValue, HashFlag, depth, ply, Player);
PopupInfo(depth, score);
}
}

// 记录第一层的所有着法
if( score < -MATEVALUE )
BanMoveList[ nBanMoveNum ++ ] = ThisMove; // 禁止着法
else
FirstLayerMoves[ nFirstLayerMoves ++ ] = ThisMove | (score<<16); // 合理着法
}

//四、产生所有合法的移动
//1.将军局面  ：产生将军逃避着法；
//2.非将军局面：吃子着法和非吃子着法，吃子着法附加历史得分，全部按历史启发处理。
CChessMove ChessMove[111];
if( nChecked )
way = CheckEvasionGen(Player, nChecked, ChessMove); // 产生逃避将军的着法
else
{
way  = CapMoveGen(Player, ChessMove); // 产生所有的吃子移动
for(w=0; w<way; w++)
ChessMove[w] += HistoryRecord[ChessMove[w] & 0xFFFF] << 16; // 吃子着法 + 历史启发
way += MoveGenerator(Player, ChessMove+way); // 产生所有非吃子移动
}

//五、Alpha-Beta搜索算法
// 1. 冒泡排序挑选最大值(Bubble Sort for Max Value)
// 2. 过滤HashMove
// 3. 主分支搜索(PVS)(Principal Variation Search)
// 4. Fail-Soft Alpha-Beta Search
int nChecking;
for(w=0; w<way; w++)
{
BubbleSortMax(ChessMove, w, way);
ThisMove = ChessMove[w] & 0xFFFF;

// 过滤HashMove和禁止着法
if( ThisMove==HashMove || IsBanMove(ThisMove) )
continue;

assert(Board[ThisMove & 0xFF]!=16 && Board[ThisMove & 0xFF]!=32); // 不应该出现，否则有错误，通过将军检测，提前一步过滤调这类走法
nCaptured = MovePiece( ThisMove ); // 注意：移动后Player已经表示对方，下面的判断不要出错。尽管这样很别扭，但在其它地方很方便，根本不用管了
if(Checked(1-Player)) // 我方被将军，下一步对方走，无法挽救，返回失败的分数.免除一层搜索
score = ply+1-WINSCORE; // 对方胜利，我方走了一步臭棋。如双王照面等，多是自己送上门的将军(应该统计一下，这样的移动历史得分应该很低，如何减少无效的运算)
else
{
nChecking = Checking(Player) << 24; // 对方被将军，传送到下一层
StepRecords[nCurrentStep-1] |= nChecking;

// 历史剪枝(History Alpha-Beta Pruning)
if( nFirstLayerMoves >= 12       //a. HistoryMoves==6 // 6为了保险
&& !nChecked //b. 我方被将军时，不允许使用History Pruning
     && !nChecking //c. 对方将军时，不允许使用History Pruning，稍慢，但更聪明，往往能提前几步发现杀棋。
&& !nCaptured //d. 非吃子移动
   )
{
score = -AlphaBetaSearch(depth-2, bPruning, SubKillerTab, -alpha-1, -alpha); // 用depth-2进行搜索，允许使用带风险的剪枝
if( score > alpha )
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha); // 用depth-1验证alpha，不允许“空着裁减”或“历史裁减”
}
// 以下禁止使用带风险的剪枝
else if( nFirstLayerMoves )
{
score = -AlphaBetaSearch(depth-1, bPruning, SubKillerTab, -alpha-1, -alpha);
if( score>alpha ) //&& score<beta)
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha);
}
else
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha);
}
UndoMove(); // 恢复移动，恢复移动方，恢复一切
nNonCapNum = nNonCaptured; // 恢复原来的无杀子棋步数目

//********************************************************************************************************
//Fail-Soft Alpha-Beta MainSearch（Hash和MTDf必须的方法）

if(score > nBestValue)
{
nBestValue = score;
BestMove = ThisMove;

if( score >= beta ) // Beta剪枝
{
nBetaNodes++;
HashFlag = HashBeta;
break;
}
if( score > alpha ) // 缩小窗口。
{
nPvNodes ++;
alpha = score;
HashFlag = HashPv;

m_Hash.RecordHash(BestMove, nBestValue, HashFlag, depth, ply, Player);
PopupInfo(depth, score);
}
else
nAlphaNodes ++;
}

// 记录第一层的所有着法
if( score < -MATEVALUE )
BanMoveList[ nBanMoveNum ++ ] = ThisMove; // 禁止着法
else
FirstLayerMoves[ nFirstLayerMoves ++ ] = ThisMove | (score<<16); // 合理着法
}

//十二、历史启发、杀手启发、记录Hash表

if(HashFlag != HashAlpha)
{
if( HistoryRecord[BestMove] > 64000 ) // 流出余地：65535-64000=1535
UpdateHistoryRecord(1);
HistoryRecord[BestMove] += depth*depth;
}

m_Hash.RecordHash( BestMove, nBestValue, HashFlag, depth, ply, Player );
return nBestValue;
}

int CSearch::AlphaBetaSearch(int depth, int bDoCut, CKillerMove &KillerTab, int alpha, int beta)
{
const int  ply = nCurrentStep - nStartStep; // 获取当前的回合数
int score, nBestValue = ply-WINSCORE; // 搜索窗口返回的极小极大值

//一、循环判断
//1.移动方：这里判断上一步以前是否构成循环，最后的移动是对方。
//2.回合数：既然判断上一步，自然ply = ply-1。不注意这个细节返回值将不会精确。
//3.技  巧：nNonCapNum=0,1,2,3时，不可能构成循环，如此大大减少了循环判断的次数。
//4.与Hash表冲突：
if( nNonCapNum>=4 )
{
score = RepetitionDetect();
if(score)
return LoopValue(Player, ply, score);
}

//二、杀棋裁剪：Mate-Distance Pruning
if(nBestValue >= beta)
return nBestValue;

//三、和棋裁剪：敌我双方均不存在任何能够过河攻击的棋子
if(!(BitPieces & BitAttackPieces))
return m_Evalue.Evaluation(Player);

//四、将军扩展 & 兑子扩展
const unsigned int nChecked = (StepRecords[nCurrentStep-1] & 0xFF000000) >> 24;    // 从走法队列(全局变量)中获取(我方)将军标志
int Extended = 0;
if( nChecked && ply<MaxDepth+16)    // 将军扩展，多搜索一层，直到没有将军为止
{
depth++;
Extended = 1;
}
// 兑子扩展，连续两步杀子，仅限于车炮马兑杀。
// 对子扩展可能会引起一些局面无法退出。
// 经8小时的检查发现，原因不在这里，是由于棋盘字符串FenBoard的数组长度不够，而陷入死循环。
else if(bDoCut && nNonCapNum==0 && ply<=MaxDepth+4)
{
score = nPieceID[ (StepRecords[nCurrentStep-1] & 0xFF0000)>>16 ];
if(score>=1 && score<=3) // 子粒价值为：车炮马
{
score = nPieceID[ (StepRecords[nCurrentStep-2] & 0xFF0000)>>16 ];
if(score>=1 && score<=3) // 子粒价值为：车炮马
{
depth++;
Extended = 1;
}
}
}

//五、Hash探察，如果Hash表命中，直接返回估值。能够极大提高剪枝效率，(不冲突时)副作用极小。
CChessMove HashMove = 0;
int nHashValue = m_Hash.ProbeHash(HashMove, alpha, beta, depth, ply, Player);
if( nHashValue!=INT_MIN && nHashValue!=INT_MAX ) //Hash命中
{
if(depth>0)
{
nTreeHashHit ++;
nTreeNodes ++;
}
else
{
nLeafHashHit ++;
nLeafNodes ++;
}
return nHashValue;
}

//六、叶节点放入Hash表，速度快16～20%。若不这样作，把这段去掉，并把开始的5行语句的注释去掉。
// 经试验，对于简单的估值函数，这样作足够了，若再使用Futility剪枝，会起反作用。由于复杂的判断，反而使速度稍微降低一些。Razor起到的作用很有限。
// 曾经尝试，叶节点不进行散列，Rador和Futility却是起到了相当大的作用。这两种剪枝都会不同程度降低解出概率。
// 今后若使用复杂的估值函数，可以考虑使用Rador和Futility剪枝。
if( depth <= 0 )
{
score = QuiescenceSearch(0, alpha, beta);

// 记录Hash值，注意叶节点并没有真正的移动，插入空着。
// 为了保守，避免搜索的不稳定性，应分别存储alpha,beta,score.
// 全部存储score, 带来更高的Hash表命中率和剪枝概率，速度快3.5%。
// 由于寂静搜索很不精确，为了安全，还应进行保守的存入。
if(score >= beta)
m_Hash.RecordHash(0,  beta, HashBeta,  0, ply, Player); // score=beta
else if(score <= alpha)
m_Hash.RecordHash(0, alpha, HashAlpha, 0, ply, Player); // score=alpha
else
m_Hash.RecordHash(0, score, HashPv, 0, ply, Player); // score=score

return score;
}

nTreeNodes ++; // 统计树枝节点

//七、引擎中断搜索：返回-32768，上次的移动保证不写入Hash表，也不会成为Pv节点。
// 停止思考，强制出着。
if( bStopThinking )
return -SHRT_MAX;
// 4095个节点查看一次，后台思考是否命中
if(!(nTreeNodes & BusyCounterMask))
{
if( Interrupt() )
return -SHRT_MAX;
}

// 初始化一些有用的变量
//const unsigned int bInEndGame = ( Count32( BitPieces & (Player ? 0x7E0000:0x7E)) < 3 ) ? 1 : 0; // 移动方车马炮数量少于3个，表示移动方进入残局
const unsigned int nNonCaptured = nNonCapNum;
CKillerMove SubKillerTab;
SubKillerTab.MoveNum = 0;

//七、空着裁减：Null-Move Pruning
// 1. Adaptive  Null-Move Pruning 开局中局适应性空着裁剪
// 2. Verified  Null-Move Pruning 残局带校验空着裁剪
if(
   bDoCut         // 上层是非PV节点，允许本层使用NullMove；若上层是PV节点，本层将禁止使用NullMove
&& depth >= 2         // depth==1,无法校验，不使用NullMove,进行正常的搜索
&& !nChecked       // 移动方没有被将军
&& BitPieces & (Player ? 0xF87E0000:0xF87E) // 移动方至少存在一颗够过河攻击的棋子，减小Zugzwang发生几率。
&& beta>-MATEVALUE && beta<MATEVALUE // 非将军的局面（Fruit的作法）  // 2b1k4/5c3/9/9/9/9/3h2P2/9/8R/5K3 r - - 0 1 去掉限制后，此局面20层25秒得到正解。个别其它局面，往往需要多搜一层。估值不是很精确，即不是最短路径的杀棋，从实战角度讲，还是去掉的好。
   )
{
// 比较好的局面才使用，速度稍稍快些，应该更安全，空着剪枝率上升20%。
// 按照NullMove理论来说，我很强壮，已经到了不用走棋的地步。不强壮的局面，往往得不到剪枝。
// 加上此限定条件后，开局与中局几乎无需校验，而不会产生Zugzwang
// 空着裁剪时，移动方失去先手权，故而用-nOffensiveValue，而不是+nOffensiveValue
if( Evalue[Player]-Evalue[1-Player]-nOffensiveValue >= beta )
{
nNullMoveNodes ++;

// MakeNullMove()
StepRecords[nCurrentStep] = 0; // 当前的移动为空着，即我方不走棋
nCurrentStep ++;
nNonCapNum = 0; // 对方连续走棋，不可能构成循环，如此可以把循环判断次数减少一半
Player = 1 - Player; // 改变对手，让对方连续走两步棋，中间隔一空着

// bPruning==0，下一层将不允许使用NullMove，除非再次遇到非PV结点时，才能打开这个开关。
// 连续两次使用NullMove是非常危险的，深蓝甚至限制一条搜索路线只使用一次NullMove。
score = -AlphaBetaSearch(depth-nAdaptive_R-1, 0, SubKillerTab, -beta, 1-beta);

// UndoNullMove()
Player = 1 - Player; // 还原对手，无需彻着
nCurrentStep --;
nNonCapNum = nNonCaptured; // 恢复原来的数据

if(score >= beta) // 仿效深蓝的做法，加上一个保险阈值：score >= beta+delta
{
// 开局与中局，不进行校验，因为有Evaluation(Player)>=beta作为保障，阻断了绝大多数Zugzwang
if( Count32( BitPieces & (Player ? 0x7E0000:0x7E)) >= 3 )    // 非残局：车马炮的数量大于等于3个
{
nNullMoveCuts++;

// 未经证实的将军，返回非杀棋的分数，可以进行剪枝，防止写入Hash表时被改写。
if( score > MATEVALUE )
score -= WINSCORE - MATEVALUE;

return score;
}
else // 残局必须进行校验
{
if(nStyle==2) // 冒进
score = AlphaBetaSearch(depth-nVerified_R, 0, KillerTab, beta-1, beta); // depth-5 进行验证
else          // 保守 || 普通
score = AlphaBetaSearch(depth<=nVerified_R ? 1:depth-nVerified_R, 0, KillerTab, beta-1, beta); // depth-5～1 进行验证

if(score >= beta)
{
nNullMoveCuts ++;
return score;
}

// 若校验不成功，发现了一个Zugswang，还原深度值，继续以后的搜索。
// 这里可以统计Zugswang出现的几率，开局与中局较少，拦截后更是凤毛麟角；残局的确不容忽视。
nZugzwang ++;
}
}

//if( !Extended && score==ply+3-WINSCORE && ply<MaxDepth+6 ) // 将军恐吓，延伸一层
//{
// depth ++;
// Extended = 1;
//}
}
}

// 初始化一些有用的变量
int d, w, way, nCaptured;
int HashFlag = HashAlpha; // Hash标志
int nSearched = 0;
CChessMove ThisMove;
CChessMove BestMove = 0;       // 初始化为空着。若形成困闭，可以返回此空着。

//八、内部深度迭代： Internal Iterative Deepening if no HashMove found
// 如果Hash表未命中，使用depth-2进行内部深度迭代，目的是为了获取HashMove
// 感觉速度快10～15%，有的局面并不显得快，但也不会慢。
// 残局能够增加Hash表的命中率，加快解体速度。即提前发现将军的局面。
if( nHashValue == INT_MIN // Hash表未命中
&& !bDoCut // 是个PV节点，非PV节点传过来的bDoCut==1
&& depth >= 3 ) // depth=2和depth=1时，没有必要，直接进行正常搜索就可以了。
{
score = AlphaBetaSearch(depth-2, 0, KillerTab, alpha, beta); // 不使用带风险的裁剪

CHashRecord *pHashIndex = m_Hash.pHashList[Player] + (m_Hash.ZobristKey & m_Hash.nHashMask); //找到当前棋盘Zobrist对应的Hash表的地址
if((pHashIndex->flag & HashExist) && pHashIndex->zobristlock==m_Hash.ZobristLock)
{
if( pHashIndex->move )
{
HashMove = pHashIndex->move;
nHashValue = INT_MAX;
}
}
}

//九、HashMove启发算法  利用hash表中同一棋局但是未命中的信息
if( nHashValue == INT_MAX )
{
nHashMoves ++;
ThisMove = HashMove;

assert(Board[ThisMove & 0xFF]!=16 && Board[ThisMove & 0xFF]!=32); // 不应该出现，否则有错误，通过将军检测，提前一步过滤调这类走法
MovePiece( ThisMove );
if(Checked(1-Player)) // 我方被将军，下一步对方走，无法挽救，返回失败的分数.免除一层搜索
score = ply+1-WINSCORE; // 对方胜利，我方走了一步臭棋。如双王照面等，多是自己送上门的将军(应该统计一下，这样的移动历史得分应该很低，如何减少无效的运算)
else
{
StepRecords[nCurrentStep-1] |= Checking(Player) << 24; // 对方被将军，传送到下一层
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha); // HashMove一般是主分支，下一层不允许带风险的剪枝
}
UndoMove();
nNonCapNum = nNonCaptured; // 恢复原来的无杀子棋步数目

//Fail-Soft Alpha-Beta MainSearch（Hash和MTDf必须的方法）
if(score > nBestValue)
{
nBestValue = score;
BestMove = ThisMove;

if( score >= beta ) // Beta剪枝
{
nHashCuts ++;
HashFlag = HashBeta;
goto CUT;
}

if( score > alpha ) // 缩小窗口。
{
alpha = score;
HashFlag = HashPv;
}
}

nSearched ++;
}

//十、杀手启发：Killer Moves
//1.国际象棋的杀手数目为2；中国象棋杀手的数目2-4个比较合适，太多速度变慢。
//2.Killer Moves采用先进先出FIFO策略。使用历史启发效果并不明显，杀手倒序有时也很快。
//3.如果被将军，不使用杀手启发，因为有将军逃避函数，杀手不一定能够解将。
//4.杀手移动中若包含HashMove，进行过滤
unsigned int ThereIsKillers = 0; // 杀手位图
if( !nChecked )
{
for( w=0; w<KillerTab.MoveNum; w++ )
{
// 过滤HashMove和不合法的杀手移动
ThisMove = KillerTab.MoveList[w];
if( ThisMove==HashMove || !IsLegalKillerMove(Player, ThisMove) )
continue;

// 统计杀手的数目
nKillerNodes[w]++;
ThereIsKillers ^= 1<<w; // 更新杀手位图

assert(Board[ThisMove & 0xFF]!=16 && Board[ThisMove & 0xFF]!=32); // 不应该出现，否则有错误，通过将军检测，提前一步过滤调这类走法
MovePiece( ThisMove );
if(Checked(1-Player)) // 我方被将军，下一步对方走，无法挽救，返回失败的分数.免除一层搜索
score = ply+1-WINSCORE; // 对方胜利，我方走了一步臭棋。如双王照面等，多是自己送上门的将军。
else
{
StepRecords[nCurrentStep-1] |= Checking(Player) << 24; // 对方被将军，传送到下一层

score = -AlphaBetaSearch(depth-1, bPruning, SubKillerTab, -beta, 1-beta);
if(score>alpha && score<beta)
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha);
}
UndoMove(); // 恢复移动，恢复移动方，恢复一切
nNonCapNum = nNonCaptured; // 恢复原来的无杀子棋步数目

//Fail-Soft Alpha-Beta MainSearch（Hash和MTDf必须的方法）

if(score > nBestValue)
{
nBestValue = score;
BestMove = ThisMove;

if( score >= beta ) // Beta剪枝
{
nKillerCuts[w] ++;
HashFlag = HashBeta;
goto CUT;
}

if( score > alpha ) // 缩小窗口。
{
alpha = score;
HashFlag = HashPv;
}
}

nSearched ++;
}
}

//十一、吃子移动：CaptureMove
CChessMove ChessMove[111];
int NextKiller = ThereIsKillers & 1 ? 0 : 1; //奇数从0开始找，偶数至少从1开始找。
if( !nChecked )
{
way = CapMoveGen(Player, ChessMove); // 产生所有的移动
for(w=0; w<way; w++)
{
BubbleSortMax(ChessMove, w, way);
ThisMove = ChessMove[w] & 0xFFFF;

// 过滤HashMove和杀手移动
if( ThisMove==HashMove )
continue;

// 如果有杀手存在，过滤杀手移动。如果所有的杀手都已经过滤，ThereIsKillers = 0;
if( ThereIsKillers )
{
for(d=NextKiller; d<KillerTab.MoveNum; d++)
{
if( ThisMove==KillerTab.MoveList[d] )
{
if(d==NextKiller)
NextKiller = d+1; // 下一个杀手的位置
ThereIsKillers ^= 1<<d; // 从ThereIsKillers标志中删除这个杀手
d = -1; // d < 0, 说明当前的移动是个杀手
break;
}
}
if( d<0 ) // 当前的移动曾经是个杀手，跳过它，无需再次进行搜索
continue;
}

// 统计吃子移动的数目
nCapMoves ++;

assert(Board[ThisMove & 0xFF]!=16 && Board[ThisMove & 0xFF]!=32); // 不应该出现，否则有错误，通过将军检测，提前一步过滤调这类走法
nCaptured = MovePiece( ThisMove ); // 注意：移动后Player已经表示对方，下面的判断不要出错。尽管这样很别扭，但在其它地方很方便，根本不用管了
if(Checked(1-Player)) // 我方被将军，下一步对方走，无法挽救，返回失败的分数.免除一层搜索
score = ply+1-WINSCORE; // 对方胜利，我方走了一步臭棋。如双王照面等，多是自己送上门的将军(应该统计一下，这样的移动历史得分应该很低，如何减少无效的运算)
else
{
StepRecords[nCurrentStep-1] |= Checking(Player) << 24; // 对方被将军，传送到下一层

if( nSearched )
{
score = -AlphaBetaSearch(depth-1, bPruning, SubKillerTab, -alpha-1, -alpha);
if(score>alpha && score<beta)
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha);
}
else
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha);

}
UndoMove(); // 恢复移动，恢复移动方，恢复一切
nNonCapNum = nNonCaptured; // 恢复原来的无杀子棋步数目

//********************************************************************************************************
//Fail-Soft Alpha-Beta MainSearch（Hash和MTDf必须的方法）
if(score > nBestValue)
{
nBestValue = score;
BestMove = ThisMove;

if( score >= beta ) // Beta剪枝。吃子移动的剪枝率不很高，故而写在里面
{
nCapCuts ++;
HashFlag = HashBeta;
goto CUT;
}

if( score > alpha ) // 缩小窗口。
{
alpha = score;
HashFlag = HashPv;
}
}

nSearched ++;
}
}

//十二、静态移动：QuiesceMove

if( nChecked )
{
way = CheckEvasionGen(Player, nChecked, ChessMove); // 产生解将的着法。由于使用了将军扩展，将军逃避将很大程度上提高搜索效率。

// 不能解将，无需搜索，直接返回估值。
if( !way )
{
nAlphaNodes ++;
score = ply+1-WINSCORE; // 下一步老将被对方吃掉。
m_Hash.RecordHash( 0, score, HashFlag, depth, ply, Player );
return score;
}
}
else
way = MoveGenerator(Player, ChessMove); // 产生所有的移动

//十一、非吃子移动的历史启发搜索算法
// 1. 冒泡排序挑选最大值(Bubble Sort for Max Value)
// 2. 过滤HashMove与KillerMove
// 3. 主分支搜索(PVS)(Principal Variation Search)
// 4. 历史剪枝(History Pruning)
// 5. Fail-Soft Alpha-Beta Search

int nChecking;
const int bHistoryPruning = (alpha+1==beta && nStyle )|| (bDoCut && nStyle==0);

for(w=0; w<way; w++)
{
if( w < 6 )
BubbleSortMax(ChessMove, w, way);
ThisMove = ChessMove[w] & 0xFFFF;

if( ThisMove==HashMove )
continue;
// 如果有杀手存在，过滤杀手移动。如果所有的杀手都已经过滤，ThereIsKillers = 0;
if( ThereIsKillers )
{
for(d=NextKiller; d<KillerTab.MoveNum; d++)
{
if( ThisMove==KillerTab.MoveList[d] )
{
if(d==NextKiller)
NextKiller = d+1; // 下一个杀手的位置
ThereIsKillers ^= 1<<d; // 从ThereIsKillers标志中删除这个杀手
d = -1; // d < 0, 说明当前的移动是个杀手
break;
}
}
if( d<0 ) // 当前的移动曾经是个杀手，跳过它，无需再次进行搜索
continue;
}

MovePiece( ThisMove ); // 注意：移动后Player已经表示对方，下面的判断不要出错。尽管这样很别扭，但在其它地方很方便，根本不用管了
if( Checked(1-Player) ) // 我方被将军，下一步对方走，无法挽救，返回失败的分数.免除一层搜索
score = ply+1-WINSCORE; // 对方胜利，我方走了一步臭棋。如双王照面等，多是自己送上门的将军(应该统计一下，这样的移动历史得分应该很低，如何减少无效的运算)
else
{
nChecking = Checking(Player) << 24; // 对方被将军，传送到下一层
StepRecords[nCurrentStep-1] |= nChecking;

// 历史剪枝(History Alpha-Beta Pruning)
if(       bHistoryPruning //a. 根据界面传送的下棋风格以及当前局面的类型决定是否使用History Pruning
   && nSearched >= 3 //b. HistoryMoves==3  国际象棋与中国象棋通用的常数
   && depth>=3       //c. HistoryDepth==3  depth-2>=1，保证与NullMove不冲突。假若上层使用NullMove，本层校验时，需试验全部着法，防止Zugswang。
   && !nChecked //d. 我方被将军时，不允许使用History Pruning
        && !nChecking //e. 对方被将军时，不允许使用History Pruning
   )
{
score = -AlphaBetaSearch(depth-2, bPruning, SubKillerTab, -alpha-1, -alpha); // 用depth-2进行搜索
if( score > alpha ) // 若alpha+1==beta，score>=beta
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha); // 用depth-1验证alpha
}
// 非标准的PVS搜索(Principal Variation Search)，标准的PVS搜索需要找到score>alpha，即bFoundPV=true
// 以下是不能进行历史裁减的分支，
else if( nSearched )
{
score = -AlphaBetaSearch(depth-1, bPruning, SubKillerTab, -alpha-1, -alpha);
if(score>alpha && score<beta)
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha);
}
else //if( !nSearched )
score = -AlphaBetaSearch(depth-1, 0, SubKillerTab, -beta, -alpha);
}
UndoMove(); // 恢复移动，恢复移动方，恢复一切
nNonCapNum = nNonCaptured; // 恢复原来的无杀子棋步数目

//********************************************************************************************************
//Fail-Soft Alpha-Beta MainSearch（Hash和MTDf必须的方法）
if(score > nBestValue)
{
nBestValue = score;
BestMove = ThisMove;

if( score >= beta ) // Beta剪枝，经验证99%以上的beta节点产生于w<6
{
if(w<4)
nBetaNodes++;
HashFlag = HashBeta;
break;
}
if( score > alpha ) // 缩小窗口。
{
nPvNodes ++;
alpha = score;
HashFlag = HashPv;
}
else
nAlphaNodes ++;
}
else
nAlphaNodes ++;
nSearched ++;
}

//十二、历史启发、杀手启发、记录Hash表
/*

//十二、历史启发、杀手启发、记录Hash表

if(HashFlag != HashAlpha)
{
if( HistoryRecord[BestMove] > 64000 ) // 流出余地：65535-64000=1535
UpdateHistoryRecord(1);
HistoryRecord[BestMove] += depth*depth;
}

m_Hash.RecordHash( BestMove, nBestValue, HashFlag, depth, ply, Player );
return nBestValue;
}
*/
CUT:

if(HashFlag != HashAlpha)
{
if( HistoryRecord[BestMove] > 64000 ) // 流出余地：65535-64000=1535
UpdateHistoryRecord(1);
HistoryRecord[BestMove] += depth*depth;

// 记录杀手移动
if(KillerTab.MoveNum < MaxKiller)
{
// 去掉重复的杀手，速度大致快10%
for(d=0; d<KillerTab.MoveNum; d++)
{
if(BestMove==KillerTab.MoveList[d])
{
d = MaxKiller;
break;
}
}
if(d<MaxKiller)
{
KillerTab.MoveList[KillerTab.MoveNum] = BestMove;
KillerTab.MoveNum ++;
}
}
}

// 置换表中存储的FailLow修正算法：
if( nBestValue<alpha && nHashValue==INT_MAX ) // FailLow情况出现(nBestValue<alpha); 置换表中有存储HashMove(nHashValue==INT_MAX)
BestMove = HashMove; // Best为原来置换表中的HashMove，而不改变原来的结果
m_Hash.RecordHash( BestMove, nBestValue, HashFlag, depth, ply, Player );

return nBestValue;
}

// 寂静搜索(能够明显提高棋力，无法避免有露算的可能)。主要技术：
// 1. 循环检测----否则会出现长将；
// 2. 空着探测----不被将军时，比较不走棋好还是杀子更好；
// 3. 吃子移动产生器----CapMoveGen()；
// 4. 解将移动产生器----CheckEvasionGen()；
// 5. 冒泡排序寻找最大值
// 6. 位棋盘快速将军检测；
// 7. Fail Soft Alpha-Beta搜索。
int CSearch::QuiescenceSearch(int depth, int alpha, int beta)
{
int score;
const int ply = nCurrentStep - nStartStep;
const int nChecked = (StepRecords[nCurrentStep-1] & 0xFF000000) >> 24;
int nBestValue = ply-WINSCORE; //搜索窗口返回的极小极大值

if( depth < 0 )
{
// 统计寂静搜索的次数
nQuiescNodes++;

//一、循环判断
//1.移动方：这里判断上一步以前是否构成循环，根据负值极大原理，必须返回负值。
//2.回合数：既然判断上一步，自然ply = ply-1。不注意这个细节返回值将不会精确。
//2.技巧 1：若前面的条件失败，程序不进行后面的判断，nNonCapNum=0,1,2,3时，不可能构成循环，如此大大减少了循环判断的次数。
//3.技巧 2：depth==0，已经在上层搜索时进行了判断，无需重复。
if( nNonCapNum>=4 )
{
score = RepetitionDetect();
if(score)
return LoopValue(Player, ply, score);
}

// 杀棋裁剪
if(nBestValue>=beta)
return nBestValue;

// 和棋裁剪：敌我双方不存在任何能够过河攻击的棋子
if(!(BitPieces & BitAttackPieces))
return m_Evalue.Evaluation(Player);

/*
//三、Hash探察 (寂静搜索的命中率极低)
CChessMove HashMove;
score = m_Hash.ProbeHash(HashMove, alpha, beta, depth, ply, Player);
if(score!=INT_MIN && score!=INT_MAX) //Hash命中
{
nLeafHashHit ++;
return score;
}
*/
}
else
nLeafNodes ++;

//二、若非将军的局面，首先进行Null-Move测试。
// 目的是为了比较吃子好还是不吃子好，如果不吃子的分数已经能够剪枝，吃子后也必然剪枝。
if(!nChecked)
{
score = m_Evalue.Evaluation(Player, alpha, beta);
if(score >= beta)
return score;
if(score>nBestValue)
{
nBestValue = score;
if(score > alpha)
alpha = score;
}
}

int w, way;
const unsigned int nNonCaptured = nNonCapNum;

//fen.BoardToFen(Board, Player, nNonCapNum, nCurrentStep, StepRecords, fen.FenStr);

//三、产生吃子的移动以及解将的移动
CChessMove ChessMove[32]; // 使用了解将移动产生器后，数组可以设得小些，32就足够了。Max=19

// 试验过一些棋局，残局不进行将军扩展时，电脑经常走出昏着而丢子。
if( nChecked )
{
way = CheckEvasionGen(Player, nChecked, ChessMove); // 我方被将军，展开所有的走法，应该先产生解将的步法
if(!way)
return ply+1-MATEVALUE; // 因为寂静搜索并不精确，若无解，返回非杀棋分数，防止改写Hash表，但可以进行剪枝。
}
else
way = CapMoveGen(Player, ChessMove); // 产生所有的吃子着法

CChessMove ThisMove;

//四、Soft Alpha-Beta搜索
for(w=0; w<way; w++)
{
BubbleSortMax(ChessMove, w, way);
ThisMove = ChessMove[w] & 0xFFFF;

assert(Board[ThisMove & 0xFF]!=16 && Board[ThisMove & 0xFF]!=32); // 不应该出现，否则有错误，通过将军检测，提前一步过滤调这类走法
MovePiece( ThisMove );

// 胜负检验: verify game
if(Checked(1-Player)) // 我方被将军，下一步对方走，无法挽救，返回失败的分数.免除一层搜索
score = ply+1-MATEVALUE;       // 对方胜利，由于寂静搜索中的杀棋并非精确，故而使用MATEVALUE，不使用WINSCORE。
else       // 这种策略意味着不把此局面当作杀棋，以免返回时对Hash表造成影响，但又不会影响剪枝。
{
StepRecords[nCurrentStep-1] |= Checking(Player) << 24;
score = -QuiescenceSearch(depth-1, -beta, -alpha);
}

UndoMove(); // 恢复移动，恢复移动方，恢复一切
nNonCapNum = nNonCaptured; // 恢复原来的无杀子棋步数目

if(score >= beta)
return score;
if(score>nBestValue)
{
nBestValue = score;
if(score > alpha)
alpha = score;
}
}

return nBestValue;
}

void CSearch::BubbleSortMax(CChessMove *ChessMove, int w, int way)
{
int i;
unsigned int temp;

for(i=way-1; i>w; i--)
{
if(ChessMove[i-1] < ChessMove[i])
{
temp = ChessMove[i-1];
ChessMove[i-1] = ChessMove[i];
ChessMove[i] = temp;
}
}
}

int CSearch::MovePiece(const CChessMove move)
{
int nSrc = (move & 0xFF00) >> 8;
int nDst = move & 0xFF;
int nMovedChs = Board[nSrc];
int nCaptured = Board[nDst];
int nMovedPiece = nPieceType[nMovedChs];

assert( nMovedChs>=16 && nMovedChs<48 );
assert( nCaptured>=0 && nCaptured<48 );

//更新棋盘
Board[nSrc] = 0;
Board[nDst] = nMovedChs;

m_Hash.ZobristKey  ^= m_Hash.ZobristKeyTable[nMovedPiece][nSrc] ^ m_Hash.ZobristKeyTable[nMovedPiece][nDst];
m_Hash.ZobristLock ^= m_Hash.ZobristLockTable[nMovedPiece][nSrc] ^ m_Hash.ZobristLockTable[nMovedPiece][nDst];

//更新棋子坐标
Piece[nMovedChs] = nDst;
Evalue[Player] += PositionValue[nMovedPiece][nDst] - PositionValue[nMovedPiece][nSrc]; // 更新估值

if( nCaptured )
{
nNonCapNum = 0;
Piece[nCaptured] = 0;
BitPieces ^= 1<<(nCaptured-16);

int nKilledPiece = nPieceType[nCaptured];

m_Hash.ZobristKey  ^= m_Hash.ZobristKeyTable[nKilledPiece][nDst];
m_Hash.ZobristLock ^= m_Hash.ZobristLockTable[nKilledPiece][nDst];

Evalue[1-Player] -= PositionValue[nKilledPiece][nDst] + BasicValues[nKilledPiece];
}
else
nNonCapNum ++; // 双方无杀子的半回合数

// 擦除起点nSrc的位行与位列，置“0”
xBitBoard[ nSrc >> 4 ]  ^= xBitMask[nSrc];
yBitBoard[ nSrc & 0xF ] ^= yBitMask[nSrc];

// 更新终点nDst的位行与位列，置“1”
xBitBoard[ nDst >> 4 ]  |= xBitMask[nDst];
yBitBoard[ nDst & 0xF ] |= yBitMask[nDst];

//记录当前局面的ZobristKey，用于循环探测、将军检测
StepRecords[nCurrentStep] = move  | (nCaptured<<16);
nZobristBoard[nCurrentStep] = m_Hash.ZobristKey; // 当前局面的索引
nCurrentStep++;

Player = 1 - Player; // 改变移动方
//m_Hash.ZobristKey ^= m_Hash.ZobristKeyPlayer;
//m_Hash.ZobristLock ^= m_Hash.ZobristLockPlayer;

return(nCaptured);
}

void CSearch::UndoMove(void)
{
CChessMove move = StepRecords[nCurrentStep-1];
int nSrc = (move & 0xFF00) >> 8;;
int nDst = move & 0xFF;
int nMovedChs = Board[nDst];
int nMovedPiece = nPieceType[nMovedChs];
int nCaptured = (move & 0xFF0000) >> 16;

// 首先恢复移动方
Player = 1 - Player;
//m_Hash.ZobristKey ^= m_Hash.ZobristKeyPlayer;
//m_Hash.ZobristLock ^= m_Hash.ZobristLockPlayer;

m_Hash.ZobristKey  ^= m_Hash.ZobristKeyTable[nMovedPiece][nSrc] ^ m_Hash.ZobristKeyTable[nMovedPiece][nDst];
m_Hash.ZobristLock ^= m_Hash.ZobristLockTable[nMovedPiece][nSrc] ^ m_Hash.ZobristLockTable[nMovedPiece][nDst];

//更新棋盘与棋子
Board[nSrc] = nMovedChs;
Board[nDst] = nCaptured;
Piece[nMovedChs] = nSrc;
Evalue[Player] -= PositionValue[nMovedPiece][nDst] - PositionValue[nMovedPiece][nSrc]; // 更新估值

// 恢复位行与位列的起始位置nSrc，使用“|”操作符置“1”
xBitBoard[ nSrc >> 4 ]  |= xBitMask[nSrc];
yBitBoard[ nSrc & 0xF ] |= yBitMask[nSrc];

if( nCaptured ) //吃子移动
{
int nKilledPiece = nPieceType[nCaptured];

Piece[nCaptured] = nDst; //恢复被杀棋子的位置。
BitPieces ^= 1<<(nCaptured-16);

m_Hash.ZobristKey  ^= m_Hash.ZobristKeyTable[nKilledPiece][nDst];
m_Hash.ZobristLock ^= m_Hash.ZobristLockTable[nKilledPiece][nDst];

Evalue[1-Player] += PositionValue[nKilledPiece][nDst] + BasicValues[nKilledPiece];
}
else //若是非吃子移动，必须把俘获位置置"0"
{
// 清除位行与位列的起始位置nDst，使用“^”操作符置“0”
// 反之，若是吃子移动，终点位置本来就是"1"，所以不用恢复。
xBitBoard[ nDst >> 4 ]  ^= xBitMask[nDst];
yBitBoard[ nDst & 0xF ] ^= yBitMask[nDst];
}

//清除走法队列
nCurrentStep --;
nNonCapNum --;
}

// 根据棋子位置信息，初始化所有棋盘与棋子的数据
// 也可使用棋盘信息，需循环256次，速度稍慢。
void CSearch::InitBitBoard(const int Player, const int nCurrentStep)
{
int m,n,x,y;
int chess;

// 初始化，清零
BitPieces = 0;
Evalue[0] = Evalue[1] = 0;
m_Hash.ZobristKey  = 0;
m_Hash.ZobristLock = 0;
for(x=0; x<16; x++)
xBitBoard[x] = 0;
for(y=0; y<16; y++)
yBitBoard[y] = 0;

// 根据32颗棋子位置更新
for(n=16; n<48; n++)
{
m = Piece[n]; // 棋子位置
if( m ) // 在棋盘上
{
chess             = nPieceType[n]; // 棋子类型：0～14
BitPieces       |= 1<<(n-16); // 32颗棋子位图
xBitBoard[m >> 4 ] |= xBitMask[m]; // 位行
yBitBoard[m & 0xF] |= yBitMask[m]; // 位列
m_Hash.ZobristKey  ^= m_Hash.ZobristKeyTable[chess][m]; // Hash键
m_Hash.ZobristLock ^= m_Hash.ZobristLockTable[chess][m]; // Hash锁

if(n!=16 && n!=32)
Evalue[ (n-16)>>4 ] += PositionValue[chess][m] + BasicValues[chess];
}
}

//m_Hash.InitZobristPiecesOnBoard( Piece );

// 用于循环检测
nZobristBoard[nCurrentStep-1] =  m_Hash.ZobristKey;

// 当前移动方是否被将军，写入走法队列
// StepRecords[nCurrentStep-1] |= Checking(Player) << 24;
}

//还应参照棋规作更详细的判断，为了通用，最好不使用CString类
char *CSearch::GetStepName(CChessMove ChessMove, int *Board) const
{
//棋子编号
static char StepName[12]; // 必须用静态变量，否则不能返回

static const char ChessName[14][4] = {"帥","車","炮","马","象","士","卒", "將","車","炮","馬","相","仕","兵"};

static const char PostionName[2][16][4] = { {"", "", "", "１","２","３","４","５","６","７","８","９", "", "", "", ""},
                                             {"", "", "", "九","八","七","六","五","四","三","二","一", "", "", "", ""} };

const int nSrc = (ChessMove & 0xFF00) >> 8;
const int nDst = ChessMove & 0xFF;

if( !ChessMove )
return("HashMove");

const int nMovedChs = Board[nSrc];
const int x0 = nSrc & 0xF;
const int y0 = nSrc >> 4;
const int x1 = nDst & 0xF;
const int y1 = nDst >> 4;

const int Player = (nMovedChs-16) >> 4;

strcpy( StepName, ChessName[nPieceType[nMovedChs]] );
strcat( StepName, PostionName[Player][x0] );

//检查此列x0是否存在另一颗成对的棋子.
int y,chess;
if( nPieceID[nMovedChs]!=0 && nPieceID[nMovedChs]!=4 && nPieceID[nMovedChs]!=5 ) // 将、士、象不用区分
{
for(y=3; y<13; y++)
{
chess = Board[ (y<<4) | x0 ];

if( !chess || y==y0) // 无子或者同一颗棋子，继续搜索
continue;

if( nPieceType[nMovedChs] == nPieceType[chess] ) // 遇到另一个相同的棋子
{
if( !Player ) // 黑子
{
if(y > y0)
strcpy( StepName, "前" );
else
strcpy( StepName, "后" );
}
else // 红子
{
if(y < y0)
strcpy( StepName, "前" );
else
strcpy( StepName, "后" );
}

strcat( StepName, ChessName[nPieceType[nMovedChs]] );
break;
}
}
}

int piece = nPieceID[nMovedChs];

//进, 退, 平
if(y0==y1)
{
strcat( StepName, "平" );
strcat( StepName, PostionName[Player][x1]); // 平，任何棋子都以绝对位置表示
}
else if((!Player && y1>y0) || (Player && y1<y0))
{
strcat( StepName, "进" );

if(piece==3 || piece==4 || piece==5) // 马、象、士用绝对位置表示
strcat( StepName, PostionName[Player][x1] );
else if(Player) // 将、车、炮、兵用相对位置表示
strcat( StepName, PostionName[1][y1-y0+12] ); // 红方
else
strcat( StepName, PostionName[0][y1-y0+2] ); // 黑方
}
else
{
strcat( StepName, "退" );

if(piece==3 || piece==4 || piece==5) // 马、象、士用绝对位置表示
strcat( StepName, PostionName[Player][x1] );
else if(Player) // 将、车、炮、兵用相对位置表示
strcat( StepName, PostionName[1][y0-y1+12] ); // 红方
else
strcat( StepName, PostionName[0][y0-y1+2] ); // 黑方
}

return(StepName);
}

// 获得主分支
// 由于使用了Hash表，有时主分支是错误的，有待修正！？？？
void CSearch::GetPvLine(void)
{
CHashRecord *pHashIndex = m_Hash.pHashList[Player] + (m_Hash.ZobristKey & m_Hash.nHashMask); //找到当前棋盘Zobrist对应的Hash表的地址

if((pHashIndex->flag & HashExist) && pHashIndex->zobristlock==m_Hash.ZobristLock)
{
if( pHashIndex->move )
{
PvLine[nPvLineNum] = pHashIndex->move;

MovePiece( PvLine[nPvLineNum] );

nPvLineNum++;

if( nNonCapNum<4 || !RepetitionDetect() )
GetPvLine();

UndoMove();
}
}
}

void CSearch::PopupInfo(int depth, int score, int Debug)
{
unsigned int n;
int MoveStr;
if(depth)
{
fprintf(OutFile, "info depth %d score %d pv", depth, score);

n = nNonCapNum;
nPvLineNum = 0;
GetPvLine();
nNonCapNum = n;

for(n=0; n<nPvLineNum; n++)
{
MoveStr = Coord(PvLine[n]);
fprintf(OutFile, " %.4s", &MoveStr);
}

fprintf(OutFile, "\n");
fflush(OutFile);
}

if(Debug)
{
n = nTreeNodes + nLeafNodes + nQuiescNodes;
fprintf(OutFile, "info Nodes %d = %d(T) + %d(L) + %d(Q)\n", n, nTreeNodes, nLeafNodes, nQuiescNodes);
fflush(OutFile);

float SearchTime = (clock() - StartTimer)/(float)CLOCKS_PER_SEC;
fprintf(OutFile, "info TimeSpan = %.3f s\n", SearchTime);
fflush(OutFile);

fprintf(OutFile, "info NPS = %d\n", int(n/SearchTime));
fflush(OutFile);
}
}

void CSearch::SaveMoves(char *szFileName)
{
unsigned int m, n;
int k, nSrc, nDst, nCaptured;

// 创建文件，并删除原来的内容。利用这种格式化输出比较方便。
FILE *out = fopen(szFileName, "w+");

fprintf(out, "***************************搜索信息***************************\n\n");

fprintf(out, "搜索深度：%d\n", MaxDepth);
n = nTreeNodes + nLeafNodes + nQuiescNodes;
fprintf(out, "TreeNodes : %u\n", n);
fprintf(out, "TreeStruct: BranchNodes = %10u\n", nTreeNodes);
fprintf(out, "          LeafNodes = %10u\n", nLeafNodes);
fprintf(out, "          QuiescNodes = %10u\n\n", nQuiescNodes);

float TimeSpan = StartTimer/1000.0f;
fprintf(out, "搜索时间 : %8.3f 秒\n", TimeSpan);
fprintf(out, "枝叶搜索速度: %8.0f NPS\n", (nTreeNodes+nLeafNodes)/TimeSpan);
fprintf(out, "整体搜索速度: %8.0f NPS\n\n", n/TimeSpan);

fprintf(out, "Hash表大小: %d Bytes  =  %d M\n", m_Hash.nHashSize*2*sizeof(CHashRecord), m_Hash.nHashSize*2*sizeof(CHashRecord)/1024/1024);
fprintf(out, "Hash覆盖率: %d / %d = %.2f%%\n\n", m_Hash.nHashCovers, m_Hash.nHashSize*2, m_Hash.nHashCovers/float(m_Hash.nHashSize*2.0f)*100.0f);

unsigned int nHashHits = m_Hash.nHashAlpha+m_Hash.nHashExact+m_Hash.nHashBeta;
fprintf(out, "Hash命中: %d = %d(alpha:%.2f%%) + %d(exact:%.2f%%) +%d(beta:%.2f%%)\n", nHashHits, m_Hash.nHashAlpha, m_Hash.nHashAlpha/(float)nHashHits*100.0f, m_Hash.nHashExact, m_Hash.nHashExact/(float)nHashHits*100.0f, m_Hash.nHashBeta, m_Hash.nHashBeta/(float)nHashHits*100.0f);
fprintf(out, "命中概率: %.2f%%\n", nHashHits/float(nTreeNodes+nLeafNodes)*100.0f);
fprintf(out, "树枝命中: %d / %d = %.2f%%\n", nTreeHashHit, nTreeNodes, nTreeHashHit/(float)nTreeNodes*100.0f);
fprintf(out, "叶子命中: %d / %d = %.2f%%\n\n", nLeafHashHit, nLeafNodes, nLeafHashHit/(float)nLeafNodes*100.0f);

fprintf(out, "NullMoveCuts = %u\n", nNullMoveCuts);
fprintf(out, "NullMoveNodes  = %u\n", nNullMoveNodes);
fprintf(out, "NullMove剪枝率 = %.2f%%\n\n", nNullMoveCuts/(float)nNullMoveNodes*100.0f);

fprintf(out, "Hash冲突 : %d\n", m_Hash.nCollision);
fprintf(out, "Null&Kill  : %d\n", m_Hash.nCollision-nHashMoves);
fprintf(out, "HashMoves  : %d\n", nHashMoves);
fprintf(out, "HashCuts : %d\n", nHashCuts);
fprintf(out, "Hash剪枝率 : %.2f%%\n\n", nHashCuts/(float)nHashMoves*100.0f);

fprintf(out, "杀手移动 : \n");
k = n = 0;
for(m=0; m<MaxKiller; m++)
{
fprintf(out, " Killer %d : %8d /%8d = %.2f%%\n", m+1, nKillerCuts[m], nKillerNodes[m], nKillerCuts[m]/float(nKillerNodes[m]+0.001f)*100.0f);
n += nKillerCuts[m];
k += nKillerNodes[m];
}
fprintf(out, " 杀手剪枝率 : %8d /%8d = %.2f%%\n\n", n, k, n/float(k+0.001f)*100.0f);

fprintf(out, "吃子移动剪枝率 = %d / %d = %.2f%%\n\n", nCapCuts, nCapMoves, nCapCuts/(float)nCapMoves*100.0f);

m = nBetaNodes + nPvNodes + nAlphaNodes;
fprintf(out, "非吃子移动: %d\n", m);
fprintf(out, " BetaNodes: %10d  %4.2f%%\n", nBetaNodes, nBetaNodes/float(m)*100.0f);
fprintf(out, " PvNodes  : %10d  %4.2f%%\n", nPvNodes, nPvNodes/float(m)*100.0f);
fprintf(out, " AlphaNode: %10d  %4.2f%%\n\n", nAlphaNodes, nAlphaNodes/float(m)*100.0f);

m += nNullMoveCuts + nHashMoves + nKillerNodes[0] + nKillerNodes[1] + nCapMoves;
fprintf(out, "TotalTreeNodes: %d\n\n\n", m);

n = nCheckCounts-nNonCheckCounts;
fprintf(out, "将军次数: %d\n", n);
fprintf(out, "探测次数: %d\n", nCheckCounts);
fprintf(out, "成功概率: %.2f%%\n\n", n/(float)nCheckCounts*100.0f);

fprintf(out, "CheckEvasions = %d\n", nCheckEvasions);
fprintf(out, "解将 / 将军 = %d / %d = %.2f%%\n\n", nCheckEvasions, n, nCheckEvasions/float(n)*100.0f);

// 显示主分支
int BoardStep[256];
for(n=0; n<256; n++)
BoardStep[n] = Board[n];

static const char ChessName[14][4] = {"帥","車","炮","马","象","士","卒", "將","車","炮","馬","相","仕","兵"};

fprintf(out, "\n主分支：PVLine***HashDepth**************************************\n");
for(m=0; m<nPvLineNum; m++)
{
nSrc = (PvLine[m] & 0xFF00) >> 8;
nDst = PvLine[m] & 0xFF;
nCaptured = BoardStep[nDst];

// 回合数与棋步名称
fprintf(out, " %2d. %s", m+1, GetStepName( PvLine[m], BoardStep ));

// 吃子着法
if( nCaptured )
fprintf(out, " k-%s", ChessName[nPieceType[nCaptured]]);
else
fprintf(out, "    ");

// 搜索深度
fprintf(out, "  depth = %2d", PvLine[m]>>16);

// 将军标志
nCaptured = (PvLine[m] & 0xFF0000) >> 16;
if(nCaptured)
fprintf(out, " Check Extended 1 ply ");
fprintf(out, "\n");

BoardStep[nDst] = BoardStep[nSrc];
BoardStep[nSrc] = 0;
}

fprintf(out, "\n\n***********************第%2d 回合********************************\n\n", (nCurrentStep+1)/2);
fprintf(out, "***********************引擎生成：%d 个理合着法**********************\n\n", nFirstLayerMoves);
for(m=0; m<(unsigned int)nFirstLayerMoves; m++)
{
nSrc = (FirstLayerMoves[m] & 0xFF00) >> 8;
nDst = FirstLayerMoves[m] & 0xFF;

// 寻找主分支
if(PvLine[0] == FirstLayerMoves[m])
{
fprintf(out, "*PVLINE=%d***********Nodes******History**************************\n", m+1);
fprintf(out, "*%2d.  ", m+1);
}
else
fprintf(out, "%3d.  ", m+1);

//n = m==0 ? FirstLayerMoves[m].key : FirstLayerMoves[m].key-FirstLayerMoves[m-1].key; // 统计分支数目
n = FirstLayerMoves[m] >> 16; // 统计估值
fprintf(out, "%s = %6d hs = %6d\n", GetStepName(FirstLayerMoves[m], Board), n, HistoryRecord[FirstLayerMoves[m]&0xFFFF]);
}

fprintf(out, "\n\n********************引擎过滤：%d个禁止着法********************************\n\n", nBanMoveNum);
for(m=0; m<(unsigned int)nBanMoveNum; m++)
{
fprintf(out, "%3d. %s\n", m+1, GetStepName( BanMoveList[m], Board ));
}

fprintf(out, "\n\n***********************历史记录********************************\n\n", (nCurrentStep+1)/2);

int MoveStr;
for(m=0; m<=(int)nCurrentStep; m++)
{
MoveStr = Coord(StepRecords[m]);
fprintf(out, "%3d. %s  %2d  %2d  %12u\n", m, &MoveStr, (StepRecords[m] & 0xFF0000)>>16, (StepRecords[m] & 0xFF000000)>>24, nZobristBoard[m]);
}

// 关闭文件
fclose(out);
}

/*
int CSearch::Evaluation(int player)
{
return Evalue[player] - Evalue[1-player] + nOffensiveValue;
}
*/

// 循环检测：通过比较历史记录中的zobrist键值来判断。
// 改进方案：使用微型Hash表，LoopHash[zobrist & LoopMask] = zobrist  LoopMask=1023=0B1111111111  可以省去检测过程中的循环判断。
// 表现为双方的两个或多个棋子，在两个或者两个以上的位置循环往复运动。
// 根据中国象棋的棋规，先手将军出现循环，不变作负。下面列举测试程序时发现的将军循环类型：
// 5.       10101  01010  00100
// 6.       001010
// 7.    1001001
// 8.    00001010
// 9.    100000001  101000001  010001000 000001000
//12. 1000000000001  0000001000000
// 如此看来，各种各样的循环都可能出现。循环的第一步可以是吃子移动，以后的是非吃子移动。
// 最少5步棋可以构成循环，非吃子移动的最少数目是4。5循环是最常见的类型，6～120的循环类型，象棋棋规并没有定义。
// 循环检测，实际上起到剪枝的作用，可以减小搜索数的分支。如果不进行处理，带延伸的程序有时会无法退出。
int CSearch::RepetitionDetect(void)
{
// 100步(50回合)无杀子，视为达到自然限着，判定为和棋
//if(nNonCapNum >= 120)
// return(-120);

unsigned int m, n;
unsigned int *pBoard = &nZobristBoard[nCurrentStep-1];

for(m=4; m<=nNonCapNum; m++)
{
if( *pBoard == *(pBoard-m) ) // 构成循环
{
// 统计循环中出现的将军次数。
CChessMove *pMove = &StepRecords[nCurrentStep-1];
int nOwnChecks = 0;
int nOppChecks = 0;
for(n=0; n<=m; n++)
{
if((*(pMove-n)) & 0xFF000000)
{
if( 1 & n )
nOppChecks ++;
else
nOwnChecks ++;
}
}

// 查看循环的种类
// 我长将对手, 不一定是移动的棋子将军, 移动后其他的棋子将军也属于此类。
if( nOwnChecks>=2 && !nOppChecks ) // 如 10101
return 1;

// 对手长将将我方，主动权在我方，因为最后一步我方移动。
// 最后移动的位置，有时是被迫的，有时可以自己主动构成循环，造成对手犯规。
else if( nOppChecks>=2 && !nOwnChecks ) // 如 01010
return 2;

// 其他情况，如长捉等，不形成将军，视为和棋。
// 中国象棋的棋规相当复杂，例如阻挡对方某颗棋子的下一步将军，虽然循环体内不构成将军，但若不阻挡则必死无疑。
// 根据棋规，此情况视为对方不变为负。实现此算法相当复杂。
else
return -int(m);
}
}

return(0);
}

// 循环的返回值
// 输棋： - WINSCORE * 2 不记录于Hash表
// 赢棋： + WINSCORE * 2 不记录于Hash表
// 和棋：估值 * 藐视因子
int CSearch::LoopValue(int Player, int ply, int nLoopStyle)
{
// 我方循环，是由于长将对方，故而对方胜利。不记录在Hash表。
if( nLoopStyle == 2 )
return (ply-1)-WINSCORE*2;

// 对方长将，我方胜利，返回胜利的分数。不记录在Hash表。
else if( nLoopStyle == 1 )
return WINSCORE*2-(ply-1);

// 和棋：返回估值×藐视因子，不再继续搜索。
else // nLoopStyle < 0
return int(m_Evalue.Evaluation(Player)*0.9f);

// 藐视因子：0.9f 优势时冒进，追求赢棋；略势时保守，极力求和；势均力敌时，均衡，以免犯错。
// 国象的作法是使用一个藐视因数delta，优势为负，弱势为正。
// 根据国际象棋的经验，开局为0.50个兵，中局为0.25个兵，残局接近于0。
}

// 中断引擎思考
int CSearch::Interrupt(void)
{
if(!Ponder && clock() > nMaxTimer)
bStopThinking = 1;
else if(!bBatch)
{
switch(BusyLine(Debug))
{
case e_CommIsReady:
fprintf(OutFile, "readyok\n");
fflush(OutFile);
break;

case e_CommPonderHit:
if(Ponder != 2)
Ponder = 0;
break;

case e_CommStop:
bStopThinking = 1;
break;
}
}

return bStopThinking;
}

用vc++6.0调试出现以下错误：
search.cpp(968) : error C2362: initialization of 'bHistoryPruning' is skipped by 'goto CUT'
      \search.cpp(861) : see declaration of 'bHistoryPruning'
search.cpp(968) : error C2362: initialization of 'bHistoryPruning' is skipped by 'goto CUT'
   \search.cpp(861) : see declaration of 'bHistoryPruning'
\search.cpp(968) : error C2362: initialization of 'NextKiller' is skipped by 'goto CUT'
      \search.cpp(751) : see declaration of 'NextKiller'
search.cpp(968) : error C2362: initialization of 'bHistoryPruning' is skipped by 'goto CUT'
   search.cpp(861) : see declaration of 'bHistoryPruning'
search.cpp(968) : error C2362: initialization of 'NextKiller' is skipped by 'goto CUT'
      search.cpp(751) : see declaration of 'NextKiller'
search.cpp(968) : error C2362: initialization of 'ThereIsKillers' is skipped by 'goto CUT'
      search.cpp(692) : see declaration of 'ThereIsKillers'
执行 cl.exe 时出错.

- 1 error(s), 0 warning(s)

这是从网上下载的代码。请高手帮忙：这倒底是为什么呢？如何修改？谢谢

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)

收藏・0

免费・0

支持