NAME Games::AlphaBeta - game-tree search with object oriented interface SYNOPSIS package My::GamePos; use base qw(Games::AlphaBeta::Position); # initialise starting position sub _init { ... } # Methods required by Games::AlphaBeta sub apply { ... } sub endpos { ... } # optional sub evaluate { ... } sub findmoves { ... } # Draw a position in the game (optional) sub draw { ... } package main; my $pos = My::GamePos->new; my $game = Games::AlphaBeta->new($pos); 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 must pass an object representing the initial state of the game as the first argument to `new()'. This object must provide the following methods: `copy()', `apply()', `endpos()', `evaluate()' and `findmoves()'. This is explained more carefully in Games::AlphaBeta::Position which is a base class you can use to implement your position object. INHERITED METHODS The following methods are inherited from Games::Sequential: new debug peek_pos peek_move move undo METHODS _init [@list] *Internal method.* Initialize an 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 on success, and 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, describing this and other projects: http://brautaset.org/projects/ AUTHOR Stig Brautaset, 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.