The following bit of Python code tells me to expect an ideal winrate of at most 0.0142%:

from math import comb
fill = [[] for i in range(21)]
fill[0] = [1]*1001
for n in range(1,21):
    for d in range(1000):
        fill[n].append(sum(max(fill[i][k]*fill[n-1-i][d-k]*comb(n-1,i) for i in range(n)) for k in range(d+1)))
print(fill[-1][-1]/10**60)

In the program, n is the number of empty slots in an interval, and d is the difference between the endpoints of an interval. For each n from 1 to 20 and d from 0 to 999, we do the following:

• Simulate a draw of each of the d+1 numbers that can be placed within the interval. Call the currently-drawn number k.
• Each of the n slots that k could be placed in splits the interval into two new intervals. Check fill for the number of ways that each interval could be filled, and multiply those together. Since the sequences that fill the subintervals can be interleaved, and the value of k lets you determine which sequence you've drawn from*, multiply by the number of ways these sequences can be combined.
• The greatest of these n products gives the number of winning sequences under the ideal placement of k. Add up the total number of sequences for all k, and place the sum into the corresponding place in fill.
• Once all calculations are finished, fill[20][999] will give you the number of winning sequences for the original problem, and this can be divided by the $1000^{20}$ possible draws to obtain the final probability.

*This overcounts the cases where k is drawn multiple times and can be placed in either subinterval.

The following bit of Python code tells me to expect an ideal winrate of at most 0.0142%:

from math import comb
fill = [[] for i in range(21)]
fill[0] = [1]*1001
for n in range(1,21):
    for d in range(1000):
        fill[n].append(sum(max(fill[i][k]*fill[n-1-i][d-k]*comb(n-1,i) for i in range(n)) for k in range(d+1)))
print(fill[-1][-1]/10**60)

In the program, n is the number of empty slots in an interval, and d is the difference between the endpoints of an interval. For each n from 1 to 20 and d from 0 to 999, we do the following:

• Simulate a draw of each of the d+1 numbers that can be placed within the interval. Call the currently-drawn number k.
• Each of the n slots that k could be placed in splits the interval into two new intervals. Check fill for the number of ways that each interval could be filled, and multiply those together. Since the sequences that fill the subintervals can be interleaved, and the value of k lets you determine which sequence you've drawn from*, multiply by the number of ways these sequences can be combined.
• The greatest of these n products gives the number of winning sequences under the ideal placement of k. Add up the total number of sequences for all k, and place the sum into the corresponding place in fill.
• Once all calculations are finished, fill[20][999] will give you the number of winning sequences for the original problem, and this can be divided by the $1000^{20}$ possible draws to obtain the final probability.

*This overcounts the cases where k is drawn multiple times and can be placed in either subinterval. Duplicates occur in roughly 17.5% of draws, so some further analysis is needed.