Lambda-search Java-code (version 2.0)

Java-code including Go-moku implementation. Before reading the Java-code, please read the overview given below. About this code please note as well that it uses very crude alpha-beta and does not implement so-called relevancy zones (cf. my paper on lambda-search). In games like Go-moku, Go, Hex etc. the use of such zones speeds up the search significantly, but for the sake of simplicity relevancy zones are not used here.

Brief overview of the code (small version)

Note: an arrow from method A to method B indicates that B calls/uses A.

lambda()
The method lamda() is called with two arguments, n and d, restricting the l-search to at most l-order n, and restricting the search depth to at most d plies. Lamda() must be called with d being an uneven number, and lamda() always assumes that the attacker moves first. Lambda() tries l-trees of orders 0, 1, 2, ..., up to n. If lambda() returns value 1, the attacker's goal can be obtained; if it returns value 0, it cannot be obtained at l-order n and search depth d. Lambda() calls the method alphabeta(), searching out the l-tree.

alphabeta()
This is the "search engine" for searching the l-tree. However, the program is written in a modular way so that alphabeta() could be easily replaced with something else; e.g. proof-number search. Alphabeta calls itself recursively, with the same l-order n, and depth d – 1. If a node has no siblings, the method returns value 1 (=succes for the attacker) if the defender is to move, and 0 (= success for the defender) if the attacker is to move. Alphabeta() calls the method eval() to see if the goal has been acheived, and also calls the method nextLambdaMove() providing the next l-child (successor-node).

nextLambdaMove()
Returns the next l-move for the player to move. A move x is a l-move if the following is true after the move x has been made: if (a) x is an attacker's move and a l-search of l-order n – 1 and depth d – 2 has value 1, or if (b) x is a defender's move and a l-search of l-order n – 1 and depth d – 1 has value < 1. All legal moves are tried out as l-move candidates, the legal moves being provided by the method nextLegalMove().

nextLegalMove()
Returns the next legal move in the given position. The code in nextLegalMove() is game-specific.

eval()
Evaluates the current board position, the evaluation being = 1 if the attacker's goal is obtained, 0 if the attacker's goal cannot be obtained (for instance in chess if the attacker's own king gets captured), and 0.5 otherwise. The code in eval() is game-specific.

 

Note generally...
...that the variable moveColor attains value 1 if the attacker is to move, and –1 if the defender is to move. Note also that eval() is always seen from the attacker's perspective (and therefore sometimes muliplied with moveColor in alphabeta()). Note finally that if alphabeta() is called with n = –12345 ("missing value"), a normal alphabeta-search without use of l-trees is carried out.

 

The large version of the Java-code
This version adds some more functionality for, among other things, printing out diagrams with indication of current variation. In addition, the large version is able to distinguish three values of a l-tree, 1, 0.5 or 0. Value 1 means that the goal can be acheived (proof). Value 0.5 means that it is unknown (at the current search depth d) whether or not the goal can be achieved at l-order n. Value 0 means that the goal cannot be acheived at l-order n (disproof). This functionality adds some information regarding disproofs: the algorithm now knows whether a failed l-search ran into the depth limit or not. If not, the goal is disproved at l-order n, meaning that there would be no point in searching this l-tree any deeper, and such knowledge could be used to terminate an iterative-deepening alphabeta-search. (Note: such a disproof does not, of course, entail that the goal could not be acheived in a l-tree of order n + 1 or higher – it only has to do with terminating iterative-deepening alpha-beta as early as possible).