Skip to content

Instantly share code, notes, and snippets.

@eqhmcow
Last active Nov 7, 2020
Embed
What would you like to do?
compute all possible tic tac toe games
#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;
my %games;
my $checked_games;
my $good_games;
# gen board
# at least 5 plays to generate a valid board
# at most 9 plays ?
# x then o alternating
# game is over at 9 plays or when board has a win, whichever comes first
# x at pos 0 thru 8, o at each pos
# then x at pos 0 thru 8, o at each pos
# recursive then?
# start with creating a board with x at pos 0 thru 8
sub initial_board {
foreach my $x (0..8) {
my @board;
$board[$x] = 'x';
gen_board(\@board, 1, 'o');
}
}
sub gen_board {
my ($board, $plays, $turn) = @_;
if ($plays == 9) {
$games{draw}++;
$good_games++;
return;
}
$plays++;
my $new_turn;
if ($turn eq 'x') {
$new_turn = 'o';
} else {
$new_turn = 'x';
}
foreach my $x (0..8) {
my @board = @$board;
next if defined $board[$x];
$board[$x] = $turn;
if ($plays >= 5) {
next if check_board(\@board, $plays);
}
gen_board(\@board, $plays, $new_turn);
}
}
# check board
# see if three x or o in a row, col, or two possible diagonal
sub check_board {
$checked_games++;
no warnings 'uninitialized';
my ($board, $plays) = @_;
# row
foreach my $x (0, 3, 6) {
my $tictac = $board->[$x] || 'n';
if ($board->[$x + 1] eq $tictac and $board->[$x + 2] eq $tictac) {
$games{win}{$tictac}{$plays}++;
$good_games++;
return 1;
}
}
# col
foreach my $x (0, 1, 2) {
my $tictac = $board->[$x] || 'n';
if ($board->[$x + 3] eq $tictac and $board->[$x + 6] eq $tictac) {
$games{win}{$tictac}{$plays}++;
$good_games++;
return 1;
}
}
# diag 0, 4, 8
my $tictac = $board->[0] || 'n';
if ($board->[4] eq $tictac and $board->[8] eq $tictac) {
$games{win}{$tictac}{$plays}++;
$good_games++;
return 1;
}
# diag 2, 4, 6
$tictac = $board->[2] || 'n';
if ($board->[4] eq $tictac and $board->[6] eq $tictac) {
$games{win}{$tictac}{$plays}++;
$good_games++;
return 1;
}
return;
}
initial_board();
print "checked games: $checked_games\n";
print "good games: $good_games\n";
print Dumper \%games;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment