Witsaff

I strongly expect that this note will get no traction among experienced TAS’ers until somebody demonstrates a successful application of the principles, but that’s life. ~ Corbin, 2023

Witsaff

Designed by	Corbin
Appeared in	2023
Computational class	Unknown
Reference implementation	Unimplemented
Influenced by	Make, Prolog, TLA+
File extension(s)	.witsaff

Witsaff is a proposed language for describing the layout of video games which can be completed quickly, particularly when that layout has been mechanically randomized. In the jargon, Witsaff is a language for describing randomizers: item layouts, techniques, strategies, paths, logic, and tracking.

History

Witsaff is a pseudo-acronym for "well, it's a fifty-fifty," a common utterance by speedrunning commentators. Witsaff was originally designed around the fact that item checks are usually not fifty-fifty or uniformly distributed, but highly influenced by the ambient logic of the randomizer as well as classical constructive and destructive interference from probability theory leading to classical entanglement.

The original motivation for Witsaff came from the limitations of hand calculation. In 2022, User:Corbin used a whiteboard to estimate that many common categories for Zelda 3 randomizer will place Moon Pearl in Kakariko Village over 30% of the time, a statistically-significant result that changed their route. Further calculation was stymied by the amount of variables that had to be managed, and a hand-groomed spreadsheet wasn't going to cut it. They then tried a pile of Prolog, but that wasn't satisfying due to the overhead of fitting into Prolog syntax.

Witsaff is also designed with respect to the compositional theory of tool-assisted speedrunning. This theory requires a game to be analytically described in terms of primitives which fit together using mathematical tools like quivers.

Syntax

Witsaff is mostly line-oriented, although some operators may span multiple lines. In particular, lines ending in : or ; are continued. Comments start with #. Each line describes a facet of item layout.

The idea behind a Witsaff document is to describe the vanilla layout: a game-specific well-known item layout which can be completely explored. From there, automatic tooling could compute other layouts.

Goals

An goal is a line starting with ~. It has a name and a semicolon-separated list of goals and items. The idea is that if the player can produce any of the listed goals or has any of the listed items then they can produce this goal as well. For most games, goals will always start from an implicit beginning location and branch out in a tree. Some games, famously Metroid 3, require backtracking and instead form a graph.

For example, the following snippet for Chrono Trigger randomizer describes access to the final dungeons. A comma-separated list creates conjunctions; all of the comma-separated goals within a single semicolon-separated goal are required simultaneously.

~ Death Peak: Pendant, Clone, Chrono Trigger
~ Black Omen:
    Gate Key, Dreamstone, Ruby Knife;
    Frog, Ruby Knife, Masamune;
    Death Peak

Locations

A location is a pair of an item and a goal. The idea is that if the player can produce the goal then they can obtain the item, or whatever replacement the randomizer has chosen. In the simplest arrangement, there are no other considerations. For example, Zelda 3 has an Ice Rod Cave, within which is an Ice Rod.

Ice Rod @ Ice Rod Cave

A location can belong to a group. Groups are listed at the end of a location as comma-separated tags contained by square brackets. The typical usage of a group is to indicate that the location's items can only be permuted with other items within that group. Examples include per-dungeon items in Zelda randomizers and chozo pedestals in Metroid randomizers. For example, in major/minor settings with chozo pedestals, a Metroid 3 location might be tagged with whether it is major or minor as well as whether it is chozo:

Plasma Beam @ Plasma Beam [major,chozo]

Item multipliers work within locations. Another Metroid 3 example concerns the Billy Mays Room, which has two items to check. Those items are both missile packs, so a multiplier is appropriate.

2x Missiles @ Billy Mays [minor]

Multiple items at a location can be entered with multiple lines, but usually it is easier to put them all as a comma-separated list. For example, there is a room in Zelda 3 that is only entered in randomizer runs, because it so rarely holds anything useful for the player and takes so much time to visit:

2x Bombs, 2x Arrow Pack @ Randomizer Room

Note that in all cases, the actual cardinality of the underlying ammunition is irrelevant. This is in accord with the typical randomizer design; for example, Zelda 3 randomizers assume that a player with one bomb can acquire at least five bombs.

Additionally, items can be treated as goals which yield the item, as long as the entire goal is tucked onto the left-hand side of the @. For example, there is a Metroid 3 location that has power bombs, and also a missile pack if the player has power bombs. When randomized, those power bombs might be elsewhere, so the constraint needs to be added.

Power Bombs @ Alpha Power Bombs [minor,chozo]
Power Bombs: Missiles @ Alpha Power Bombs [minor]

Techniques

A technique is a named block which conditionalizes goals or locations. The idea is that a player should be able to indicate their ambit and ability at a high level, producing multiple categories and difficulties from a single document. For example, in Metroid 3, the Alcatraz jump is an optional and difficult technique that allows the player to access the Bomb Torizo goal provided that they already have the Morphing Ball:

$ Alcatraz
  ~ Bomb Torizo: Morphing Ball

Semantics

The intended semantics for Witsaff begins with doubly stochastic matrices (DSMs). A DSM is a matrix of real numbers where every row and column sums to one. Every item is assigned a row and every location is assigned a column. Each DSM therefore represents the probability that an item is found at a location. The structure of the DSM that we are using does not care about the ordering of rows and columns; what matters is the structure relating the cells. When looked at this way, a matrix becomes a Chu space, a sort of a number-oriented crossword puzzle.

Stationary distributions

Main article: Stationary distribution

Consider the following locations and the corresponding vanilla matrix:

Green  @ Here
Blue   @ There

[1.0 0.0]
[0.0 1.0]

One of the central concepts in probability is the expectation: how much of a value we expect to observe when we measure, or how many of each type of item we expect to find when checking a location. We can turn a vanilla matrix into a stationary matrix, which stores all of the expectations, by relaxing the various symmetries. For now, the main symmetries we want to consider are transpositions which swap the location of two items or which swap the item of two locations. There's only one swap here, putting blue here and green there, and when we relax with respect to it, we obtain a matrix that is uniformly distributed.

[0.5 0.5]
[0.5 0.5]

Slicing & scaling

Let's simulate an item check. Without loss of generality, suppose we find green here. We start by slicing the stationary matrix into four blocks: the item at the location, the other possible items, the other possible locations, and the rest of the matrix. We'll also want to note that we have N=2 items remaining before this check.

[0.5 | 0.5]
-----+-----
[0.5 | 0.5]

The probability flows from the possibilities which didn't occur to the possibility that did occur. Intuitively, we want the upper-left cell to go to one and the lower-left column and upper-right row to go to zero. However, we must balance the rest of the matrix too. Fortunately, it turns out that we merely have to scale it by N / (N - 1), which accounts for the fact that we used to have N checks remaining but now we have N - 1. So we rebalance as:

[1.0 | 0.0]
-----+-----
[0.0 | 1.0]

And then we may marginalize away the upper- and left-hand blocks, leaving a reduced matrix:

[1.0]

So we may conclude that blue is there. This is a nice instance of wave interference leading to classical entanglement; as the reader may have already imagined, green is there when blue is here and blue is there when green is here.

Without loss of generality, we will let each row and column sum to some natural number. Zero indicates an item or location that has been removed. Numbers greater than one indicate a multiplier of the sort that appears in Witsaff syntax. For example, a location that has one item with a "2x" multiplier will receive a +2 adjustment to its row sum for the two extra instances of one item and a +2 adjustment to its column sum for the two extra locations containing that item. In this way, the sum of a row is the total number of copies of that item in the game, and the sum of a column is the total number of item checks that can be performed at a location. We're allowed to retain generality over DSMs because each of these greater-than-one columns and rows represents multiple columns and rows bundled together.

To understand this, let's work a more complicated example. We'll add another check here:

2x Green @ Here
Blue     @ There

The corresponding stationary matrix has a green column and a row here which sum to two. Note that the value 4/3 means that we expect one green here on average.

[4/3 2/3]
[2/3 1/3]

Now let's find green here. There are multiple checks, but we'll do just one. Again, let's slice the matrix into pieces:

[4/3 | 2/3]
-----+-----
[2/3 | 1/3]

We aren't going to flow all of the probability, just enough to sum to one. We also aren't going to discard the extra sliced blocks. Instead, we scale the bulk by N / (N - 1), which here is 3/2, just like before. We also adjust the side cells with per-column or per-row scalar; there are several formulae, and we will use s + r - rs, where s is the bulk scaling factor and r is the reciprocal of the cell to adjust. Here, this matrix is simple enough that the scalar is 3/4, representing the probability which flowed into the bulk. There are multiple ways to compute the upper-left cell, but it will be the unique value that makes its row and column add up.

[1/2 1/2]
[1/2 1/2]

Multiple checks

Now let's check multiple items at once. For sanity, we'll check a single location. First, let's add more items here and there, and their matrices:

2x Green, Blue @ Here
Green, Blue, Red @ There

[2 1 0]
[1 1 1]

[3/2 1 1/2]
[3/2 1 1/2]

This matrix is intentionally non-rectangular. Now, let's find green and red here. In order to compute the new cells, we'll use column summation; similarly, if we wanted to check multiple items at a location, as with hints in Zelda 5 randomizer, then we might alter multiple cells in a column and require row summation instead. To make this clear, first let's find green here. The bulk scaling factor s is 6/5.

[3/2 | 1 1/2]    [... | ...    ]
-----+------- => -----+---------
[3/2 | 1 1/2]    [... | 6/5 3/5]

The generalized formula for scaling a row/column outside the bulk is r + s - rs, where r is the intended row/column sum divided by the outer cell; the earlier formula we saw is for when the sum is one. For the row, that sum is three, so r=2 and the scalar is 4/5. For the columns, r=2 and the scalar is 4/5 there as well. This sort of symmetry only occurs when a matrix has a trivial logic; there's nothing preventing any color from being here nor there. We can then compute the upper-left value by summation and subtraction.

[... | 4/5 2/5]    [4/5 | 4/5 2/5]    [4/5 4/5 2/5]
-----+--------- => -----+--------- => [6/5 6/5 3/5]
[6/5 | 6/5 3/5]    [6/5 | 6/5 3/5]

At this point, writing out every step crowds the page. The reader can go ahead and try to find red here, in which case the result will be:

[1/2 1/2 0]
[3/2 3/2 0]

Or they can find a blue (or symmetrically another green) here, resulting in:

[1/2 1/4 1/4]
[3/2 3/4 3/4]

The interpretation of a zero column is that we have found every instance of an item. Similarly, a zero row indicates that we have checked an entire location.

Note that the probability of another green here is 1/2 regardless of whether we find blue or red here, another symmetry. This indicates that green's occurrence is not dependent on whether non-green finds are blue or red in particular.

Floating-point issues

Due to floating-point limitations, this approach won't scale to games with more than a few dozen types of items or distinct locations. In particular, even if we pre-learn a stationary matrix with arbitrary precision and store it in a file, we can only extract a limited amount of entropy with online tracking before reaching the noise floor. For this reason, a serious implementation of Witsaff should include an online Monte Carlo searcher which generates logically-plausible sequences of item checks and trains the matrix while tracking, even if it only twiddles the least-significant bits. Regardless of such twiddling, floating-point inaccuracies also require online renormalization of the matrix; it will suffice to randomly choose a row or column and normalize it, and for that it will suffice to Kahan-sum the row or column vector and divide by its length.

Logic

Let's consider non-trivial logic. The path there is now locked by a key:

Key, 2x Green @ Here
Treasure: Key @ There

Regardless of where the key is, the treasure is always accessible, so most speedrunners are unconcerned with questions of logic here. However, there is an interesting question here: what is the probability that the key is there, locked behind itself, logically inacessible? The answer should be in the stationary matrix. We have a column for greens, a column for treasure, and a column for the key. Let's set up the vanilla matrix first:

[2 0 1]
[0 1 0]

What kinds of symmetries can we use to relax? The column for greens already removes the swap between them, and the rows remove the swaps between different checks here. However, we could permute all of the items, subject to the constraint that some ultimate goal is still reachable. We'll say that the key isn't necessary for that goal, although it doesn't change the reasoning much. Four objects have 24 permutations, and the matrix comes out as:

[1   1/2 1/2]
[1/2 1/4 1/4]

So, in addition to expecting one green here as usual, we also expect that the treasure is here half of seeds, and the other half the runner must obtain the key here and then the treasure will be there. Additionally, we get the answer to our question: the key is there, locked behind itself, one quarter of seeds.

Let's work an example that approximates an actual Metroidvania. The following setup is isolated and simplified from Zelda 3. What is the probability that the treasure is accessible, assuming that the boss room is guaranteed to be accessible?

Key @ Torch Room
Cash @ Map Room
Cash, Tool Key: Key @ Cannon Room
Tool: Tool Key @ Beam Room
Treasure: Tool @ Boss Room

The vanilla matrix has columns for cash, key, tool key, tool, and treasure; and rows for each room in order.

[0 1 0 0 0]
[1 0 0 0 0]
[1 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]

Can we count the permutations? Sure, although there are 720 of them, and some shortcuts are appropriate. Linearity of expectation allows us to quickly hack out the following:

[1/3 1/6 1/6 1/6 1/6]
[1/3 1/6 1/6 1/6 1/6]
[2/3 1/3 1/3 1/3 1/3]
[1/3 1/6 1/6 1/6 1/6]
[1/3 1/6 1/6 1/6 1/6]

Now we must do logic ourselves. By simulation (see Witsaff/Appendix), we find that 600 of those 720 permutations will work, and those are precisely the 5/6 possibilities where the tool does not obstruct itself. By the pigeonhole principle, all other arrangements must either allow the player to grab one key, the tool, or the treasure, from which it follows that everything is accessible. We can use that simulation to work out the entire stationary matrix, too:

[8/15 1/5  1/6 1/6 1/5]
[8/15 1/5  1/6 1/6 1/5]
[8/5  4/15 1/3 1/3 4/15]
[2/3  1/6  1/6 1/6 1/6]
[2/3  1/6  1/6 1/6 1/6]

This reveals that there is an expectation of one cash item in the cannon room. It also reveals that the two keys have the same probability distribution over locations, indicating that there is a symmetry in the logical layout of the dungeon despite the functional differences in the two types of key.

Examples

The following examples were hand-crafted to imagine what might be asked from the language. The following snippet addresses a routing scenario in Zelda 3 where the Ice Rod is used to trigger (any) distant Crystal Switch and obtain the Moon Pearl:

~ distant Crystal Switch: Bow; Boomerang; Fire Rod; Ice Rod; Cane of Somaria
Ice Rod @ Ice Rod Cave
Hera Big Key @ Hera Big Key Chest [hera]
~ Hera Big Key Chest: Tower of Hera, distant Crystal Switch
Moon Pearl @ Hera Big Chest [hera]
~ Hera Big Chest: Tower of Hera, distant Crystal Switch, Hera Big Key

The following snippet enumerates the ways of accessing the X-Ray Scope in Metroid 3:

X-Ray Scope @ X-Ray Scope [major,chozo]
~ X-Ray Scope:
     6x Energy Tank, Bombs;
     2x Energy Tank, Varia Suit, Bombs;
     Ice Beam;
     Spring Ball;
     Speed Booster, Hi Jump Boots;
     Space Jump

The following snippet shows practical routing in Metroid 3 with an optional technique. Note the "1x" multiplier which has no effect but helps organize expectations around stacking/multiple items.

Power Bombs: Power Bombs @ Crateria Power Bomb [minor]
~ Crateria Power Bomb:
    Speed Booster, 1x Energy Tank;
    Space Jump
$ Infinite Bomb Jump: Bombs
  ~ Crateria Power Bomb