📄 searchengine.java
字号:
if (!inCheck && futValue <= Alpha) {
futPrune = thisDepth;
bestValue = futValue;
}
}
}
// 7. 空着裁减
if (nullMove && futPrune==0 && !inCheck && activeBoard.lastMove().src != -1 && activeBoard.getEvalue(activeBoard.getPlayer()) > CCEvalue.EndgameMargin) {
activeBoard.nullMove();
thisValue = -search(subKillerTab, -Beta, 1 - Beta, thisDepth - 1 - RAdapt(thisDepth));
activeBoard.undoNull();
if (thisValue >= Beta) {
nullNodes ++;
return Beta;
}
}
// 8. 搜索命中Hash Table
if (hashValue == ObsoleteValue) {
//System.out.println(ThisMove.Coord());
if (activeBoard.movePiece(thisMove)) {
movable = true;
if (futPrune!=0 && -activeBoard.evaluation() + (futPrune == 2 ? CCEvalue.ExtFutMargin : CCEvalue.SelFutMargin) <= Alpha && activeBoard.lastMove().chk) {
activeBoard.undoMove();
} else {
thisValue = -search(subKillerTab, -Beta, -thisAlpha, thisDepth - 1);
searched = true;
activeBoard.undoMove();
if (stop) {
return 0;
}
if (thisValue > bestValue) {
if (thisValue >= Beta) {
histTab[thisMove.src][thisMove.dst] += 1 << (thisDepth - 1);
recordHash(thisMove, HashBeta, Beta, thisDepth);
hashNodes ++;
return thisValue;
}
bestValue = thisValue;
bestMove = thisMove;
if (thisValue > thisAlpha) {
thisAlpha = thisValue;
hashFlag = HashPv;
if (activeBoard.getMoveNum() == startMove) {
recordHash(bestMove, hashFlag, thisAlpha, thisDepth);
popInfo(thisAlpha, Depth);
}
}
}
}
}
}
// 9. 命中杀着表
for (i = 0; i < KillerTab.moveNum; i ++) {
thisMove = KillerTab.moveList[i];
if (activeBoard.leagalMove(thisMove)) {
if (activeBoard.movePiece(thisMove)) {
movable = true;
if (futPrune!=0 && -activeBoard.evaluation() + (futPrune == 2 ? CCEvalue.ExtFutMargin : CCEvalue.SelFutMargin) <= Alpha && activeBoard.lastMove().chk) {
activeBoard.undoMove();
} else {
if (searched) {
thisValue = -search(subKillerTab, -thisAlpha - 1, -thisAlpha, thisDepth - 1);
if (thisValue > thisAlpha && thisValue < Beta) {
thisValue = -search(subKillerTab, -Beta, -thisAlpha, thisDepth - 1);
}
} else {
thisValue = -search(subKillerTab, -Beta, -thisAlpha, thisDepth - 1);
searched = true;
}
activeBoard.undoMove();
if (stop) {
return 0;
}
if (thisValue > bestValue) {
if (thisValue >= Beta) {
killerNodes ++;
histTab[thisMove.src][thisMove.dst] += 1 << (thisDepth - 1);
recordHash(thisMove, HashBeta, Beta, thisDepth);
return thisValue;
}
bestValue = thisValue;
bestMove = thisMove;
if (thisValue > thisAlpha) {
thisAlpha = thisValue;
hashFlag = HashPv;
if (activeBoard.getMoveNum() == startMove) {
recordHash(bestMove, hashFlag, thisAlpha, thisDepth);
popInfo(thisAlpha, Depth);
}
}
}
}
}
}
}
// 10. 生成当前所有合法着法并排序
moveSort.GenMoves(activeBoard, histTab);
nodes+=moveSort.MoveNum;
for (i = 0; i < moveSort.MoveNum; i ++) {
moveSort.BubbleSortMax(i);
thisMove = moveSort.MoveList[i];
if (activeBoard.movePiece(thisMove)) {
movable = true;
// 11. Alpha-Beta Search
if (futPrune!=0 && -activeBoard.evaluation() + (futPrune == 2 ? CCEvalue.ExtFutMargin : CCEvalue.SelFutMargin) <= Alpha && activeBoard.lastMove().chk) {
activeBoard.undoMove();
} else {
if (searched) {
thisValue = -search(subKillerTab, -thisAlpha - 1, -thisAlpha, thisDepth - 1);
if (thisValue > thisAlpha && thisValue < Beta) {
thisValue = -search(subKillerTab, -Beta, -thisAlpha, thisDepth - 1);
}
} else {
thisValue = -search(subKillerTab, -Beta, -thisAlpha, thisDepth - 1);
searched = true;
}
activeBoard.undoMove();
if (stop) {
return 0;
}
// 12. 超出边界Alpha-Beta
if (thisValue > bestValue) {
if (thisValue >= Beta) {
betaNodes ++;
histTab[thisMove.src][thisMove.dst] += 1 << (thisDepth - 1);
recordHash(thisMove, HashBeta, Beta, thisDepth);
if (KillerTab.moveNum < MaxKiller) {
KillerTab.moveList[KillerTab.moveNum] = thisMove;
KillerTab.moveNum ++;
}
return thisValue;
}
bestValue = thisValue;
bestMove = thisMove;
if (thisValue > thisAlpha) {
thisAlpha = thisValue;
hashFlag = HashPv;
if (activeBoard.getMoveNum() == startMove) {
recordHash(bestMove, hashFlag, thisAlpha, thisDepth);
popInfo(thisAlpha, Depth);
}
}
}
}
}
}
// 13.无路可走，输棋！
if (!movable) {
mateNodes ++;
return activeBoard.getMoveNum() - startMove - CCEvalue.MaxValue;
}
// 14. Update History Tables and Hash Tables
if (futPrune!=0 && bestValue == futValue) {
bestMove.src = bestMove.dst = -1;
}
if ((hashFlag & HashAlpha)!=0) {
alphaNodes ++;
} else {
pvNodes ++;
histTab[bestMove.src][bestMove.dst] += 1 << (thisDepth - 1);
if (KillerTab.moveNum < MaxKiller) {
KillerTab.moveList[KillerTab.moveNum] = bestMove;
KillerTab.moveNum ++;
}
}
recordHash(bestMove, hashFlag, thisAlpha, thisDepth);
return bestValue;
// 15. 静态搜索
} else {
thisValue = quiesc(Alpha, Beta);
thisMove.src = bestMove.dst = -1;
if (thisValue <= Alpha) {
recordHash(thisMove, HashAlpha, Alpha, 0);
} else if (thisValue >= Beta) {
recordHash(thisMove, HashBeta, Beta, 0);
} else {
recordHash(thisMove, HashPv, thisValue, 0);
}
leafNodes ++;
return thisValue;
}
}
// End Search Procedures
// Start Control Procedures
private boolean interrupt(){
if (stop)
return true;
return false;
}
public void stopSearch(){this.stop=true;}
private void popInfo(int value, int depth) {
int i, quiescNodes, nps, npsQuiesc;
char[] moveStr;
long tempLong;
if (depth!=0) {
String logString="PVNode: depth=" + depth + ",score=" + value +",Move: "+"\n";
pvLineNum = 0;
GetPvLine();
for (i = 0; i < pvLineNum; i ++) {
moveStr = pvLine[i].location();
logString+=" " + String.copyValueOf(moveStr)+"\n";
}
if (ponder && System.currentTimeMillis() > minTimer && value + CCEvalue.InadequateValue > lastScore) {
stop = true;
}
if(log.isDebugEnabled()) log.debug(logString);
}
}
public void setupControl(int depth,long proper,long limit){
this.depth = depth;
this.properTimer = proper;
this.limitTimer = limit;
}
public void control() throws LostException{
//int Depth, int ProperTimer, int LimitTimer) throws IOException {
int i, MoveNum, ThisValue;
char[] MoveStr;
stop=false;
bestMove=null;
MoveNode ThisMove=new MoveNode(), UniqueMove=new MoveNode();
HashRecord TempHash;
SortedMoveNodes MoveSort=new SortedMoveNodes();
KillerStruct SubKillerTab=new KillerStruct();
// The Computer Thinking Procedure：
// 1. Search the moveNodes in Book
int tmpInt = (int) (activeBoard.getZobristKey() & hashMask);
TempHash = hashList[(int) (activeBoard.getZobristKey() & hashMask)];
if (TempHash.flag!=0 && TempHash.zobristLock == activeBoard.getZobristLock()) {
if ((TempHash.flag==BookUnique)) {
MoveStr = TempHash.bestMove.location();
bestMove = new MoveNode(String.copyValueOf(MoveStr));
return;
} else if (TempHash.flag == BookMulti) {
ThisValue = 0;
i = Math.abs(rand.nextInt())%(bookList[TempHash.value].moveNum);
MoveStr = bookList[TempHash.value].moveList[i].location();
bestMove = new MoveNode(String.copyValueOf(MoveStr));
return;
}
}
// 2. Initailize Timer and other Counter
startTimer = System.currentTimeMillis();
minTimer = startTimer + (properTimer >> 1);
maxTimer = properTimer << 1;
if (maxTimer > limitTimer) {
maxTimer = limitTimer;
}
maxTimer += startTimer;
stop = false;
startMove = activeBoard.getMoveNum();
nodes = nullNodes = hashNodes = killerNodes = betaNodes = pvNodes = alphaNodes = mateNodes = leafNodes = 0;
quiescNullNodes = quiescBetaNodes = quiescPvNodes = quiescAlphaNodes = quiescMateNodes = 0;
hitBeta = hitPv = hitAlpha = 0;
pvLineNum = 0;
// 3. 不合法：主动送将
if (activeBoard.checked(activeBoard.getOppPlayer())) {
return;
}
ThisValue = activeBoard.isLoop(3);
if (ThisValue!=0) {
throw new LostException("不可常捉!");
}
if (activeBoard.getMoveNum() > ActiveBoard.MAX_CONSECUTIVE_MOVES) {
throw new LostException("最大步数,和棋!");
}
// 4. 测试所有应将的着法
if (activeBoard.lastMove().chk) {
MoveNum = 0;
MoveSort.GenMoves(activeBoard, histTab);
for (i = 0; i < MoveSort.MoveNum; i ++) {
ThisMove = MoveSort.MoveList[i];
if (activeBoard.movePiece(ThisMove)) {
activeBoard.undoMove();
UniqueMove = ThisMove;
MoveNum ++;
if (MoveNum > 1) {
break;
}
}
}
if (MoveNum==0) {
if(log.isDebugEnabled())
log.debug("score " + -CCEvalue.MaxValue +"\n");
}
if (MoveNum == 1) {
MoveStr = UniqueMove.location();
if(log.isDebugEnabled())
log.debug("bestmove " + String.copyValueOf(MoveStr) + "\n");
bestMove = new MoveNode(String.copyValueOf(MoveStr));
return;
}
}
// 5. 迭代加深
if (depth==0) {
return;
}
for (i = 4; i <= depth; i ++) {
if(log.isDebugEnabled())
log.debug("info depth " + i +"\n");
SubKillerTab.moveNum = 0;
ThisValue = search(SubKillerTab, -CCEvalue.MaxValue, CCEvalue.MaxValue, i);
popInfo(ThisValue,depth);
if (stop) {
break;
}
lastScore = ThisValue;
// 6. Stop thinking if timeout or solved
if (!ponder && System.currentTimeMillis() > minTimer) {
break;
}
if (ThisValue > CCEvalue.MaxValue - ActiveBoard.MAX_MOVE_NUM / 2
|| ThisValue < ActiveBoard.MAX_MOVE_NUM / 2 - CCEvalue.MaxValue) {
break;
}
}
// 7. 得到最佳着法及其线路
if (pvLineNum!=0) {
MoveStr = pvLine[0].location();
bestMove = new MoveNode(String.copyValueOf(MoveStr));
if(log.isDebugEnabled())
log.debug("bestmove: " + String.copyValueOf(MoveStr) + "\n");
if (pvLineNum > 1) {
MoveStr = pvLine[1].location();
if(log.isDebugEnabled())
log.debug("ponder:" + String.copyValueOf(MoveStr) + "\n");
}
} else {
if(log.isDebugEnabled())
log.info("score:" + ThisValue);
}
}
//End Control Procedures
public MoveNode getBestMove() throws LostException{
control();
MoveNode retVal = bestMove;
return bestMove;
}
//for test
public static void main(String[] args) throws IOException {
long start,end;
RandomAccessFile testResult;
log.info("begin search, please wait......");
start = System.currentTimeMillis();
int steps = 8;
ActiveBoard cp= new ActiveBoard();
String FenStr = "1c1k1abR1/4a4/4b4/6NP1/4P4/2C1n1P2/r5p2/4B4/4A4/2BAK4 w - - 0 20";
cp.loadFen(FenStr);
SearchEngine searchMove = new SearchEngine(cp);
searchMove.loadBook("./data/BOOK.DAT");
//System.out.println(cp.AllPieces);
//searchMove.Control(steps,CLOCK_M*2,CLOCK_M*4);
log.info(FenStr);
end = System.currentTimeMillis();
long second=(end - start)/1000;
long minutes=second/60;
testResult = new RandomAccessFile("./data/test.log","rw");
Calendar c = Calendar.getInstance();
String tmpStr = "\n\n********************************************************************\n";
tmpStr = tmpStr + "[Test Time] "+c.getTime()+"\n";
tmpStr = tmpStr + "[Fen String] "+ FenStr + "\n";
tmpStr = tmpStr + " Deep =" + steps+",Used Time:"+ minutes +":" + second%60 + "\n";
tmpStr = tmpStr + "[Nodes] " + searchMove.nodes+"\n";
tmpStr = tmpStr + "[AlphaNodes] " + searchMove.alphaNodes+"\n";
tmpStr = tmpStr + "[BetaNodes] " + searchMove.betaNodes+"\n";
tmpStr = tmpStr + "[HashNodes] " + searchMove.hashNodes+"\n";
tmpStr = tmpStr + "[KillerNodes] " + searchMove.killerNodes+"\n";
tmpStr = tmpStr + "[LeafNodes] " + searchMove.leafNodes+"\n";
tmpStr = tmpStr + "[NullNodes] " + searchMove.nullNodes+"\n";
tmpStr = tmpStr + "[QuiescAlphaNodes] " + searchMove.quiescAlphaNodes+"\n";
tmpStr = tmpStr + "[QuiescBetaNodesNodes] " + searchMove.quiescBetaNodes+"\n";
tmpStr = tmpStr + "[QuiescMateNodes] " + searchMove.quiescMateNodes+"\n";
tmpStr = tmpStr + "[QuiescNullNodes] " + searchMove.quiescNullNodes+"\n";
tmpStr = tmpStr + "[QuiescPvNodes] " + searchMove.quiescPvNodes+"\n";
tmpStr = tmpStr + "[HitAlpha] " + searchMove.hitAlpha+"\n";
tmpStr = tmpStr + "[HitBeta] " + searchMove.hitBeta+"\n";
tmpStr = tmpStr + "[HitPv] " + searchMove.hitPv+"\n";
tmpStr = tmpStr + "[BetaNode] " + searchMove.betaNodes+"\n";
tmpStr = tmpStr + "[BPS] "+ searchMove.nodes/second;
int count = 0;
for (int i=1;i<searchMove.hashList.length;i++){
if (searchMove.hashList[i].flag!=0) count++;
}
tmpStr = tmpStr + "[HashTable] length="+searchMove.hashList.length+", occupied="+count;
testResult.seek(testResult.length());
testResult.writeBytes(tmpStr);
testResult.close();
System.out.println(tmpStr);
searchMove=null;
cp=null;
System.gc();
}
}
class BookRecord {
int moveNum;
MoveNode[] moveList;//[MaxBookMove];
public BookRecord(){
moveList = new MoveNode[SearchEngine.MaxBookMove];
moveNum=0;
}
};
class KillerStruct {
int moveNum;
MoveNode[] moveList;//[MaxKiller];
public KillerStruct(){
moveList = new MoveNode[SearchEngine.MaxKiller];
for (int i=0;i<SearchEngine.MaxKiller;i++)
moveList[i]= new MoveNode();
moveNum=0;
}
};
class HashRecord {
public HashRecord(){
flag=0;
depth=0;
value=0;
zobristLock = 0;
bestMove = new MoveNode();
}
long zobristLock;
int flag, depth;
int value;
MoveNode bestMove;
};
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -