Go Mode podcast - the Fill Algorithm and the Stats Dump

Yo podcast team!

I loved the quiz episode, I hope we get more of those soon! It's fun to be thinking about my own answers to a question (and to realize how often I'm wrong =P)

I'm writing mostly about the "percentage chance a location contains progression" section, as this seems to be a common way people read and interpret the stats dumps. However, it can often be very misleading to use this information in your actual speedruns. For example, Axiel advised that since left side of Swamp Palace only contains progression 1/10 of the time that it can often be safely ignored. This is true from the perspective of the spoiler logs, but not exactly true from the perspective of someone in the middle of a race, and I'll explain why.

The stats dumps are generated based off of spoiler logs meaning that consideration is not given to which items you have in your inventory at any particular time, which is why these stats dumps appear to show that there is a bias for certain locations containing or not containing progression. This apparent bias is due to the fill algorithm - a lot of work has been done to ensure that the fill algorithm doesn't have so much bias that it can be read like a book, however there is one fundamental "problem" that is preventing it from being 100% unbiased (wherein every location would have an equal chance of progression), and that is that the fill algorithm works to ensure that all seeds are completable. Because of the way the fill algorithm works, the vast majority of the time progressive items which are placed during the beginning of the fill process have a much higher chance of being placed in a location that requires more items to get to, and as you work through the fill algorithm, items tend to be placed in locations that have fewer and fewer requirements so that the fill can ensure that the seed is completable. The bias that we are seeing is a product of this: the more items that are required to get to a location the less likely it is that the fill algorithm will be able to place a progressive item there.

For example, at the start of a seed when I have no items it is less likely that the Desert Ledge and the two items in Desert Palace combined will have a progression item than that the 3 items in Sahasrala's closet will because we have no idea how difficult it will have been for the fill algorithm to place a progressive item in Desert Palace, which can require all sorts of combinations of items to full clear, including the book, the gloves, a weapon for lanmolas, a fire source, boots, mitts, flute, or mirror; while Saha's closet has zero requirements. However, as soon as I pick up the book, the boots, the lamp, and a sword, the probability that Desert Palace/Desert Ledge DOES have progression shoots way, way up. Not only did I discover that the logic potentially had the ability to fill a progressive item in DP early on in the logical progression, but also just having these progressive items can be accurately thought of as a potential breadcrumb toward Desert Palace. In this scenario, I would guess (although I haven't yet done the math because it's complicated) that DP + DP Ledge is actually MORE likely to contain progression than Saha's closet when you have these progressive items, despite the stats dump apparently telling you the opposite.

My own personal rule of thumb is that if a location is logically available to me, it has a baseline roughly equal chance of being just as likely to contain progression as any other logically available item location, with a slightly higher weight given to locations that require more items to get to. A sequence broken item location will actually be LESS likely to contain progression because it is out of logic. However, this is just a baseline to start my estimation from because there IS in fact an exploitable bit of bias in the fill algorithm:

Because required items that were placed early on during the fill process are more likely to be filled into locations which have many requirements than items filled later on in the process, this means that required items which are filled later in the process are more likely to LEAD to these locations which were filled earlier. And later filled items are most likely to be found in the earlier spheres: Sphere 1 or 2 locations. Therefore, the earlier you find a progressive item the more likely it is to lead to progression! It's not quite as simple as this, though: some items like hammer unlock far too many locations to be useful as signposts. So the way we think about this is: the earlier you find a progressive item (earlier sphere, not necessarily earlier time) the more likely it is to lead to another progression item inversely proportional to how many locations that item unlocks. For example, the Powder only logically can unlock 1 location, so if you have the Powder and the Hammer in Sphere 1 you best get your butt to the Magic Bat because it has a much higher probability than normal of containing progression.

This rule applies when you "stack" requirements together: for example, the left side of Swamp requires you to have DW access, the mirror, the hammer, and the flippers. The mirror and flippers don't unlock too many locations on their own, and if you found no items in Zora's Domain or Lake Hylia than this points very strongly to Swamp.

Another way to think about this problem of using the stats dump is that the stats you are seeing in the dump include seeds in which the flippers or mirror are not even accessible until you get to Ganon's Tower! So no wonder it would be as low as a 10% chance that left side SP contains progression among all seeds. However, in a seed in which you have all of the items to get to the left side of Swamp then the likelihood that left side SP has progression shoots way, way up.

This is what makes it so, so dangerous to make any sort of routing decision based off of the stats dump: the later you are into a seed the more and more likely it is that the stats dump is actually telling you the opposite of what you should be doing. For example, if I ignored Ice Rod Cave all seed and I'm at the point where my last two locations are Trinexx and Ice Rod Cave, it is far, far less likely that Ice Rod Cave has a progression item because it was probably considered late in the fill while Trinexx was likely considered early and there were many, many more items which were required to get me inside of TR and allow me to defeat Trinexx than there are to go to Ice Rod Cave. That said, if you are in the flute menu deciding where to go you should still probably check Ice Rod Cave first because I mean, come on, it takes a fraction of the time and you could avoid going all the way back through TR =P Just because the stats tell you it's more probable for something to be somewhere, that doesn't mean it can't be elsewhere.

Okay, rant over.

I'm honestly not an expert on this stuff and these ideas came from the' "How to Read the Logic" doc made by fantallis, which I highly recommend to people wanting to understand the fill and how to take advantage of the bias to make smart routing decisions:  https://www.dropbox.com/s/vh5voea4s0e3cha/how_to_read_the_logic.pdf?dl=0

All the best,
Qirn