I am trying to implement principal Variation Search with transposition tables.
However, I am wondering whether I should store exact values when I am doing a null-window-Search. Seems a little odd to do so.
Additionally, I dont know whether my implementation of collecting the PV is correct. I wouldn't mind if you spot any mistakes.
Here is my current implementation I have been working on. (Some of the parameters are not used because I am still experimenting with some of t things)
Code: Select all
public int principalVariation(Board board, int depth,int ply, int alpha, int beta,int[]currentLine,boolean inPVLine,long endingTime){
if(board.isTerminalState() || depth<=0 ||(System.currentTimeMillis()-endingTime>=0))
return board.color*GameEvaluation.evaluate(board);
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.LOWER)
alpha = Math.max(alpha, entry.value);
else if (entry.flag == Transposition.UPPER)
beta = Math.min(beta, entry.value);
if (alpha >= beta) {
return entry.value;
}
}
ArrayList<Integer>sucessors= MGenerator.getSucessors(board);
final int size =sucessors.size();
int[]localPV = new int[depth];
int bestValue=-10000000;
if(sucessors.size()>=1){
board.makeMove(sucessors.get(0));
bestValue =-principalVariation(board,depth-1,ply+1,-beta,-alpha,localPV,inPVLine,endingTime);
board.undoMove(sucessors.get(0));
if(bestValue>alpha){
if(bestValue>=beta) {
history[sideToMove][sucessors.get(0)]+=depth*depth;
return bestValue;
}
alpha=bestValue;
currentLine[0]=sucessors.get(0);
for(int i=1;i<depth;i++){
currentLine[i]=localPV[i-1];
}
}
}
for(int i=1;i<size;i++){
board.makeMove(sucessors.get(i));
int score =-principalVariation(board,depth-1,ply+1,-alpha-1,-alpha,localPV,false,endingTime);
if(score>alpha && score<beta){
score =-principalVariation(board,depth-1,ply+1,-beta,-alpha,localPV,false,endingTime);
if(score>alpha){
alpha=score;
}
}
board.undoMove(sucessors.get(i));
if(score>bestValue){
bestValue=score;
if(score>=beta){
break;
}
currentLine[0]=sucessors.get(i);
for(int p=1;p<depth;p++){
currentLine[p]=localPV[p-1];
}
}
}
Transposition trans = new Transposition();
trans.value =bestValue;
if (bestValue <= alphaOrig) {
trans.flag=Transposition.UPPER;
} else if (bestValue >= beta) {
trans.flag =Transposition.LOWER;
} else {
trans.flag=Transposition.EXACT;
}
trans.depth=depth;
trans.key=board.key;
table.insert(trans);
return bestValue;
}
