NAME

Games::AlphaBeta - game-tree search with object oriented interface

SYNOPSIS

use Games::AlphaBeta;
my $game = Games::AlphaBeta->new( ... );

while ($game->abmove) {
    print draw($game->peek_pos);
}

DESCRIPTION

Games::AlphaBeta provides a generic implementation of the AlphaBeta game-tree search algorithm (also known as MiniMax search with alpha beta pruning). This algorithm can be used to find the best move at a particular position in any two-player, zero-sum game with perfect information. Examples of such games include Chess, Othello, Connect4, Go, Tic-Tac-Toe and many, many other boardgames.

Users will have to provide references to four callback functions specific to the game they are implementing. These are:

move($position, $move)

Create $newpos as copy of $position and apply $move to it. Return $newpos.

findmoves($position>

Returns a list of all legal moves the current player can perform at the current $position. Note that if a pass move is legal in the game (i.e. as it is in Othello) you must allow for this function to produce a null move. A null move does nothing but pass the turn to the next player.

endofgame($position)

Returns true if $position is the end of the game, false otherwise. Remember to account for a draw in addition to either of the players winning.

evaluate($position)

Returns the calculated fitness value of the current position for the current player. The value must be in the range -99_999 - 99_999 (see BUGS).

METHODS

Most of this module's methods are inherited from Games::Sequential; be sure to check its documentation.

Users must not modify the referred-to values of references returned by any of the below methods, except, of course, indirectly using the supplied callbacks.

Games::AlphaBeta provides these new methods:

_init [@list]

Internal method.

Initialize a AlphaBeta object.

ply [$value]

Return current default search depth and, if invoked with an argument, set to new value.

abmove [$ply]

Perform the best move found after an AlphaBeta game-tree search to depth $ply. If $ply is not specified, the default depth is used (see ply()). The best move found is performed and a reference to the resulting position is returned. undef is returned on failure.

Note that this function can take a long time if $ply is high, particularly if the game in question has many possible moves at each position.

If debug() is set, some basic debugging is printed as the search progresses.

_alphabeta $pos $alpha $beta $ply

Internal method.

BUGS

The valid range of values evaluate can return is hardcoded to -99_999 - +99_999 at the moment. Probably should provide methods to get/set these.

TODO

Implement the missing iterative deepening alphabeta routine.

SEE ALSO

The author's website for this module: http://brautaset.org/projects/#games::alphabeta

AUTHOR

Stig Brautaset, <stig@brautaset.org>

COPYRIGHT AND LICENCE

Copyright (C) 2004 by Stig Brautaset

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.3 or, at your option, any later version of Perl 5 you may have available.