searchengine.java

一个网络对弈的中国象棋程序 操作： 1、Setting,选择对战方式。如果选择“网络对战”

/*
 * 创建日期 2005-3-18
 *
 * 更改所生成文件模板为
 * 窗口 > 首选项 > Java > 代码生成 > 代码和注释
 */
package org.acerge.engine;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.Calendar;
import java.util.Random;

import org.apache.commons.logging.*;
public class SearchEngine {
	private static Log log = LogFactory.getLog( SearchEngine.class );
	public static final int MaxBookMove = 40;//使用开局库的最大步数
	public static final int MaxKiller = 4;//搜索杀着的最大步数
	private static final int BookUnique = 1;//指示结点类型，下同
	private static final int BookMulti = 2;
	private static final int HashAlpha = 4;
	private static final int HashBeta = 8;
	private static final int HashPv = 16;

	private static final int ObsoleteValue = -CCEvalue.MaxValue - 1;
	private static final int UnknownValue = -CCEvalue.MaxValue - 2;
	//private static final int BookUniqueValue = CCEvalue.MaxValue + 1;
	//private static final int BookMultiValue = CCEvalue.MaxValue + 2;//推荐使用开局库,值要足够大
	
	public static final int CLOCK_S = 1000;//1秒=1000毫秒
	public static final int CLOCK_M = 1000*60;//1分=60秒
	private static final Random rand = new Random();
	private MoveNode bestMove=null;

	//for search control
	private int depth;
	private long properTimer, limitTimer;
	// 搜索过程的全局变量，包括：
	// 1. 搜索树和历史表

	private ActiveBoard activeBoard;
	private int histTab[][];
	public void setActiveBoard(ActiveBoard activeBoard){
		this.activeBoard=activeBoard;
	}
	// 2. 搜索选项
	private int selectMask,style;//下棋风格 default = EngineOption.Normal;
	private boolean wideQuiesc, futility, nullMove;
	//SelectMask:随机性 , WideQuiesc(保守true if Style == EngineOption.solid) 
	//Futility(true if Style == EngineOption.risky冒进)
	//NullMove 是否空着剪裁 
	private boolean ponder;
	// 3. 时间控制参数
	private long startTimer, minTimer, maxTimer;
	private int startMove;
	private boolean stop;
	// 4. 统计信息：Main Search Nodes, Quiescence Search Nodes and Hash Nodes
	private int nodes, nullNodes, hashNodes, killerNodes, betaNodes, pvNodes, alphaNodes, mateNodes, leafNodes;
	private int quiescNullNodes, quiescBetaNodes, quiescPvNodes, quiescAlphaNodes, quiescMateNodes;
	private int hitBeta, hitPv, hitAlpha;
	// 5. 搜索结果
	private int lastScore, pvLineNum;
	private MoveNode pvLine[]=new MoveNode[ActiveBoard.MAX_MOVE_NUM];

	// 6. Hash and Book Structure
	private int hashMask, maxBookPos, bookPosNum;
	private HashRecord[] hashList;
	private BookRecord[] bookList;
	public SearchEngine(ActiveBoard chessP){
		this();
		activeBoard = chessP;
	}
	public SearchEngine(){
		int i;
		//Position = new ChessPosition();
		histTab=new int[90][90];;
		nodes=nullNodes=hashNodes=killerNodes=betaNodes=pvNodes=alphaNodes=mateNodes=leafNodes=0;
		selectMask=0;//1<<10-1;//随机性
		style=EngineOption.Normal;
		wideQuiesc=style==EngineOption.Solid;
		futility=style==EngineOption.Risky;
		nullMove=true;
		// Search results
		lastScore=0; pvLineNum=0;
		MoveNode PvLine[]=new MoveNode[ActiveBoard.MAX_MOVE_NUM];
		for (i=0;i < ActiveBoard.MAX_MOVE_NUM;i++){
			PvLine[i]=new MoveNode();
		}
		newHash(17,14);
		depth = 8; properTimer = CLOCK_M * 1 ; limitTimer = CLOCK_M *20;	
	}
	
	//Begin History and Hash Table Procedures
	public void newHash(int HashScale, int BookScale) {
		histTab = new int[90][90];
		hashMask = (1 << HashScale) - 1;
		maxBookPos = 1 << BookScale;
		hashList = new HashRecord[hashMask+1];
		for (int i=0; i< hashMask+1; i++){
			hashList[i]=new HashRecord();
		}
		bookList = new BookRecord[maxBookPos];
		//for (int i=0; i< MaxBookPos; i++){
		//	BookList[i]=new BookRecord();
		//}

		clearHistTab();
		clearHash();
		//BookRand = rand.nextLong();//(unsigned long) time(NULL);
	}
	public void delHash() {
		histTab=null;
		hashList=null;
		bookList=null;
	}

	public void clearHistTab() {
		int i, j;
		for (i = 0; i < 90; i ++) {
			for (j = 0; j < 90; j ++) {
				histTab[i][j] = 0;
			}
		}		
	}

	public void clearHash() {
		int i;
		for (i = 0; i <= hashMask; i ++) {
			hashList[i].flag = 0;
		}
	}

	private int probeHash(MoveNode HashMove, int Alpha, int Beta, int Depth) {
		boolean MateNode;
		HashRecord TempHash;
		int tmpInt = (int) (activeBoard.getZobristKey() & hashMask);
		long tmpLong1 = activeBoard.getZobristLock(),tmpLong2;
		TempHash = hashList[(int) (activeBoard.getZobristKey() & hashMask)];
		tmpLong2 = TempHash.zobristLock;
		if (TempHash.flag!=0 && TempHash.zobristLock == activeBoard.getZobristLock()) {
			MateNode = false;
			if (TempHash.value > CCEvalue.MaxValue - ActiveBoard.MAX_MOVE_NUM / 2) {
				TempHash.value -= activeBoard.getMoveNum() - startMove;
				MateNode = true;
			} else if (TempHash.value < ActiveBoard.MAX_MOVE_NUM / 2 - CCEvalue.MaxValue) {
				TempHash.value += activeBoard.getMoveNum() - startMove;
				MateNode = true;
			}
			if (MateNode || TempHash.depth >= Depth) {
				if ((TempHash.flag & HashBeta)!=0) {
					if (TempHash.value >= Beta) {
						hitBeta ++;
						return TempHash.value;
					}
				} else if ((TempHash.flag & HashAlpha)!=0) {
					if (TempHash.value <= Alpha) {
						hitAlpha ++;
						return TempHash.value;
					}
				} else if ((TempHash.flag & HashPv)!=0) {
					hitPv ++;
					return TempHash.value;
				} else {
					return UnknownValue;
				}
			} 
			if (TempHash.bestMove.src == -1) {
				return UnknownValue;
			} else {
				HashMove = TempHash.bestMove;
				return ObsoleteValue;
			}
		}
		return UnknownValue;
	}

	private void recordHash(MoveNode hashMove, int hashFlag, int value, int depth) {
		HashRecord tempHash;
		tempHash = hashList[(int) (activeBoard.getZobristKey() & hashMask)];
		if ((tempHash.flag!=0) && tempHash.depth > depth) {
			return;
		}
		tempHash.zobristLock = activeBoard.getZobristLock();
		tempHash.flag = hashFlag;
		tempHash.depth = depth;
		tempHash.value =  value;
		if (tempHash.value > CCEvalue.MaxValue - ActiveBoard.MAX_MOVE_NUM / 2) {
			tempHash.value += activeBoard.getMoveNum() - startMove;
		} else if (tempHash.value < ActiveBoard.MAX_MOVE_NUM / 2 - CCEvalue.MaxValue) {
			tempHash.value -= activeBoard.getMoveNum() - startMove;
		}
		tempHash.bestMove = hashMove;
		hashList[(int) (activeBoard.getZobristKey() & hashMask)] = tempHash;
	}

	private void GetPvLine() {
		HashRecord tempHash;
		tempHash = hashList[(int) (activeBoard.getZobristKey() & hashMask)];
		if ((tempHash.flag!=0) && tempHash.bestMove.src != -1 && tempHash.zobristLock == activeBoard.getZobristLock()) {
			pvLine[pvLineNum] = tempHash.bestMove;
			activeBoard.movePiece(tempHash.bestMove);
			pvLineNum ++;
			if (activeBoard.isLoop(1)==0) {//???????
				GetPvLine();
			}
			activeBoard.undoMove();
		}
	}

//	record example: i0h0 4 rnbakabr1/9/4c1c1n/p1p1N3p/9/6p2/P1P1P3P/2N1C2C1/9/R1BAKAB1R w - - 0 7
//	i0h0:Move , 4: evalue, other: FEN String

	public void loadBook(final String bookFile) throws IOException{//开局库
		int bookMoveNum, value ,i;
		BufferedReader inFile;
		String lineStr;
		// LineStr;
		int index=0;
		MoveNode bookMove=new MoveNode();//note:wrong
		HashRecord tempHash;
		ActiveBoard BookPos=new ActiveBoard();//note:wrong
		inFile = new BufferedReader(new FileReader(bookFile),1024*1024);
		if (inFile == null) return;
		bookPosNum = 0;
		int recordedToHash = 0;//for test
		while ((lineStr=inFile.readLine())!=null) {
			bookMove = new MoveNode();
			bookMove.move(lineStr);
			index=0;
			if (bookMove.src != -1) {
				index += 5;
				while(lineStr.charAt(index)==' '){
					index++;
				}
				BookPos.loadFen(lineStr.substring(index));
				long tmpZob = BookPos.getZobristKey();
				int tmp = BookPos.getSquares(bookMove.src);//for test
				if (BookPos.getSquares(bookMove.src)!=0) {
					tempHash = hashList[(int) (BookPos.getZobristKey() & hashMask)];
					if (tempHash.flag!=0) {//占用
						if (tempHash.zobristLock == BookPos.getZobristLock()){//局面相同
							if ((tempHash.flag & BookMulti)!=0) {//多个相同走法
								bookMoveNum = bookList[tempHash.value].moveNum;
								if (bookMoveNum < MaxBookMove) {
									bookList[tempHash.value].moveList[bookMoveNum] = bookMove;
									bookList[tempHash.value].moveNum ++;
									recordedToHash++;//for test
								}
							}else{
								if(bookPosNum < maxBookPos) {
									tempHash.flag = BookMulti;
									bookList[bookPosNum] = new BookRecord();
									bookList[bookPosNum].moveNum = 2;
									bookList[bookPosNum].moveList[0] = tempHash.bestMove;
									bookList[bookPosNum].moveList[1] = bookMove;
									tempHash.value = bookPosNum;
									bookPosNum ++;
									hashList[(int) (BookPos.getZobristKey() & hashMask)] = tempHash;
									recordedToHash++;//for test
								}
							}
						}
					} else {
						tempHash.zobristLock = BookPos.getZobristLock();
						tempHash.flag = BookUnique;
						tempHash.depth = 0;
						tempHash.value = 0;
						tempHash.bestMove = bookMove;
						hashList[(int) (BookPos.getZobristKey() & hashMask)] = tempHash;
						recordedToHash++;
					}
				}
			}
		}
		inFile.close();		
	}

//	End History and Hash Tables Procedures

//	Begin Search Procedures
	// Search Procedures
	private int RAdapt(int depth) {
		//根据不同情况来调整R值的做法,称为“适应性空着裁剪”(Adaptive Null-Move Pruning)，
		//它首先由Ernst Heinz发表在1999年的ICCA杂志上。其内容可以概括为
		//a. 深度小于或等于6时，用R = 2的空着裁剪进行搜索
		//b. 深度大于8时，用R = 3； 
		//c. 深度是6或7时，如果每方棋子都大于或等于3个,则用 R = 3，否则用 R = 2。

		if (depth <= 6) {
			return 2;
		} else if (depth <= 8) {
			return activeBoard.getEvalue(0) < CCEvalue.EndgameMargin || activeBoard.getEvalue(1) < CCEvalue.EndgameMargin ? 2 : 3;
		} else {
			return 3;
		}
	}
	
	private int quiesc(int Alpha, int Beta) {//只对吃子
		int i, bestValue, thisAlpha, thisValue;
		boolean inCheck, movable;
		MoveNode thisMove;
		SortedMoveNodes moveSort=new SortedMoveNodes();
		
		// 1. Return if a Loop position is detected
		if (activeBoard.getMoveNum() > startMove) {
			thisValue = activeBoard.isLoop(1);//note:wrong
			if (thisValue!=0) {
				return activeBoard.loopValue(thisValue, activeBoard.getMoveNum() - startMove);
			}
		}
		
		// 2. Initialize
		inCheck = activeBoard.lastMove().chk;
		movable = false;
		bestValue = -CCEvalue.MaxValue;
		thisAlpha = Alpha;

		// 3. For non-check position, try Null-Move before generate moves
		if (!inCheck) {
			movable = true;
			thisValue = activeBoard.evaluation() + (selectMask!=0 ? (rand.nextInt() & selectMask) - (rand.nextInt() & selectMask) : 0);
			if (thisValue > bestValue) {
				if (thisValue >= Beta) {
					quiescNullNodes ++;
					return thisValue;
				}
				bestValue = thisValue;
				if (thisValue > thisAlpha) {
					thisAlpha = thisValue;
				}
			}
		}
		// 4. Generate and sort all moves for check position, or capture moves for non-check position
		moveSort.GenMoves(activeBoard, inCheck ? histTab : null);
		for (i = 0; i < moveSort.MoveNum; i ++) {
			moveSort.BubbleSortMax(i);
			thisMove = moveSort.MoveList[i];
			if (inCheck || activeBoard.narrowCap(thisMove, wideQuiesc)) {
				if (activeBoard.movePiece(thisMove)) {
					movable = true;
					
					// 5. Call Quiescence Alpha-Beta Search for every leagal moves 
					thisValue = -quiesc(-Beta, -thisAlpha);
					//for debug
					String tmpStr="";
					for (int k=0;k<activeBoard.getMoveNum();k++){
						 tmpStr = tmpStr + activeBoard.moveList[k]+",";
					}
					
					tmpStr = tmpStr+"Value:"+thisValue+"\n";
					activeBoard.undoMove();

					// 6. Select the best move for Fail-Soft Alpha-Beta
					if (thisValue > bestValue) {
						if (thisValue >= Beta) {
							quiescBetaNodes ++;
							return thisValue;
						}
						bestValue = thisValue;
						if (thisValue > thisAlpha) {
							thisAlpha = thisValue;
						}
					}
				}
			}
		}

		// 7. Return a loose value if no leagal moves
		if (!movable) {
			quiescMateNodes ++;
			return activeBoard.getMoveNum() - startMove - CCEvalue.MaxValue;
		}
		if (thisAlpha > Alpha) {
			quiescPvNodes ++;
		} else {
			quiescAlphaNodes ++;
		}
		return bestValue;
	}
	// 搜索算法，包括
	//	1. Hash Table;
	//	2. 超出边界的Alpha-Beta搜索
	//	3. 适应性空着裁减
	//	4. 选择性扩展
	//	5. 使用Hash Table的迭代加深;
	//	6. 杀着表
	//	7. 将军扩展
	//	8. 主要变例搜索
	//	9. 历史启发表
	
	private int search(KillerStruct KillerTab, int Alpha, int Beta, int Depth) {
		int i, j, thisDepth, futPrune, hashFlag;
		boolean inCheck, movable, searched;
		int hashValue, bestValue, thisAlpha, thisValue, futValue=0;
		MoveNode thisMove=new MoveNode();
		MoveNode bestMove=new MoveNode();
		SortedMoveNodes moveSort=new SortedMoveNodes();
		KillerStruct subKillerTab=new KillerStruct();
		// Alpha-Beta Search:
		// 1. 重复循环检测
		if (activeBoard.getMoveNum() > startMove) {
			thisValue = activeBoard.isLoop(1);//
			if (thisValue!=0) {
				return activeBoard.loopValue(thisValue, activeBoard.getMoveNum() - startMove);
			}
		}
		
		// 2. 是否需要扩展
		inCheck = activeBoard.lastMove().chk;
		thisDepth = Depth;
		if (inCheck) {
			thisDepth ++;
		}

		// 3. Return if hit the Hash Table
		hashValue = probeHash(thisMove, Alpha, Beta, thisDepth);
		if (hashValue >= -CCEvalue.MaxValue && hashValue <= CCEvalue.MaxValue) {
			return hashValue;
		}

		// 4. Return if interrupted or timeout
		if (interrupt()) {
			return 0;
		};

		// 5. 正式开始搜索：
		if (thisDepth > 0) {
			movable = false;
			searched = false;
			bestValue = -CCEvalue.MaxValue;
			thisAlpha = Alpha;
			hashFlag = HashAlpha;
			subKillerTab.moveNum = 0;
			
			// 6. 是否需要空着裁减与冒进？
			futPrune=0;
			if (futility) {
				// 冒进 
				if (thisDepth == 3 && !inCheck && activeBoard.evaluation() + CCEvalue.RazorMargin <= Alpha && activeBoard.getEvalue(activeBoard.getOppPlayer()) > CCEvalue.EndgameMargin) {
					thisDepth = 2;
				}
				if (thisDepth < 3) {
					futValue = activeBoard.evaluation() + (thisDepth == 2 ? CCEvalue.ExtFutMargin : CCEvalue.SelFutMargin);