Finish 2010-11-17 12:00:00 UTC

feeling loopy

by Michael Bindschadler

Status: Passed
Results: 25486 (cyc: 31, node: 1915)
CPU Time: 22.747
Score: 5120.19
Submitted at: 2010-11-12 03:43:34 UTC
Scored at: 2010-11-12 03:44:13 UTC

Current Rank: 2173rd (Highest: 46th )

Comments
Michael Bindschadler
12 Nov 2010
looks around, cuts loops, and gives up gracefully when necessary :)
Please login or create a profile.
Code
function [thrustRow, thrustCol,loc,score] = look_and_drift(chart, aIndex, bIndex, maxThrottle)
% if nargin<5
%     extra_input = [];
% end
% Improved
% 

% allows structure input
if nargin<3
    ts = chart;
    if nargin < 2
        index = 1;
    else
        index = aIndex;
    end
    ts = ts(index);
    chart = ts.chart;
    aIndex = ts.aIndex;
    bIndex = ts.bIndex;
    maxThrottle = ts.maxThrottle;
end
    

rwind = chart(:,:,1);
cwind = chart(:,:,2);
nHood = neighborhood(maxThrottle);
[nr,nc] = size(rwind);
[ar,ac] = ind2sub([nr,nc],aIndex);
[br,bc] = ind2sub([nr,nc],bIndex);

% note that point B is dangerous to approach if it's very windy and the
% winds blow off the board
br_blow = br+rwind(br,bc); bc_blow = bc+cwind(br,bc);
b_blow_off_border = br_blow < 1 || br_blow>nr || bc_blow<1 || bc_blow>nc;
if abs(rwind(br,bc))+abs(cwind(br,bc))>maxThrottle && b_blow_off_border
    dangerous_B = true;
else
    dangerous_B = false;
end
dangerous_dist = maxThrottle/3; % try this

thrustRow = [];
thrustCol = [];
loc = [ar,ac];
v = [0,0];
iter = 1;

cur_r = ar;
cur_c = ac;
cur_pos = [ar,ac];
cur_vr = 0; %rwind(aIndex);
cur_vc = 0; %cwind(aIndex);
curV = [cur_vr,cur_vc];
cur_goal = [br,bc];


% Parameters
    function change_parameters(factor)
        current_factor = factor;
        target_speed = maxThrottle/2*factor;  % going faster or slower than this is penalized
        max_speed = maxThrottle*.66*factor; % going faster than this is heavily penalized
        close_enough = maxThrottle/2*factor;  % this distance is close enough to try to go straight to a goal
        distance_weight = 1; % when comparing costs, how much does a unit of distance count for?
        thrust_weight = 2*factor; % worth of a unit of thrust
        velocity_weight = 4; % the difference from target speed is currently squared, and then muliplied by this
        way_too_fast_weight = 5/factor; % penalty for each velocity unit above the max speed
        if factor<1
            values_reduced = true;
        else
            values_reduced = false;
        end
        distance_ratio = 3; % maxThrottle*this is considered a 'big' distance
    end
% Set parameters
change_parameters(1);

nRollbacks = 0;
nRollbackSteps = 2; % number of steps to go back when rolling back from a mistake
maxRollbacks = 0;
max_loops = 50;

%looping_noted_iters = [];
looping_stigma = zeros(nr,nc);
stigma_interval = 10;
looping_count = 0;

keepgoing = true;
giving_up = false;
reached_B = false;
%revert_iter = [];

score = [];

while keepgoing
    
    d = cur_goal-cur_pos;
    scalar_dist = sum(abs(d));
    
    if scalar_dist/maxThrottle > distance_ratio && values_reduced
        % reset weights and speeds to original values if they've been
        % reduced
        %disp('RESETTING PARAMETERS')
        change_parameters(1);
    end
    
    if scalar_dist > close_enough
        too_far = true;
    else
        too_far = false;
    end
    
    % no-thrust next posision
    zt_next_r = cur_r + cur_vr + rwind(cur_r,cur_c);
    zt_next_c = cur_c + cur_vc + cwind(cur_r,cur_c);
    
    % next neighborhood
    nrs = nHood(:,1) + zt_next_r;
    ncs = nHood(:,2) + zt_next_c;
    ns_inds = (1:length(nrs))';
    
    % prune illegal locations
    bad = nrs<1 | nrs>nr | ncs<1 | ncs>nc;
    if all(bad(:))
        % This means we made a mistake at least one step back, because all
        % of our possible moves take us off the board
        %keyboard
        nRollbacks = nRollbacks+1;
        if nRollbacks > maxRollbacks
            break;
        end
        % The solution is to roll it back a couple steps, and retune the
        % parameters for this difficult situation.
        rollItBack(nRollbackSteps);
        % Tune parameters to be more careful!
        change_parameters(.5);
        if scalar_dist/maxThrottle > distance_ratio
            % then we need to raise distance_ratio so that these changes
            % aren't immediately undone
            distance_ratio = 1.1*scalar_dist/maxThrottle;
        end
        %Start from here
        continue
        
    end
    nrs(bad) = [];
    ncs(bad) = [];
    ns_inds(bad) = [];
    
    % If we can reach the goal directly, we don't have to do some of the
    % extra calculations below
    [c,ia] = intersect([nrs,ncs],cur_goal,'rows');

    if ~too_far && ~isempty(c) && (~dangerous_B || reached_B)     
        next_r = nrs(ia);
        next_c = ncs(ia);
        cur_tr = nHood(ns_inds(ia),1);
        cur_tc = nHood(ns_inds(ia),2);
        cur_vr = cur_vr + rwind(cur_r,cur_c)+cur_tr;
        cur_vc = cur_vc + cwind(cur_r,cur_c)+cur_tc;
        
        if isequal(cur_goal,[br,bc])
            reached_B = true;
            reached_B_iter = size(loc,1);
            cur_goal = [ar,ac];
        elseif isequal(cur_goal,[ar,ac])
            keepgoing = false;
            
        end
        
    else
        % Can't reach goal directly or not slowly enough
        
        if dangerous_B && ~reached_B && (scalar_dist < dangerous_dist) 
            % time to SLOW down
            max_speed = 3;
            target_speed = 1.5;
        end
        
        % winds in that neighborhood
        nrws = rwind(sub2ind([nr,nc],nrs,ncs));
        ncws = cwind(sub2ind([nr,nc],nrs,ncs));
        
        %  subsequent next velocity if each spot were the next visited
        next_Vs = [nrs-cur_r+nrws,ncs-cur_c+ncws];
        
        % projected location if zero-thrust the next turn
        loc_proj = [nrs+next_Vs(:,1), ncs+next_Vs(:,2)];
        
        bad2 = loc_proj(:,1)<1 | loc_proj(:,1)>nr | loc_proj(:,2)<1 | loc_proj(:,2)>nc;
        
        if all(bad2)
            %%disp('second pruning failed');
            % This just means that you always drift off the board if you
            % don't thrust next time.  Not that big of a deal. Just pick
            % the best point which still exists right before this pruning
            
            % What's the best point now
            d_proj = [cur_goal(1)-nrs,cur_goal(2)-ncs]; %distance to goal
        else
            loc_proj(bad2,:) = [];
            nrs(bad2) = [];
            ncs(bad2) = [];
            %nrws(bad2) = [];
            %ncws(bad2) = [];
            next_Vs(bad2,:) = [];
            ns_inds(bad2) = [];
            % Best might be defined as minimum distance from the goal, let's start
            % there
            d_proj = [cur_goal(1)-loc_proj(:,1),cur_goal(2)-loc_proj(:,2)];
            
        end
        
        % might also consider whether the intermediate location is actually
        % closer to the goal... not implemented yet
        
        d_proj_scalar = sum(abs(d_proj),2);
        % Also could consider thrust cost
        thrust_cost = sum(abs(nHood(ns_inds,:)),2);
        velocity_cost = (target_speed-sum(abs(next_Vs),2)).^2;  
        way_too_fast_cost = max(0,sum(abs(next_Vs),2)-max_speed); % additional penalty for exceeding maximum speed
        %velocity_cost = max(0,sum(abs(next_Vs),2)-too_fast_thresh);% going too fast is also bad
        looping_cost = looping_stigma(sub2ind([nr,nc],nrs,ncs));
        quality_measure = d_proj_scalar*distance_weight+thrust_cost*thrust_weight...
            +velocity_cost*velocity_weight+way_too_fast_cost*way_too_fast_weight...
            +looping_cost; % smaller distance and smaller thrust are both better
        
        % Pick the one with the best quality
        [dum,min_ind] = min(quality_measure);
        
        
        %Update Results
        cur_tr = nHood(ns_inds(min_ind),1);
        cur_tc = nHood(ns_inds(min_ind),2);
        cur_vr = cur_vr + rwind(cur_r,cur_c)+cur_tr;
        cur_vc = cur_vc + cwind(cur_r,cur_c)+cur_tc;
        scalar_v = abs(cur_vr)+abs(cur_vc);
        next_r = nrs(min_ind);
        next_c = ncs(min_ind);
        %cur_pos = [cur_r,cur_c];
    end
    % Are we off the board?
    if isempty(next_r)
        %disp('off the board');
        %keyboard
        % give up
        break
    end
    
    cur_r = next_r;
    cur_c = next_c;
    cur_pos = [cur_r,cur_c];
    loc(iter,:) = [cur_r,cur_c]; 
    v(iter+1,:) = [cur_vr,cur_vc];
    thrustRow(iter) = cur_tr;
    thrustCol(iter) = cur_tc;
    
    % Check for loops
    [we_are_looping_tf,dup_inds,cycle] = loop_check;
    
    if we_are_looping_tf
        looping_count = looping_count+1;
        %cycle
        cycle_inds = sub2ind([nr,nc],cycle(:,1),cycle(:,2));
        looping_stigma(cycle_inds) = looping_stigma(cycle_inds)+stigma_interval;
        
%         looping_noted_iters(end+1) = iter;
%         gaps = diff(looping_noted_iters);
%         if ~isempty(gaps) && abs(gaps(end))>3 % we're more than 5 iterations from the last time looping was observed
%             looping_count = 0; % reset looping count
%         end
%         looping_count = looping_count+1;
        
        % Trim it back to the best place
        inds_to_consider = dup_inds(1):size(loc,1)-1;
        locs_to_consider = loc(inds_to_consider,:);
        dist2_to_goal = (locs_to_consider(:,1)-cur_goal(1)).^2+(locs_to_consider(:,2)-cur_goal(2)).^2;
        [dum,min_ind] = min(dist2_to_goal);
        closest_loc_ind = inds_to_consider(min_ind);
        % declare that one as close as we'll ever get to the goal, and change
        % goals or stop
        if giving_up || looping_count>max_loops
            if reached_B
                %disp('GIVING UP BECAUSE OF LOOPING')
                keepgoing = false;
            else
                keepgoing = true;
                reached_B = true;
                %disp('PRETENDING WE REACHED B BECAUSE OF LOOPING')
                if looping_count > max_loops
                    % reset so that there's some room to try to get back to
                    % point A
                    looping_count = 0; 
                end
                reached_B_iter = closest_loc_ind;
                cur_goal = [ar,ac];
            end
        end
        % truncate everything back to this point in time, adjust iter,
        % and continue from there
        %keyboard
        iter = closest_loc_ind;
        loc(iter+1:end,:) = [];
        thrustRow(iter+1:end) = [];
        thrustCol(iter+1:end) = [];
        v(iter+2:end,:) = [];
        cur_r = loc(end,1);
        cur_c = loc(end,2);
        cur_pos = loc(end,:);
        cur_vr = v(end,1);
        cur_vc = v(end,2);
        
%         switch looping_count
%             case 1
%                 % Strategy 1: Temporarily sigificantly boost position weight
%                 revert_iter = iter+2;
%                 distance_weight = 10;
%                 velocity_weight = 0;
%                 way_too_fast_weight = 0;
%                 thrust_weight = 1;
%             case 2
%                 % Strategy2: Incentivize speed
%                 revert_iter = iter+2;
%                 max_speed = 2*max_speed;
%                 target_speed = 1.5*target_speed;
%                 
%             case 3
%                 % Strategy3: Take a big jump
%                 revert_iter  = iter+2;
%                 target_speed = maxThrottle;
%                 max_speed = 2*max_speed;
%                                                 
%             case 4
%                 % Strategy4: give up
%                 %keyboard
%                 giving_up = true;
%         end
%             
        
            
    end
    
    iter = iter+1;
    
%     %revert any parameters needed in this section
%     if isequal(iter,revert_iter)
%         fprintf('REVERTING %i \n',looping_count);
%         
%         %keyboard % reverting parameters
%         change_parameters(current_factor);
%     end
end
loc = [ar,ac;loc]; %add back in starting location
score = scoreme(thrustRow,thrustCol,loc,ar,ac,br,bc,maxThrottle);

%% %%%%%%%%%%% NESTED FUNCTIONS %%%%%%%%%%%%%%

%% loop_check
function [tf,dup_inds,cycle] = loop_check

if reached_B
        % only consider locations in iterations since then
        dup_inds = find(loc(reached_B_iter:end-1,1)==cur_r & loc(reached_B_iter:end-1,2)==cur_c);
        dup_inds = dup_inds+reached_B_iter-1;
else
        % consider all locations up to now
        dup_inds = find(loc(1:end-1,1)==cur_r & loc(1:end-1,2)==cur_c);
end

if length(dup_inds)>=2
    tf = true;
    cycle = loc(dup_inds(end-1):dup_inds(end),:);
else
    tf = false;
    cycle = [];
    return
end


end % eof for loop_check

%% rollItBack
function  rollItBack(nRollbackSteps)

%store_current_results;    

if iter==1
    % can't rollback from the first step
    return
end

iter = iter-nRollbackSteps; % this is the iteration I'm about to rerun
iter = max(iter,2); % can't rollback to before 1, so iter must be at least two
    
cur_pos = loc(iter-1,:);
loc(iter:end,:) = [];
curV = v(iter,:);
cur_vr = curV(1);
cur_vc = curV(2);
v(iter+1:end,:) = [];
thrustRow(iter:end) = [];
thrustCol(iter:end) = [];
if reached_B && iter-1<reached_B_iter
    reached_B = false;
    reached_B_iter = [];
    cur_goal = [br,bc];
end

end % eof for rollItBack

end % eof for solver.m


%% %%%%%%%%%%%%%% SUBFUNCTIONS %%%%%%%%%%%%%%%%%%

%% scoreme
function score = scoreme(thrustRow,thrustCol,loc,ar,ac,br,bc,maxThrottle)
[thrustRow, thrustCol] = validatesolution(thrustRow, thrustCol, maxThrottle);
dA = sum((loc(end,:)-[ar,ac]).^2);
dBs = (loc(:,1)-br).^2+(loc(:,2)-bc).^2;
dB = min(dBs);
score = dA+dB+sum(abs(thrustRow))+sum(abs(thrustCol));

end



%% validate?
function [thrustRow, thrustCol] = validatesolution(thrustRow, thrustCol, maxThrottle)
% VALIDATESOLUTION Validates the solution vectors given by the solver
% just copied from runcontest

% Ensure column vectors and reals
thrustRow = real(thrustRow(:));
thrustCol = real(thrustCol(:));

% Check maximum number of moves
mnmoves = 1000;
if numel(thrustRow) > mnmoves
   thrustRow = thrustRow(1:mnmoves);
end
if numel(thrustCol) > mnmoves
   thrustCol = thrustCol(1:mnmoves);
end

% Ensure integers
if any(rem(thrustRow,1))
    thrustRow = round(thrustRow);
end
if any(rem(thrustCol,1))
    thrustCol = round(thrustCol);
end

% Ensure same length
ntR = numel(thrustRow);
ntC = numel(thrustCol);
if ntR~=ntC
    n = min(ntR,ntC);
    thrustRow = thrustRow(1:n);
    thrustCol = thrustCol(1:n);
end

% Check maximum throttle
h = (abs(thrustRow) + abs(thrustCol)) > maxThrottle;
if any(h)
    % Motor is blown for every turn the throttle exceeds the motor capacity!
    thrustRow(h) = 0;
    thrustCol(h) = 0;
end

end

%% neighborhood
function uList = neighborhood(N)
list = [];

for i = 0:N
    for j = 0:N
        if i+j<=N
            list(end+1,:) = [i,j];
        end
    end
end

list = [list;-list;[list(:,1),-list(:,2)];[-list(:,1),list(:,2)]];
uList = unique(list,'rows');
end