Work Text:
“Let’s play a game,” Giovanni said, motioning to an infinitely long row of switches in front of Latias. “In order to earn your freedom, you must turn on more switches than I can.”
That’s easy, thought Latias. Just as she is about to flip a switch, Giovanni added, “However, there’s a catch. You must program a robot to do it for you.” Giovanni then pointed to a machine with a single arm and numerous switches on it. “This robot is quite simple to use. Let me explain.”
“The robot has five states. Every step, it starts off by reading the state of the switch in front of it. It then combines that information with its internal state and performs three actions. First, it either turns the switch in front of it on or off. Second, it either moves left or right by one space. And third, it can either stay in the same state, enter a different state, or enter a sixth special ‘STOP’ state, in which it will stop running. The robot is deterministic, so given the same internal state and switch state it will perform the same set of actions. Your goal is to program the robot such that it will turn on as many switches as possible. However, the robot must eventually stop for the result to count.”
Latias stared at the robot. There seems to be 31 switches on it – 30 for programming the robot, and 1 for activating and deactivating it. The 30 programming switches are neatly divided into 10 groups, each group corresponding to an internal state switch state pair.
“Feeling overwhelmed?” Giovanni said sarcastically, “I’ll first give you a short tutorial. Suppose the robot only had one state. How many switches can you turn on?”
Latias thought for a moment, and realized that such a machine can only perform one action before stopping. She flicked a few switches, and turned on the robot. The robot turned on the switch in front of it, moved left, and stopped.
“Very good,” Giovanni said, “What if the robot had two states?”
Latias thought for a while, and asked, “Can I have some scratch paper?”
“Sure,” Giovanni said as he handed Latias a pad of paper and a pen. After some more calculations, Latias went to the robot, flicked some switches, and turned on the robot. This time, the robot’s motion is more complex than last time, stopping after 6 steps, leaving 4 switches on.
“Now that you’ve got the hang of it, I’ll leave you alone. You may experiment with three or four states before taking on my challenge,” Giovanni said, “Oh, and by the way, this room is monitored, so don’t even think about escaping before you’re done.” With that, Giovanni left the room.
Latias stared at the robot and the wall of switches, and then at the pad of paper. After thinking about the three-state robot for a while, she realized that there are far more configurations than she could write down. She will need a computer.
“Giovanni, I need a computer,” Latias said.
“You may have one,” Giovanni replied. The door opened, and a Team Rocket agent handed Latias a laptop computer. Giovanni said that the laptop is equipped with a powerful GPU to enable fast calculations.
Latias wrote a program capable of simulating any n-state robot, and began enumerating all the three-state robots. Soon after, the computer produced a file containing a list of roughly 17 million configurations. Now all that’s left is to simulate all of them.
Soon, however, Latias realized that many of the robots would never stop, meaning that the key to winning at Giovanni’s game is to determine which of the robots would stop, and which would not. For now, Latias decided to set the bailout value to 1 million moves, after which the computer would declare the robot non-stopping and move on to the next robot.
After a while, the computer finished computation. Fortunately, the longest running robot out of those that did not reach 1 million moves only made 21 moves, indicating that it is highly unlikely that there are terminating robots that would run for longer than 1 million moves. Out of the terminating robots, the highest score achieved was 6, taking 14 moves.
Feeling confident, Latias decided to tackle the five-state robot. Enumerating all the robots took a few minutes, producing a file containing roughly 63 trillion configurations. Latias could immediately tell that she would not be able to simulate all of them with a bailout value of 1 million. However, seeing that a three-state robot could only make 21 moves while halting, Latias doubted that a five-state robot could make over 1000. Setting the bailout value to 1000 moves, Latias started the program, and waited. After all, it is expected to take many days to finish. During those few days, Latias took a shot at finding a general algorithm that could tell if an arbitrary robot would stop or not, but she didn’t make any progress for robots with more than three states. It was far more complicated than she thought.
After a few days of computing, Latias went to check the output. This is when disaster struck. There were many, many robots with runtimes of hundreds of steps, some even coming close to 1000, indicating that a bailout value of 1000 is most likely too low. Unable to afford a higher bailout value, Latias realized that she needs to find patterns to narrow down which configurations to check.
After a few more days of hard work, Latias found a list of rules that are able to eliminate most non-stopping five-state robots, as well as most robots that stop early on. Re-enumerating the robots with these sets of rules narrows it down to roughly 200 million configurations, a massive improvement. Setting the bailout value back to 1 million, Latias let the computer run, hoping to find a large gap between the runtime of the longest-running robot and 1 million. Unfortunately, there are still many robots with runtimes in the hundreds of thousands, indicating that there are likely terminating five-state robots that run for longer than 1 million steps. Hoping that Giovanni did not bother to find the optimal solution for five states, Latias picked the configuration with the highest score and called Giovanni in.
“Impressive,” Giovanni said, “However, I can do better. Watch this.” He walked up to the robot, flicked some switches, and activated the robot. It began to move in a complicated fashion. Giovanni took out a device, and pressed a few buttons. “This will take 47 million moves, so I’m going to speed up time.”
As the robot blurred in front of the two of them, Latias couldn’t help but wonder how Team Rocket got such technology. “If you don’t mind answering, how does your device work?”
“Oh, we managed to chain up Dialga and harness its powers,” Giovanni said proudly.
“YOU WHAT?” Latias exclaimed in anger. She tried to blast Giovanni to shreds, but just like last time, nothing happened. Something is preventing her from fighting back.
Just then, the robot finished running. The final tally read 4098, which was much higher than Latias’ solution. “You’re welcome,” Giovanni cackled before leaving the room.
Latias fell into despair. All that hard work, only to lose to a mafia boss. Now that she thought about it, Giovanni probably took the time to compute the optimal solution beforehand, meaning that no matter what Latias did, she would not be able to beat Giovanni at his own game. In fact, there’s no way Giovanni would be willing to set a legendary Pokémon free after capturing it. Giovanni only played this game with her as a show of strength, to establish Team Rocket’s dominance over everyone else. It was truly a diabolical game.