Very fun! I translated your code into nearly-pseudocode for anyone who cares.

use strict;
use warnings FATAL => 'all';
use vars qw(@Game_Board @Available_Moves $Turn);

play_game();

sub eqany { $_[0] eq $_ && return 1 for @_[1 .. $#_]; return   }
sub eqall { $_[0] ne $_ && return   for @_[1 .. $#_]; return 1 }

sub play_game {
    # Reset the game before playing.
    local $Turn = 0;
    # The first element is never used
    local @Game_Board = (undef, ('.') x 9);
    local @Available_Moves = 1 .. 9;

    while ( @Available_Moves ) {
        switch_players();
        my $marker = player_marker();

        make_random_move( $marker );
        my $winning_move = find_winning_move( $marker );

        print rendered_board( $winning_move );

        return if $winning_move;

        pause_a_moment();
    }
}

sub pause_a_moment { select undef, undef, undef, .1 }

sub rendered_board {
    my $winning_move = shift;
    my $board = "\ec";
    for my $position ( 1 .. $#Game_Board ) {
        # Highlight winning positions
        if ($winning_move and
            eqany( $position, @$winning_move) ) {
            # invert highlight
            $board .= "\e[7m";

            $board .= $Game_Board[$position];

            # Remove highlight
            $board .= "\e[m";
        } else {
            $board .= $Game_Board[$position];
        }

        # Spaces until the end of the line
        $board .= $position % 3
            ? ' '
            : "\n";
    }

    return $board;
}

sub switch_players { $Turn = not $Turn }

sub player_marker { $Turn ? 'X' : 'O' }

sub find_winning_move {
    my $marker = shift;
    for my $candidate_win ( [ 1, 2, 3 ],
                            [ 4, 5, 6 ],
                            [ 7, 8, 9 ],
                            [ 1, 4, 7 ],
                            [ 2, 5, 8 ],
                            [ 3, 6, 9 ],
                            [ 1, 5, 9 ],
                            [ 3, 5, 7 ] ) {
        if ( eqall( $marker,
                    @Game_Board[ @$candidate_win ] ) ) {
            return $candidate_win;
        }
    }
}

sub make_random_move {
    my $marker = shift;
    $Game_Board[ choose_random_move() ] = $marker;
}

sub choose_random_move {
    shuffle( \ @Available_Moves );
    pop @Available_Moves;
}

sub shuffle {
    # copied from perldoc
    my $array = shift;
    my $i;
    for ($i = @$array; --$i; ) {
        my $j = int rand ($i+1);
        @$array[$i,$j] = @$array[$j,$i];
    }
}
[download]

It has a random solution each time. The thing really does play tic-tac-toe. Check out my expanded version.