## The mathematics of the Perfect Dark Elite

### What is the easiest way to beat 2:00:00 total time in Perfect Dark?

I haven't played Perfect Dark competitively in some years but the game still holds some challenges for me, which I do, one day, intend to fulfill.

0:06 Defection Agent - the easiest WR I don't yet have - is probably a pipe dream. I just don't have the patience to try for that, I don't think. Getting under 4:00 Attack Ship PA is still on the table - it's a great level, and if I can pull it off then I'll have all my times under four minutes, which is not an inconsiderable achievement. But getting under two hours total is the big one. The sum of the Elite's world records fell below 2:00:00 many many years ago and many individual players have cracked the mark since. It's a tough nut, but a recognisable and achievable one.

More importantly, it's not a task you have to fight other people for. Being at the top of the time or points rankings, sure. Simply getting points at all involves devotion of time which a guy of my age is no longer in a position to spare. Besides which, I'm pretty much maxed out at the game by this point. There is a limit to how many points I can even hope to gain. There's only a finite number of points available in the first place, and as more and more people join the Elite the number within reach drops. I'm currently 94th on the points rankings and expect to drop out of the top 100 within a year.

On the other hand, 2:00:00 is a respectable benchmark which doesn't move away from you over time. I'm at 2:03:02 and have been for many months. That's not changing. Thus arose my question.

This is obviously an extremely subjective problem - "work on PA more than SA and SA more than Agent" is the only real universal rule. Different levels hold different difficulty for different people. But I also saw it as challenging from a mathematical standpoint.

### Defining "easiest"

Perfect Dark has 63 individual levels. A personal record (PR) on a given level yields a score between 100 and 0 points inclusive. The world record (WR) is worth 100 points; from there, the number of points decreases until you pass the 100th-ranked player or so, after which you get 0. That means we can define a score function, S(L,T), where L is the level and T(L) is your personal record for that level. S(L,T) is non-strictly decreasing in T. We can use this as our benchmark for the relative difficulty in obtaining a given PR.

Let TT(L) be the total time over the levels 1 to L, and TS(L) be our total score over the levels 1 to L.

```TT(L) = T(1) + T(2) + ... + T(L)

TS(L) = S(1,T(1)) + S(2,T(2)) + ... + S(L,T(L))
```

Our problem, "Find the easiest 1:59:59", becomes: minimise TS(63) subject to TT(63) = 1:59:59.

### Brute force

This seems like a fairly straightforward problem to solve: simply check every combination of PRs which adds up to 1:59:59, and find the combination which gives the lowest score.

But a moment's thought reveals that the size of this possibility space is GIGANTIC! If we assume that every PR can vary freely between 0:00 and 1:59:59, then we are searching within a 63-dimensional hypercube of side 7200, which is 720063 ~= 10243 individual points. Actually, we're restricting our search to the 62-dimensional hyperplane on which the PRs add up to 1:59:59, but this is still 7262C62 ~= 10154 points. The general problem for time T over L levels is O(TL). Brute force doesn't work.

### A better way

A little thought, however, serves well. We can reduce this 63-dimensional problem to 62 two-dimensional problems - each solvable in a relatively short space of time.

Let B(L,TT) be the lowest possible score over the levels 1 to L, given a total time of TT(L) over those levels. (We seek B(63,1:59:59).) Then:

```L = 1:   B(1,TT(1)) = S(1,TT(1))

L ≥ 2:   B(L,TT(L)) = min { B(L-1,TT(L)-t) + S(L,t) : 0 < t < TT(L) }
```

We have a recurrence relation. The values of B on one level depend solely on the values it had on the previous level. That means we can calculate B for each level sequentially, starting at L=1 and moving up to 63.

Systematically calculate B(1,0:00) to B(1,1:59:59). This is O(T). Then use these results to calculate B(2,0:00) to B(2,1:59:59), which is O(T2) because of the number of comparisons. All the steps from here are O(T2) until we reach B(63,0:00) to B(63,1:59:59). Technically we only need to calculate B(63,1:59:59) here, which is O(T), but either way, the overall process is O(LT2).

We now have an array in L and TT which gives, for each level and total-time-up-to-that-level, the lowest possible score.

To calculate the PR distribution we need a little more, but that's simple: For each (L,TT), have another array C alongside B, storing the PR for level L which yields this score-- that is, the value of t which minimises the expression above. We can then deduce the PR distribution by working backwards:

```TT(63) = 1:59:59 (always)
C(63,TT(63)) yields T(63)

TT(62) = TT(63) - T(63)
C(63,TT(62)) yields T(62)

...

TT(1) = TT(2) - T(2)
C(1,TT(1)) yields T(1) = TT(1)
```

### Complications

Since we are taking score as our benchmark here, times which give equal scores are considered to be of equal difficulty. For example, if you hold the world record (100 points), improving that world record to 0:00 would leave you at 100 points still - so the program must be altered to take this into account, by not considering times faster than the world record on any given level.

Unfortunately the same cannot easily be done for intermediate points. For example, if the WR is 1:02 and you are tied with lots of people below that on 1:04, then improving your time to 1:03 will gain 1 very difficult second, but gain 0 points - hence it would trivially easy, according to the program!

Ignoring times faster than the WR saves calculation time. We can save more time by doing the same thing from the opposite direction. Every level has a "pointless time", the fastest possible time which is worth 0 points. Likewise, we can sum those pointless times over the levels 1 to L for any given L. Above this point, B(L,TT(L)) will always return 0, so we can just stop calculating B(L,-) automatically here-- or at 1:59:59, whichever is smaller.

Lastly, certain values of t will necessarily yield an impossible combination of PRs for the previous levels. For example, if the sum of the world records up to level L-1 is 1:00:00 and our target for level L is 1:05:00, then T(L)>5:00 is obviously impossible.

Enough minutiae. Here's what the machine spat out, then:

 Level Agent SA PA Defection 0:09 / 0pts 0:50 / 0pts 1:59 / 46pts Investigation 1:34 / 0pts 2:23 / 0pts 2:57 / 66pts Extraction 0:59 / 0pts 1:51 / 1pt 2:12 / 1pt Villa 1:19 / 1pt 1:39 / 0pts 2:20 / 0pts Chicago 0:18 / 0pts 0:34 / 0pts 0:38 / 1pt G5 0:54 / 0pts 1:06 / 0pts 1:26 / 0pts Infiltration 1:19 / 0pts 2:07 / 1pt 1:58 / 85pts Rescue 1:40 / 0pts 2:42 / 0pts 3:59 / 0pts Escape 2:45 / 0pts 4:02 / 0pts 4:21 / 0pts Air Base 1:26 / 0pts 2:01 / 0pts 2:48 / 17pts AF1 1:00 / 0pts 1:31 / 0pts 1:46 / 0pts Crash Site 1:32 / 0pts 1:48 / 0pts 2:41 / 0pts Pelagic II 1:06 / 0pts 2:32 / 0pts 2:49 / 42pts Deep Sea 3:16 / 0pts 3:03 / 94pts 4:25 / 13pts CI 0:57 / 0pts 1:42 / 0pts 2:15 / 0pts Attack Ship 2:34 / 0pts 3:20 / 0pts 4:22 / 21pt Ruins 1:28 / 0pts 2:00 / 0pts 2:29 / 0pts MBR 1:41 / 0pts 1:47 / 0pts 1:52 / 0pts Maian 1:51 / 0pts 2:20 / 0pts 2:40 / 9pts War 0:29 / 0pts 0:55 / 0pts 1:09 / 0pts Duel 0:04 / 0pts 0:07 / 0pts 0:12 / 0pts

#### Total: 1:59:59 / 398pts

This individual would be ranked 64th in time and 140th in points. Cute!

The program assumes that you can get all the zero pointers with zero effort as part of the calculation. Obviously, it's a pretty silly set of times, requiring immense skill on a few levels and barely any on many others. Still, a fairly interesting mathematical curio.

Naturally, the reverse question, "What's the slowest time which will earn me, say, 1000 points?" is pointless since a PR can increase without limit while all the others are world records...