randomusernamerandomusername
(edited: ) 
I've recently watched a few D2 speedruns and noticed the reset strategy to get the "right" A1 town exit; I've since found the thread explaining it here: https://www.speedrun.com/d2lod/thread/wi5mn I've put some thought into why this works and how this can be exploited further.... 1. How does a pseudorandom number generator (PRNG) work? A PRNG has some internal state and when you ask it for a random number this state changes in a deterministic way. An example for a simple PRNG would be calling this function on some state x and returning the state as random result for each number generated. f(x) = x * 7 mod 13 Let's say x starts with 1 (called the seed) and we want some random numbers, here's what we get: 1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1 That's clearly a pretty bad PRNG because it is very predictable. Seeing just one result allows us to calculate the next one (because we give out the complete state as result, easy to fix). And imagine not being able to observe the full result but just a coin flip, e.g., mapping 16 to head and 712 to tail in this function for the output. Then it's much harder to predict. Now there are two properties of a RNG that we are interested in: i) how predictable is it, i.e., can we get the internal state by observing the output? The thing we are interested here is only the size of the state. You might think that i) is the more interesting thing, but it turns out the size is the limiting factor for Diablo II map generation. Our example function above only has 12 different states (values 1 to 12). That means two things: i) it repeats itself after at most 12 different outputs, see example above, it gets back to 1 in the 13th output, since that's the only state it has it'll just start over We care about ii) here. Assume that this function would be used to generate a map and our map just consists of 4 random numbers between 1 and 12 How many maps that consist of 4 numbers between 1 and 12 are there? 12 12 12 * 12 = 20736 So for example we'll never get the map 1, 10, 2, 3 because there is no such seed that generates this sequence. Or we never get a map where the same number occurs twice because it only repeats after 12 outputs, but we only look at 4. So even tough it looks like there are only very few maps our PRNG is already insufficient. 2. So you build a bad PRNG, a real game would surely use a better one with more than 12 possible seeds? Diablo 2 seems to use a RNG with a seed of 64 bits: https://github.com/OpenDiablo2/OpenDiablo2/blob/8a547ebf0e23daedbaf0c5717b9f81b72a74ecb0/d2core/d2gamestate/d2gamestate.go#L22 That means there are a total of 2^64 (that's 18,446,744,073,709,551,616) different possible maps. Diablo 2 maps have lots of coin flip (or 3way or 4way) "decisions" that are being made during generation. • Town exits in A1 and A2 You can probably find tons of these examples. Let's look at each of these decisions as a coin flip decision. For most it's clearly more than a single coin flip (4 town exits in A1, 3 exits for many areas), let's ignore that and say there's one coin flip on average in each decision. How many of these coin flips in maps can you find? 100? Probably! How many different maps are there theoretically if they only consist if 100 coin flips? 2^100 is way more than 2^64. It's a factor of 2^36 more, that's around a factor of 68 billion more. Diablo 2 can only make 64 coin flips for map generation without becoming predictable. There are more than 64 coin flips in maps, so we can gain some information by observing maps. A lot of things that could be possible are simply never generated due to this limitation and there are unexpected correlations that can be exploited. 3. Some assumptions about map generation in Diablo 2 There's one big assumption to make this useful that seems to be true: The whole map is generated at once for all acts. This is important: the whole problem could be avoided if D2 generated maps as you first enter the area. Because the PRNG state would then be influenced by whatever you did before you entered the area (such as kills, spell damage calculations, whatever else the seed is being used for). This can be tested: start the game with seed X and check in new games whether all acts look the same in different playthroughs. I guess they do? 4. Finding correlations (in an automated way) There are probably way more correlations than have been found. There's probably stuff like "real tomb was circle, therefore exit in area X faces direction Y". These could be figured out: i) make a list with easily identifiable "markers" like the examples I gave in 2) Once you got enough data you can write a simple tool to find correlations. Note that these can be more complex than just one finding implies one other. It could be that three different decisions are tails imply that another two can never be heads. Gathering that data can be automated. Inject some code in the game, make it generate maps (in the simplest case by just starting a game). Look at what it generated in memory. Example code from a map hack looks easy enough: https://github.com/planqi/slashdiablomaphack/blob/master/BH/Modules/Maphack/Maphack.cpp#L802 Stuff it finds has a position and an ID. Something like finding "tower in A1 is on the left part of the map" or "exit in arcane sanctuary is top right" is easy to figure out based on this. No, I didn't do any of this. I didn't even play the game in 15 years... I'm just procrastinating here... 5. Fun fact: more serious PRNG problems This "limitation" isn't really a problem for a game like D2 when played normally. But there has been at least one case of an online poker site using a seed of only 64 bits, i.e., they had only 2^64 different possibilities the deck could be shuffled. However, there are 52! ways a deck could be shuffled. 52! is way way way bigger than 2^64 (it's bigger by factor of 4 followed by 48 zeroes). Clever people did exploit that to earn serious money. (Can't find the story right now, was ~10 years ago) Problems with the PRNG in slot machines are also not unheard of, there's a fun story of people feeding the output of slot machines to a phone app which then told them when to bet a lot of money because the next move is gonna be a winner: https://www.wired.com/2017/02/russiansengineerbrilliantslotmachinecheatcasinosnofix/ Edit 1: removing accidental smileys 
Bender_Bender_

Some people in MrLlamaSC discord are trying to do just that, mainly aimed at figuring out the arcane ( https://discordapp.com/invite/0cdE0TjHEACCSO2L if you want to join them). They have gathered data from like 20k seeds Problem is there is an insane amount of stuff you can combine with each other, so if you just want to bruteforce check for correlations, you probably have to ask NASA or google if they are willing to borrow you a supercomputer for a few month to get it done. Then looking at speedrunning, the relations need to be something thats actually useable for us. Lets say something in radamentlevel would tell you the arcane direction, "just get lucky" would still be the fastest strat. 
randomusernamerandomusername

The correlation itself for the relevant parts can be calculated with no problems. No brute force needed because we're not interested in all combinations and outcomes. Idea is to define m markers that are easily accessible (obviously would use something like waypoint position, exit directions that you take anyways) and run that for n seeds. Then calculate probabilities for the outcome of all these markers, e.g. it might be 50/50 if town exit in A2 is left or right. Call this the baseline. Next look at a marker you are interested in such as "Arcane Sanctuary is top left" and look again at the probabilities for all other markers for the subset of samples that have the marker you are interested in. Calculate the difference to the baseline. Or the difference to the remaining samples (i.e., the ones without the marker you are looking for). If that tells you "town exit A2 is top left 70%, only 30% top right" then you've found a useful correlation. That's a O(m * n) operation for each marker you care about, easy! Key is you need lots of samples and lots of markers (because you don't know which ones end up being useful), so better automate this. 
lagdotcomlagdotcom

Wouldn't it be possible to run D2's code externally and observe the output? That is, you could repeatedly call the map generation code and observe the results by maphacking (maybe even that step could be automated). 
randomusernamerandomusername
(edited: ) 
The most elegant way would indeed be to use the server component of the game to generate maps and gather the necessary information. No UI needed and easy to run hundreds of instances in parallel. However, there's probably more custom code needed to run the scan on the map data. Running in normal singleplayer also makes initial debugging and finding "markers" easier 
327327
(edited: ) 
Diablo 2 seems to use a RNG with a seed of 64 bits: https://github.com/OpenDiablo2/OpenDiablo2/blob/8a547ebf0e23daedbaf0c5717b9f81b72a74ecb0/d2core/d2gamestate/d2gamestate.go#L22 This link is going to OpenDiablo2, I'm not sure it works the same way as the original engine. About markers  this is the first idea that comes to mind when you think about speedrun Diablo 2. But thats not how RNG in Diablo 2 works. The only 1 marker I can remember is this one  The thing is RNG works in different ways. I don`t think it works like "How many different maps are there theoretically if they only consist if 100 coin flips? Because item drops are even more random than cards. Every time you receive an item, RNG work as the first time. So it looks like every map ( https://diablo.gamepedia.com/Area_Size_(Diablo_II) ) generated separately. There is no connection betwen tower level 1 and tower level 2 at all, diablo 2 speedrun is not a new thing, if diablo 2 had markers, then they were already found. 
327327

Yeah, and the main thing  maps are not the biggest problem for speedrunners, finding a path is not a difficult part of speedrun. 
randomusernamerandomusername
(edited: ) 
64 bit seed from OpenDiablo2 was an example, actual code seems to use 32 bit per act for map generation: https://github.com/noah/d2bs/blob/328463364b8128339e00c59e40413b2242e2a10e/D2Structs.h#L361 That means there are only 4 billion possible maps for each act. Next question would be where these seeds come from (i.e., are Acts correlated? data between A1 exits and A4/5 stuff seems to be evidence of this). But that doesn't really matter. The point is that only a very small subset of the maps that you can imagine can actually be generated by the algorithm. You are misunderstanding what I mean by markers/map generation, sorry if I wasn't clear. There are only so many maps, apparently 4 billion variations per act. These maps do have markers that are an accidental result of the generation and they can be correlated to useful facts. With only 4 billion per act: that's very much in the realm of a brute force solution generating all the possible maps and figuring out what correlates with useful things. The markers are just a simple way to gain information about the map. Hard to see "this is room with ID X in position Y in this dungeon", easy to see "exit faces left". 
IndrekIndrek

"Because item drops are even more random than cards. Every time you receive an item" 327 Good discussion, just want to add that there are item drops that can be manipulated. It's possible to almost always get the same item from weapon/armor racks based on the direction you approach them. 
327327

ekgm many dungeons have layouts ... 
blazerflamewingblazerflamewing

The direction that exits face for most maps has always been known based on the starting tile of that map  tower will always be a left turn, no matter what, for example, and is therefore a bit irrelevant. The real benefit to the right right act 1 map is a fast act 1 layout, knowing which way kurast is, act 4 layout afaik. The only thing that would really benefit is if we could find correlation for arcane that does not lose more time than simply being lucky, most other maps we have a way of telling already, and time loss is simply weird generation ("3 lefts make a right", which as far as the way the maps are generated goes, isn't very predictable at all). Only exceptions to having a tell is catacombs 1 and 3 and worldstone keep 1 and 3 (both level 2 only if you find wp) 