Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

A simple game AI that learns

by Falkkin (Chaplain)
on Jan 14, 2001 at 01:31 UTC ( #51644=sourcecode: print w/ replies, xml ) Need Help??

Category: Fun Stuff
Author/Contact Info Colin McMillen
Description: A set of modules that implement a very simple gaming AI. The AI players know nothing about the actual game that is being played; they merely take in a list of valid moves and provide functions to call at the end of a given game. The AI remembers what moves it's made and the results, and learns how to play the game better, even though it doesn't know any of the rules.

I've tested this code using tic-tac-toe; after about 35,000 runs of the Defensive player vs. the Random player, the Defensive player no longer loses. I ran ~2,000,000 games and it's not lost once. Since this is basically a brute-force AI method, it'll probably be incredibly inefficient for complex games (although I've not tested it with any other games yet.)

The code is optimized for speed, not readability... it doesn't pass -w because of hash accesses to undefined values in Memory.pm. I'm pondering submitting this to CPAN, after cleaning up some stuff and writing the documentation as pod, so any advice or comments would be much appreciated.

I still have much to try with these modules, such as:
- Different games (suggestions, anyone?)
- Will it learn faster if it plays against a better player?
- I'd also like to write a CGI script that allows the AI to play human opponents online.

### Memory.pm

package Memory;

# A class that implements a simple memory. Memory is stored by keying
# "states" to "priorities"; a higher priority indicates that the
# corresponding state is a better state than those of lower priority.

use strict;
use integer;

# Constructor
sub new { 
  my $class = shift;
  my $self = {};
  bless $self, $class;
  return $self;
}

# Loads the memory from the given filename.
sub load {
  my ($self, $filename) = @_;
  open(MEMORY_FILE, $filename) || warn "could not load memory from $fi
+lename: $!";
  my @memory = <MEMORY_FILE>;
  close(MEMORY_FILE);
  for (my $i = 0; $i < @memory; $i++) {
    chomp $memory[$i];
  }
  my %memory = @memory;
  foreach my $key (keys %memory) {
    $self->set($key, $memory{$key});
  }
}

# Dumps the current state of memory to a file.
sub save {
  my ($self, $filename) = @_;
  open(MEMORY_FILE, ">$filename") || warn "could not save memory to $f
+ilename: $!";
  foreach my $key (sort keys %$self) {
    my $value = $self->get($key);
    print MEMORY_FILE "$key\n$value\n";
  }
}

# Takes in a string representing a state, and returns
# the priority of that state.
sub get {
  return $_[0]{$_[1]};
}

# Takes in a string representing a state, and a numerical priority for
# the state. Sets the priority of that state accordingly.
sub set {
  $_[0]{$_[1]} = $_[2];
}

# Takes in a string representing a state, and an amount to modify the
# priority of that state by. Modifies the priority by the given amount
+.
sub modify {
  my ($self, $state, $priority) = @_;
  $self->{$state} = $self->get($state) + $priority;
}

# Takes in a reference to a list of all the valid states that can
# currently occur, and returns the state with the highest priority. If
# more than one state shares the highest priority, it randomly picks
# one of the best states.
sub get_best_state {
  my ($self, $states) = @_;

  # Find the highest priority of any of the states.
  my $highest_priority = -2**30;
  foreach (@$states) {
    if ($self->get($_) > $highest_priority) {
      $highest_priority = $self->get($_);
    }
  }

  # Find all of the states at the highest priority.
  my @best_states;
  foreach my $state (@$states) {
    my $priority = $self->get($state);
    if ($priority == $highest_priority) {
      push @best_states, $state;
    }
  }

  # Randomly choose a state out of our list of best states, and return
+ it.
  return $best_states[int(rand(@best_states))];
}

1;

### Random.pm

package Random;

# A game-player AI implementing a player who merely makes a
# random move out of a list of available moves.
#
# Nothing very exciting is going on here.

use strict;
use integer;

sub new {
  my $class = shift;
  my $self = {};
  bless $self, $class;
  return $self;
}

sub make_move {
  my ($self, $valid_states) = @_;
  my @valid_states = keys %$valid_states;
  my $move = $valid_states[int(rand(@valid_states))];
  return $$valid_states{$move};
}

sub win {}
sub lose {}
sub tie {}

1;

### Defensive.pm

package Defensive;

# A class implementing a "defensive" AI game player. The defensive
# player considers all states that have led to losses as "bad" and
# makes no preference between a win and a tie. The defensive player is
# the only type of player that can evolve to become an unbeatable
# tic-tac-toe player.
#
# Although I've only tested this player in the game of tic-tac-toe,
# it knows nothing about the rules of tic-tac-toe.  At any
# given time when it has to make a move, it just gets a list of the
# valid states it can put the board into, and chooses the "best" state
# out of memory. At the end of a game, it receives the result of the
# game (win, loss, or tie) and modifies its memory to adjust for the
# result.
#
# Adapting this player to a different game should be incredibly easy;
# the game just has to send in a list of valid states and call the
# appropriate win(), lose(), or tie() method at the end of the game.

use Memory;

@Defensive::ISA = ("Memory");

# Constructor
sub new {
  my $class = shift;
  my $self = Memory::new($class);
  return $self;
}

# Do nothing if the result of a game was a win or a tie, except clear
# the "states" entry.
sub win { delete $_[0]->{"states"}; }
sub tie { delete $_[0]->{"states"}; }

# If we lost, decrease the priorities of all states that we put the
# game into. States which occurred toward the end of the game are
# weighted as "more bad" than states which occurred at the
# beginning.
sub lose {
  my $self = shift;
  my @states = @{$self->{"states"}};
  my $score = -32;
  while (@states) {
    my $state = pop(@states);
    $self->modify($state, $score);
    $score /= 2;
  }
  delete $self->{"states"};
}

# Uses Memory.pm's get_best_state() method to find and return the best
# move out of those provided in the @$valid_states array.
#
# Keeps track of the moves it's made during this game, such that it
# can modify their values accordingly at the end of the game.
sub make_move {
  my ($self, $valid_states) = @_;
  my @valid_states = (keys %$valid_states);
  my $best_state = $self->get_best_state(\@valid_states);
  push @{$self->{"states"}}, $best_state;
  return $valid_states->{$best_state};
}

1;

### TicTacToe.pm

package TicTacToe;

use integer;
use strict;

# A class that implements a game of tic-tac-toe.
#
# The board is indexed as follows:
# 0 1 2
# 3 4 5
# 6 7 8
#
# Each tic-tac-toe state is represented as a nine-character string
# where each character in the string corresponds to the given location
# on the board. The character is a "0" if that square is empty, "1" is
# that square has a mark by the current player, and "2" is that square
# has a mark y the current player's opponent.

# Constructor.
sub new {
  my $class = shift;
  my $self = { board             => [0, 0, 0, 0, 0, 0, 0, 0, 0],
           moves_made        => 0,
           player            => int(rand(2) + 1),
           winning_positions => [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 
+3, 6], 
                     [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]] };
  bless $self, $class;
  return $self;
}

# Plays an entire game of tic-tac-toe. Takes in references to two
# "player" objects; it alternates between these objects, asking each
# for a move, until the game is over. At the end of the game, it
# notifies each player of the result of the game, and returns the
# result. 0 is a tie, 1 and 2 are wins by player 1 and player 2,
# respectively.

sub play {
  my ($self, $p1, $p2) = @_;
  my $result = undef;

  until (defined $result) {
    if (current_player($self) == 1) {
      $result = $self->request_move($p1);
    } else {
      $result = $self->request_move($p2);
    }
    $self->switch_player();
  }
  if ($result == 1) {
    $p1->win();
    $p2->lose();
  } elsif ($result == 2) {
    $p2->win();
    $p1->lose();
  } else {
    $p1->tie();
    $p2->tie();
  }
  return $result;
}

# Takes in a reference to a player object, and requests (through the
# player's make_make() method) that the player make a move.
#
# BUG: We send the player a list of the valid moves (actually, a list
# of the valid states that the player can currently put the board
# into), but never check to see whether the player actually made a
# valid move. It's assumed that we have honest (and
# correctly-programmed) players, which is probably a bad assumption to
# make. 
sub request_move {
  my ($self, $ai) = @_;
  my $move = $ai->make_move($self->valid_states());
  $$self{"board"}->[$move] = $self->current_player();
  $self->{"moves_made"}++;
  return $self->check_for_win();
}

# Checks to see if the game has been won.
# Returns 1 or 2 if player 1 or 2 has won, undef otherwise.
#
# This sub is horribly non-optimized, but it works.
sub check_for_win {
  my $self = shift;
  return undef if ($self->{moves_made} < 3);
  my $player = $self->current_player();
  my $win = 0;
  my @winning_positions = @{$self->{"winning_positions"}};
  for (my $i = 0; $win == 0 && $i < scalar(@winning_positions); $i++) 
+{
    $win = 1;
    my @needed_moves = @{$winning_positions[$i]};
    foreach my $move (@needed_moves) {
      unless ($self->{"board"}->[$move] == $player) {
    $win = 0;
      }
    }
  }

  if ($win) {
    return $player;
  } elsif ($self->{"moves_made"} == 9) { 
    return 0; 
  } else {
    return undef;
  }
}

# Returns a list of the currently-valid moves.
sub valid_moves {
  my $self = shift;
  my @valid_moves;
  for (my $i = 0; $i < 9; $i++) {
    if ($self->{"board"}->[$i] == 0) {
      push(@valid_moves, $i);
    }
  }
  return @valid_moves;
}

# Returns the current player (1 or 2).
sub current_player {
  my $self = shift;
  return $$self{"player"};
}

# Switches the current player.
sub switch_player {
  my $self = shift;
  if ($$self{"player"} == 1) {
    $$self{"player"} = 2;
  } else {
    $$self{"player"} = 1;
  }
}

# Returns the board.
sub board { 
  my $self = shift;
  return @{$self->{"board"}};
}

# Returns a string representation of the current state of the board.
# The nth character in the string corresponds to square n of the
# board, where n is an integer from 0 to 8.The current player is
# always denoted as "1", its opponent "2", and an empty space "0".
sub current_state {
  my $self = shift;
  my $current_state = join("", board($self));

  # If the current player is 2, we need to swap the 1's and 2's in the
+ board state.
  if (current_player($self) == 2) {
    $current_state =~ tr/12/21/;
  }
  return $current_state;
}

# Returns a reference to a hash of the states that the current player
# can legally put the board into. The keys of the hash are the states
# themselves; the values are the moves required to put the board into
# each state.
sub valid_states {
  my $self = shift;
  my $current_state = current_state($self);
  my %valid_states;

  my @valid_moves = $self->valid_moves();

  foreach my $move (@valid_moves) {
    my $valid_state = $current_state;
    substr($valid_state, $move, 1) = 1;
    $valid_states{$valid_state} = $move;
  }
  return \%valid_states;
}

1;

### main.pl

#!/usr/bin/perl

# Driver program for tic-tac-toe games. Plays a (basically) infinite
# number of games, dying gracefully when interrupted. Prints out the
# results so far, at every 100 games. Also handles loading and saving
# of player memories.

use strict;
use integer;

use TicTacToe;
use Defensive;
use Random;

$SIG{INT} = \&sig_handler;


my @record = (0, 0, 0);
my $p1 = Defensive->new();
my $p2 = Random->new();
$p1->load("player-1-memory.txt");

my $dead = 0;
my $num_games = 0;

until ($dead) {
  $num_games++;
  my $ttt = TicTacToe->new();
  my $result = $ttt->play($p1, $p2);
  $record[$result]++;
  if ($num_games % 100 == 0) {
    print "($num_games) $record[1]/$record[2]/$record[0]\n";
  }
}

$p1->save("player-1-memory.txt");
print "Player 1 memory saved OK.\n";

sub sig_handler {
  print "\nCaught INT signal... shutting down.\n";
  $dead = 1;
}

Comment on A simple game AI that learns
Download Code
Re: A simple game AI that learns
by Fastolfe (Vicar) on Jan 14, 2001 at 04:32 UTC
    Interesting stuff.. Have you considered using Storable for saving state information?
      I'm currently using Data::Dumper to simply write the contents of the memory to disk and to load them back in again when the program is restarted -- is there any specific reason I should be using Storable instead? I read the pod for it and it looks like it basically does the same thing I'm doing with Data::Dumper.
        Data::Dumper actually expands the data structure into human- and perl-readable form, which requires re-parsing it when you want to use it again. Storable works more like serialization in Java, in that a portable binary representation of the Perl variable is made, preserving things like blessed references and the like. I suspect Storable is going to be a little more efficient if all you want to do is store and retrieve the Perl structure.
Re: A simple game AI that learns
by Blue (Hermit) on Jan 15, 2001 at 18:47 UTC
    Very cool, I'm looking forward to playing around with this.

    Since you mentioned tic-tac-toe, I've worked along these same set of assumptions (know what's a legal move, know if & how the game ends) for both (very simple) neural nets and also genetic algorithms. Both a lot of fun, you may want to look into them. I must admit that the math for the NN is very slow going when it's not beyond me, but GAs were fun and cool.

    Two twists on it that I tried I think may of helped, or at least kept me more interested. For games like tic-tac-toe where board orientation is unimportant I developed a routine to orient the board before evaluating such that multiple boards that were just rotations or flips of each other went through the same game logic.

    In addition, I started with many randomly weighted oppenents, and then let them battle each other. This slowly gave a "better opponent" as you mention, which I think allowed a quicker training. It was needful for the GAs, but just plain fun for the NNs.

    There are a lot or resources out there on the web. My old bookmark list (that had my favs) got wiped a while ago so I can't rememebr specific ones, but just search around.

    Have fun.

    =Blue
    ...you might be eaten by a grue...

Re: A simple game AI that learns (Connect Four)
by chipmunk (Parson) on Jan 16, 2001 at 00:55 UTC
    I've created a ConnectFour.pm (based on TicTacToe.pm) so that your AI can learn to play Connect Four.

    I found that the Defensive strategy is not effective for Connect Four; it barely managed to beat Random more times than it lost. So, I created an Offensive.pm, which gives priority to winning states and ignores losses and ties (the opposite of Defensive.pm). That strategy is doing much better; after about 15,000 games it beat Random more than twice as often as it lost to Random, although 2/3 of the games were ties. I figure it's still got a lot of learning to do.

    I then created an OffenseDefense.pm, which combines the behaviors of Offensive and Defensive; wins get rated up, losses get rated down. This strategy so far has produced essentially identical results to Offensive.pm; it remains to be seen whether rating losses in addition to wins will give any advantage.

    I also include below mainc4.pl, which is really just main.pl using the new modules. However, I renamed the memory file, because 'player-1-memory.txt' really is not descriptive. :)

    ### ConnectFour.pm package ConnectFour; use integer; use strict; # A class that implements a game of Connect Four # # A board has 7 columns and 6 rows. When indexed by X and Y position, # X is the primary index. When indexed by a single number, position N # corresponds to X = N%width, Y = N/width. # Each Connect Four state is represented as a 42-character string # where each character in the string corresponds to position N on the # board. The character is a "0" if that square is empty, "1" if that # square has a mark by the current player, and "2" if that square has # a mark by the current player's opponent. # Constructor. sub new { my $class = shift; my $width = 7; my $height = 6; my $self = { width => $width, height => $height, board => [ map [(0) x $height], 1 .. $width], top => [ (0) x $width ], moves_made => 0, player => int(rand(2) + 1), }; bless $self, $class; return $self; } # Plays an entire game of Connect Four. Takes in references to two # "player" objects; it alternates between these objects, asking each # for a move, until the game is over. At the end of the game, it # notifies each player of the result of the game, and returns the # result. 0 is a tie, 1 and 2 are wins by player 1 and player 2, # respectively. sub play { my ($self, $p1, $p2) = @_; my $result = undef; until (defined $result) { if (current_player($self) == 1) { $result = $self->request_move($p1); } else { $result = $self->request_move($p2); } $self->switch_player(); } if ($result == 1) { $p1->win(); $p2->lose(); } elsif ($result == 2) { $p2->win(); $p1->lose(); } else { $p1->tie(); $p2->tie(); } return $result; } # Takes in a reference to a player object, and requests (through the # player's make_make() method) that the player make a move. # # BUG: We send the player a list of the valid moves (actually, a list # of the valid states that the player can currently put the board # into), but never check to see whether the player actually made a # valid move. It's assumed that we have honest (and # correctly-programmed) players, which is probably a bad assumption to # make. sub request_move { my ($self, $ai) = @_; my $move = $ai->make_move($self->valid_states()); $self->{board}[$move][$self->{top}[$move]] = $self->current_player() +; $self->{"moves_made"}++; return $self->check_for_win($move, $self->{top}[$move]++); } # Checks to see if the game has been won. # Returns 1 or 2 if player 1 or 2 has won, undef otherwise. # # This sub is horribly non-optimized, but it works. sub check_for_win { my $self = shift; my($move_x, $move_y) = @_; return undef if ($self->{moves_made} < 7); my $player = $self->current_player(); my $win = 0; X: for my $x (-1, 0, 1) { Y: for my $y (-1, 0, 1) { next if $x == 0 and $y == 0; my($pos_x, $pos_y) = ($move_x, $move_y); for my $d (1..3) { $pos_x += $d * $x; $pos_y += $d * $y; next Y if $pos_x < 0 or $pos_x >= $self->{width}; next Y if $pos_y < 0 or $pos_y >= $self->{height}; next Y if $self->{board}[$pos_x][$pos_y] != $player; } $win = $player; last X; } } if ($win) { return $player; } elsif ($self->{"moves_made"} == $self->{width} * $self->{height}) +{ return 0; } else { return undef; } } # Returns a list of the currently-valid moves. sub valid_moves { my $self = shift; my @valid_moves = grep $self->{top}[$_] < $self->{height}, 0 .. $self->{width} - 1; return @valid_moves; } # Returns the current player (1 or 2). sub current_player { my $self = shift; return $self->{player}; } # Switches the current player. sub switch_player { my $self = shift; if ($self->{player} == 1) { $self->{player} = 2; } else { $self->{player} = 1; } } # Returns a string representation of the current state of the board. # The Nth character in the string corresponds to square X = N%width, # Y = N/width. # The current player is always denoted as "1", its opponent "2", # and an empty space "0". sub current_state { my $self = shift; my $current_state = join("", map @$_, @{ $self->{board} }); # If the current player is 2, swap the 1's and 2's in the board stat +e. if (current_player($self) == 2) { $current_state =~ tr/12/21/; } return $current_state; } # Returns a reference to a hash of the states that the current player # can legally put the board into. The keys of the hash are the states # themselves; the values are the moves required to put the board into # each state. sub valid_states { my $self = shift; my $current_state = current_state($self); my %valid_states; my @valid_moves = $self->valid_moves(); foreach my $move_x (@valid_moves) { my $valid_state = $current_state; my $move_y = $self->{top}[$move_x]; substr($valid_state, ($move_y * $self->{width} + $move_x), 1) = 1; $valid_states{$valid_state} = $move_x; } return \%valid_states; } 1; ### Offensive.pm package Offensive; # A class implementing an "offensive" AI game player. The offensive # player considers all states that have led to wins as "good" and # makes no preference between a loss and a tie. # # Adapting this player to a different game should be incredibly easy; # the game just has to send in a list of valid states and call the # appropriate win(), lose(), or tie() method at the end of the game. use Memory; @Offensive::ISA = ("Memory"); # Constructor sub new { my $class = shift; my $self = Memory::new($class); return $self; } # Do nothing if the result of a game was a loss or a tie, except clear # the "states" entry. sub lose { delete $_[0]->{"states"}; } sub tie { delete $_[0]->{"states"}; } # If we win, increase the priorities of all states that we put the # game into. States which occurred toward the end of the game are # weighted as "more good" than states which occurred at the # beginning. sub win { my $self = shift; my @states = @{$self->{"states"}}; my $score = 32; while (@states) { my $state = pop(@states); $self->modify($state, $score); $score /= 2; } delete $self->{"states"}; } # Uses Memory.pm's get_best_state() method to find and return the best # move out of those provided in the @$valid_states array. # # Keeps track of the moves it's made during this game, such that it # can modify their values accordingly at the end of the game. sub make_move { my ($self, $valid_states) = @_; my @valid_states = (keys %$valid_states); my $best_state = $self->get_best_state(\@valid_states); push @{$self->{"states"}}, $best_state; return $valid_states->{$best_state}; } 1; ### OffenseDefense.pm package OffenseDefense; # A class implementing an "offensive/defensive" AI game player. The # offensive/defensive player considers all states that have led to # wins as "good", all states that have led to losses as "bad", and all # states that have led to ties as "neutral". # # Adapting this player to a different game should be incredibly easy; # the game just has to send in a list of valid states and call the # appropriate win(), lose(), or tie() method at the end of the game. use Memory; @OffenseDefense::ISA = ("Memory"); # Constructor sub new { my $class = shift; my $self = Memory::new($class); return $self; } # Do nothing if the result of a game was a tie, except clear the # "states" entry. sub tie { delete $_[0]->{"states"}; } # If we win or lose, adjust the priorities of all states that we put # the game into; up for a win, down for a loss. sub win { $_[0]->adjust(+32) } sub lose { $_[0]->adjust(-32) } # Adjust all the states that we put the game into, based on the # specified priority. States which occurred toward the end of the # game are weighted as "more good/bad" than states which occurred at # the beginning. sub adjust { my $self = shift; my $score = shift; my @states = @{$self->{"states"}}; while (@states) { my $state = pop(@states); $self->modify($state, $score); $score /= 2; } delete $self->{"states"}; } # Uses Memory.pm's get_best_state() method to find and return the best # move out of those provided in the @$valid_states array. # # Keeps track of the moves it's made during this game, such that it # can modify their values accordingly at the end of the game. sub make_move { my ($self, $valid_states) = @_; my @valid_states = (keys %$valid_states); my $best_state = $self->get_best_state(\@valid_states); push @{$self->{"states"}}, $best_state; return $valid_states->{$best_state}; } 1; ### mainc4.pl #!/usr/bin/perl # Driver program for Connect Four games. Plays a (basically) infinite # number of games, dying gracefully when interrupted. Prints out the # results so far, at every 100 games. Also handles loading and saving # of player memories. use strict; use integer; use ConnectFour; use Offensive; use Random; $SIG{INT} = \&sig_handler; $| = 1; my $mem = 'c4-off.mem'; my @record = (0, 0, 0); my $p1 = Offensive->new(); my $p2 = Random->new(); $p1->load($mem); my $dead = 0; my $num_games = 0; until ($dead) { $num_games++; my $ttt = ConnectFour->new(); my $result = $ttt->play($p1, $p2); $record[$result]++; if ($num_games % 100 == 0) { print "\n($num_games) $record[1]/$record[2]/$record[0]\n"; } } $p1->save($mem); print "Player 1 memory saved OK.\n"; sub sig_handler { print "\nCaught INT signal... shutting down.\n"; $dead = 1; }
      Thanks for writing this--I'll ++ it tomorrow when I have votes.

      I'm guessing that the Offensive player will, indeed, do better than a defensive player, at this game. The comp.ai FAQ says that Connect Four has been solved as a win for the first player, whereas Tic-Tac-Toe is solved as a guaranteed tie. I'll be running the program basically 24/7 and let ya know how the results turn out.

Re: A simple game AI that learns
by Nimster (Sexton) on Jan 16, 2001 at 14:57 UTC
    If you want to do something *really* cool, that will surely show how the AI is by far superior, develop 3D tic-tac-toe, or even checkers for it. Those games have more combinations, and thus after X games, the AI has a bigger advantage. Checkers shouldn't be too hard to develop (you can use the same tic tac toe diagram of which places are taken by what, only 8x8 in size), win happens when one player has no tokens, and when a square is taken, and the square beyond it is free, the AI may move to the square beyond it and "kill" a token. You have to allow them to move backwards for a solvable play, and you can program a "queen" (when a token reaches the end of the board) later. 3D-tic-tac-toe is even easier, you simply edit the tic-tac-toe for 3-dimensional lists, and change the combos. I'm safely assuming this would take about 4,000,000 games just to reach the state of absolute superiority for the AI, since there are more combinations.
    Also - there's a chance of infinite game in checkers, although once you do program a queen, the chance is much lower (since the queen can move across the whole board). It will be slower to run, of course.
    I believe after enough runs in this game you will reach a state where the AI wins every single time over the random player. I also believe, that it will require the AI less runs to reach such a state in checkers than it did for the tic-tac-toe AI, in relation to the number of possibilities. (i.e it will take it more, but less if you divide that number by the number of possibilities)
    Also - you can try and adapt my Perl Hangman to the AI, this time not with 2 players, but an AI going against the number of failed guesses (trying to reach minimum). I wonder how will that work, since in hangman you basically guess letters. Giving preference to certain letters means at some point it will build a table of the most common letters in the english letters, and then you can completely throw it off by giving it Xzxyqv for example. :)
    I'll try working on Checkers for perl, then see if I can place it in your code, or just give it to you if you want.
    A list of combination for 3D tic-tac-toe
    each of the regular tic tac toe combos, on each plane (z=0,1,2): [(0,1),(1,1),(2,1)] [(x,0)(x,1)(x,2)] types each of the regular tic toe combos, with each of the parts of the comb +o, on serial planes (0,1,2 or 2,1,0): [(0,0),(1,1),(2,2)]

    I hope you understood me in spite of my lackluster english. Other than that, amazing work, of course I ++'ed it, and the guy who did it for connect 4 - you too.

    -Nimster
      I agree that checkers is probably the game which will be most interesting to see this AI play.

      There's currently one technical problem that needs to be solved before a feasible checkers AI can be generated, however: we need to use less space in memory. The Connect 4 AI uses up about 100 MB of memory once it plays up to about 70,000 games; there is simply too much state information to keep it all resident in memory at once. My computer has 96 MB of memory, and crawls to a halt after the memory size blows up.

      A side effect of the huge amount of memory taken by the program is that it's also about 100 MB to write out the state information to disk. I plan on using Storable to store the data onto disk, because it should take up less space, and maybe tying the state data to some sort of database such that we don't have to keep it all in memory at once. We could also decide to pack state info into a more concise form than strings; that should save on space, but I doubt that the small savings there (on the order of using roughly 5x less space) would be enough savings to make checkers (or even connect four) viable.

      All this space doubles if you choose to use another AI player (as opposed to the Random player) for the second player.

Re: A simple game AI that learns
by chip_creep (Acolyte) on Dec 18, 2003 at 06:52 UTC
    Howdy, I'm just starting to learn Perl. A while ago I wondered if something like that could be done with the stock market. "more_money" = WIN. however there is a smaller version of chess that could be played w/o too much modification(I think?). It consists of a 3x3 board of 3 pawns on either side. Winning is when you get your pawn to the other side OR when it is your opponents turn and he cannot move. Normal pawn movement other than that. Code on!!

Back to Code Catacombs

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: sourcecode [id://51644]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (3)
As of 2014-09-21 13:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (171 votes), past polls