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).