#!/usr/bin/perl

use TicTacToe;        # defined earlier in this chapter

# exhaustive analysis of tic-tac-toe using a transpose table
sub ttt_exhaustive_table {

    my $game = tic_tac_toe->new( );

    my $answer = ttt_analyze_table( $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";
    }
}

@cache = ( );

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

    # Compute id - the index for the current position.
    #    Treat the board as a 9-digit base 3 number.  Each square

    #    contains 0 if it is unoccupied, 1 or 2 if it has been
    #    taken by one of the players.
    if( ! defined $move ) {
        # Empty board.
        $game->{id} = 0;
    } else {
        # A move is being tested, add its value to this id of
        # the starting position.
        my $id = $game->{id} + ($game->{turn}+1)*(3**$move);
        if( defined( my $score = $cache[$id] ) ) {
            # That resulting position was previously analyzed.
            return -1 if $score < 0;
            return 0;
        }
        my $prevgame = $game;
        # A new position - analyze it.
        $game = $game->make_move( $move );
        $game->{id} = $id;
    }

    unless ( defined $game->prepare_moves ) {
        # No moves possible.  Either the other player just won,
        # or else it is a draw.
        my $score = $game->evaluate;
        $cache[$game->{id}] = $score;
        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_table( $game, $move );

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

    $cache[$game->{id}] = $best_score;
    return $best_score;
}

&ttt_exhaustive_table();