vladkorotnev 11 июн в 09:05

Полная ×○□△ — поиск наилучшего прохождения уровня в ритм-игре алгоритмическим путём

Средний

23 мин

4.3K

Блог компании Timeweb CloudПрограммирование*Математика*Читальный залИгры и игровые консоли

Кейс

У каждого из нас помимо хобби есть ещё и "времяпрепровождение" — как раз для тех случаев, когда времени на руках оказывается слишком много и надо бы его проводить куда подальше.

В моём случае таким занятием ещё со времён актуальности PSP стала ритм-игра под названием "Project DIVA". Базовая концепция максимально простая — на экране появляются мишени, к которым летят иконки клавиш, оные и нужно нажимать в ритм песни.

Вскоре после переезда в Японию я узнал, что есть куда более серьёзная версия этой игры — Project DIVA Arcade. Однако и некоторые игровые механики в ней существенно отличаются от её карманного прородителя. Именно они среди прочего и делают эту игру уникальной — возможно, единственной ритм-игрой "с открытой концовкой".

Давайте же в этот раз разберём правила игры, создадим имитационную модель игрового процесса и посмотрим, можно ли получить преимущество в игре путём вычислений, или же уже всё посчитано до нас :-)

Концепция игры

На игровом автомате у нас есть четыре полуяйцеобразных клавиши с иконками от плейстейшена, а также сенсорный слайдер:

После выбора песни, на мониторе начинает твориться какая-то дичь, а поверх всего этого появляются мишени, к которым летят «ноты» в форме тех же иконок, что и на клавишах:

Как только иконка становится максимально концентричной с мишенью, то нужно нажать клавишу с соответствующим рисунком:

В случае, если несколько нот прилетят к своим мишеням одновременно, игра подсвечивает их красным, и соединяет линией:

Если же под мишенью есть надпись HOLD, то эту клавишу можно продолжить удерживать, получая таким образом бонус за удержание в течение 5 секунд максимум:

Уникальная фишка

Однако, даже попадая во все тайминги практически идеально, мы обнаруживаем, что полученное количество очков весьма далеко даже от последней строчки глобальных рейтингов!

Откуда у людей в лидерборде сверху аж на 17к очков больше, если из-за 15 FINE мы потеряли лишь 3000?

Спойлер: в отличие от обычных ритм-игр, где единственная цель — просто идеально нажимать на клавиши, в Диве прохождение уровня на идеальный результат не гарантирует максимального количества очков! Тут уже приходится подключать стратегию, которая у начинающего игрока только и вызовет желание сказать "Чёрт возьми, да как же он лажает!"

Дисклеймер

Дядя, я же не настоящий математик, я просто ЛаТеХ нашёл!

Сразу должен оговориться, что знаниями матана я очень сильно не блистал даже тогда, когда в нас его усердно старались запихивать в универе. Кодить что-то настолько запутанное и требующее сильной оптимизации тоже доселе не доводилось.

Посему всё нижеописанное настоящим программистам, скорее всего, покажется каким-то творением последователя Терри Дэвиса, а настоящим математикам — выкладками стабильного двоечника, который интеграл в жизни использовал только единожды, дабы упавшие в унитаз ключи выудить.

Задачу в конечном итоге всё-таки хочется решить полноценно — во-первых, это интересно, во-вторых, большинство игроков по сей день считает вручную с использованием вспомогательного листа в экселе.

Поэтому если у вас есть советы (кроме как "засунуть его назад и переписать на чём-нибудь нормальном") — не забудьте отписаться в комментариях!

Правила игры

Прежде чем начинать писать модель игры, давайте проанализируем записи игр и определим правила.

Как и в любой ритм-игре, основная задача игрока — вводить комбинации клавиш ("ноты") с клавиатуры в соответствии с заданными в программе таймштампами.

Очки

За каждую отбитую ноту начисляется определённое количество очков, в зависимости от точности попадания. В случае нажатия неверной клавиши в пределах схожего тайминга, впрочем, очки тоже начисляются — но в меньшем количестве.

	Точность	Очки	Очки при WRONG эквивалентной точности
COOL	± 30мс	500	250
FINE	± 70мс	300	150
SAFE	± 100мс	100	50
SAD	± 130мс	50	30
WORST	клавиша не нажата	0	-

В отличие от прочих правил, если нота состоит из нескольких клавиш, то начисляются очки соответственно количеству клавиш. Например, Fine из трёх клавиш даст нам 3 × 300 = 900 очков.

Жизни

Также вверху экрана есть индикатор "жизней", который всегда стартует с 50% (127), заполняется по мере попадания по нотам, и расходуется в случае непопадания. Это правило различается в зависимости от уровня сложности, но так как глобальные рейтинги сводятся только по сложностям Hard и Extreme, то здесь и дальше будем рассматривать только их.

	Прирост жизней (HARD)	Прирост жизней (EXTREME)	...при WRONG (HARD)	...при WRONG (EXTREME)
COOL	2	2	-3	-6
FINE	1	1	-6	-8
SAFE	0	0	-9	-10
SAD	-10	-15	-15	-20
WORST	-20	-25	-20	-25

Даже если нота состоит из нескольких клавиш, то в счётчик жизней идёт только одно приращение. Если же количество жизней уже равно 100% (255), то вместо положительного приращения жизней начисляется бонус в +10 очков.

В начале песни счётчик жизней ограничен снизу значением, равным 76 — для Hard/Extreme ограничение длится ровно 30 секунд. В течение этого времени проиграть невозможно, даже если очень сильно захотеть.

Комбо

За комбо, конечно же, тоже начисляются бонусные очки. Вычисляется этот бонус по достаточно простой формуле:

$K(combo) = \begin{cases}combo \ge 10, &{min(combo, 50) * 5} \\ combo \lt 10, & 0\end{cases}$

Даже если нота состоит из нескольких клавиш, то бонус начисляется лишь один раз. Комбо при этом нарастает только при попаданиях в тайминги COOL или FINE, и сбрасывается во всех остальных случаях.

Удержание

"Открытость" геймплею добавляет, как я думаю, именно эта механика! Даже в карманной Диве удерживать ноты нужно было в течение определённого времени — но в аркадной версии ограничение убрали. На иконке ноты появляется лишь надпись HOLD, обозначающая, что её можно начать удерживать.

Теперь нам начисляется по 10 очков в кадр за каждую удерживаемую клавишу. При этом после 5 секунд отсчёт останавливается, и даётся дополнительный бонус по 1500 очков за каждую клавишу. Однако, если до этого момента начать удерживать следующую ноту, то пятисекундный таймер сбрасывается и начинает отсчёт сначала!

В предыдущем поколении аркадной дивы таймер был в 5 секунд + 1 кадр — из-за чего на части песен в топах рейтингов застряли результаты, которые теперь невозможно побить даже теоретически, из-за разницы в эти самые несчастные 10-40 очков.

Интересный факт: из-за того, что опрос клавиатуры идёт по Vsync, а вот начисление бонуса по обычному таймеру, то в зависимости от дрейфа тактовых частот компонентов автомата, на некоторых из них в некоторых песнях легче получить Max Hold, чем на других. Также было замечено влияние температуры в комнате на это, но в весьма узких пределах :-)

Процент достижения

Вместе с очками вычисляется так же и "процент достижения" (達成率), который нужно удержать выше 60% для Hard, или выше 70% для Extreme. Считается он исходя из "опорных очков", являющихся суммой всех нот с таймингом COOL, комбо-бонуса и бонуса жизней. Можно свести это всё в одну формулу и посчитать для конкретной песни и уровня:

$R = 10\times(n - \frac{L_{max} - L_0}{L_{COOL}}) + \sum_{i = 0..n} K(i) + \sum_{i = 0..n}(P_{COOL}\times B[i])$

где R — опорные очки, n — число нот в песне, K(i) — комбо-бонус при комбо равном i, $P_{COOL}$ — цена COOL в очках на текущем уровне сложности, B[i] — количество клавиш в ноте на i-той позиции, $L_{max}$ — максимальное значение счётчика жизней, — начальное значение счётчика жизней, $L_{COOL}$ — количество начисляемых жизней за один COOL.

Дробь в первом члене выражения является константой, так как изначальные и максимальные значения жизни для нашей сложности известны, как и цена одного COOL в жизнях, поэтому можно упростить выражение до:

$R = 10\times max(0, (n - 64)) + \sum_{i = 0..n} K(i) + \sum_{i = 0..n}(P_{COOL}\times B[i])$

Впоследствии процент достижения можно в любой момент посчитать как сумму отношения очков без учёта слайдеров и удержаний к опорным очкам, а также отношения отмасштабированных очков за удержания к опорным очкам (но не более 5%):

$A = 100\times\frac{S - S_{slide} - S_{hold}}{R} + min(5, \frac{S_{hold}\times K_{hold}}{R})$

где A — процент достижения от 0 до 100+%, S — текущие очки на момент рассчёта, R — опорные очки, $K_{hold}$ — константа (20 для Extreme, 50 для Hard).

Игровая тактика

Исходя из этих правил, можно уже определить несколько стилей игры:

«Казуальный» — просто отбиваем все ноты в порядке их появления, стараясь попадать максимально точно. В таком случае мы гарантированно получаем рейтинг Perfect, но не более того.
«Оптимизированный» — играем точно так же, но ищем такие перестановки удержаний, в которых $S_{hold}$ будет максимальным. Как пример — начало уровня Adolescence/EXTREME: если играть вслепую, то сначала у нас получается короткое удержание двух клавиш, а потом длинное удержание одной. Если же первую клавишу в момент появления второй «бросить», то получается короткое удержание одной, а затем длинное удержание двух, что даёт примерно в два раза больше очков.
За счёт того, что в пределах следующих 5 секунд эти клавши не появляются, можно ещё заморочиться с тем, чтобы в первую попасть раньше, а во вторую позже — тогда мы получим преимущество ещё в пару десятков очков за счёт этого.

И самый главный, который поможет нам попасть в рейтинги — «жадный», оптимизированный не по проценту достижения, а по сумме очков.

В таком случае, нам нужно найти такое решение, которое придерживается лишь A >= 60 (70 для Extreme), и максимизирует (S + $S_{slide}$ + $S_{hold}$ ).

$S_{slide}$ мы можем пренебречь — так как слайдер на клавиатуру никак не влияет, то нет смысла выбивать что-то кроме COOL на слайд-нотах.

мы можем менять в узких пределах, меняя тайминги попадания в ноты, или не попадая в них вообще — таким образом отказываясь от накопленного комбо-бонуса, бонуса жизней, и очков за конкретную ноту.

$S_{hold}$ мы можем менять в гораздо более широких пределах, удерживая ноты как можно дольше.

В конечном итоге, формальная формулировка задачи уже звучит не так просто: нужно найти такой путь прохождения уровня, при котором прирост в $S_{hold}$ будет существенно больше, чем потеря в , вызванная специально совершёнными ради этого ошибками, при удержании счётчика жизней выше 0, и оканчивающийся с A ≥ 60 (либо 80 для Extreme).

Весёлую игру в унылый матан из заплесневелого задачника с забытых всеми полок университетской библиотеки мы превратили — погнали теперь её моделировать!

Описание игрового процесса

Для пущего удобства и лёгкости распараллеливания, давайте представим всю игру как последовательность переходов между состояниями. Переходами между состояниями будут являться как отбития нот, так и просто промежутки времени между ними.

В качестве описания состояния будем использовать структуру:

class SystemState
{
    /// Является ли состояние конечным
    public bool IsFinal = false;
    /// Удерживаемые кнопки
    public ButtonState HeldButtons = ButtonState.None;
    /// В какой момент времени началось удержание
    public uint HoldStartTime = 0;
    /// В какой момент времени последний раз были начислены очки за удержание
    public uint LastHoldRecalcTime = 0;
    /// Текущее комбо
    public uint Combo = 0;
    /// Текущая сумма очков
    public long Score = 0;
    /// Текущие очки, начисленные за удержание
    public long HoldBonus = 0;
    /// Текущие очки, начисленные за слайдеры
    public long SlideBonus = 0;
    /// Текущие жизни
    public int Life = DEFAULT_LIFE;
    /// Текущий процент прохождения
    public int Attain = 0;
    /// Текущее время
    public uint Time = 0;
    /// Количество удерживаемых в текущий момент кнопок
    public uint HeldButtonCount
    {
        return Util.CountButtons(HeldButtons);
    }
    /// Является ли состояние гарантированно тупиковым
    public bool IsFailed
    {
        return Life <= 0;
    }
}

При этом каждый переход имеет одно исходное состояние, но может иметь множество конечных — в зависимости от того, какое решение было принято в тот момент игры.

Например, событие «нота ○-HOLD» будет иметь следующие потенциальные исходы:

Если ни одна клавиша сейчас не удерживается, то единственным исходом будет нажать эту клавишу и продолжать её удерживать
Если ○ сейчас удерживается, то количество вариантов растёт:
- Если есть свободные клавиши, можно нажать на другую, чтобы всё равно получить очки за WRONG
- Если свободных клавиш нет, можно пропустить эту ноту, и получить штраф в счётчик жизней
Если сейчас удерживается любое количество других клавиш, кроме ○
- Можно отпустить их, и нажать ○ («перестановка»)
- Можно добавить ○ к остальным удерживаемым клавишам

Также есть возможность подвигать тайминги, отбивая ноты не строго как прописано, а на пару кадров раньше или позже, чтобы получать ранний/поздний COOL/FINE — но для простоты вычислений пока что обойдёмся лишь строгим отсчётом по ровному COOL.

Уже тут закрадывается подозрение, что гейм-дизайнеры подсунули нам форк-бомбу, но всё же давайте опишем эти события. Начнём с течения времени:

Функция описания течения времени

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<SystemState> GetPotentialOutcomes(SystemState currentState, SimulationSystem system)
    {
        var variants = new List<SystemState>(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<SystemState> FindOutcomesAtTimeOffset(ref List<SystemState> 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;
    }

    /// Рассчёт исхода в случае нажатия и удержания
    /// <param name="resetHold">Бросить ли уже удерживаемые ноты (выполнить перестановку)</param>
    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 };
    }
}

Конвертация видео геймплея или каких-то других смутно похожих на карту игры бинарных данных остаётся читателю в качестве домашнего задания :-)

Поиск решения брутфорсом

Итак, нам явно подсунули форк-бомбу, а мы задаёмся вопросом — долбанёт? Да вроде не должно, так что давайте её запускать!

Создадим простенькие интерфейсы для очереди задач и свалки результатов, чтобы потом параллелить всё это на небольшой кластер из тредтрипперов проще было:

interface WorkProvider
{
    /// Получить следующую необработанную ноду пути решения, если есть
    SystemState DequeueWork();
    /// Передать новую необработанную ноду пути решения для дальнейшей обработки
    void EnqueueWork(SystemState work);
    /// Симулируемый таймлайн с набором переходов между состояниями
    HappeningSet Timeline { get; }
    /// Симулируемая система с набором правил
    SimulationSystem System { get; }
}

interface WorkReceiver
{
    /// Сохранить финальное решение прохождения уровня
    void ReceiveSolution(SystemState finalNode, WorkProvider from);
}

В том виде, как мы объявили модели событий, алгоритм симуляции получается достаточно простым:

Берём из очереди начальное состояние (не обязательно нулевое — возможно, уже какие-то события были симулированы до этого)
Просчитываем все возможные исходы
- Окончательные (IsFinal == true ) проверяем на конечное условие по проценту прохождения и отдаём в WorkReceiver
- Запоротые (IsFailed == true) просто игнорируем
- Прочие отдаём назад в WorkProvider, чтобы остальные ноды могли взять их оттуда и просчитать решение дальше
Если в WorkProvider есть какая-то ещё непросчитанная нода (или мы приберегли таковую для себя, чтобы сэкономить на XPC/обменах по сети), то начать просчитывать уже её

Записываем это в виде кода (обвязка для многопоточности вся оставлена за скобками для сокращения статьи):

override protected void SolveFromNodeEx(SystemState startNode)
{
    var node = startNode;
    while (node != null && !interruptFlag)
    {
        // Находим следующее событие в таймлайне
        var nextHappening = Provider.Timeline.NextHappeningFromTime(node.Time);
        if (nextHappening != null)
        {
            // Считаем новые варианты состояний после этого события
            var nextStates = nextHappening.GetPotentialOutcomes(node, Provider.System);
            for (int i = 0; i < nextStates.Count; i++)
            {
                var nextState = nextStates[i];

                if (nextState.IsFinal && !nextState.IsFailed)
                {
                    // Нашли окончательное решение
                    var atn = Provider.System.AttainPoint(nextState);
                    if (atn >= Provider.System.GameRules.ClearAttain)
                    {
                        // Уровень пройден, можно сохранить
                        Receiver.ReceiveSolution(node, Provider);
                        node = null;
                    }
                    else
                    {
                        // Уровень не пройден, выбросить
                        if(Program.Verbose)
                            Console.Error.WriteLine("[SOLVE] found bad solution atn={0}, minimum={1}, discarded", atn, Provider.System.GameRules.ClearAttain);
                        node = null;
                    }
                }
                else if (nextState.IsFailed)
                {
                    // Найден тупиковый вариант
                    if(Program.Verbose)
                        Console.Error.WriteLine("[SOLVE] found bad solution track life={0}", nextState.Life);
                    node = null;
                }
                else
                {
                    if (i == nextStates.Count - 1)
                    {
                        // Немножко экономим на обменах по сети и сохраняем дальнейшую работу для себя
                        node = nextState;
                    }
                    else
                    {
                        // Отдаём прочую работу другим воркерам на локальной машине или по сети
                        SolveFromNodeAsync(nextState);
                    }
                }
            }

        }
        else throw new Exception("Кто-то где-то что-то не продумал до конца и всё всралось, начальник!");
    }
}

Испытаем на достаточно простой песне — всё тот же Packaged на Hard. Берём игровой ноутбук ~~два ядра два гига~~ на Core i7 10 поколения и 16 гигов оперативки. Запускаем, ждём...

Целый час как под наркозом я работал нодовозом, ой-ой-ой!

Ну... Из плюсов — это больше очков, чем при прохождении «казуальным» способом (который на этой песне эквивалентен «оптимизированному»). Но если на такую простую песню потребовался целый час, то на что-нибудь со сложности Extreme, где нот может быть в разы больше, у нас уйдёт время жизни небольшой галактики.

Переписывание кода для минимизации аллокаций (в частности, выкидывание лишней обёртки DecisionPathNode вокруг каждого шага и отказ от сохранения всего дерева решений) помог ускорить процесс, но не то чтобы существенно.

Преждевременная неоптимизация

Если бы за каждую пройденную на максимум песню мне бы давали по баксу, то итоговых 200 баксов как раз хватило бы на то, чтобы посчитать одну из них где-то в кластерах Амазонки. Поэтому придётся вместо кошелька опять подключать мозги.

Представим, что у нас есть таймлайн:

Рассмотрим два крайних случая — X_hold удерживается до максимума, либо бросается на второй ноте ради сохранения комбо.

В первом случае теоретически максимальное количество очков за этот сегмент:

$S_1 = n \tau_{max} S_{H'} + S_{COOL} \times 2 + S_L \times 1 + K(k) + S_{H_{max}}$

где $\tau_{max} = 5000$ (из правил игры), $S_{H'}$ — очки за 1 мс удержания, — бонус за переполнение счётчика жизни, n — кол-во удерживаемых клавиш в течение сегмента, k — комбо на момент начала сегмента.

Во втором случае:

$S_2 = n \tau S_{H'} + S_{COOL} \times 6 + S_{L}\times6 + \sum_{k_i = 0..6} K(k+k_i)$

Тогда первый случай выгоднее второго, если:

$(\tau_{max} - \tau)nS_{H'} + S_{H_{max}} > S_{COOL}\times4+S_L\times5+\sum_{k_i = 0..6}K(k + k_i - 1)$

Можно заметить, что все члены слева относятся лишь к очкам за удержание, а справа — к очкам за попадание по нотам.

В таком случае можно предположить:

Решения, принятые в этом сегменте, будут влиять на суммарные очки только до момента получения max hold бонуса.
Соответственно, имеет смысл терять комбо и продолжать удерживать первую ноту только в том случае, если сумма очков после момента теоретического max hold бонуса меньше, чем сумма очков в случае с удержанием и пропусками нот ради получения max hold, после:
- 11 нот (10 нот для начала комбо-бонуса, + 1 нота), либо
- числа нот, равного отношению теоретически потерянной жизни за сегмент к восстановлению жизни за одну успешную ноту

Пишем расстановку чекпоинтов по этому правилу:

Очередной длинный говнокод

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

И добавляем код, останавливающий вычисления на чекпоинте, если очки в момент его достижения заведомо ниже, чем на каком-то из других рассчитываемых вариантов:

Hidden text

    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();
        }

Пробуем заново:

Попутно я не забыл правильно указать уровень сложности, поэтому нашёлся результат с большим числом очков, чем в прошлом запуске

Как говорится, ну нихренажсебе! Время поиска решения скостилось на четыре порядка!

Берём распечатку решения

Hidden text

>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

И идём в аркаду проверять!

Результат, как говорится, прямо в лицо — "казуальное" прохождение:

И подобранное нашей программой — вроде бы не сильно сложнее, но 22 тыщи очков к рукам прилипло!

Два прохода, три прихлопа

Теперь, когда мы уже имеем способ нахождения наиболее перспективного маршрута, осталось лишь максимизировать его за счёт сдвигов таймингов. Рефакторим всё так, чтобы логика принятия решения и сдвига таймингов оказалась отделена от логики самих рассчётов — я перенёс её в класс PlayerSkill, чтобы заменять его в зависимости от требуемого решения.

После этого выводим правила, по которым можно оптимизировать тайминги. Ограничимся пока что пределами границ рейтинга COOL:

Следует придерживаться ранней границы COOL, если:
- Взятие ноты приведёт к увеличению количества удерживаемых клавиш
- Краевой случай: если после этого увеличения мы ничего не нажимаем до тех пор, пока не получим Max Hold.
Поздней границы следует придерживаться, если:
- Взятие ноты приведёт к уменьшению количества удерживаемых клавиш
- Описанный выше краевой случай
В прочих вариантах при взятии ноты с таймингом COOL конкретное время в пределах границ этого рейтинга значения не имеет

Основные случаи очевидны — стараемся брать большее количество клавиш быстрее, чтобы начать набирать больше очков как можно скорее, и стремимся не отпускать их как можно дольше.

Для краевого случая же лучше проверить гипотезу формальным доказательством. Рассмотрим участок карты, где мы подбираем последовательно три холда (так будет наиболее наглядно):

Для такого отрезка, где мы набираем последовательно всё больше и больше холдов, а затем прожимаем их до максимума общее число очков будет равно:

$S_i = S_{H'}\tau + S_{H'}(\tau - t_1) + S_{H'}(\tau - t_1 - t_2) + 3S_{COOL} + S_{H_{MAX}} = \\ = S_{H'}(3\tau - 2t_1 - t_2) + 3S_{COOL} + S_{H_{MAX}}$

Где , , — задержка от начала удержания соответствующей клавиши до нажатия следующей, $\tau$ — суммарное время удержания, $S_{H'}$ — очки за 1 мс удержания одной клавиши, $S_{H_{MAX}}$ — Max Hold бонус.

При этом каждый добавленный холд обнуляет отсчёт таймера наступления Max Hold, то есть $\tau$ у нас зависит от всех трёх времён следующим образом:

$\tau = \begin{cases} t_{n_{max}} < \tau_{max}, & \sum_n t_n \\ t_{n_{max}} \ge \tau_{max}, & \sum_{n-1} t_n + \tau_{max} \end{cases}$

Подставляем его для случая с тремя нотами, дотянутыми до максимума, в изначальное выражение, и смотрим на изначальный вариант без оптимизации:

$S_i = S_{H'}(3t_1 + 3t_2 + 3\tau_{max} - 2t_1 - t_2) + 3S_{COOL} + S_{H_{MAX}} = \\ = S_{H'}(t_1 + 2t_2 + 3\tau_{max} ) + 3S_{COOL} + S_{H_{MAX}}$

Таким образом, для максимизации полученных очков нам нужно максимизировать значение $\tau$ и минимизировать значения , . Из-за того, что в конечном итоге и будет приравнено к 5000 мс, а , заведомо меньше мс, наиболее оптимальным решением будет занизить, взяв вторую ноту раньше, а завысить, взяв третью ноту позже. Примем наше некое смещение во времени за $\alpha$ и посчитаем его одинаковым (например, идеальный случай — вторую ноту берём на первой миллисекунде раннего COOL, а третью — на последней). Тогда:

$S_i = S_{H'}(3(t_1 - \alpha + t_2 + \alpha + t_3) - 2(t_1 - \alpha) - (t_2 + \alpha)) + 3S_{COOL} + S_{H_{MAX}} = \\ = S_{H'}(3t_1 + 3t_2 + 3t_3 - 2t_1 + 2\alpha - t_2 - \alpha) + 3S_{COOL} + S_{H_{MAX}} = \\ = S_{H'}(t_1 + 2t_2 + 3t_3 + \alpha) + 3S_{COOL} + S_{H_{MAX}}$

Подставляем финальное значение $t_3 =\tau_{max}$ и сравниваем множители при $S_{H'}$ :

$(t_1 + 2t_2 + 3\tau_{max} + \alpha) - (t_1 + 2t_2 + 3\tau_{max}) = \alpha$

Таким образом, мы получили выигрыш в $S_{H'}\times\alpha \approx 30$ очков на том же промежутке. Не то, чтобы много, но при схватке за первое место — очень даже роляет.

Записываем в виде кода:

Класс Skill для второго прохода решателя

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) };
}

Прогоняем с двумя проходами с оптимизацией... И получаем как раз тот результат, который находится в верхушке рейтинга:

Дальнейшее развитие

Действительно, полученное решение оказалось рабочим, и даёт нам заведомо больше очков, чем просто прохождение уровня на полное комбо. У меня, правда, получилось пока что запрыгнуть лишь на 196 место, что тоже весьма неплохо:

В планах когда-нибудь таки доработать эту программу, если игра в офлайн не уйдёт раньше.

Итоговую дичь можно посмотреть как компонент другого проекта на гитхабе.

Жопное чутьё мне подсказывает, что всё это можно как-то расписать аналитически, и считать куда быстрее. Ну а до тех пор следить за моими всратыми похождениями вы можете среди тонн фоток еды, Мику, и всякого древнего железного барахла, в моём Телеграм-канале :-)

Использованные справочные материалы

Project Diva Arcade Atwiki
Статьи о принципах рассчёта таймингов и зависимости их от конкретного железа на Hiroyuki's Homepage: часть 1, часть 2, часть 3
Project DIVA Arcadeの正しい遊び方と間違った遊び方 Part 2
108memo — для сравнения находимых программой прохождений с уже известными корректными
Отдельное спасибо офлайновым друзьям из местных аркад, которые рассказывали и показывали всё это "в полях" на практике :-)

Разрабатывайте и развивайте свою игру (и не только) с помощью облачного хостинга для GameDev ↩

Теги:

Хабы: