Lambda-search Java-code (large version 2.0)
The code below runs under Java 2, but should run under older Java versions as well. The code is deliberately simple, using only methods, arrays, loops, and so on. Only additions compared to the small version of the code are commented, so the code below should be read together with the comments to the small version of the code (see here).
Differences between large and small version
of the code
This version adds some more functionality for, among other
things, printing out diagrams with indication of current
variation. In addition, the large version is able to distinguish
three values of a l-tree, 1, 0.5 or 0.
Value 1 means that the goal can be acheived (proof). Value 0.5
means that it is unknown (at the current search depth d)
whether or not the goal can be achieved at l-order
n. Value 0 means that the goal cannot be acheived at l-order n (disproof). This
functionality adds some information regarding disproofs:
the algorithm now knows whether a failed l-search
ran into the depth limit or not. If not, the goal is disproved at
l-order n, meaning that there
would be no point in searching this l-tree
to any deeper, and such knowledge could be used to terminate an
iterative-deepening alphabeta-search. (Note: such a disproof does
not, of course, entail that the goal could not be acheived in a l-tree of order n + 1 or higher
– it only has to do with terminating iterative-deepening
alpha-beta as early as possible).
import java.io.*;
public class Large {
static int boardSize;
static int winLength;
static int[] board;
static int minimax;
static int movesGenerated;
static int print;
static float alpha0;
static float beta0;
static int evalCanBe0;
static int[][] lambdaTreeCoord;
static float lambda(int n, int d, int printDiagrams) {
if(2*(d/2)==d)writeln("*** ERROR: lambda must be called with uneven d");
if(d<0)return 0.5f;
if(eval()==1)return 1f;
float result=0f;
for(int i=0;i<=n;i++) {
if(i==0)result=lambda0(d);
if(i>=1)result=alphabeta(i,d,d,alpha0,beta0,1,printDiagrams);
if(result==1)return 1;
}
return result;
}
static float lambda0(int d) {
if(d<=0)return 0.5f;
int move=nextLegalMove(-1,1);
while(move!=-12345) {
makeMove(move,1);
float temp=eval();
unmakeMove(move,1);
if(temp==1)return 1f;
move=nextLegalMove(move,1);
}
return 0f;
}
static float alphabeta(int n, int d, int dMax, float alpha, float beta, int moveColor, int printDiagrams) {
if(n>=1 && print==1 && printDiagrams==1) {
writeln("n="+n+" d="+d+" dMax="+dMax+" moveColor="+moveColor);
for(int i=0;i<dMax-d;i++) {
write(lambdaTreeCoord[n][i]+" ");
}
writeln(" ");
printPosition();
}
if(eval()!=0.5f || d<=0)return moveColor*eval();
float current = -1.0e+15f;
float[] move=new float[2];
int siblings=0;
move[0]=-1;
if(n==-12345) move[0]=nextLegalMove((int)move[0],moveColor);
else move=nextLambdaMove(n,d,move,moveColor);
while(move[0]!=-12345) {
siblings++;
makeMove((int)move[0],moveColor);
//stores current variation for use when printing diagrams
if(n!=-12345)lambdaTreeCoord[n][dMax-d]=siblings;
float score=-alphabeta(n,d-1,dMax,-beta,-alpha,-moveColor,printDiagrams);
unmakeMove((int)move[0],moveColor);
if(score>=current) {
current=score;
if(score>=alpha)alpha=score;
if(score>=beta && minimax==0) {
return score;
}
}
if(n==-12345) move[0]=nextLegalMove((int)move[0],moveColor);
else move=nextLambdaMove(n,d,move,moveColor);
}
if(siblings==0) {
if(n==-12345)return eval()*moveColor;
else {
//returns info extracted from lambda{n-1} search.
return moveColor*move[1];
}
}
return current;
}
static float[] nextLambdaMove(int n, int d, float[] move, int moveColor) {
//used if attacker moves
float max=-1.0e+15f;
//used if defender moves
float min=1.0e+15f;
//return[0]=move coordinates, return[1]=move value
float[] returnValue= new float[2];
int moveCandidate=nextLegalMove((int)move[0],moveColor);
while(moveCandidate!=-12345) {
float temp=-12345;
if(moveColor==1) {
makeMove(moveCandidate,moveColor);
temp=lambda(n-1,d-2,0);
unmakeMove(moveCandidate,moveColor);
if(temp>=1) {
returnValue[0]=moveCandidate;
returnValue[1]=temp;
return returnValue;
}
//keep the best of the non-working lambda-moves
if(temp>max)max=temp;
}
else {
makeMove(moveCandidate,moveColor);
temp=lambda(n-1,d-1,0);
unmakeMove(moveCandidate,moveColor);
if(temp<1) {
returnValue[0]=moveCandidate;
returnValue[1]=temp;
return returnValue;
}
//keep the best of the non-working lambda-moves
if(temp<min)min=temp;
}
moveCandidate=nextLegalMove(moveCandidate,moveColor);
}
returnValue[0]=-12345;
if(moveColor==1)returnValue[1]=max;
if(moveColor==-1)returnValue[1]=min;
return returnValue;
}
static int nextLegalMove(int move, int moveColor) {
for(int i=move+1;i<boardSize*boardSize;i++) {
if(board[i]==0) {
return i;
}
}
return -12345;
}
static void makeMove(int move, int moveColor) {
board[move]=moveColor;
movesGenerated++;
}
static void unmakeMove(int move, int moveColor) {
board[move]=0;
}
static float eval() {
int attacker=0;
int defender=0;
for(int k=-1;k<=1;k=k+2) {
for(int i=0;i<boardSize;i++) {
label1:
for(int j=0;j<boardSize;j++) {
if(j<=boardSize-winLength) {
for(int kk=0;kk<=winLength-1;kk++) {
if(board[i+boardSize*j+kk*boardSize]!=k)continue label1;
}
if(k==-1)defender++;
if(k==1)attacker++;
}
}
}
for(int i=0;i<boardSize;i++) {
label2:
for(int j=0;j<boardSize;j++) {
if(i<=boardSize-winLength) {
for(int kk=0;kk<=winLength-1;kk++) {
if(board[i+boardSize*j+kk*1]!=k)continue label2;
}
if(k==-1)defender++;
if(k==1)attacker++;
}
}
}
for(int i=0;i<boardSize;i++) {
label3:
for(int j=0;j<boardSize;j++) {
if(i<=boardSize-winLength && j<=boardSize-winLength) {
for(int kk=0;kk<=winLength-1;kk++) {
if(board[i+boardSize*j+kk*boardSize+kk*1]!=k)continue label3;
}
if(k==-1)defender++;
if(k==1)attacker++;
}
}
}
for(int i=0;i<boardSize;i++) {
label3:
for(int j=0;j<boardSize;j++) {
if(i<=boardSize-winLength && j>=winLength-1) {
for(int kk=0;kk<=winLength-1;kk++) {
if(board[i+boardSize*j-kk*boardSize+kk*1]!=k)continue label3;
}
if(k==-1)defender++;
if(k==1)attacker++;
}
}
}
}
if(defender>0)return 0f;
if(attacker>0)return 1f;
return 0.5f;
}
static void writeln(String xxx) {
System.out.println(xxx);
System.err.println(xxx);
return;
}
static void write(String xxx) {
System.out.print(xxx);
System.err.print(xxx);
return;
}
static void printPosition() {
for(int i=boardSize-1;i>=0;i=i-1) {
for(int j=0;j<=boardSize-1;j++) {
if(board[boardSize*i+j]==1)write(" #");
if(board[boardSize*i+j]==-1)write(" O");
if(board[boardSize*i+j]==0)write(" .");
}
writeln(" ");
}
writeln(" ");
}
public static void main (String[] args) {
//If 1, eval can also attain value 0 (in addition to values 1 and 0.5)
//It attains value 0 when the defender winLength or more stones in a row
evalCanBe0=0;
//Initial value of alpha in alpha-beta-calls
//Could be set to 0.25 in order to find disproofs quicker,
//but normally 0.75 is probably better
alpha0=0.75f;
//Initial value of beta in alpha-beta-calls
beta0=0.75f;
//Array storing tree coordinates (assumes n<=30 and d<=200)
lambdaTreeCoord=new int[30][200];
winLength=4;
boardSize=4;
board=new int[boardSize*boardSize];
board[0]=1;
board[3]=1;
board[15]=1;
//Print diagrams? (1/0)
print=0;
//Optional use of minimax instead of alphabeta (1/0)
minimax=0;
//Max search depth
int d=13;
writeln(winLength+"-in-a-row on "+winLength+"x"+winLength+" board");
writeln("Position to analyze, with # (attacker) moving first:");
printPosition();
writeln(" n=1 n=2 n=3 n=4 n=5 n=6");
for(int i=3;i<=d;i=i+2) {
write("d="+i+": ");
if(i<10)write(" ");
for(int j=1;j<=(i-1)/2;j=j+1) {
movesGenerated=0;
float result=lambda(j,i,1);
write(result+" {"+movesGenerated+"}");
for(int k=0;k<8-(int)(Math.log(movesGenerated)/Math.log(10));k++)write(" ");
}
writeln(" ");
}
writeln(" ");
for(int i=0;i<=d;i++) {
movesGenerated=0;
float result=alphabeta(-12345,i,i,alpha0,beta0,1,0);
writeln("ALPHABETA d="+i+": "+result+" {"+movesGenerated+"}");
}
writeln(" ");
writeln(" ");
writeln(" ");
writeln(" ");
writeln("Shows diagrams for special case (n,d)=(2,7)");
writeln(" ");
print=1;
float result1=lambda(2,7,1);
print=0;
writeln(" ");
writeln(" ");
writeln(" ");
winLength=3;
boardSize=3;
board=new int[boardSize*boardSize];
d=9;
writeln(winLength+"-in-a-row on "+winLength+"x"+winLength+" board");
writeln("Position to analyze, with # (attacker) moving first:");
printPosition();
writeln(" n=1 n=2 n=3 n=4 n=5 n=6");
for(int i=3;i<=d;i=i+2) {
write("d="+i+": ");
if(i<10)write(" ");
for(int j=1;j<=(i-1)/2;j=j+1) {
movesGenerated=0;
float result=lambda(j,i,1);
write(result+" {"+movesGenerated+"}");
for(int k=0;k<8-(int)(Math.log(movesGenerated)/Math.log(10));k++)write(" ");
}
writeln(" ");
}
writeln(" ");
for(int i=0;i<=d;i++) {
movesGenerated=0;
float result=alphabeta(-12345,i,i,alpha0,beta0,1,0);
writeln("ALPHABETA d="+i+": "+result+" {"+movesGenerated+"}");
}
writeln(" ");
writeln(" ");
writeln(" ");
writeln(" ");
writeln("Shows diagrams for special case (n,d)=(2,9)");
writeln(" ");
print=1;
result1=lambda(2,9,1);
print=0;
}
}