Uncommented lambda-search Java-code (small version 2.0)
import java.io.*;
public class Small {
static int boardSize;
static int winLength;
static int[] board;
static int movesGenerated;
static float lambda(int n, int d) {
if(2*(d/2)==d)writeln("*** ERROR: lambda must be called with uneven d");
if(d<0)return 0f;
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,0.75f,0.75f,1);
if(result==1)return 1f;
}
return result;
}
static float lambda0(int d) {
if(d<=0)return 0f;
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, float alpha, float beta, int moveColor) {
if(eval()!=0.5f || d<=0)return eval()*moveColor;
float current = -1.0e+15f;
int siblings=0;
int move=-1;
if(n==-12345)move=nextLegalMove(move,moveColor);
else move=nextLambdaMove(n,d,move,moveColor);
while(move!=-12345) {
siblings++;
makeMove(move,moveColor);
float score=-alphabeta(n,d-1,-beta,-alpha,-moveColor);
unmakeMove(move,moveColor);
if(score>=current) {
current=score;
if(score>=alpha)alpha=score;
if(score>=beta) {
return score;
}
}
if(n==-12345)move=nextLegalMove(move,moveColor);
else move=nextLambdaMove(n,d,move,moveColor);
}
if(siblings==0) {
if(n==-12345)return eval()*moveColor;
else {
return moveColor*(1-moveColor)/2;
}
}
return current;
}
static int nextLambdaMove(int n, int d, int move, int moveColor) {
int moveCandidate=nextLegalMove(move,moveColor);
while(moveCandidate!=-12345) {
float temp=-12345;
if(moveColor==1) {
makeMove(moveCandidate,moveColor);
temp=lambda(n-1,d-2);
unmakeMove(moveCandidate,moveColor);
if(temp>=1)return moveCandidate;
}
else {
makeMove(moveCandidate,moveColor);
temp=lambda(n-1,d-1);
unmakeMove(moveCandidate,moveColor);
if(temp<1)return moveCandidate;
}
moveCandidate=nextLegalMove(moveCandidate,moveColor);
}
return -12345;
}
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) {
winLength=4;
boardSize=4;
board=new int[boardSize*boardSize];
board[0]=1;
board[3]=1;
board[15]=1;
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);
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,0.75f,0.75f,1);
writeln("ALPHABETA d="+i+": "+result+" {"+movesGenerated+"}");
}
writeln(" ");
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);
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,0.75f,0.75f,1);
writeln("ALPHABETA d="+i+": "+result+" {"+movesGenerated+"}");
}
writeln(" ");
}
}