Integrate Simulated Annealing Repo

[amarshah1999]

Integrate https://github.com/amarshah1999/analytics_cup_research/tree/main

High level plan:

1. Define an interface of how we will call the annealing function
2. Create a new objective function and weight primitive with pre-defined examples based on the repo above
3. Make some improvements to the perturbation algorithm to be more realistic based on initial player velocities
4. Quality of life improvements like error handling, edge cases

[Alek050]

Hi @amarshah1999,

This looks like a great addition!

From an architectural perspective I think it would be logical to put everything in a seperate module (databallpy.optimization). Here we obviously need a file with the Simulated Annealing functionality. The base function that users will call will look something like this I think:

def optimize_tracking_frame(
    frame: pd.Series,
    objective: PerformanceObjective,
    algorithm: OptimizationAlgorithm, # --> in the beginning only SimulatedAnnealing
    constraints: Constraints, # Within optimization algo
    filters: Filters # The variables the optimization algo is allowed to change
) -> OptimizationResult:

For an initial performance objective you use create the Ferandez pitch control * xT threat since that is already implemented in databallpy

Last, we should consider adding a function in databallpy.visualise to make sure the differences can be easilyl visualised.

Optimization module TODO

• Add the new databallpy.optimization module + file structure.
• Add the interfaces: PerformanceObjective, OptimizationAlgorithm, Constraints, Filters, OptimizationResult.
• Implement the optimize_tracking_frame(...) entry function.
• Implement the first optimizer (SimulatedAnnealing) using those interfaces.
• Add the Fernandez pitch-control × xT objective.
• Assert the optimizer never mutates the original frame.
• Add a visualisation helper to show original vs. optimized frame.
• Add unit tests.
• Add docs with simple integration with pc × xT on a test frame, also show how to create manual performance objectives and how to change the constraints and filters.
• Alter ChangeLog & ReadMe to showcase new functionalities

[amarshah1999]

Notes:

I have added files for constraints, objectives, and an algorithm base class. There is no need for a filter for now, but this could be generalised if we decided to add more optimization algorithms that re-use the filters in simulated annealing.

Link to repo

Open questions I have not been able to solve:

1. There is no easy way to logically separate constraints, weights etc from the algorithm, as it needs those properties on the class in order to run the compute_objective and perturbation methods. This means that we cannot easily instantiate SimulatedAnnealing independently of the optimization parameters, and therefore optimize_tracking_frame cannot be cleanly implemented.

2. The TimeToIntercept constraint needs the starting positions of the players to work out whether the perturbation is allowed. Because of the above, we need to compute those starting positions as part of the SimulatedAnnealing algorithm, I called this compute_prerequisites. If we could fix item 1 above, then that would allow us to compute the starting positions on init of the constraint by passing the game and frame objects into the constraint from optimize_tracking_frame, which is much cleaner and generalises better.

3. xT array is currently just a hard coded pkl file I made by manually entering values from https://karun.in/blog/expected-threat.html , not sure how to best replace this with something more robust.

Once I solve these questions, I can:

• Add a "retry" boolean if the algorithm gets stuck in a local minimum, maybe with max_retries.
• Add unit tests and documentation
• Finish the visualization function that I started

[Alek050]

Hi @amarshah1999,

Thanks for the first draft of the implementation, it looks promising! Let me try to answer your questions:

1. I am not understanding this 100%, but if I am correct you are saying we can not implement something like:

game.optimize_tracking_frame(engine str | OptimizationAlgorithm ="simulated_annealing", objective: str | ObjectiveTerm = "xt_weighted_pitch_control", constraints:list[Constraint] = [], distance_pertubation, max_tti, num_iterations, ...)

Why is that exactly? Based on the implementation I am not seeing why we would not be able to do this, but probably I am missing something here.

2. Relates to point 1.
3. I would propose using the xt grid saved in databallpy/models/open_play_xT.npy. This can be loaded with out pickle (safer) and is used in other places in the project as well so is more in line with databallpy implementation (see docs for implementaiont).

[amarshah1999]

I had some time away, and now I have an implementation that looks like:

optimize_tracking_frame(
    game = game,
    selected_frame_idx = selected_frame_idx, 
    objective_terms = [
            WeightedPitchControlObjective(
                grid=grid,
                attacking_team=attacking_team,
                defending_team=defending_team,
                attacking_team_influence=attacking_team_influence,
                defending_player_ids=game.get_column_ids(team=defending_team),
            ),
            PressureObjective(
                attacking_player_ids=game.get_column_ids(team=defending_team), game=game
            ),
        ], 
    weights=[1, 1], 
    constraints=[TTIConstraint(max_time_to_intercept_seconds=2)], 
    algorithm=SimulatedAnnealing,
    num_iterations = 1000,
    )

I have also implemented your xt array - super helpful thank you!

[Alek050]

Hi @amarshah1999,

I haven't looked at the code since my last reply, but is the code now fully functional?

• if so, could you please open a PR so I can formally review and test the code
• if not, is there anything I can do to help in terms of architectural choices?

[amarshah1999]

Hi @amarshah1999,

I haven't looked at the code since my last reply, but is the code now fully functional?

• if so, could you please open a PR so I can formally review and test the code
• if not, is there anything I can do to help in terms of architectural choices?

Hey @Alek050 - Sorry not yet - I just moved house so I have been too busy! Hoping to get some more time to work on it tonight.
The code is functional so I can open a PR, but it's missing:

• unit tests
• a proper visualisation helper function to diff the results
• documentation / examples

Happy to let you try out a first draft if you want me to raise a PR now or I can finish the above tasks first. Let me know - thanks for your continued support :)

[Alek050]

@amarshah1999 open a PR, can't wait to play around with it! We can arrange the tests, visualisations, and documenation later