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(" "); } }