我遇到了以下问题。我已经实现了换位表,它们似乎运行良好,或者至少我看不到它们不起作用。
此外,我想实现一些移动排序。
基本上,我首先搜索保存在转置表中的移动。出于某种原因,这根本不会改善搜索。要么我没有正确实现移动排序,要么我对 alpha-beta 算法和转位表的实现是错误的。
为了衡量性能,我计算了搜索期间访问的节点数。我的移动排序实现根本没有任何效果。
这是我想出的Java代码:
public int alphabeta(final CheckerBoard board,int alpha,int beta,int depth,boolean nullMoveAvailable){
nodeCount++;
int alphaOrig=alpha;
Transposition entry =table.find(board.key);
if(entry!=null && entry.depth>=depth){
if(entry.flag==Transposition.EXACT){
return entry.value;
}else if(entry.flag==Transposition.UPPER){
beta = Math.min(beta,entry.value);
}else if(entry.flag == Transposition.LOWER){
alpha =Math.max(alpha,entry.value);
}
if(alpha>=beta){
return entry.value;
}
}
if(depth==0 || board.isTerminalState()){
return quiesceneSearch2(board,alpha,beta);
}
ArrayList<Move>sucessors =MGenerator.getMoves(board);
Move currentBest =null;
for( int i=0;i<sucessors.size();i++){
if(entry!=null && entry.depth<depth && (entry.flag == Transposition.UPPER || entry.flag == Transposition.EXACT) && sucessors.get(i).equals(entry.best)){
Collections.swap(sucessors,0,i);
break;
}
}
int bestValue =Integer.MIN_VALUE;
for(Move move : sucessors){
board.makeMove(move);
int value =-alphabeta(board, -beta, -alpha, depth - 1, true);
board.undoMove(move);
if(value>bestValue){
bestValue =value;
currentBest = move;
}
alpha =Math.max(alpha,value);
if(alpha>=beta){
break;
}
}
Transposition next =new Transposition();
next.depth=depth;
next.value =bestValue;
next.zobrisKey=board.key;
next.best = currentBest;
if(bestValue<=alphaOrig){
next.flag =Transposition.UPPER;
}else if(bestValue>=beta){
next.flag = Transposition.LOWER ;
}else{
next.flag = Transposition.EXACT;
}
table.insert(next);
return alpha;
}
和以下代码开始搜索:
public int findBestMove(int depth){
if (table != null) {
table.clear();
}
ArrayList<Move> sucessors =MGenerator.getMoves(board);
int max = Integer.MIN_VALUE;
for(Move m : sucessors){
board.makeMove(m);
int value =-alphabeta(board, -1000000, 1000000, depth, true);
board.undoMove(m);
if(value>max){
max=value;
bestMove=m;
}
}
board.makeMove(bestMove);
return max;
}
如果有人看了我的代码,将不胜感激。也许我的这部分代码没有任何问题,但我不想发布所有内容,因为它已经有很多代码可以查看。
与这个字母表参考网站相比,我看到一些事情"关闭":https://web.archive.org/web/20071031100051/http://www.brucemo.com/compchess/programming/hashing.htm
1) 您没有存储深度 0 的任何转置条目;和
2)当alpha>=beta时,您存储的换位值为alpha而不是beta。
不知道这是否会有所作为,但是...
而且,哦,3)当 alpha>=beta 时,您还会从函数返回 alpha 而不是 beta。