view release on metacpan or  search on metacpan

lib/AI/Pathfinding/OptimizeMultiple.pm  view on Meta::CPAN

    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 ||= {};

    my $chosen_scans = ( $args->{chosen_scans} || $self->chosen_scans );

    my @info = PDL::list( $self->_orig_scans_data()->slice("$board_idx,:") );

lib/AI/Pathfinding/OptimizeMultiple.pm  view on Meta::CPAN

=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"