Let's try this again.
Paddle War II: This Time He Means Business
11 years ago today I submitted my
Keen 4 paddle war TAS. To this day, it remains my only rejected submission. It was rejected for two main reasons:
1. Faster conclusions are possible.
2. The gameplay is trivial.
With the second reason
no longer applicable, I want to revisit this goal. Now that I have more knowledge and tools at my disposal, I aim to find out what went wrong with the previous submission and find the true optimal solution.
An explanation of this run: Paddle War is a pong-like mini-game found in the Galaxy trilogy (4, 5, and 6) of Commander Keen where the first to 21 points wins. When you are scored on, the ball is spawned in the middle of the field and launched towards your side in one of three different angles. It's possible to position the paddle so that two of the possible trajectories will hit the edge of your paddle without ever having to move. Then, when the ball respawns and launches toward the CPU's side, if they are far enough from the edge then you can score on them multiple times before they can reach the ball again. The result is that you can move the paddle to one initial position and end input early while still eventually winning. This makes the result then entirely dependent on the initial RNG seed...
Planting the Seed
The first step to optimizing the solution is figuring out how the RNG is initialized. One of the easier ways to do this would be to look at the source code. The source code for Keen 4 is not available, but the code for
Keen Dreams is. These are not exactly the same game, and Keen Dreams doesn't even have Paddle War, but the engines are very similar so it's a good place to start.
Upon seeing the
RNG code for Keen Dreams, I immediately recognized it as functionally identical to the
Wolfenstein 3D RNG, which is something that I am
intimately familiar with, but had never looked into how the RNG is seeded in the first place. The fact that they used the same RNG is encouraging because it means that they probably reused this RNG for most of their games, including Keen 4.
The RNG is fairly primitive: the game stores a table of 256 preset values. It keeps its current place in the table by storing an RNG index. When the game needs a random number, it grabs a number from the table corresponding with the current RNG index and then increases the RNG index by one. Once the game reaches the end of the table, the RNG index is set back to zero and the table starts over again. If the programmers want to make the RNG different every time the game is booted up, they can set up a way to randomize the initial RNG index.
Looking at the initialization function in this code yields some fairly straightforward x86 assembly instructions:
mov ah,2ch
int 21h ;GetSystemTime
and dx,0ffh
mov [rndindex],dx
Going line by line...
mov ah,2ch
Puts 0x2C into the AH register.
int 21h ;GetSystemTime
Generates a call to software interrupt
0x21. This is a common interrupt that serves many basic DOS functions like reading inputs and doing file I/O. Its function is based on whatever is in the
AH register, which was just set to
0x2C in the previous line of code. Using one of many
handy references, we can see that the
0x2C function grabs the system time! It puts the current hour in the
CH register, the current minute in the
CL register, the current second in the
DH register, and the current hundredth of a second in the
DL register.
and dx,0ffh
Does a bitwise AND on the DX register with 0xFF. This basically erases the DH register and preserves the DL register that contains the current hundredth of a second.
mov [rndindex],dx
Moves the DX register, which only contains the current hundredth of a second, into the RNG index variable.
I can confirm this same code is used in Keen 4 by using the DOSBox-X debugger and setting a breakpoint on interrupt 21h function 0x2C and booting up the game. This also gives me the location of the RNG index in the RAM. Poking this value in the original Paddle War movie completely changes the outcome of the game, so we've found our target. Commander Keen 4's RNG is seeded based on the system's current hundredth of a second.
2015 Post Mortem
A big problem I had with the original movie was that I was only getting the same handful of games repeatedly no matter what I set the system time to. The solution seems fairly simple now: just adjust the initial system time's milliseconds. But didn't I try that originally? Something seems fishy here.
In JPC-rr's
.jrsr format, the initial clock time can be set by changing the
INITIALTIME variable. The time is
set in milliseconds, so by changing the second-to-last and third-to-last digits, it should change the initial RNG index. However, doing this yields no change to the RNG index at all. Changing the seconds or minutes does change it slightly, but I could only get and RNG index between 22 and 27 by changing the initial time in the original movie.
This makes the core problem in the original movie apparent:
JPC-rr does not pass down its initial milliseconds into the system time. This can be easily confirmed by making a movie that executes
FreeDOS's TIME utility and trying different milliseconds in the movie's
INITIALTIME.
It might be worth switching emulators to get around this, so let's look at those:
- PCem has the exact same problem. libTAS can set initial nanoseconds, but again, making a movie that executes the
TIME utility and playing around with the hundredths of a second yields no difference in the displayed system time.
- BizHawk's DOSBox-X core does not have a way of changing the system time outside of using DOSBox-X's internal
TIME function, which can't even set milliseconds. You would just have to wait for the millisecond you want.
So those aren't going to be ideal. It seems like the next best way to change the time is to use the TIME utility in the DOS prompt, since it is able to change the current hundredths of a second. This step could slightly increase the time over the original movie, but will yield better game outcomes. We could argue that this time loss is only from setup in the DOS prompt and does not really count towards gameplay, and is the only way to rectify the original movie's issues.
The Paddle War Comprehensive Multiverse
We've established that the RNG index is seeded by the current hundredth of a second, so it can only start between 0 and 99. Here are all 100 possible outcomes
[1]. Time is based on the frame the "You won!" message pops up.
| Index | Player score | CPU score | Outcome | Time | Notes |
|---|
| 0 | 18 | 21 | LOSS | | |
| 1 | 21 | 20 | WIN | 2:34.938 | |
| 2 | 13 | 21 | LOSS | | |
| 3 | 14 | 21 | LOSS | | |
| 4 | 21 | 19 | WIN | 2:46.082 | |
| 5 | 19 | 21 | LOSS | | |
| 6 | 21 | 18 | WIN | 2:41.987 | |
| 7 | 15 | 21 | LOSS | | |
| 8 | 15 | 21 | LOSS | | |
| 9 | 21 | 19 | WIN | 3:07.912 | Slowest win |
| 10 | 17 | 21 | LOSS | | |
| 11 | 19 | 21 | LOSS | | |
| 12 | 14 | 21 | LOSS | | |
| 13 | 21 | 19 | WIN | 2:43.713 | |
| 14 | 21 | 16 | WIN | 2:35.994 | |
| 15 | 20 | 21 | LOSS | | |
| 16 | 12 | 21 | LOSS | | |
| 17 | 12 | 21 | LOSS | | |
| 18 | 14 | 21 | LOSS | | |
| 19 | 21 | 18 | WIN | 2:22.582 | |
| 20 | 18 | 21 | LOSS | | |
| 21 | 21 | 18 | WIN | 2:44.355 | |
| 22 | 14 | 21 | LOSS | | |
| 23 | 10 | 21 | LOSS | | |
| 24 | 15 | 21 | LOSS | | |
| 25 | 20 | 21 | LOSS | | |
| 26 | 21 | 20 | WIN | 2:33.283 | Original movie |
| 27 | 10 | 21 | LOSS | | |
| 28 | 21 | 18 | WIN | 2:34.653 | |
| 29 | 17 | 21 | LOSS | | |
| 30 | 21 | 20 | WIN | 2:57.454 | |
| 31 | 21 | 15 | WIN | 2:34.268 | |
| 32 | 12 | 21 | LOSS | | |
| 33 | 21 | 16 | WIN | 2:06.944 | |
| 34 | 19 | 21 | LOSS | | |
| 35 | 20 | 21 | LOSS | | |
| 36 | 21 | 18 | WIN | 2:22.582 | |
| 37 | 18 | 21 | LOSS | | |
| 38 | 17 | 21 | LOSS | | |
| 39 | 14 | 21 | LOSS | | |
| 40 | 12 | 21 | LOSS | | |
| 41 | 21 | 20 | WIN | 2:11.310 | |
| 42 | 17 | 21 | LOSS | | |
| 43 | 21 | 19 | WIN | 2:31.557 | |
| 44 | 14 | 21 | LOSS | | |
| 45 | 10 | 21 | LOSS | | |
| 46 | 19 | 21 | LOSS | | |
| 47 | 21 | 19 | WIN | 2:55.727 | |
| 48 | 10 | 21 | LOSS | | |
| 49 | 21 | 12 | WIN | 1:50.265 | Biggest & fastest win |
| 50 | 21 | 17 | WIN | 2:23.338 | |
| 51 | 19 | 21 | LOSS | | |
| 52 | 11 | 21 | LOSS | | |
| 53 | 15 | 21 | LOSS | | |
| 54 | 18 | 21 | LOSS | | |
| 55 | 17 | 21 | LOSS | | |
| 56 | 16 | 21 | LOSS | | |
| 57 | 19 | 21 | LOSS | | |
| 58 | 21 | 18 | WIN | 2:20.014 | |
| 59 | 13 | 21 | LOSS | | |
| 60 | 21 | 18 | WIN | 2:32.170 | |
| 61 | 14 | 21 | LOSS | | |
| 62 | 21 | 18 | WIN | 2:29.745 | |
| 63 | 17 | 21 | LOSS | | |
| 64 | 18 | 21 | LOSS | | |
| 65 | 21 | 13 | WIN | 2:08.985 | |
| 66 | 17 | 21 | LOSS | | |
| 67 | 17 | 21 | LOSS | | |
| 68 | 20 | 21 | LOSS | | |
| 69 | 18 | 21 | LOSS | | |
| 70 | 17 | 21 | LOSS | | |
| 71 | 13 | 21 | LOSS | | |
| 72 | 16 | 21 | LOSS | | |
| 73 | 8 | 21 | LOSS | | Biggest loss |
| 74 | 14 | 21 | LOSS | | |
| 75 | 21 | 18 | WIN | 2:15.363 | |
| 76 | 13 | 21 | LOSS | | |
| 77 | 17 | 21 | LOSS | | |
| 78 | 21 | 20 | WIN | 2:45.383 | |
| 79 | 14 | 21 | LOSS | | |
| 80 | 19 | 21 | LOSS | | |
| 81 | 17 | 21 | LOSS | | |
| 82 | 10 | 21 | LOSS | | |
| 83 | 17 | 21 | LOSS | | |
| 84 | 12 | 21 | LOSS | | |
| 85 | 18 | 21 | LOSS | | |
| 86 | 21 | 19 | WIN | 2:31.585 | |
| 87 | 19 | 21 | LOSS | | |
| 88 | 13 | 21 | LOSS | | |
| 89 | 19 | 21 | LOSS | | |
| 90 | 10 | 21 | LOSS | | |
| 91 | 14 | 21 | LOSS | | |
| 92 | 21 | 17 | WIN | 2:13.636 | |
| 93 | 21 | 19 | WIN | 2:53.359 | |
| 94 | 17 | 21 | LOSS | | |
| 95 | 21 | 19 | WIN | 2:43.656 | |
| 96 | 18 | 21 | LOSS | | |
| 97 | 21 | 19 | WIN | 2:46.139 | |
| 98 | 17 | 21 | LOSS | | |
| 99 | 10 | 21 | LOSS | | |
The Caveat
[
1] When I say there are only 100 possible outcomes, this is not completely true. While the initial value of the RNG index can only be 0 through 99, the RNG index actually goes up to 255 while playing the game. This does mean that there are more possible games, and some of the other game durations might even be shorter. However, in order to see these games,
significant additional gameplay time must be added to advance the RNG. The game could only start at an RNG index as high as 99, and then the RNG would have to be advanced either through an extra Paddle War game or through playing the actual Keen 4 game. Obviously adding gameplay time would increase the movie length in a more meaningful way, so I've avoided doing that.
Final Product
I went with index 49, which was not only the biggest winning margin out of the 100 tested, but also the fastest win. The result is a 21 to 12 win with the winning point scored at 1:50.265. This is an improvement of 8 points over the original movie and a whopping 43 seconds faster. The movie time is actually identical to the original movie; either there was enough room in the keyboard buffer to set the system time without losing a frame, or I accidentally found some improvement in the setup. I hope I've done an adequate job at proving that this is the best possible outcome from an initial seed.
Sync Stuff
- Emulator: JPC-RR r11.8 rc2
Tracks: 16
Sides: 16
Sectors 63
Total Sectors: 16128
MD5: dd5f0aba8d13c390b209f7a9a6ba494c
Entry: N/A N/A 7 /
Entry: 19900101000000 125c93a549a3e5b2ab4c6c6ec1ad3e7d 33325 /AUDIO.CK4
Entry: 19900101000000 af43c120c2c322e2bd4e1e7cad7678f2 5375 /DOPEFISH.ANS
Entry: 19900101000000 e38064818169e365bcff61dbaec55aef 520581 /EGAGRAPH.CK4
Entry: 19900101000000 9e1811deb429f7edc6bffa5bb786ebb4 99040 /GAMEMAPS.CK4
Entry: 19900101000000 56de6f7f48300a0774e194f7ed98811d 105108 /KEEN4E.EXE
Entry: 19900101000000 063d3bfda9c014b6395c1aa952ad2f8b 5714 /ORDER.FRM
Entry: 19900101000000 241452c154120ce6b06d21479e4dc188 7459 /VENDOR.DOC
