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