AI-Pathfinding-OptimizeMultiple
view release on metacpan or search on metacpan
lib/AI/Pathfinding/OptimizeMultiple.pm view on Meta::CPAN
my $args = shift;
my $scans_data = PDL::cat(
map {
my $id = $_->id();
my $pdl = $self->_scans_iters_pdls()->{$id};
my $factor = $self->_stats_factors->{$id};
(
defined($factor)
? ( ( $pdl >= 0 ) * ( ( $pdl / $factor )->ceil() ) +
( $pdl < 0 ) * $pdl )
: $pdl
);
} @{ $self->_selected_scans() }
);
$self->_orig_scans_data($scans_data);
$self->_scans_data( $self->_orig_scans_data()->copy() );
return 0;
}
my $BOARDS_DIM = 0;
my $SCANS_DIM = 1;
my $STATISTICS_DIM = 2;
sub _next_iter_idx
{
my $self = shift;
my $ret = $self->_iter_idx();
$self->_iter_idx( $ret + 1 );
return $ret;
}
sub _get_next_quota
{
my $self = shift;
my $iter = $self->_next_iter_idx();
if ( ref( $self->_quotas() ) eq "ARRAY" )
{
return $self->_quotas()->[$iter];
}
else
{
return $self->_quotas()->($iter);
}
}
sub _calc_get_iter_state_param_method
{
my $self = shift;
my $optimize_for = $self->_optimize_for();
my %resolve = (
len => "_get_iter_state_params_len",
minmax_len => "_get_iter_state_params_minmax_len",
speed => "_get_iter_state_params_speed",
);
return $resolve{$optimize_for};
}
sub _get_iter_state_params
{
my $self = shift;
my $method = $self->_calc_get_iter_state_param_method();
return $self->$method();
}
sub _my_sum_over
{
my $pdl = shift;
return $pdl->sumover()->slice(":,(0)");
}
sub _my_xchg_sum_over
{
my $pdl = shift;
return _my_sum_over( $pdl->xchg( 0, 1 ) );
}
sub _get_iter_state_params_len
{
my $self = shift;
my $iters_quota = 0;
my $num_solved_in_iter = 0;
my $selected_scan_idx;
# If no boards were solved, then try with a larger quota
while ( $num_solved_in_iter == 0 )
{
my $q_more = $self->_get_next_quota();
if ( !defined($q_more) )
{
AI::Pathfinding::OptimizeMultiple::Error::OutOfQuotas->throw(
error => "No q_more", );
}
$iters_quota += $q_more;
my $iters = $self->_scans_data()->slice(":,:,0");
my $solved = ( ( $iters <= $iters_quota ) & ( $iters > 0 ) );
my $num_moves = $self->_scans_data->slice(":,:,2");
my $solved_moves = $solved * $num_moves;
my $solved_moves_sums = _my_sum_over($solved_moves);
my $solved_moves_counts = _my_sum_over($solved);
my $solved_moves_avgs = $solved_moves_sums / $solved_moves_counts;
( undef, undef, $selected_scan_idx, undef ) =
$solved_moves_avgs->minmaximum();
$num_solved_in_iter = $solved_moves_counts->at($selected_scan_idx);
}
lib/AI/Pathfinding/OptimizeMultiple.pm view on Meta::CPAN
$self->_total_iters(0);
$self->_status("iterating");
# $self->_inspect_quota() throws ::Error::OutOfQuotas if
# it does not have any available quotas.
eval {
while ( $self->_status() eq "iterating" )
{
$self->_inspect_quota();
}
};
if (
my $err = Exception::Class->caught(
'AI::Pathfinding::OptimizeMultiple::Error::OutOfQuotas')
)
{
$self->_status("out_of_quotas");
}
else
{
$err = Exception::Class->caught();
if ($err)
{
if ( not( blessed $err && $err->can('rethrow') ) )
{
die $err;
}
$err->rethrow;
}
}
return;
}
sub _get_num_scans
{
my $self = shift;
return ( ( $self->_scans_data()->dims() )[$SCANS_DIM] );
}
sub _calc_chosen_scan
{
my ( $self, $selected_scan_idx, $iters_quota ) = @_;
return AI::Pathfinding::OptimizeMultiple::ScanRun->new(
{
iters => (
$iters_quota * (
$self->_stats_factors->{
( $self->_selected_scans->[$selected_scan_idx]->id() ),
} // 1
)
),
scan_idx => $selected_scan_idx,
}
);
}
sub calc_flares_meta_scan
{
my $self = shift;
$self->chosen_scans( [] );
$self->_total_boards_solved(0);
$self->_total_iters(0);
$self->_status("iterating");
my $iters_quota = 0;
my $flares_num_iters = PDL::Core::pdl( [ (0) x $self->_get_num_scans() ] );
my $ones_constant =
PDL::Core::pdl( [ map { [1] } ( 1 .. $self->_get_num_scans() ) ] );
my $next_num_iters_for_each_scan_x_scan =
( ( $ones_constant x $flares_num_iters ) );
my $num_moves = $self->_scans_data->slice(":,:,1");
# The number of moves for dimension 0,1,2 above.
my $num_moves_repeat = $num_moves->clump( 1 .. 2 )->xchg( 0, 1 )
->dummy( 0, $self->_get_num_scans() );
my $selected_scan_idx;
my $loop_iter_num = 0;
my $UNSOLVED_NUM_MOVES_CONSTANT = 64 * 1024 * 1024;
my $last_avg = $UNSOLVED_NUM_MOVES_CONSTANT;
FLARES_LOOP:
while ( my $q_more = $self->_get_next_quota() )
{
$iters_quota += $q_more;
# Next number of iterations for each scan x scan combination.
my $next_num_iters = (
( $ones_constant x $flares_num_iters ) + (
PDL::MatrixOps::identity( $self->_get_num_scans() ) *
$iters_quota
)
);
# print "\$next_num_iters = $next_num_iters\n";
my $iters = $self->_scans_data()->slice(":,:,0");
my $iters_repeat =
$iters->dummy( 0, $self->_get_num_scans() )->xchg( 1, 2 )
->clump( 2 .. 3 );
# print "\$iters_repeat =", join(",",$iters_repeat->dims()), "\n";
my $next_num_iters_repeat =
$next_num_iters->dummy( 0, $self->_num_boards() )->xchg( 0, 2 );
# print "\$next_num_iters_repeat =", join(",",$next_num_iters_repeat->dims()), "\n";
# A boolean tensor of which boards were solved:
# Dimension 0 - Which scan is it. - size - _get_num_scans()
# Dimension 1 - Which scan we added the quota to
# - size - _get_num_scans()
# Dimension 2 - Which board. - size - _num_boards()
my $solved =
( $iters_repeat >= 0 ) * ( $iters_repeat < $next_num_iters_repeat );
# print "\$num_moves_repeat =", join(",",$num_moves_repeat->dims()), "\n";
my $num_moves_solved =
( $solved * $num_moves_repeat ) +
( $solved->not() * $UNSOLVED_NUM_MOVES_CONSTANT );
my $minimal_num_moves_solved =
$num_moves_solved->xchg( 0, 1 )->minimum();
my $which_minima_are_solved =
( $minimal_num_moves_solved != $UNSOLVED_NUM_MOVES_CONSTANT );
my $minimal_with_zeroes =
$which_minima_are_solved * $minimal_num_moves_solved;
my $solved_moves_sums = _my_xchg_sum_over($minimal_with_zeroes);
my $solved_moves_counts = _my_xchg_sum_over($which_minima_are_solved);
my $solved_moves_avgs = $solved_moves_sums / $solved_moves_counts;
# print join(",", $solved_moves_avgs->minmaximum()), "\n";
my $min_avg;
( $min_avg, undef, $selected_scan_idx, undef ) =
$solved_moves_avgs->minmaximum();
$last_avg = $min_avg;
push @{ $self->chosen_scans() },
$self->_calc_chosen_scan( $selected_scan_idx, $iters_quota );
$flares_num_iters->set( $selected_scan_idx,
$flares_num_iters->at($selected_scan_idx) + $iters_quota );
$self->_selected_scans()->[$selected_scan_idx]->mark_as_used();
$iters_quota = 0;
my $num_solved = $solved_moves_counts->at($selected_scan_idx);
my $flares_num_iters_repeat =
$flares_num_iters->dummy( 0, $self->_num_boards() );
# A boolean tensor:
# Dimension 0 - board.
# Dimension 1 - scans.
my $solved_with_which_iter =
( $flares_num_iters_repeat >= $iters->clump( 1 .. 2 ) ) &
( $iters->clump( 1 .. 2 ) >= 0 );
my $total_num_iters = (
( $solved_with_which_iter * $flares_num_iters_repeat )->sum() + (
$solved_with_which_iter->not()->andover() *
$flares_num_iters->sum()
)->sum()
);
print "Finished ", $loop_iter_num++,
" ; #Solved = $num_solved ; Iters = $total_num_iters ; Avg = $min_avg\n";
STDOUT->flush();
}
}
sub calc_board_iters
{
my $self = shift;
my $board = shift;
my $board_iters = 0;
my @info = PDL::list( $self->_orig_scans_data()->slice("$board,:") );
my @orig_info = @info;
foreach my $s ( @{ $self->chosen_scans() } )
{
if ( ( $info[ $s->scan_idx() ] > 0 )
&& ( $info[ $s->scan_idx() ] <= $s->iters() ) )
{
$board_iters += $info[ $s->iters() ];
last;
}
else
{
if ( $info[ $s->scan_idx() ] > 0 )
{
$info[ $s->scan_idx() ] -= $s->iters();
}
$board_iters += $s->iters();
}
}
return {
'per_scan_iters' => \@orig_info,
'board_iters' => $board_iters,
};
}
sub get_final_status
{
my $self = shift;
return $self->_status();
}
sub simulate_board
{
my ( $self, $board_idx, $args ) = @_;
if ( $board_idx !~ /\A[0-9]+\z/ )
{
die "Board index '$board_idx' is not numeric!";
}
$args ||= {};
lib/AI/Pathfinding/OptimizeMultiple.pm view on Meta::CPAN
sub _add_to_total_boards_solved
{
my $self = shift;
my $how_much = shift;
$self->_total_boards_solved( $self->_total_boards_solved() + $how_much );
return;
}
1; # End of AI::Pathfinding::OptimizeMultiple
__END__
=pod
=encoding UTF-8
=head1 NAME
AI::Pathfinding::OptimizeMultiple - optimize path finding searches for a large
set of initial conditions (for better average performance).
=head1 VERSION
version 0.0.17
=head1 SYNOPSIS
use AI::Pathfinding::OptimizeMultiple
my @scans =
(
{
name => "first_search"
},
{
name => "second_search",
},
{
name => "third_search",
},
);
my $obj = AI::Pathfinding::OptimizeMultiple->new(
{
scans => \@scans,
num_boards => 32_000,
optimize_for => 'speed',
scans_iters_pdls =>
{
first_search => $first_search_pdl,
second_search => $second_search_pdl,
},
quotas => [400, 300, 200],
selected_scans =>
[
AI::Pathfinding::OptimizeMultiple::Scan->new(
id => 'first_search',
cmd_line => "--preset first_search",
),
AI::Pathfinding::OptimizeMultiple::Scan->new(
id => 'second_search',
cmd_line => "--preset second_search",
),
AI::Pathfinding::OptimizeMultiple::Scan->new(
id => 'third_search',
cmd_line => "--preset third_search",
),
],
}
);
$obj->calc_meta_scan();
foreach my $scan_alloc (@{$self->chosen_scans()})
{
printf "Run %s for %d iterations.\n",
$scans[$scan_alloc->scan_idx], $scan_alloc->iters;
}
=head1 DESCRIPTION
This CPAN distribution implements the algorithm described here:
=over 4
=item * L<https://groups.google.com/group/comp.ai.games/msg/41e899e9beea5583?dmode=source&output=gplain&noredirect>
=item * L<http://www.shlomifish.org/lecture/Perl/Lightning/Opt-Multi-Task-in-PDL/>
=back
Given statistics on the performance of several game AI searches (or scans)
across a representative number of initial cases, find a scan
that solves most deals with close-to-optimal performance, by using switch
tasking.
=head1 SUBROUTINES/METHODS
=head2 my $chosen_scans_array_ref = $self->chosen_scans()
Returns the scans that have been chosen to perform the iteration. Each one is
a AI::Pathfinding::OptimizeMultiple::ScanRun object.
=head2 $calc_meta_scan->calc_meta_scan()
Calculates the meta-scan after initialisation. See here for the details
of the algorithm:
L<http://www.shlomifish.org/lecture/Freecell-Solver/The-Next-Pres/slides/multi-tasking/best-meta-scan/>
=head2 $self->calc_flares_meta_scan()
This function calculates the flares meta-scan: i.e: assuming that all atomic
scans are run one after the other and the shortest solutions of all
successful scans are being picked.
=head2 $calc_meta_scan->calc_board_iters($board_idx)
Calculates the iterations of the board $board_idx in all the scans.
Returns a hash_ref containing the key 'per_scan_iters' for the iterations
per scan, and 'board_iters' for the total board iterations when ran in the
scans.
=head2 my $status = $calc_meta_scan->get_final_status()
Returns the status as string:
=over 4
=item * "solved_all"
=item * "iterating"
=item * "out_of_quotas"
=back
=head2 my $sim_results_obj = $calc_meta_scan->simulate_board($board_idx, $args)
Simulates the board No $board_idx through the scan. Returns a
L<AI::Pathfinding::OptimizeMultiple::SimulationResults> object.
$args is an optional hash reference. It may contain a value with the key of
C<'chosen_scans'> that may specify an alternative scans to traverse.
=head2 my $n = $calc_meta_scan->get_total_iters()
Returns the total iterations count so far.
=head2 BUILD()
Moo leftover. B<INTERNAL USE>.
=head1 SEE ALSO
=over 4
=item * L<Freecell Solver|http://fc-solve.shlomifish.org/>
For which this code was first written and used.
=item * L<Alternative Implementation in C#/.NET|https://bitbucket.org/shlomif/fc-solve/src/cc5b428ed9bad0132d7a7bc1a14fc6d3650edf45/fc-solve/presets/soft-threads/meta-moves/auto-gen/optimize-seq?at=master>
An Alternative implementation in C#/.NET, which was written because the
performance of the Perl/PDL code was too slow.
=item * L<PDL> - Perl Data Language
Used here.
=back
=head1 AUTHOR
Shlomi Fish, L<http://www.shlomifish.org/> .
=head1 ACKNOWLEDGEMENTS
B<popl> from Freenode's #perl for trying to dig some references to an existing
algorithm in the scientific literature.
=for :stopwords cpan testmatrix url bugtracker rt cpants kwalitee diff irc mailto metadata placeholders metacpan
=head1 SUPPORT
=head2 Websites
The following websites have more information about this module, and may be of help to you. As always,
in addition to those websites please use your favorite search engine to discover more resources.
=over 4
=item *
MetaCPAN
A modern, open-source CPAN search engine, useful to view POD in HTML format.
L<https://metacpan.org/release/AI-Pathfinding-OptimizeMultiple>
=item *
RT: CPAN's Bug Tracker
The RT ( Request Tracker ) website is the default bug/issue tracking system for CPAN.
L<https://rt.cpan.org/Public/Dist/Display.html?Name=AI-Pathfinding-OptimizeMultiple>
=item *
CPANTS
The CPANTS is a website that analyzes the Kwalitee ( code metrics ) of a distribution.
L<http://cpants.cpanauthors.org/dist/AI-Pathfinding-OptimizeMultiple>
=item *
CPAN Testers
The CPAN Testers is a network of smoke testers who run automated tests on uploaded CPAN distributions.
L<http://www.cpantesters.org/distro/A/AI-Pathfinding-OptimizeMultiple>
=item *
CPAN Testers Matrix
The CPAN Testers Matrix is a website that provides a visual overview of the test results for a distribution on various Perls/platforms.
L<http://matrix.cpantesters.org/?dist=AI-Pathfinding-OptimizeMultiple>
=item *
CPAN Testers Dependencies
The CPAN Testers Dependencies is a website that shows a chart of the test results of all dependencies for a distribution.
L<http://deps.cpantesters.org/?module=AI::Pathfinding::OptimizeMultiple>
=back
=head2 Bugs / Feature Requests
Please report any bugs or feature requests by email to C<bug-ai-pathfinding-optimizemultiple at rt.cpan.org>, or through
the web interface at L<https://rt.cpan.org/Public/Bug/Report.html?Queue=AI-Pathfinding-OptimizeMultiple>. You will be automatically notified of any
progress on the request by the system.
=head2 Source Code
The code is open to the world, and available for you to hack on. Please feel free to browse it and play
with it, or whatever. If you want to contribute patches, please send me a diff or prod me to pull
from your repository :)
L<http://github.com/shlomif/fc-solve>
git clone ssh://git@github.com/shlomif/fc-solve.git
=head1 AUTHOR
Shlomi Fish <shlomif@cpan.org>
=head1 BUGS
Please report any bugs or feature requests on the bugtracker website
L<https://github.com/shlomif/fc-solve/issues>
When submitting a bug or request, please include a test-file or a
patch to an existing test-file that illustrates the bug or desired
feature.
=head1 COPYRIGHT AND LICENSE
This software is Copyright (c) 2012 by Shlomi Fish.
This is free software, licensed under:
The MIT (X11) License
=cut
( run in 2.250 seconds using v1.01-cache-2.11-cpan-df04353d9ac )