README
1NAME
2 Games::AlphaBeta - game-tree search with object oriented interface
3
4SYNOPSIS
5 package My::GamePos;
6 use base qw(Games::AlphaBeta::Position);
7
8 # initialise starting position
9 sub _init { ... }
10
11 # Methods required by Games::AlphaBeta
12 sub apply { ... }
13 sub endpos { ... } # optional
14 sub evaluate { ... }
15 sub findmoves { ... }
16
17 # Draw a position in the game (optional)
18 sub draw { ... }
19
20 package main;
21 my $pos = My::GamePos->new;
22 my $game = Games::AlphaBeta->new($pos);
23
24 while ($game->abmove) {
25 print draw($game->peek_pos);
26 }
27
28DESCRIPTION
29 Games::AlphaBeta provides a generic implementation of the AlphaBeta
30 game-tree search algorithm (also known as MiniMax search with alpha beta
31 pruning). This algorithm can be used to find the best move at a
32 particular position in any two-player, zero-sum game with perfect
33 information. Examples of such games include Chess, Othello, Connect4,
34 Go, Tic-Tac-Toe and many, many other boardgames.
35
36 Users must pass an object representing the initial state of the game as
37 the first argument to `new()'. This object must provide the following
38 methods: `copy()', `apply()', `endpos()', `evaluate()' and
39 `findmoves()'. This is explained more carefully in
40 Games::AlphaBeta::Position which is a base class you can use to
41 implement your position object.
42
43INHERITED METHODS
44 The following methods are inherited from Games::Sequential:
45
46 new
47 debug
48 peek_pos
49 peek_move
50 move
51 undo
52METHODS
53 _init [@list]
54 *Internal method.*
55
56 Initialize an AlphaBeta object.
57
58 ply [$value]
59 Return current default search depth and, if invoked with an
60 argument, set to new value.
61
62 abmove [$ply]
63 Perform the best move found after an AlphaBeta game-tree search to
64 depth $ply. If $ply is not specified, the default depth is used (see
65 `ply()'). The best move found is performed and a reference to the
66 resulting position is returned on success, and undef is returned on
67 failure.
68
69 Note that this function can take a long time if $ply is high,
70 particularly if the game in question has many possible moves at each
71 position.
72
73 If `debug()' is set, some basic debugging is printed as the search
74 progresses.
75
76 _alphabeta $pos $alpha $beta $ply
77 *Internal method.*
78
79BUGS
80 The valid range of values `evaluate()' can return is hardcoded to
81 -99_999 - +99_999 at the moment. Probably should provide methods to
82 get/set these.
83
84TODO
85 Implement the missing iterative deepening alphabeta routine.
86
87SEE ALSO
88 The author's website, describing this and other projects:
89 http://brautaset.org/projects/
90
91AUTHOR
92 Stig Brautaset, <stig@brautaset.org>
93
94COPYRIGHT AND LICENCE
95 Copyright (C) 2004 by Stig Brautaset
96
97 This library is free software; you can redistribute it and/or modify it
98 under the same terms as Perl itself, either Perl version 5.8.3 or, at
99 your option, any later version of Perl 5 you may have available.
100
101