The Pokémon Regularity Problem | Nathan Dalaklis

The speaker returns to discuss a complex problem in computational theory known as the Pokémon Regularity Problem, introduced by Alex Clemmer in 2018. The problem revolves around whether Pokémon games from the first generation (Red, Blue, or Yellow) can be solved using a finite state automaton. The speaker explains the need to understand terms like 'regular language' and 'finite automaton' and delves into the definition of a regular language in complexity theory. The language corresponding to solving Pokémon games is defined as the set of moves leading to the defeat of the champion, without the requirement to catch all Pokémon. The problem's significance lies in classifying the game's complexity, which would imply the type of machine or computer needed to solve it. The finite automaton is described as an abstract machine with a five-tuple definition, including states, symbols, transition function, start state, and accept states. The speaker sets the stage for further exploration into whether Pokémon games can indeed be solved by such a machine.

The speaker explores the concept of solving mazes, which parallels the navigation in Pokémon games, using finite automata. They propose a method to transform a simple maze into a finite state automaton where states represent tiles and symbols represent movements (left, right, up, down). This transformation is demonstrated with an example, showing how the automaton can describe all possible paths from the start to the goal. The speaker acknowledges that while this method works for simple mazes, Pokémon games present unique challenges due to their complexity. They address the issue of changing maps, such as item existence, by suggesting a machine with two sets of states to account for items acting as walls or normal tiles. The speaker also discusses how doors in the game can be incorporated into the automaton as transitions, and hints at the complexity introduced by features like flying and surfing, which relate to the player's Pokémon party. The summary ends with an invitation for the audience to consider these complexities and the challenge of applying the concept to the full scope of Pokémon gameplay.

The speaker shifts focus to the battles in Pokémon games, which add a significant layer of complexity to the problem of solving the game with a finite automaton. They outline the numerous factors that must be tracked to define the state space for battles, including the stats of both the player's and the opponent's Pokémon, power points for moves, and the specific Pokémon involved in the battle. The state of a battle is described as a cross between these various elements, leading to a vast number of possible states. The speaker admits the complexity of constructing a battle automaton and the difficulty of conceptualizing it. They also touch upon the broader implications of the Pokémon Regularity Problem, highlighting how it challenges our understanding of the game's complexity and the computational models required to solve it. The video concludes with a reflection on the enduring appeal and intellectual curiosity sparked by analyzing older games like Pokémon, and an invitation for viewers to engage with more mathematical content.