#!/usr/bin/perl

# tic-tac-toe game package
package tic_tac_toe;

$empty = ' ';
@move = ( 'X', 'O' );
# Map X and O to 0 and 1.
%move = ( 0=>0, 1=>1, 'X'=>0, 'O'=>1 );

# new( turn, board )
#
# To create a new tic-tac-toe game:
#    tic_tac_toe->new( )
#

# This routine is also used internally to create the position
# that will occur after a move, switching whose turn it is and
# adding a move to the board:
#    $board = ... adjust current board for the selected move
#    tic_tac_toe->new( 1 - $self->{turn}, $board )
sub new {
    my ( $pkg, $turn, $board ) = @_;
    $turn = 0 unless defined $turn;
    $turn = $move{$turn};
    $board = [ ($empty) x 9 ] unless defined $board;
    my $self = { turn => $turn, board => $board };
    bless $self, $pkg;
    $self->evaluate_score;

    return $self;
}

# We cache the score for a position, calculating it once when
# the position is first created.  Give the value from the
# viewpoint of the player who just moved.
#
# scoring:
#       100 win for current player (-100 for opponent)
#        10 for each unblocked 2-in-a-row (-10 for opponent)
#         1 for each unblocked 1-in-a-row (-1 for opponent)
#         0 for each blocked row
sub evaluate_score {
    my $self  = shift;
    my $me    = $move[1 - $self->{turn}];
    my $him   = $move[$self->{turn}];
    my $board = $self->{board};
    my $score = 0;

    # Scan all possible lines.
    foreach $line (
		   [0,1,2], [3,4,5], [6,7,8],   # rows
		   [0,3,6], [1,4,7], [2,5,8],   # columns
		   [0,4,8], [2,4,6] )           # diagonals
    {
	my ( $my, $his );
	foreach (@$line) {
	    my $owner = $board->[$_];

	    ++$my if $owner eq $me;
	    ++$his if $owner eq $him;
	}

	# No score if line is blocked.
	next if $my && $his;

	# Lost.
	return $self->{score} = -100 if $his == 3;

	# Win can't really happen, opponent just moved.
	return $self->{score} = 100 if $my == 3;

	# Count 10 for 2 in line, 1 for 1 in line.
	$score +=
	    ( -10, -1, 0, 1, 10 )[ 2 + $my - $his ];
    }

    return $self->{score} = $score;
}

# Prepare to generate all possible moves from this position.
sub prepare_moves {
    my $self = shift;

    # None possible if game is already won.
    return undef if abs($self->{score}) == 100;

    # Check whether there are any possible moves:
    $self->{next_move} = -1;
    return undef unless defined( $self->next_move );

    # There are.  Next time we'll return the first one.
    return $self->{next_move} = -1;
}

# Determine the next move possible from the current position.
# Return undef when there are no more moves possible.
sub next_move {
    my $self = shift;

    # Continue returning undef if we've already finished.
    return undef unless defined $self->{next_move};

    # Check each square from where we last left off, skipping
    # squares that are already occupied.
    do {
	++$self->{next_move}
    } while $self->{next_move} <= 8
	&& $self->{board}[$self->{next_move}] ne $empty;

    $self->{next_move} = undef if $self->{next_move} == 9;
    return $self->{next_move};
}

# Create the new position that results from making a move.
sub make_move {
    my $self = shift;
    my $move = shift;

    # Copy the current board, changing only the square for the move.
    my $myturn = $self->{turn};
    my $newboard = [ @{$self->{board}} ];
    $newboard->[$move] = $move[$myturn];

    return tic_tac_toe->new(1 - $myturn, $newboard);
}

# Get the cached evaluation of this position.
sub evaluate {
    my $self = shift;

    return $self->{score};
}

# Display the position.
sub description {
    my $self = shift;
    my $board = $self->{board};
    my $desc = "@$board[0..2]\n@$board[3..5]\n@$board[6..8]\n";
    return $desc;
}

sub best_rating {
    return 101;
}

1;
