back to main

Introduction

In Yoshi's Cookie for the Super Nintendo, the VS mode can be played against a second player or a CPU-controlled opponent. This document is my brief analysis of the implementation of the CPU-controlled opponent. I am writing with an assumption that the reader is familiar with playing the VS mode of Yoshi's Cookie. Additionally, if you are familiar with assembly language programming, there are some details that you may find interesting.

In my descriptions of the implementation, sometimes it's more convenient for me to use hexadecimal values rather than decimal values. When a number is shown in fixed-width font, it's a hexadecimal value. Otherwise, it's a decimal value. For example, if I wrote 11, that would equal a decimal value of seventeen.

Implementation Structure

The code that controls the CPU opponent is divided into subroutines, each of which represent a step in its operation. For each of these steps, I will describe it in terms of the conditions when the step starts and ends. When I say "conditions," this includes both the visible state of the game board, as well as internal memory values that are used by later steps. If there are any helper subroutines used in the step, I will try to give some details about those as well.

Top level structure and jump table

The top-level subroutine calls the subroutine for the current step. The jump address for each step is stored in a data table immediately following the top-level subroutine. The addresses are shown in the following table. Note that I start numbering the steps at 1, but the value stored for the step starts at 0 for easier data storage.

At the beginning of the game, the CPU is at step 1. The steps do not always proceed in order, so I will make note of what step changes can occur.

Step one

This step is responsible for determining which of the two game boards will be used: the one belonging to player one, or the one belonging to player two.

• Set the player two controller input values to zero. That is, stop holding any buttons.
• If a piece is currently sliding, or if player two is currently under the "slave" status effect, this step ends. There is nothing more to do until those events finish.
• Then, determine which of the two boards should be used for futher calculations. Under most circumstances, this is the player two board, since that's the one that belongs to the CPU player. But, there are circumstances under which the player one board will be used.
  • There is a helper subroutine used here and in some later steps that I call the "try for reversal" subroutine. This subroutine produces a boolean result: true if it makes sense to go for a reversal, false if it doesn't. It returns true when all of the following conditions are met:
    • Player one is under the "slave" status
    • Player one is not under the "panic" status
    • Player one's score is less than 24
    • Player one's current attack is something that will not benefit player one
  • If all of the following conditions are met, set the board to control to the player one board. Otherwise, set it to the player two board.
    • The "try for reversal" subroutine returns true
    • Player two is not under the "panic" status
    • Player two's main timer is at a value of at least 24
    • There are at least five Yoshi cookies on the player one board
• Set the delay timer and proceed to step 2.

That is quite a few conditions that must be met in order to go for a reversal attack! It is interesting to note that there are safeguards against going for it: when player one is only one point away from winning, or when player two's fuse is low. However, the amount of time remaining before player one's attack changes is not factored in here. This means that the CPU player may start going for a reversal, then stop before actually performing the reversal. In narrowly timed situations, the attack may change while the last Yoshi cookie is moving into place, usually thwarting the attempted reversal.

After choosing which board to control, a delay timer is set that will cause the next step to exit early until it counts down to zero. The delay is shorter on hard mode, and can be different at different steps. Most steps after this will one start by waiting for the delay counter and setting the delay counter when the step changes.

Time units

If a player's timer hits zero, they immediately lose the round. Time is tracked with a pair of variables: the main timer and the sub-timer. The sub-timer decrements by one every frame. When it hits zero, the main timer decrements by one, and the sub-timer is reset to its starting value. The starting value for the sub-timer is equal to the character's LIMIT value times the game speed value. Mario, Yoshi, and Peach all have a LIMIT value of 2. Bowser has a LIMIT value of 1. The game speed value is 9 on slow, 7 on medium, and 5 on fast. When the player clears cookies, the main timer resets to 80.

Step two

• If trying to control the player one board, check if performing a reversal is still a good idea. If not, go back to step one.
• If the delay timer hasn't hit zero yet, decrement the delay timer and exit.
• Store a value that indicates that this is the first time we are trying to put a match together. This may be important later if we end up having to change plans for what cookies to match. It's E for the first attempt.
• If controlling the player two board, count up all the pieces on the board. Then, choose the most popular pieces as the ones to match.
  • The pieces are checked in the order of their internal values: Heart, Flower, Green, Check, Circle, Yoshi. Ties are broken by the piece that is checked later.
  • The first and second most popular are stored as targets. But, if Yoshi cookies end up as the second most popular, nothing is used for the second target.
• If controlling the player one board, don't bother doing any counting: just set the first target to Yoshi cookies and the second target to nothing.
• Set the delay timer and proceed to step 3.

Never trying to use Yoshi cookies as the second target is interesting. This implementation can't employ a tactic of trying to make a double that uses only four Yoshi cookies in order to get an attack without needing a fifth Yoshi cookie.

Step three

• If trying to control the player one board, check if performing a reversal is still a good idea. If not, go back to step one.
• If the delay timer hasn't hit zero yet, decrement the delay timer and exit.
• For the first target cookie, count the number of that cookie that exist in each row and column. Set the row or column that has the most of the target cookie as the line in which to assemble the clear.
  • Ties are again broken in favor of rows or columns that are checked later.
  • Since all rows are checked before the columns, this ends up favoring columns.
• Set the delay timer and proceed to step 4.

This is a sensible step that most players will also attempt to take. If a row or column already has three of a target cookie, it usually doesn't take long to put the two other cookies into place.

Step four

• If trying to control the player one board, check if performing a reversal is still a good idea. If not, go back to step one.
• If the delay timer hasn't hit zero yet, decrement the delay timer and exit.
• Check if the cursor is currently in the chosen clear line.
  • If the cursor is not yet in the clear line, set controller inputs to move the cursor so that it is in the chosen clear line.
  • If the cursor is in the clear line, clear all controller inputs, set the delay timer, and proceed to step 5.

The implementation will always minimize the number of moves it has to make. So, this will move the cursor at most two spaces.

Step five

Get a glass of water before this one. It's a bit more complex.

• If trying to control the player one board, check if performing a reversal is still a good idea. If not, go back to step one.
• Check the cursor's sub-position.
  • If the sub-position indicates that the cursor is between board positions, clear all controller inputs and exit.
• If the delay timer hasn't hit zero yet, decrement the delay timer and exit.
• Count how many of the target cookie are in the clear line.
  • If there are not yet four of the target cookie in the clear line, set the delay timer and proceed to step 6.
  • If there are four of the target cookie in the clear line, we need to decide whether to finish the clear by putting the fifth cookie into the clear line, or if we need to continue working to set up a double clear.
    • If we are controlling player one's board, we want to finish the reversal quickly. Set the delay timer and proceed to step 6.
    • If our score is 24, we only need one more clear to win. Set the delay timer and proceed to step 6.
    • If we have less than 24 time units left on the main timer, we don't have enough time to make a double. Set the delay timer and proceed to step 6.
• Okay, we got this far and we haven't gone to step 6 yet. Check if the target cookie is Yoshi or not.
  • If the target cookie is not Yoshi, there are two additional checks: check if we are under the blind status, and the secondary target cookie.
    • If the blind status is in effect, we'll play fair and act like we don't know how to build a double here. Set the delay timer and proceed to step 6.
    • If the blind status is not in effect, check to make sure we have a secondary target cookie. If not, we can't make a double. Set the delay timer and proceed to step 6.
    • If we have a secondary target cookie, consult the random number generator and compare the value to our character's preference for doubles.
      • If the random number is greater than or equal to the character's double preference, we decide we don't want a double. Set the delay timer and proceed to step 6.
      • If the random number is less than the character's double preference, we want to make a double. Set the first target cookie to the second target cookie, and set the second target cookie to zero. If the first part of the double was built in a row, we need to build the second part in a column. If the first part of the double was built in a column, we need to build the second part in a row. Set the cursor movement target to the place in the current build line that doesn't have the original first target. Set the delay timer, and move back to step 4 so we can move the cursor to the correct spot.
  • If the target cookie is Yoshi, we have additional checks: the "first attempt" value that we set back in step 2, and whether the current attack is beneficial or not.
    • If we are on the first attempt, represented by a value of E, keep going. If we are not on the first attempt, set the delay timer and proceed to step 6.
    • If the current attack is beneficial or neutral, set the delay timer and proceed to step 6.
    • If the current attack is harmful, we get into some character-specific and difficulty-specific behavior.
      • As Peach, provide no controller input.
      • As Mario, check if a secondary target cookie is available.
        • If so, make that into the target cookie and zero out the secondary target cookie. Set the delay timer, and go back to step 3.
        • If no secondary target cookie is available, consult the random number generator. Perform a binary AND with that value and F8, then check the result.
          • If the result is nonzero, we don't provide any controller input this frame.
          • If the result is zero (which is the case 1/32 of the time), we're going to make a second attempt. Set the "first attempt" value to D to represent this. Set the delay timer, and go back to step 3.
      • As Bowser, we check for the blind status and for a secondary target cookie.
        • If we are under the blind status, set the delay timer and proceed to step 6.
        • If we are not under the blind status, and a secondary target cookie is available, make that into target cookie and zero out the secondary target cookie. Set the delay timer, and go back to step 3.
        • If no secondary target cookie is available, consult the random number generator. Perform a binary AND with that value and FC, then check the result.
          • If the result is nonzero, we don't provide any controller input this frame.
          • If the result is zero (which is the case 1/64 of the time), set the delay timer and proceed to step 6.
      • As Yoshi on normal difficulty, we check for the blind status and for a secondary target cookie.
        • If we are under the blind status, set the delay timer and proceed to step 6.
        • If we are not under the blind status, and a secondary target cookie is available, make that into target cookie and zero out the secondary target cookie. Set the delay timer, and go back to step 3.
        • If no secondary target cookie is available, set the delay timer and proceed to step 6.
      • As Yoshi on hard difficulty, we check only for a secondary target cookie. The blind check from normal difficulty is skipped.
        • If a secondary target cookie is available, make that into target cookie and zero out the secondary target cookie. Set the delay timer, and go back to step 3.
        • If no secondary target cookie is available, set the delay timer and proceed to step 6.

This step checks some values that haven't been explained yet.

Cursor sub-position

What is a cursor sub-position? A cursor's horizontal and vertical positions are stored in one byte each. The upper bits store the board position, and the lower bits store the sub-position. For example, a value of 2A means that the cursor is at board position 2 and sub-position A. The board position corresponds to an actual row or column on the board, so its value will always be between 0 (the leftmost column and bottommost row) and 4 (the rightmost column and topmost row), inclusive. The sub-position is what lets movement happen gradually as a directional input is held down. Each frame that a directional input is held down, 2 is added to (for moving right or up) or subtracted from (for moving left or down) from the position. If no directional inputs are held down, the sub-position is set to 8. So, a value of 18 represents the cursor at rest in row or column 1.

It would take eight frames of continuous input for the cursor to move from one "rest point" to the other. But, the cursor's board position will change sooner than that! Consider a cursor currently at rest. When moving up or right, the board position will move to the next value after four addition operations (for example, 18, 1A, 1C, 1E, 20). When moving down or left, the board position will move to the next value after five subtraction operations (for example, 18, 16, 14, 12, 10, 0E). Once the board position has changed, the directional input can be released, and the sub-position will snap to the rest value of 8.

Double preference

The CPU-controlled opponent doesn't always go for a double. To go for a double, a byte from the random number generator has to be less than the character's double preference value.

Peach and Bowser go for a double about 1/3 of the time. Mario goes for a double about 1/5 of the time, and Yoshi a mere 1/10 of the time. These values are not affected by difficulty.

Choices about bad attacks

The different decisions made by the characters when targeting Yoshi cookies with a bad attack available creates interesting play behaviors. The ever-patient Peach is willing to wait for the attack to change. This works well with her characteristic of the attacks changing more frequently. Mario demonstrates some patience, but will sometimes get tired of waiting and decide to try matching something else instead. Bowser is more prone to frustration, charging forward recklessly when he can't see. Yoshi has no sense of danger, never waiting for the attack to change. This fits with the slower attack change speed and higher defense: even if Yoshi ends up stumbling, it's not as much trouble as it would be for the other characters.

Step six

• If trying to control the player one board, check if performing a reversal is still a good idea. If not, go back to step one.
• For each row and column, count how many times the target piece appears.
• Do an additional count for targets in line with the cursor.
  • If building the target into a row, check column by column in the cursor's row.
  • If building the target into a column, check row by row in the cursor's column.
• If the target is present in the line with the cursor, it's possible to pull it in to the line where we're building the target.
  • If the cursor is on top of a target piece, though, we don't want to move it. Slide the build line so that the cursor is over a non-target piece. Sliding fewer spaces is better, with ties going to up/right. Set the controller input to perform a slide and proceed to step 7.
  • If the cursor isn't on top of a target piece, slide the target piece in. This uses the shortest path, so it's at most two slides. Set the controller input to perform a slide and proceed to step 9.
• If the target is not present in the line with the cursor, it's not possible to pull it in.
  • For each line perpendicular to the target build line that doesn't contain the cursor, check if it contains the target piece.
    • The lines that are one move away are checked before the lines that are two moves away.
    • The line above or to the right is checked before the line below or to the left.
    • If the line contains at least one of the target piece, we need to move the cursor towards it. Set a value that stores where we want the cursor to end up, set the controller input to movement, and proceed to step 8.

After all the complex checks of step five, the step that actually puts the cookies into place is refreshingly simple. This strategy keeps the cursor on the build line at all times, moving the cursor to a place where the target cookie can be pulled in. The build line slides so that the cursor is on top of a non-target cookie, and the target cookie is pulled in.

Steps seven, eight, and nine

These steps are discussed together because they fulfill similar purposes: they keep the controller inputs the same until a certain condition is met.

• Step seven keeps the controller input until the piece under the cursor is not the target piece. This is used when sliding the build line before pulling in a target piece.
• Step eight keeps the controller input until the cursor has been moved to a position specified in step six. This is used when moving the cursor along the build line so that it can pull in a target piece.
• Step nine keeps the controller input until the piece under the cursor is the target piece. This is used when pulling a target piece into the build line.

In all cases, when the condition is met, zero out the controller inputs and go back to step 5.

Discussion

The implementation opts for simplicity over optimality. By trying to keep the cursor in the build line, it means that there are really only four types of inputs:

• Move the cursor to the build line
• Move the cursor along the build line
• Slide the build line
• Slide a piece into the build line

There's nothing in here that tries to calculate what is most optimal from a given board state. But, although this isn't optimal, it's still reasonably good. And, of course, it doesn't make any input mistakes: given these four types of movement, it will always use the least amount of time it can.

Honestly, I'm not too sure what else to put here. I don't think I could change this for a more optimal result without dramatically increasing the implementation complexity. I think it's a useful reminder for both programming and playing Yoshi's Cookie that while optimal may be difficult and intricate, you don't always need to be perfectly optimal. A merely good solution that is much simpler to write is often good enough to meet your needs.

back to main