Lambda-search Java-code (small 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.
import java.io.*; public class Small { //Global variables //Size of the board (3=tic-tac-toe) static int boardSize; //How many stones in a row in order to win? (3=tic-tac-toe) static int winLength; //Global array containing the board position static int[] board; //Counting the number of moves generated (nodes visited) static int movesGenerated; //Procedure trying out trees of lambda-order 0,1,2,...,n, all with depth=d. //Note that the attacker moves first (moveColor=1) 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); //tree is searched by means of alphabeta if(i>=1)result=alphabeta(i,d,0.75f,0.75f,1); if(result==1)return 1f; } return result; } //Lambda{0} is quite special, so it has its own method //Note that the attacker moves first (moveColor=1) static float lambda0(int d) { if(d<=0)return 0f; int move=nextLegalMove(-1,1); //try all legal moves while(move!=-12345) { makeMove(move,1); float temp=eval(); unmakeMove(move,1); //this move acheives the goal if(temp==1)return 1f; //try the next legal move move=nextLegalMove(move,1); } return 0f; } //Fail-soft alpha-beta static float alphabeta(int n, int d, float alpha, float beta, int moveColor) { //Game ends if eval()!=0.5, or if the remaining depth<=0 if(eval()!=0.5f || d<=0)return eval()*moveColor; float current = -1.0e+15f; //Counts the number or siblings (successive moves) int siblings=0; //Initial value for move int move=-1; //n==-12345 <=> standard alphabeta without lambda-trees if(n==-12345)move=nextLegalMove(move,moveColor); //Lambda-trees are made of lambda-moves 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 the node has no siblings if(siblings==0) { //If standard alphabeta, the evaluation is returned if(n==-12345)return eval()*moveColor; else { //Lambda-search: 1 is returned if moveColor==-1 (defender to move), //0 is returned if moveColor==1 (attacker to move) return moveColor*(1-moveColor)/2; } } return current; } //Method for generating lambda-moves static int nextLambdaMove(int n, int d, int move, int moveColor) { int moveCandidate=nextLegalMove(move,moveColor); while(moveCandidate!=-12345) { //Just an arbitrary initialization float temp=-12345; if(moveColor==1) { //Makes an attacker's move makeMove(moveCandidate,moveColor); //Makes a lambda-search of lambda-order n-1 to depth d-2 temp=lambda(n-1,d-2); unmakeMove(moveCandidate,moveColor); //If the lambda-search returns value<1, this is a lambda-move for the attacker if(temp>=1)return moveCandidate; } else { //Makes a defender's move makeMove(moveCandidate,moveColor); //Makes a lambda-search of lambda-order n-1 to depth d-1 temp=lambda(n-1,d-1); unmakeMove(moveCandidate,moveColor); //If the lambda-search returns value<1, this is a lambda-move for the defender if(temp<1)return moveCandidate; } //Try the next legal move moveCandidate=nextLegalMove(moveCandidate,moveColor); } //There are no lambda-moves return -12345; } //Finds the next empty point on the board static int nextLegalMove(int move, int moveColor) { for(int i=move+1;i<boardSize*boardSize;i++) { if(board[i]==0) { return i; } } //There are no more legal moves return -12345; } //Make the move static void makeMove(int move, int moveColor) { board[move]=moveColor; movesGenerated++; } //Unmake the move static void unmakeMove(int move, int moveColor) { board[move]=0; } //Evaluation function. //Returns 0 if (a) the defender has a string of winLength stones or more //Returns 1 if not (a) and the attacker has a string of winLength stones or more //Returns 0.5 otherwise //Note that eval() is always seen from the attacker's perspective //Therefore, in alphabeta() eval() is multiplied with moveColor (=1 for attacker //and -1 for defender) when eval() gets returned 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; } //Prints ascii diagrams of the board 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; // =========================== // // 4-IN-A-ROW ON 4x4 BOARD // // =========================== boardSize=4; //Board is initialized as empty (full of zeroes) board=new int[boardSize*boardSize]; //three attacker's stones in three corners board[0]=1; board[3]=1; board[15]=1; //board coordinates: //------------- // 12 13 14 15 // 8 9 10 11 // 4 5 6 7 // 0 1 2 3 //------------- //Board values are 0:empty (.), 1:attacker (#), and -1:defender (O) //Max search depth set to 13 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(" "); //shows alpha-beta for reference 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(" "); // ================ // // TIC-TAC-TOE // // ================ writeln(" "); writeln(" "); writeln(" "); winLength=3; boardSize=3; //board is initialized as empty (full of zeroes) board=new int[boardSize*boardSize]; //board coordinates: //---------- // 6 7 8 // 3 4 5 // 0 1 2 //---------- //Board values are 0:empty (.), 1:attacker (#), and -1:defender (O) //max search depth 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(" "); //shows alpha-beta for reference 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(" "); } }