Petal Crash Behind the Scenes: Artificial Intelligence for Puzzle Game CPU Players

As I sit down to start writing this, it’s evening on the launch day of Petal Crash for PC, Switch, and PS4, a retro-style action puzzle game created by my friend Ashley Jenkins and contributed to by several others, including myself. Ashley and I spent a good chunk of today bouncing around different places online looking for reactions to the game, and something that people were surprisingly interested in when we joined conversations was how the AI that powers the CPU opponents works. This was my most major contribution to the game, and it’s something that I am pretty proud of, so I thought it would be worth trying to write an article on the design of the system and how it’s used in the game to give each CPU character a unique playstyle that fits their personality. Note that I may elide or simplify some things for the sake of brevity, or even get some small details wrong since we did the bulk of of early development together in person so I have nothing but my poor memory to reference. I’ll try to explain game-specific vocabulary where I can, but an understanding of basic Petal Crash gameplay is probably required too.

Beginnings

At the time I got involved in the project, Ashley had been working on Petal Crash for about half a year. Before the Kickstarter campaign, a private build of the puzzle editor mode was shared with a small group of friends, and seeing the puzzle codes being exported in what was basically a raw serialization of their internal representation got me thinking about the problem of compressing those codes for ease of sharing, specifically making them small enough to fit in a tweet, or even encode in a QR code (an idea that ended up never making it off the drawing board). The details of that are another topic entirely, but writing the code to compress and decompress puzzles into tweet-sized chunks was how I first started officially contributing to Petal Crash.

  • High enough max difficulty to challenge expert players
  • Low enough minimum difficulty to accommodate inexperienced players who might have never played an action puzzle game before
  • Short enough required “thinking time” that moves could be made at a reasonable pace

Making a Plan

To understand the decisions that went into the design of the system, one first needs to understand the most important requirement, which was being able to give each CPU player a unique personality. As seen below, each character has a well-defined personality, and each character’s story mode consists of competing with each of the others in a match, so there’s a lot of room for those personalities to shine in both the writing and gameplay.

Character bios from the official Petal Crash website. Their personalities informed their behaviors as CPU opponents.
  • Strelitz: Makes moves quickly, without much forethought, as if he’s button-mashing in a fighting game.
  • Penny & Deony: Switch between a faster, haphazard playstyle and a slower, more thoughtful playstyle every 15 seconds to represent the twins’ differing personalities.
  • Ore Kid: Uses the skip button to fill her field mostly full of pieces, then chips her way out like she’s mining. She’s not good at recognizing chain opportunities but will sometimes luck into them.
  • Daize: When in danger, will focus on setting up big moves without setting them off and will set off prepared moves once the hit is resolved to counter the incoming garbage blocks.
  • Yosoti: Plays slightly slower, but is better at recognizing and preparing chain clears.
  • Rosalia: Takes her duty seriously and does not hold back or show weakness, so no gimmick or behavior changes from default optimized AI.

Building the Underlying AI

My background is in computer science, so of course the very first approach that came to mind when dealing with this problem was a search tree with some sort of scoring function to evaluate potential future states, as is commonly used in AI for traditional turn-based games like chess. After evaluating potential future states and finding the one with the best score according to the state-scoring algorithm, the move for this turn that leads down the desired path is selected. Coincidentally, a Petal Crash board is the same size as a chess board, and the fact that Petal Crash is effectively turn-based made this approach a perfect fit. From there, it was a matter of determining what the scoring function should look like, and what parameters it needed. Taking the CPU personalities into account, we arrived at the following parameters:

  • Block clear weight: Adjusts the importance of number of blocks cleared by a given move.
  • Chain size weight: Adjusts the importance of chain size (chain-reaction clears of multiple clusters of blocks from the same input).
  • Chain exponent: An exponent to use on the portion of the score calculated from the number of blocks cleared, the chain size, and their respective weights. Usually this is 1, but for characters that really want to focus on chains, this can be increased.
  • Garbage clear weight: Adjusts the importance of removing garbage blocks from the board. Allows characters to go out of their way to clean up garbage or not pay any particular attention to it depending on tuning.
  • Search depth weight: A somewhat ambiguously-named parameter that is used to weight moves further down in the search tree. For example, setting this value to something higher than 1 will result in the AI heavily favoring setting up moves for the future instead of making a match as the current move, while setting it to something between 0 and 1 would make each subsequent search level contribute less and less to the final score for its search path, effectively making the CPU “distrustful” of its ability to judge the future.
  • Skip weight: “Skipping” and “fast-forwarding” are terms we use interchangeably to refer to the feature that allows the player to automatically advance block spawners until the next set of blocks spawns in. Otherwise, these advance one step per move made by the player. Skip weight influences how likely the CPU is to select skipping as their move. This is used extensively by Ore Kid to create her playstyle where she fills her board with pieces and chisels her way out.
  • Noise weight: A weight for how much to “fuzz” a given score, obscuring to the AI how good it truly is. The calculation this controls can end up not only making some moves look worse than they really are, but making some look better than they actually are too. Effectively, this is a number between 0 and 1 that linearly interpolates from an unfuzzed score (0) to a score heavily distorted by multiplication by a potentially small or potentially large random number (1).
  • Block clear cap and chain size cap: Maximum values for the amount of block clears and the size of a chain that will be factored into a score. Anything that surpasses these values will be clamped, which means that characters that aren’t supposed to be good at spotting chains can be configured to not be able to tell the difference between, for example, a 3-chain and anything larger. These were added after the original version to address some issues detailed below.

Putting It All Together

The AI system takes an input consisting of a representation of the current board state plus all of these parameters, simulates and scores future board states, picks a winner, and outputs the block position and direction to move it in, which is then fed to the code that controls the AI player’s movements. The parameters are not set in stone, and can change due to other factors in the match. For example, when Penny and Deony flip who’s at the controls, the set of parameters fed to the underlying AI algorithm changes completely. When Daize sees a big attack coming, he can switch modes and ask the algorithm for a move that he can take now to counter it instead of continuing with his normal build-for-the-future approach. Some behaviors are achieved without modulating AI system parameters at all, such as when Lilibri gets hit by a big attack; she can ask for her next move, and then sit on that information for a certain amount of time while wiggling her cursor around wildly to demonstrate her distress before actually making the move. With the AI system plus additional code on top to modulate the parameters and perform other actions, Ashley was able to successfully create all of the desired AI personalities, which was a really exciting success the first time we saw it all wired up in game!

Post-Implementation Tuning

Yosoti’s chain power ended up being far too strong with their initial parameters

Final Thoughts

Overall, I’m really happy with how the AI in Petal Crash turned out. Ashley’s concepts for personalities-as-playstyles really shines through, and the difficulty curve feels really satisfying. Due to the computational requirements specific to Petal Crash where a single move can have cascading consequences, I wasn’t able to make the max level quite as ruthlessly bloodthirsty as I might have liked, but it still provides a challenge that I think will be stumping even the strongest players for a long time, so I can live with that.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store