#!/usr/bin/perl

use TicTacToe;

# Usage:
#    To minimize the next move:
#        ($move,$score) = ab_minimax($position,$depth)
#    You provide a game position object, and a maxmimum depth
#    (number of moves) to be expanded before cutting off the
#    move generation and evaluating the resulting position.

sub ab_minimax {
    my ( $position, $depth, $alpha, $beta ) = @_;

    defined ($alpha) or $alpha = -$position->best_rating;
    defined ($beta)  or $beta  =  $position->best_rating;

    # Have we gone as far as permitted or as far as possible?
    if ( $depth-- and defined($position->prepare_moves) ) {
        # no - keep trying additional moves from $position
        my $move;
        my $best_score = -$position->best_rating;
        my $best_move_seq;
        my $alpha_cur = $alpha;

        while ( defined($move = $position->next_move) ) {
            # Evaluate the next move.
            my ( $this_move_seq, $this_score ) =
                ab_minimax( $position->make_move($move),
                                $depth, -$beta, -$alpha_cur );
            # Opponent's score is opposite meaning from ours.
            $this_score = -$this_score;
            if ( $this_score > $best_score ) {
                $best_score = $this_score;
                $alpha_cur = $best_score if $best_score > $alpha_cur;
                $best_move_seq = $this_move_seq;
                unshift ( @$best_move_seq, $move );

                # Here is the alpha-beta pruning.
                #    - quit when someone else is ahead!
                last if $best_score >= $beta;
            }
        }

        # Return the best one we found.
        return ( $best_move_seq, $best_score );

    } else {
        # Yes - evaluate current position, no move to be taken.
        return ( [ $position ], -$position->evaluate );
    }
}

my $game = tic_tac_toe->new( );

my ( $moves, $score ) = ab_minimax( $game, 2 );
my $my_move = $moves->[0];
print "I move: $my_move\n";