# $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 base qw(Exporter);
use vars qw($VERSION @EXPORT);

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

sub min_max($) {
    my($game)=@_;
    my($best_move) = undef;
    my(@moves) = $game->generate_moves();
    foreach (@moves) {
	my($new_game) = $game->apply_move($_);
	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) = $game->generate_moves();
    foreach (@moves) {
	my($new_game) = $game->apply_move($_);
	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;