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

    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);
    }

package Games::AlphaBeta;
use base qw(Games::Sequential);

use Carp;
use 5.006001;

use strict;
use warnings;


our $VERSION = '0.4.7';

sub _init {
    my $self = shift;
    my %config = (
        # Runtime variables
        ply         => 2,       # default search depth
        alpha       => -100_000,
        beta        => 100_000,
    );

    @$self{keys %config} = values %config;
    $self->SUPER::_init(@_);

    my $pos = $self->peek_pos;
    croak "no endpos() method defined" unless $pos->can("endpos");
    croak "no evaluate() method defined" unless $pos->can("evaluate");
    croak "no findmoves() method defined" unless $pos->can("findmoves");

    return $self;
}

sub ply {
    my $self = shift;
    my $prev = $self->{ply};
    $self->{ply} = shift if @_;
    return $prev;
}

sub abmove {
    my $self = shift;
    my $ply;

    if (@_) {
        $ply = shift;
        print "Explicit ply $ply overrides default ($self->{ply})\n" if $self->{debug};
    }
    else {
        $ply = $self->{ply};
    }

    my (@moves, $bestmove);
    my $bestmove_valid = 0;
    my $pos = $self->peek_pos;

    return if $pos->endpos;
    return unless @moves = $pos->findmoves;

    my $alpha = $self->{alpha};
    my $beta = $self->{beta};

    print "Searching to depth $ply\n" if $self->{debug};
    $self->{found_end} = $self->{count} = 0;
    for my $move (@moves) {
        my ($npos, $sc);
        $npos = $pos->copy;
        $npos->apply($move) or croak "apply() failed";
        $sc = -$self->_alphabeta($npos, -$beta, -$alpha, $ply - 1);

        print "ab val: $sc" if $self->{debug};
        if ($sc > $alpha) {
            print " > $alpha new best move" if $self->{debug};
            $bestmove_valid = 1;
            $bestmove = $move;
            $alpha = $sc;
        }
        print "\n" if $self->{debug};
    }
    print "$self->{count} visited\n" if $self->{debug};

    return unless $bestmove_valid;
    return $self->move($bestmove);
}

sub _alphabeta {
    my ($self, $pos, $alpha, $beta, $ply) = @_;
    my @moves;

    # Keep count of the number of positions we've seen
    $self->{count}++;

    # When using iterative deepening we can optimise for the case
    # when we find an end position at every branch (for example,
    # near the end of the game)
    #
    if ($pos->endpos) {
        $self->{found_end}++;
        return $pos->evaluate;
    }
    elsif ($ply <= 0) {
        return $pos->evaluate;
    }

    unless (@moves = $pos->findmoves) {
        $self->{found_end}++;
        return $pos->evaluate;
    }

    for my $move (@moves) {
        my ($npos, $sc);
        $npos = $pos->copy or croak "$pos->copy() failed";
        $npos->apply($move) or croak "$pos->apply() failed";

        $sc = -$self->_alphabeta($npos, -$beta, -$alpha, $ply - 1);

        $alpha = $sc if $sc > $alpha;
        last unless $alpha < $beta;
    }

    return $alpha;
}


1;  # ensure using this module works
__END__

# vim: shiftwidth=4 tabstop=4 softtabstop=4 expandtab