[ About | The Game | Details | Download | Run ]
In this article, I describe how I created a bot that plays Yoshi’s Cookie, the tile-matching puzzle video game for the NES.
In the video below, watch the bot complete normal mode and the ending that follows.
Next, check out the bot finishing off expert mode and the subsequent finale.
Yoshi’s Cookie provides two different game modes:
In 1-player mode, the player completes stages that progressively increase in difficultly:
In versus mode, 2 players compete against each other in split-screen:
The bot is designed for 1-player mode. If you launch it during the title screen, it will play through all the stages from the first to the last. Or you can intermittently start and stop it on any stage to enable it to complete a section.
In 1-player mode, the playfield consists of a rectangular matrix populated with various cookies. And the objective of each stage is to completely clear the playfield. The player accomplished that task by repeatedly forming rows/columns consisting exclusively of the same cookie type; completed lines are automatically removed, shrinking the matrix. However, new rows/columns that slowly fall from the sides cause the matrix to grow upon contact. If the width/height of the matrix reaches 8, it’s game over.
The player controls a cursor that’s used to rotate individual rows/columns. A rotation consists of shifting all the cookies within a line by 1 space in either direction. The cookie that get pushed off the edge of the matrix wraps around to the other side, filling in the gap created by the shift.
The rotation mechanic makes the playfield topologically resemble a torus. Rotating rows is analogous to toroidal motion along the tube and rotating columns is analogous to poloidal motion around the tube, or vice versa.
In the lower-right of the frame, the game displays how many lines of each cookie type were completed by the player. Each completed line is indicated by a glowing red bulb. When the player achieves 5 red bulbs for the same cookie type, he’s rewarded with a Yoshi Cookie.
A Yoshi Cookie acts as a wild card that can be used to clear lines of any other cookie type.
Interestingly, the Yoshi’s Cookie Instruction Booklet erroneously describes a slightly different behavior:
Perhaps a last-minute design change resulted in that mismatch. In fact, the hint that appears in the instruction booklet for the SNES version correctly explains, “When you complete five lines of one type of cookie you will get a very special YOSHI COOKIE! This cookie can be used as a wild card to help complete any type of cookie line.” Whatever the case, as you’ll see below, Yoshi was right about the “special message from Mario.”
The 1P menu allows the player to choose the starting round, which normally goes up to 10. And each round consists of 10 stages. However, upon completing the tenth stage of round 10, the end credits roll and the sequence culminates with these two screens:
In rounds 11 and up, Heart, Flower, Diamond, Check and Circle cookies are respectively replaced by Super Mushroom, Boo Buddy, Goomba, Jumpin’ Piranha Plant, and Bloober cookies. Yoshi Cookies are still available upon completing 5 lines of the same type. But, as an added challenge, each stage begins with a Green Koopa Troopa Shell cookie. And only one Shell exists throughout the entire stage. The only way to eliminate it is to pair it up with a Yoshi Cookie, completing a line of length 2.
In recognition of beating round 10, the game swaps Music Type A with a new tune. Listen in to the Round 99 video above to experience it.
The bot constructs lines in much the same way that a human player does. It builds them incrementally using a greedy algorithm, making locally optimal choices at each stage. That compromise was employed due to the immense size of the solution space; an exhaustive search to compute the globally optimal way to manipulate the playfield is not feasible in real-time.
I’ll explain how the algorithm does this through an example. In the matrix below, the algorithm is in the process of building row 1. Three Hearts are already in place and three spaces remain:
The first step is to move the cursor to the column containing the nearest space:
Next, it locates the nearest Heart outside of row 1, which happens to be directly beneath the cursor. Since the Heart is within the same column, all it needs to do is to rotate the column to get the Heart into position:
With the Heart in position, the cursor advances to the column containing the nearest space. When accounting for wraparound, the nearest space is in column 0. The cursor moves there by taking 1 step right:
Anytime that the algorithm measures a distance, moves the cursor, or rotates a row/column, it always considers wraparound to exercise the minimal cost option.
As before, it locates the nearest Heart outside of row 1. And this time the target is on row 4. Since its not within the cursor’s column, the cursor moves to that row:
Next, it rotates row 4 until the Heart is within column 0:
Then it rotates column 0 to get another Heart into position:
Once again, the algorithm moves the cursor to the column containing the nearest space:
As seen twice before, it locates the nearest Heart outside of row 1, which is directly beneath the cursor. Since the Heart is within the same column, all it needs to do is to rotate the column to get the Heart into position. In this case, the optimal way to do that is to take advantage of wraparound by shifting the Heart down 2 steps:
That completes the line. But how does the bot know which line to build?
For all cookie types, the bot simulates building all possible rows and all possible columns. A line can be built if there are at least the line-length number of cookies of a given type—and/or Yoshi Cookies—on the playfield. It scores all the lines that can potentially be built and then it goes with the one with the highest score. The score depends on 3 factors:
In comparing potential lines, when the points are equal, the one with the fewest steps wins out. Regarding balance, when rows take priority, columns aren’t even considered, and the other way around.
While building a line using the greedy algorithm discussed above, it is possible to inadvertently clear other lines. And such unintentional clears may even trigger chain reactions. During simulation, clearing any lines will cause the greedy algorithm to halt, at which point it will evaluate the score. Meaning, even if the result was accidental, it may potentially be a valuable discovery and its treated as such.
The greedy algorithm is applied at the start of the stage and at any time the matrix size changes. The latter happens after clearing lines and after falling rows/columns make contact with the matrix. A falling line may make contact mid-build. In that case, the current line construction ceases, the greedy algorithm executes with the modified matrix, and the bot runs with the new results.
In general, the contents and the locations of the falling lines are ignored until contact with the matrix except when they benefit the elimination of the Green Koopa Troopa Shell in rounds 11+. When the matrix has been reduced to a single row/column containing a Shell, the bot will rotate that line to pair up the Shell with a falling Yoshi Cookie when available:
The bot often successfully reduces the matrix to the point that no additional cookies can be eliminated. When that happens, the bot holds down gamepad button B to make the falling lines drop faster. The game does not reward the player for doing so with bonus points. But it diminishes idle time.
While the bot can detect and execute patterns much faster than human players, it’s not perfect. Success varies with the cookies drawn by the RNG. Luckily, the game provides infinite continues. And the bot plays on unfazed by losses. Checkout some of the videos of its gameplay at the top of this page.
The bot uses the Nintaco API to manipulate CPU Memory, to assert gamepad buttons and to receive frame rendered events. All memory addresses were discovered through exploration with the Nintaco Debugging Tools and the information has been added to the Data Crystal ROMhacking.net wiki. In the source, they appear as constants within the Addresses interface.
YoshisCookieBot_2019-06-22.zip
The .zip contains:
|
Copyright © 2019 meatfighter.com |