speedrun.py

import copy

KEY_TIMES = [
    {"time": 60,  "optional": True, "options": [[{"delta": -0.3, "prob": 0.15},
                                                 {"delta": 2, "prob": 0.85}]]}, #1-2 wall jump
    {"time": 62,  "optional": True, "options": [[{"delta": -0.1, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #1-2 piranha plant
    {"time": 71,  "optional": True, "options": [[{"delta": -0.1, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #1-2 wall clip
    {"time": 158, "optional": True, "options": [[{"delta": -0.1, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #4-3
    {"time": 192, "optional": True, "options": [[{"delta": -0.1, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #4-4 climb
    {"time": 206, "optional": True, "options": [[{"delta": -0.1, "prob": 0.9},
                                                 {"delta": 2, "prob": 0.1}]]}, #4-4 bowser
    # {"time": 206, "optional": True, "options": [[{"delta": -0.1, "prob": 0.99},
    #                                              {"delta": 2, "prob": 0.01}]]}, #4-4 bowser
    # {"time": 206, "optional": True, "options": [[{"delta": -0.1, "prob": 0.5},
    #                                              {"delta": 2, "prob": 0.5}]]}, #4-4 bowser
    {"time": 263, "optional": True, "options": [[{"delta": -0.1, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]},
    {"time": 295, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #5-2
    {"time": 317, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #fast 8-1
    {"time": 323, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #slow down
    {"time": 360, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #
    {"time": 375, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #8-3
    {"time": 420, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #8-4 first jump
    {"time": 460, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #8-4 para
    {"time": 467, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #8-4 bruce
    {"time": 477, "optional": True, "options": [[{"delta": -0.3, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}  #8-4 bowser
]

END_TIME = 478

KEY_TIMES = [
    {"time": 60,  "optional": False, "options": [[{"delta": -0.5, "prob": 0.5},
                                                 {"delta": 2, "prob": 0.5}]]}, #1-2 wall jump
    {"time": 100,  "optional": True, "options": [[{"delta": -0.5, "prob": 0.1},
                                                 {"delta": 2, "prob": 0.9}]]}, #1-2 wall jump
    {"time": 900,  "optional": True, "options": [[{"delta": -0.5, "prob": 0.4},
                                                  {"delta": 2, "prob": 0.6}]]}, #1-2 wall jump
]

END_TIME = 1000

def iterate_speedrun(key_times, goal_time, time_to_goal, verbose = False):
    #return new time_to_goal for the speedrun, which is the expected amoount of time needed
    #to achieve the goal_time
    #time_to_goal = avg_run_time / p_success
    time = END_TIME

    #At each point in the run you have one or a few (p_success, avg_time_left) possibilities
    #these aren't well-ordered because your preference can depend on other details of the run
    #for example (0.4, 94) is worse than (0.1, 19) at the start of a run
    #comparing time_to_goal = avg_run_time / p_success: 94 / 0.4 > 19 / 0.1
    #but 100 seconds into a run the preference reverses: (94 + 100) / 0.4 < (19 + 100) / 0.1

    #At each point in the run store a list of breakpoint paces. For each breakpoint if you're ahead of that pace then you have the listed (p_success, avg_time_left) possibilities
    all_breakpoint_info = {END_TIME: {goal_time: {"pace":goal_time, "poss":[{"prob":1, "time_left":0, "route": {}}]}, float("inf"): {"pace":float("inf"), "poss":[{"prob":0, "time_left":0, "route": {}}]}}}

    for x in key_times[::-1]: #build up possibilities backwards
        next_time = time
        time = x["time"]
        next_breakpoint_info = all_breakpoint_info[next_time]
        breakpoint_info = {}
        options = x["options"]
        if x["optional"]:
            #add skip option
            options = options + [[{"delta": 0, "prob": 1}]]
        breakpoint_list = list(set(round(next_breakpoint_info[t]["pace"] - out["delta"],2) for t in next_breakpoint_info for opt in options for out in opt))
        for pace in breakpoint_list:
            def evaluate_option(i, option): #i is the option index
                #Compute all (prob, time_left) possibilities if we choose this option at this step

                #Each outcome o1, o2, o3... in the options list
                #will lead to a number of possibilities
                #o1 -> p11, p12, p13...
                #o2 -> p21, p22, p23...
                #o3 -> p31, p32, p33...
                #so the total possibilities result from picking one each from the o1 possibilities
                #o2 possibilities, o3 possibilities, ...
                #so iterate through the outcomes and at each step
                #update partial_poss = O1 X O2 X O3.. X Ok
                #on each iteration i update partial_poss to include
                #each combination of the existing partial_poss X Oi
                partial_poss = [{"prob":0,"time_left":0,"route":{}}]

                for outcome in option:
                    iter_poss = []
                    next_pace = round(pace + outcome["delta"],2)
                    next_breakpoint = min([t for t in next_breakpoint_info if t >= next_pace])
                    next_poss_list = next_breakpoint_info[next_breakpoint]["poss"]
                    for next_poss in next_poss_list:
                        #once we reach the next key time we'll have
                        #next_poss["prob"] and next_poss["time_left"] on average
                        #so current time left = next_poss["time_left"] + (next_time - time)
                        #reset if current efficiency is slower than the overall speedrun time_to_goal
                        t_continue = (next_poss["time_left"] + (next_time - time)) / (next_poss["prob"] + 1e-10)
                        if t_continue > time_to_goal or next_poss["prob"] == 0:
                            for p in partial_poss:
                                p["route"][(f"{time}p", next_pace)] = "X"
                                iter_poss.append(p)
                        else:
                            #combine each item in partial_poss with this next_poss
                            for p in partial_poss:
                                prob = p["prob"] + outcome["prob"] * next_poss["prob"]
                                time_left = p["time_left"] + outcome["prob"] * (next_poss["time_left"] + (next_time - time))
                                route = dict(next_poss["route"])
                                route[(time, pace)] = i
                                iter_poss.append({"prob":prob, "time_left":time_left, "route":route})
                    partial_poss = iter_poss
                return partial_poss

            #pull possibilities across all options
            poss = [x for i,opt in enumerate(options) for x in evaluate_option(i,opt)]
            poss.sort(key = lambda x: (x["prob"],-1*x["time_left"]),reverse=True)
            new_poss = poss[:1] #just the first element from possibilities

            #prune some possibilities
            for i in range(1,len(poss)):
                poss_old = new_poss[-1]
                poss_new = poss[i]
                marginal_prob = poss_old["prob"] - poss_new["prob"]
                marginal_time = (poss_old["time_left"] - poss_new["time_left"])
                if (poss_old["prob"] >= poss_new["prob"] and poss_old["time_left"] <= poss_new["time_left"]):
                    continue
                elif marginal_time / marginal_prob < time_to_goal: #not 100% sure this pruning is valid
                    continue
                elif poss_new["prob"] > 0:
                    new_poss.append(poss_new)
            poss = new_poss
            breakpoint_info[pace] = {"pace": pace, "poss": poss}


        #filter out any paces that are too slow or too fast

        #one_cutoff is the slowest pace that can have success with 100% probability
        one_cutoff = max(x for x in breakpoint_info if any(y["prob"] == 1 for y in breakpoint_info[x]["poss"]))

        #zero_cutoff is the fastest pace that has no chance of success
        zeros = [x for x in breakpoint_info if all(y["prob"] == 0 for y in breakpoint_info[x]["poss"]) and x != float("inf")]
        zero_cutoff = float("inf") if not zeros else min(zeros)

        breakpoint_info = {x:breakpoint_info[x] for x in breakpoint_info if x >= one_cutoff and (x < zero_cutoff or x == float("inf"))}
        all_breakpoint_info[time] = breakpoint_info

    start_time_threshold = min(x for x in all_breakpoint_info[time] if x >= 0)
    #add the time to the first trick to thresholds[start_time_threshold]["time_left"]
    best_val = min((x["time_left"] + time) / (x["prob"]) for x in all_breakpoint_info[time][start_time_threshold]["poss"])
    return best_val, all_breakpoint_info

def compute_paths(KEY_TIMES, thresholds, resets):
    #return a list of possible outcomes of the run:
    #"S" means skipped that trick,
    #(option_id, delta) means picked option_id with outcome delta
    #"X" means reset run
    paths = [[]]
    starting_pace = 0
    for x in KEY_TIMES:
        new_paths = []
        time = x["time"]
        for p in paths:
            pace = 0
            if p and p[-1] == "X": #ends in reset
                new_paths.append(p)
                continue
            for i in p:
                if i == "S": continue
                pace += i[1]
            breakpoint_time = min(x for x in thresholds[time] if x >= pace)
            option_id = thresholds[time][breakpoint_time]["option"]
            if option_id is None:
                new_paths.append(p + ["S"])
                continue
            outcomes = x["options"][option_id]
            for out in sorted(outcomes, key = lambda x: -1 *x["delta"]):
                new_pace = pace + out["delta"]
                if resets[time] < new_pace:
                    new_paths.append(p + [(option_id,out["delta"]),"X"])
                else:
                    new_paths.append(p + [(option_id,out["delta"])])
        paths = new_paths
    return paths

def optimize_speedrun(KEY_TIMES, goal_time):
    val = float("inf")
    for i in range(100):
        new_val, thresholds = iterate_speedrun(KEY_TIMES, -1, val)
        if new_val == val: break
        val = new_val
    return val, thresholds

def trick_to_practice(KEY_TIMES, goal_time, practice_pct = 0.01):
    base_val, _, _ = optimize_speedrun(KEY_TIMES, goal_time)
    output = []
    for i,x in enumerate(KEY_TIMES):
        for j,opt in enumerate(x["options"]):
            #generate a new version of the option where the best option has 1% more prob
            #(taken proportionally from the other outcomes)
            best_outcome_id = sorted([(k,x) for k,x in enumerate(opt)], key = lambda x: x[1]["delta"])[0][0]
            prob = opt[best_outcome_id]["prob"]
            prob_delta = min(1 - opt[best_outcome_id]["prob"], practice_pct)

            # print(opt)
            new_option = [{"prob":out["prob"]+prob_delta,"delta":out["delta"]} if k == best_outcome_id else {"prob":out["prob"]*(1-prob-prob_delta)/(1-prob+1e-10),"delta":out["delta"]} for k,out in enumerate(opt)]

            new_trick = copy.deepcopy(x)
            new_trick["options"][j] = new_option

            new_trick_list = copy.deepcopy(KEY_TIMES)
            new_trick_list[i] = new_trick

            new_val, _, _ = optimize_speedrun(new_trick_list, goal_time)
            output.append((i,j,new_val,base_val))
            # new_tricks = [x if i for i,x in enumerate(KEY_TIMES)]
            # best_outcome_prob = best_outcome["prob"]
            # new_prob = best_outcome_prob

            # new_tricks = [x if k == i else x for k,x in enumerate(KEY_TIMES)]
    print(output)


if __name__ == "__main__":
    val, thresholds = optimize_speedrun(KEY_TIMES, -1)

    print("***")
    print("total value")
    print(val)
    print("***")

    for x in sorted([x for x in thresholds]):
        print(x)
        for y in sorted([y for y in thresholds[x]]):
            print(y, thresholds[x][y])
        print("---")

    # trick_to_practice(KEY_TIMES, -1)