#!/usr/bin/perl

#
# First try at an alpa-beta search algorithm
# like the one in AIMA, page 168-169.
#
#  - Jim M.
#

# ------------------------------

{
 package Node;
 sub new {
   my $class = shift;
   my ($value) = @_;
   return bless { value => $value }, $class;
 }
}

#
#        A
#    B        C         D
#  3 12 8   2  4  6    14  5  2
#
sub successors {
  my ($state) = @_;
  return newStates(qw(b c d))  if $state->{value} eq 'a';
  return newStates(3,12,8) if $state->{value} eq 'b';
  return newStates(2,4,6,) if $state->{value} eq 'c';
  return newStates(14,5,2) if $state->{value} eq 'd';
  return [];
}

sub newStates {
  my @values = @_;
  my $list = [];
  push @$list, Node->new($_) for @values;
  return $list;
}

sub isTerminal {
  my ($self) = shift;
  return 0 if $state->{value} =~ /[abc]/;
  return 1;
}

sub utilityValue {
  my ($self) = shift;
  return 0 + $state->{value};
}


my $inf = 100;  # higher than any terminal utilityValue.

sub MinMaxDecision {
  my ($state) = @_;
  return MaxValue($state);

# ---- don't have a way to return the branch right now; 
# ---- need to store node value and/or marker for correct path somehow.
#  my @children = @{successors($state)};
#  foreach my $child (@children){
#    return $child->{value} if $child->{value} == $value;
#  }

}

sub MaxValue {
  my ($state, $alpha, $beta) = @_;
  if ( isTerminal($state) ) { return utilityValue($state); }
  my $v = -$inf;
  my @children = @{successors($state)};
  foreach my $child (@children){
    $v = max( $v, MinValue($child,$alpha,$beta) );
    if ($v >= $beta){ return $v; }	# here's the pruning
    $alpha = max($alpha, $v);
  }
  return $v;
}

sub MinValue {
  my ($state, $alpha, $beta) = @_;
  if ( isTerminal($state) ) { return utilityValue($state); }
  my $v = $inf;
  my @children = @{successors($state)};
  foreach my $child (@children){
    $v = min( $v, MaxValue($child,$alpha,$beta) );
    if ($v <= $alpha){ return $v; }	# here's the pruning
    $beta = min($beta, $v);
  }
  return $v;
}

# Return maximum value in the list.
sub max {
  my $best = shift;
  while (@_){
    my $candidate = shift;
    $best = $candidate if $candidate > $best;
  }
  return $best;
}

# Return min value in the list.
sub min {
  my $best = shift;
  while (@_){
    my $candidate = shift;
    $best = $candidate if $candidate < $best;
  }
  return $best;
}


# -----------------------------

print "Creating root node. \n";
my $root   = Node->new("a");
print "Starting search. \n";
my $value = MinMaxDecision($root);
print "Finished search.  Result is '$value' \n";
