Оптимальное прохождение уровня в ритмо-игре с помощью алгоритмов

public SystemState PassTime(SystemState nextState, uint newTime)
{
    if(newTime < nextState.Time) throw new ArgumentException("Time machines are forbidden at the arcade");

    // Есть активное удержание
    if (nextState.HeldButtons != ButtonState.None)
    {
        // Посчитать бонус за удержание на текущий момент
        double holdDurTotal = Math.Min(newTime - nextState.HoldStartTime, GameRules.MaxTicksInHold);
        double holdDurSinceLastCalc = Math.Min(newTime - nextState.LastHoldRecalcTime, GameRules.MaxTicksInHold - (nextState.LastHoldRecalcTime - nextState.HoldStartTime));

        int holdDurFrames = (int)Math.Round(holdDurSinceLastCalc / GameRules.TicksPerFrame);
        long holdBonusPts = holdDurFrames * GameRules.HoldBonusFactor * nextState.HeldButtonCount;
        nextState.Score += holdBonusPts;
        nextState.HoldBonus += holdBonusPts;

        // Если держим дольше максимума, добавляем максимальный бонус и отпускаем кнопки
        if (holdDurTotal == GameRules.MaxTicksInHold)
        {
            long maxHoldBonusPts = GameRules.MaxHoldBonus * nextState.HeldButtonCount;
            nextState.HeldButtons = ButtonState.None;
            
            nextState.Score += maxHoldBonusPts;
            nextState.HoldBonus += maxHoldBonusPts;
        }

        nextState.LastHoldRecalcTime = newTime;
    }

    nextState.Time = newTime;

    return nextState;
}

class NoteHappening : Happening
{
    /// Клавиши, которые нужно нажать
    public ButtonState PressButtons { get; private set; }
    /// Те из них, которые можно дальше удерживать
    public ButtonState HoldButtons { get; private set; }

    public override List GetPotentialOutcomes(SystemState currentState, SimulationSystem system)
    {
        var variants = new List(3);
        currentState.NoteNumber += 1;

        var whatToDo = system.PlayerSkill.Decide(currentState, this, system);
        FindOutcomesAtTimeOffset(ref variants, whatToDo.Decisions, currentState, system, whatToDo.Offset);
        for (int i = 0; i < variants.Count; i++)
        {
            if(variants[i].Time < Time)
            {
                // Если какое-то событие было смещено назад во времени, то докрутить до центрального времени ноты, чтобы правильно работала логика симуляции
                var variant = variants[i];
                system.PassTime(variant, Time);
            }
        }

        return variants;
    }

    protected List FindOutcomesAtTimeOffset(ref List variants, NoteHitDecisionKind todos, SystemState s, SimulationSystem system, int timeOffset)
    {
        s = system.PassTime(s, (uint) (Time + timeOffset));
        s.LastNoteTime = s.Time;

        uint i = todos.Count();
        foreach(var option in todos.AllCases())
        {
            if(todos.HasFlag(option))
            {
                i--;
                var state = (i == 0 
                    ? s // экономим память, используем повторно одну из нод
                    : s.Clone()
                 );

                switch(option)
                {
                    case NoteHitDecisionKind.Hit:
                        state = NewStateForHitAndHold(state, system, false);
                        break;

                    case NoteHitDecisionKind.Switch:
                        state = NewStateForHitAndHold(state, system, true);
                        break;

                    case NoteHitDecisionKind.Wrong:
                        state = NewStateForWrong(state, system);
                        break;

                    case NoteHitDecisionKind.Miss:
                        state = NewStateForMiss(state, system);
                        break;
                }

                variants.Add(state);
            }
        }

        return variants;
    }

    /// Рассчёт исхода в случае просто отбития ноты
    protected SystemState NewStateForJustHitting(SystemState currentState, SimulationSystem system)
    {
        var decision = system.DecideNoteTimingByOffset((int)currentState.Time - (int)Time);

        // Начислить очки за ноту
        currentState.Score += system.GameRules.ButtonScore.Correct.For(decision.Kind) * Util.CountButtons(PressButtons);
        // Начислить жизни за ноту, или бонус за переполнение жизни
        if(currentState.Life < SystemState.MAX_LIFE)
        {
            currentState.Life += system.PlayerSkill.PickScore(system.GameRules.LifeScore.Correct);
            if (currentState.Life > SystemState.MAX_LIFE) currentState.Life = SystemState.MAX_LIFE;
        }
        else
        {
            currentState.Score += system.GameRules.LifeBonus;
        }

        // Увеличить комбо и начислить бонус за него
        currentState.Combo += 1;
        currentState.Score += system.GameRules.ComboBonus(currentState.Combo);

        // Если нота взята со смещением от идеального времени, записать это решение
        if(decision.Offset != 0)
        {
            currentState.RecordDecision(decision);
        }

        return currentState;
    }

    /// Рассчёт исхода в случае нажатия и удержания
    /// Бросить ли уже удерживаемые ноты (выполнить перестановку)
    private SystemState NewStateForHitAndHold(SystemState currentState, SimulationSystem system, bool resetHold)
    {
        var nextState = NewStateForJustHitting(currentState, system);

          if (nextState.HeldButtons != ButtonState.None)
          {
              // Учитываем потенциальные потери времени на отпускание и повторное нажатие тех же клавиш
              nextState.Time += system.PlayerSkill.FrameLossSwitching(nextState.HeldButtons, PressButtons);
          }

        // Если делаем перестановку
        if(resetHold)
        {
            // Замещаем удерживаемые клавиши и запоминаем принятое решение
            if(nextState.HeldButtons != ButtonState.None)
            {
                nextState.RecordDecision(new SwitchDecisionMeta(nextState.HeldButtons, HoldButtons));
            }
            nextState.HeldButtons = HoldButtons;
        }
        else
        {
            // Добавляем клавиши текущей ноты к удерживаемым
            nextState.HeldButtons |= HoldButtons;
        }

        // Сбрасываем таймер рассчёта бонуса за удержание
        nextState.HoldStartTime = nextState.Time;
        nextState.LastHoldRecalcTime = nextState.HoldStartTime;

        return nextState;
    }

    /// Рассчёт исхода при промахе
    private SystemState NewStateForMiss(SystemState currentState_, SimulationSystem system)
    {
        currentState.RecordDecision(new MissDecisionMeta(PressButtons));
        // Начислить очки
        currentState.Score += system.GameRules.ButtonScore.Correct.Worst * Util.CountButtons(PressButtons);
        // "Начислить" жизни
        currentState.Life += system.GameRules.LifeScore.Correct.Worst;
        if (currentState.Life < system.GameRules.SafetyLevel && Time < system.GameRules.SafetyDuration)
        {
            currentState.Life = system.GameRules.SafetyLevel;
        }

        // Комбо тоже потеряли
        currentState.Combo = 0;

        return currentState;
    }

    /// Рассчёт исхода при нажатии неверной клавиши
    private SystemState NewStateForWrong(SystemState currentState_, SimulationSystem system)
    {
        currentState.RecordDecision(new WrongDecisionMeta(PressButtons));
        // Начислить очки
        currentState.Score += system.PlayerSkill.PickScore(system.GameRules.ButtonScore.Wrong) * Util.CountButtons(PressButtons);
        // "Начислить" жизни
        currentState.Life += system.PlayerSkill.PickScore(system.GameRules.LifeScore.Wrong);
        if (currentState.Life < system.GameRules.SafetyLevel && Time < system.GameRules.SafetyDuration)
        {
            currentState.Life = system.GameRules.SafetyLevel;
        }

        // Сбросить комбо
        currentState.Combo = 0;

        return currentState;
    }
}

class GeneralSkill : Skill
{
    public override NoteHitDecision Decide(SystemState currentState, NoteHappening note, SimulationSystem system)
    {
        NoteHitDecisionKind rslt = NoteHitDecisionKind.Undecided_Invalid;

        if(currentState.HeldButtons == ButtonState.None)
        {
            // Ничего сейчас не удерживаем, поэтому подбираем что угодно
            rslt = NoteHitDecisionKind.Hit;
        }
        else
        {
            if((currentState.HeldButtons & note.PressButtons) == ButtonState.None)
            {
                // Мы что-то уже удерживаем, но новая нота с этим не пересекается
                if(note.HoldButtons != ButtonState.None)
                {
                    // Новую ноту тоже надо держать — можно добавить её, а можно отпустить старую и взять новую
                    rslt |= NoteHitDecisionKind.Hit;
                    rslt |= NoteHitDecisionKind.Switch;
                }
                else
                {
                    // Новую ноту держать не надо — просто берём как есть
                    rslt = NoteHitDecisionKind.Hit;
                }
            }
            else if((currentState.HeldButtons & note.PressButtons) != ButtonState.None)
            {
                // Новая нота мешает удерживать текущую ноту

                if(
                    !ProhibitMisses &&
                    (note.HoldButtons == ButtonState.None || AllowMissHold) // ещё не встречал карты, где надо было упускать холды
                )
                {
                    // Можно бросить старую и взять новую
                    rslt |= NoteHitDecisionKind.Switch;

                    // Но если есть лишние кнопки, можно сделать WRONG и получить хоть какие-то очки
                    if(RuleSet.ButtonTotalCount - currentState.HeldButtonCount >= Util.CountButtons(note.PressButtons))
                    {
                        rslt |= NoteHitDecisionKind.Wrong;
                    }
                    else
                    {
                        // Кнопок нам не хватает, так что остаётся только проводить эту ноту взглядом
                        rslt |= NoteHitDecisionKind.Miss;
                    }
                } 
                else
                {
                    // В режиме запрета на пропуски единственный вариант — переключиться на новую ноту
                    rslt = NoteHitDecisionKind.Switch;
                }
            }
        }

        return new NoteHitDecision { Decisions = rslt, Offset = 0 };
    }
}

public void InsertCheckpointsFor(RuleSet rules)
{
    uint lastHoldStartTime = 0;
    uint checkpointIdCounter = 0;
    uint skipCounter = 0;
    int lifeLossInSegment = 0;
    ButtonState busyButtons = ButtonState.None;

    bool needCheckpoint = false;

    for (int i = 0; i < Events.Count; i++)
    {
        Happening evt = Events[i];

        // После конца уровня ничего не добавляем
        if (evt is EndOfLevelHappening) break;

        if (evt is NoteHappening note)
        {
            if (note.HoldButtons != ButtonState.None)
            {
                // Начало какого-то удержания, сбросить все счётчики
                lastHoldStartTime = note.Time;
                needCheckpoint = true;
                skipCounter = 0;
                lifeLossInSegment = 0;
                busyButtons = note.HoldButtons;
            }
            else if (evt.Time > (lastHoldStartTime + rules.MaxTicksInHold) && needCheckpoint)
            {
                // Теоретически здесь мог быть достигнут максимальный бонус, поэтому пропускаем нужное количество нот и добавляем чекпойнт
                if (skipCounter >= Math.Max(rules.ComboBonusMinCombo, lifeLossInSegment / rules.LifeScore.Correct.Cool) + 1)
                {
                    checkpointIdCounter++;
                    var ckp = new OptimizationCheckpointHappening(evt.Time + 1, checkpointIdCounter);
                    if (Program.Verbose)
                        Console.Error.WriteLine("[PREP] Time since last hold is more than {0} (cur={1}, since={2}), skipped {4} notes, insert checkpoint {3}", rules.MaxTicksInHold, evt.Time, lastHoldStartTime, checkpointIdCounter, skipCounter);
                    Events.Insert(i + 1, ckp);
                    i++;
                    needCheckpoint = false;
                }
                else skipCounter++;
            }
            else
            {
                if (busyButtons != ButtonState.None)
                {
                    if ((busyButtons & note.PressButtons) != ButtonState.None)
                    {
                        // Найдена совпадающая нота, подсчитываем теоретическую просадку жизней
                        if (RuleSet.ButtonTotalCount - Util.CountButtons(busyButtons) >= Util.CountButtons(note.PressButtons))
                        {
                            // Достаточно свободных кнопок, чтобы нажать Wrong
                            lifeLossInSegment += Math.Abs(rules.LifeScore.Wrong.Cool);
                        }
                        else
                        {
                            // Свободных кнопок нет, эту ноту мы теряем
                            lifeLossInSegment += Math.Abs(rules.LifeScore.Wrong.Worst);
                        }
                    } 
                    else
                    {
                        // Найдена не-совпадающая нота, мы можем её взять и восстановить часть жизней
                        lifeLossInSegment -= Math.Abs(rules.LifeScore.Correct.Cool);
                        // Мы не знаем начальное состояние счётчика жизней, поэтому бонус за переполнения в расчёт не идёт
                        if (lifeLossInSegment <= 0) lifeLossInSegment = 0;
                    }
                }
            }
        }
    }
}

    var nextHappening = Provider.Timeline.NextHappeningFromTime(node.state.Time);
    if (nextHappening != null)
    {
        var nextStates = nextHappening.GetPotentialOutcomes(node.state, Provider.System);
        if (nextHappening is OptimizationCheckpointHappening)
        {
            var ckp = (OptimizationCheckpointHappening)nextHappening;
            var chkState = nextStates[0];
            checkpointSemaphore.WaitOne();
            if(!checkpointToMaxScore.ContainsKey(ckp.CheckpointID))
            {
                checkpointToMaxScore.Add(ckp.CheckpointID, chkState.Score);
            }
            else
            {
                var curMaxScore = checkpointToMaxScore[ckp.CheckpointID];
                if(curMaxScore > chkState.Score)
                {
                    // Мы уже знаем, что в этой точке можно иметь большую сумму очков, так что отбрасываем эту ноду
                    if(Program.Verbose)
                        Console.Error.WriteLine("[SOLVE] found worse solution score={0} curMax={1} checkpointID={2}", chkState.Score, curMaxScore, ckp.CheckpointID);

                    node = null;
                    checkpointSemaphore.Release();
                    continue;
                }
                else if (curMaxScore < chkState.Score)
                {
                    // Обновляем максимум очков в этой точке
                    checkpointToMaxScore[ckp.CheckpointID] = chkState.Score;
                }
            }
            node.state = chkState;
            checkpointSemaphore.Release();
        }

>scoresolver --timeline pkg_hard.bin --level 2
[MAIN] Reading timeline...
[REFS] AllCool=140000
[REFS] LifeBonusNoteCount=213
[REFS] LifeBonus=2130
[REFS] ComboBonus=62000
[REFS] ChanceBonus=0 (ChanceCount=0)
[REFS] TOTAL REFS=204130
[MAIN] 277 notes, RefScore=204130
[MAIN] Setting up simulation...
[MAIN] Created 5 checkpoints
[MAIN] Local Mode
[MAIN] Using strategy: checkpointing
[MAIN] Starting solver
[SCHED] Scheduler Thread Started
[+0s] Found solution with score=205140, attain=77.29
[+0s] Found solution with score=208890, attain=76.28
[+0s] Found solution with score=209640, attain=77.29
[+0s] Found solution with score=210690, attain=78.44
[+0s] Found solution with score=214570, attain=75.73
[+0s] Found solution with score=215320, attain=76.73
[+0s] Found solution with score=222590, attain=75.19
[+0s] Found solution with score=223300, attain=76.97
[+0s] Found solution with score=224350, attain=74.92
[+0s] Found solution with score=224350, attain=74.92
[+0s] Found solution with score=227080, attain=75.19
[+0s] Found solution with score=227790, attain=76.97
[+0s] Found solution with score=228840, attain=74.92
[+0s] Found solution with score=230300, attain=73.44
[+0s] Found solution with score=231010, attain=75.22
[+0s] Found solution with score=234690, attain=71.12
[+0s] Found solution with score=235400, attain=72.9
[+0s] Found solution with score=236520, attain=74.88
[+0s] Found solution with score=237020, attain=82.45
[+0s] Found solution with score=237430, attain=76.75
[+0s] Found solution with score=241410, attain=80.13
[SCHED] Scheduler Thread Ended
[MAIN] Solved in 0.3134061s
[MAIN] Good solutions: 1, bad solutions: 0, checked solutions: 21 across 145497 nodes
[MAIN] RAM usage peaked at 0MB

===== MAX SCORE =====
score: 241410, attain 80.13
[Time 21.606s / Combo 37] WRONG:   X
[Time 21.846s / Combo 0] WRONG:   X
[Time 23.766s / Combo 4] HOLD: +   O
[Time 25.446s / Combo 6] WRONG:    O
[Time 25.686s / Combo 0] WRONG:    O
[Time 26.166s / Combo 0] WRONG:   X
[Time 26.646s / Combo 0] WRONG:   X
[Time 27.606s / Combo 2] HOLD: + S
[Time 28.566s / Combo 2] WRONG:    O
[Time 28.806s / Combo 0] WRONG:    O
[Time 29.286s / Combo 0] WRONG:  S
[Time 29.526s / Combo 0] WRONG:  S
[Time 30.006s / Combo 0] WRONG:   X
[Time 30.486s / Combo 0] WRONG:   X
[Time 31.446s / Combo 2] HOLD: +T
[Time 32.646s / Combo 2] WORST: T  O
[Time 1:11.526 / Combo 46]    O -> NONE
[Time 1:19.206 / Combo 58] T    -> NONE
[Time 1:26.886 / Combo 71]  S   -> NONE
[Time 1:34.566 / Combo 83]   X  -> NONE
[Time 1:53.046 / Combo 114] WRONG: T
[Time 1:53.286 / Combo 0] WRONG: T
[Time 1:55.926 / Combo 6] HOLD: +   O
[Time 1:56.886 / Combo 6] WRONG:    O
[Time 1:57.126 / Combo 0] WRONG:    O
[Time 1:57.606 / Combo 0] WRONG: T
[Time 1:57.846 / Combo 0] WRONG: T
[Time 1:59.766 / Combo 4] HOLD: +  X
[Time 2:00.726 / Combo 4] WRONG:   X
[Time 2:00.966 / Combo 0] WRONG:   X
[Time 2:01.446 / Combo 0] WRONG:    O
[Time 2:01.686 / Combo 0] WRONG:    O
[Time 2:02.166 / Combo 0] WRONG: T
[Time 2:02.646 / Combo 0] WRONG: T
[Time 2:03.606 / Combo 2] HOLD: + S
[Time 2:04.326 / Combo 2] WORST:  S
[Time 2:04.806 / Combo 0] WORST:  S
[Time 2:05.286 / Combo 0] WORST:    O
[Time 2:05.526 / Combo 0] WORST:    O
[Time 2:05.766 / Combo 0] WORST:    O
[Time 2:06.006 / Combo 0] WORST:    O
[Time 2:06.246 / Combo 0] WORST:    O
[Time 2:06.486 / Combo 0] WORST:    O
[Time 2:06.966 / Combo 0] WORST: T
[Time 2:07.446 / Combo 0] WORST: T
[Time 2:08.406 / Combo 0] WORST:    O
[Time 2:21.606 / Combo 24] WRONG: T
[Time 2:22.086 / Combo 0] WRONG: T
[Time 2:36.966 / Combo 20] WRONG:    O
[Time 2:37.446 / Combo 0] WRONG:    O

public override NoteHitDecision Decide(SystemState currentState, NoteHappening note, SimulationSystem system)
{
    if(
        note.HoldButtons != ButtonState.None &&
        // Увеличиваем число удерживаемых нот
        (((note.PressButtons & currentState.HeldButtons) == ButtonState.None &&
        LastPlayDecisionAtNumber(currentState.NoteNumber) == NoteHitDecisionKind.Hit) ||

        // или переключаемся на несвязанное удержание с большим числом нот
        (Util.CountButtons(note.HoldButtons) > Util.CountButtons(currentState.HeldButtons) &&
         LastPlayDecisionAtNumber(currentState.NoteNumber) == NoteHitDecisionKind.Switch)) &&

         // Кроме случаев, если следующим будет точно Max Bonus
         (currentState.HeldButtons == ButtonState.None || (currentState.NoteNumber != MaxNoteNumber && 
           (NextHittedNoteFromTime(note.Time, currentState).Time - currentState.Time) < system.GameRules.MaxTicksInHold))
      )
    {
        // Пока прибито гвоздями на Early Cool
        return new NoteHitDecision { Offset = -system.GameRules.NoteTiming.Cool, Decisions = LastPlayDecisionAtNumber(currentState.NoteNumber) };
    }

    if(
        currentState.HeldButtons != ButtonState.None &&
        (
            // Уменьшаем число удерживаемых нот
            (Util.CountButtons(note.HoldButtons) < Util.CountButtons(currentState.HeldButtons) &&
             LastPlayDecisionAtNumber(currentState.NoteNumber) == NoteHitDecisionKind.Switch) ||
             // Или увеличиваем, но эту ноту уже мы дотянем до максимума
             (currentState.HeldButtons != ButtonState.None && (currentState.NoteNumber != MaxNoteNumber &&
           (NextHittedNoteFromTime(note.Time, currentState).Time - note.Time) >= system.GameRules.MaxTicksInHold))
        )
     )
    {
        // Пока прибито гвоздями на Late Cool
        return new NoteHitDecision { Offset = system.GameRules.NoteTiming.Cool, Decisions = LastPlayDecisionAtNumber(currentState.NoteNumber) };
    }

    // С прошлой попытки прохождения решение не изменилось
    return new NoteHitDecision { Offset = 0, Decisions = LastPlayDecisionAtNumber(currentState.NoteNumber) };
}