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

  }
}