#!/usr/bin/perl

use TicTacToe;        # defined earlier in this chapter

# exhaustive analysis of tic-tac-toe
sub ttt_exhaustive {

    my $game = tic_tac_toe->new( );

    my $answer = ttt_analyze( $game );
    if ( $answer > 0 ) {
        print "Player 1 has a winning strategy\n";
    } elsif ( $answer < 0 ) {
        print "Player 2 has a winning strategy\n";
    } else {
        print "Draw\n";
    }
}

# $answer = ttt_analyze( $game )
#    Determine whether the other player has won.  If not,
#    try all possible moves (from $avail) for this player.
sub ttt_analyze {
    my $game = shift;

    unless ( defined $game->prepare_moves ) {
        # No moves possible.  Either the other player just won,
        # or else it is a draw.
        my $score = $game->evaluate;
        return -1 if $score < 0;
        return 0;
    }

    # Find result of all possible moves.
    my $best_score = -1;

    while ( defined( $move = $game->next_move ) ) {
        # Make the move negating the score
        #   - what's good for the opponent is bad for us.
        my $this_score = - ttt_analyze( $game->make_move( $move ) );

        # evaluate
        $best_score = $this_score if $this_score > $best_score;
    }

    return $best_score;
}

&ttt_exhaustive;