# $Id: MinMax.pm,v 1.1.1.1 2008/10/12 04:05:34 alamos Exp $
# The state is in an array
package TicTacToe::MinMax;
use strict;
use TicTacToe::Board;

use base qw(Exporter);
use vars qw(@ISA $VERSION @EXPORT);

$VERSION='1.0';
@EXPORT = qw(&min_max &alpha_beta);

sub min_max {
    my($game)=@_;
    my($best_move) = undef;
    my(@moves) = &generate_moves($game);
    foreach (@moves) {
	my($new_game) = &apply_move($game,$_);
	unless(defined($new_game->{result})) {
	    my($move) = &min_max($new_game);
	    $_->{value} = -$move->{value};
	}
	if(!defined($best_move) || $_->{value} > $best_move->{value}) {
	    $best_move = $_;
	}
    }
    return $best_move;
}

# Remember:
# Alpha is the guaranteed score for max.
# Beta  is the maximum score max can hope for.
sub alpha_beta {
    my($game,$alpha,$beta)=@_;
    my($best_move) = undef;
    my(@moves) = &generate_moves($game);
    foreach (@moves) {
	my($new_game) = &apply_move($game,$_);
	unless(defined($new_game->{result})) {
	    my($move) = &alpha_beta($new_game, -$beta, -$alpha);
	    $_->{value} = -$move->{value};
	}
	if(!defined($best_move) || $_->{value} > $best_move->{value}) {
	    $best_move = $_;
	    $alpha = $best_move->{value};
	    if($alpha > $beta) {
		last;
	    }
	}
    }
    return $best_move;
}

1;