There's a relatively well-known bug in New Super Mario Bros DS where the random number generator can in fact get stuck. The odds of it happening are 0.0000001164% , though.
I will add up my experience, when mario bros (with duck hunt) was basicaly my first games i had hands on, i was 5 / 6 years old, and i agree that i did learn well basic mechanic without knowing it. edit : 4:22 And that the part that blew my mind.
Even dice are pseudo random. If you could start it in the same position and throw it the same way every time in a vacuum, it would land on the same position every time. In a way that’s what speedrunners do - control the starting position and the throw.
Makes sense. At one point in the script I used the phrase "fair dice" but decided to do away with that part to keep things a bit more simple. Thanks for watching!
By that logic, everything is pseudorandom, from the daily weather, to the placement of atoms. ...which is uh, true, save for the Schrodinger stuff and the other quantum physics shenanigans...
Yes.. but really no. The dice deform, so you can never know thier true starting position before a roll, while being shaken. Then they generate heat as they are shaken and rolled, so any subsequent roll will have for all intents a totally diffrent random location based on the unkowable state and postion of all the atoms in the dice. Of course without any mechinism for shaking the dice this is all moot, a free thrown dice can be manipulated by a person to roll fairly accuratly, they have to bounce off walls or be shaken in a cup to be fair throws. And that adds a lot of additional chaotic movement. So. yes, but youd have to make new dice for each roll, and not shake them prior to rolling.
I think the "unpredictable" part is what is important here, or at least, it's what I emphasize when explaining randomness. Even cryptographically secure PRNGs are breakable if you're able to extract the seed somehow, and typically a good CSPRNG is a combination of a PRNG that is hard to analyse combined with a way of generating a seed that is hard to guess. Before CPUs had built-in systems for generating seeds, operating systems would "accumulate entropy" by measuring other hard to predict sources, a bit like the "waiting for the player to press start" method in this video. On Unix systems, the /dev/random special file would often accumulate data from things like mouse movements, disk read timings, keyboard interactions, network latencies, etc... Technically, an advanced attacker could try to guess some of these values and reverse-engineer the rest, but if the computer has been running long enough, it becomes unreasonably hard to do so. Basically, the question isn't whether or not "true randomness" exists, but whether or not you're able to be unpredictable enough. In the case of NES games, the fact that speedrunners are able to manipulate the PRNG shows that it's not unpredictable enough to beat a motivated attacker, but for a casual player, who are the intended audience for these games, it's sufficient. On the other hand, if you're running an online casino, you're going to need some way to generate random numbers that is more secure than that. If the attacker is some sort of godlike entity capable of accurately simulating every physical phenomenon around you, then nothing you do will be random to them. For most attackers, whatever CSPRNG library is available for the programming language you're developing with is probably good enough.
We recently ran into this issue when coding a Yahtzee like game on the Game Boy where there were inherent biases when trying to use an 8-bit value for a 6 sided die. We used the truncate and rejection to account for that as well and are writing an article about it for our site. Great video!
Nice! Yeah it’s subtle but can have a huge impact if unchecked. One of the other commenters mentioned a method of reusing bits from rejected numbers to get the time cost down considerably (might be worth looking into if for nothing else that “fancy” points 😂)
While rejection sampling is good to avoid bias, there is an algorithm now that can largely avoid rejections. You multiply that 8-bit value with 20 (i.e. shift the value by 4 and 2 and add those with carry), perform some adjustment and just take the upper 8 bits of the resulting 16-bit value. (Without adjustments, you have the issue that four consecutive values come from 13 possible RNG outputs, but the fifth only from 12... which is still better than naive modulo, which discriminates against high rolls.)
That's exactly how the NES Dragon Warrior games generate random numbers within an arbitrary range. They multiply the PRNG output by the desired range and then "divide by 256" by using the high-order byte of the product. Some of the early Square RPGs on the NES, Game Boy and SNES do it this way too (while others use modulo).
Also rejection sampling from 1..160 with a triple right shift achieves something similar as masking the upper three bits. It's a shame you probably don't want to do 1..240, there's no way for integer division by 12 (or modulo 20) that's significantly faster than repeated subtraction.
@@magicalgirlnicole Can't link it in a comment but there is a paper on this, "Fast Random Integer Generation in an Interval" by Daniel Lemire (arXiv 1805.10941). The included algorithm is defined for 64-bit RNG output with a 128-bit intermediary but works with smaller numbers, too.
I've done some exploration of RNG on a few games and systems. One that caught my eye was Entombed on the Atari 2600 - The RNG is seeded by how long you hold the fire button to start the game - but not by frames. It sits in a small loop rapidly incrementing the value. RNG manip would be CYCLE perfect, not frame perfect trick! It also had the odd effect that because it was stuck in this loop waiting for you to let go, the game would never start if you just... held down the button.
Interesting. Though it's not terribly different from a modern OS where if you click and hold on a button, it's effects don't take place until you release (well, unless you're going out of your way to handle MouseDown, but almost everyone uses Click)
Yeah that’s very interesting. Halting the game until a key was released sounds like something I’d do in a program as a kid because I fundamentally misunderstood how to write input code 😂
@@kirby0louiseon that, i really hate the modern touchscreen design of "all buttons are click not mouseDown and if the player shifts the cursor one pixel it doesn't register" Seriously it's so infuriating to click quickly when you are required to stay perfectly stationary in order to click a button.. Rrr
Yeah there's a lot of other videos that do that topic *way* more justice, just thought I'd mention it here so folks were aware of *what* was being manipulated exactly.
This channel is awesome … Im 22 but started collecting NES and other retro consoles when I was 12-13. I’m starting to get back into it and learning the ins and out, and have future hardware & software projects I want to start. Your channel has been so great for learning information in a digestible way especially as someone with a non technical background.
One technical note is that the major implementations of rand() in C would double the size of the working state internally so that the period was also double, but they'd only output half of the computed value so you would get numbers that repeat out of the assumed sequence. The biggest problem was that the seed value was the same for each run of a program, so even if the period was only partially known the same values would still be output for each run. This is why usually it's recommended to seed the RNG with time( NULL ). Although, this is more of a modern consideration because not a lot of C compilers actually target a 6502 and even fewer did back in those days.
FInal Fantasy games (even 8th one) used a simple array with pregenerated 255 bytes in static order. Whenever game expected to get random number, it outputed current number and increased the pointer of table by one, wrapping after 255th byte. Very random if you know that there is always 172 after 60.
I've using same, "lut" (lookup table) with 255 pregenerated perfect random numbers. Each time next number is taken. For games it is enough, no need for more complicated. Downside is 255 bits of memory is reserved only for this. Method shown in this video does the same only with 2 operations! Definitely is better.
@@DobinSergei It depends. If your game relies on random numbers it might be a bad idea because you have a simple list of numbers. As @martinchya2546 said your players might notice there‘s an order to your „random“ numbers. True randomness might give you the same number twice in a row.
@@arkadye you are right, but in Doom randomness has much different role. It doesnt decide whether enemy will drop super powerful sword, only stuff like shotgun spread or enemy behaviour (as dar as i remember). So Doom case is fine for this method.
Polished, he just blew away every statistics professor at community colleges. Thank God they aren't paid through patreon they'd try to corner the market
Almost 100K subs, and it still feels unfairly small. I think I cracked it; you make me _feel_ like I understand everything while I really don't. Compressing a vast amount of technical knowledge into easy-to-understand videos requires incredible understanding of the topic, and you've got it. Totally worth clicking the bell, keep it up! P. S. If only you had a creator page allowing people to keep the channel running, hmmm...
Yeah I’ve been resisting setting up a RUclips membership page. But it really makes sense since I’m not able to shout out my own patreon when I have sponsorships ☹️
@@NesHacker Just do it, man. I may be wrong, but I don't think you're losing anything by doing it, and I'm certain that people would join the channel to help you out. I'd donate myself but our country is blocked from sending money to RUclips and Patreon, sadly.
great video! i was already aware that the nes has no hardware division routine but i still felt pretty clever for thinking of the "just reroll until you get a number that's in the range" method before you brought it up
I try my best to give a good amount of context rather than just showing some code and call it it a day. I’m happy you found it useful and thanks for the nice comment ☺️
It's kind of like a bubble sort, only you're not necessarily dumping identical values, you're simply axing the unwanted ones. Still, doing such a process wastes CPU cycles, so it's ideal to avoid it if you can. 🙂 Personally, I always loved a bub-sort when you don't want the same number to come up twice in a row (usually from a low range).
I have a good idea for a new video: "The code that makes Simon/Trevor climb stairs". In both Castlevania and Castlevania III, there are many glitches involving stairs. There's even an interesting one in Akumajou Densetsu in stage 6 - 4 (Sunken City) which was fixed in the international releases. A video explaining both how stairs work and how the stairs glitches happen, would be very interesting. There are also stairs glitches involving the character swap
So interesting, i took a coding class in college and wanted to write a computer version of the board game “acquire” but couldn’t think of how to do a random number generator. Little did I know that someone had already written a computer version back in the early 80s
Using the internal clock as a seed helps as well. After all, it can be re-seeded from the clock at any moment, and that number should always be different every time it is queried.
As a classic Tetris player, I find this video really interesting. Thanks to the seed being randomized before the game starts, we can have Tetris GYM and play with the same seed in two separate games.
When doing rejection sampling you can reduce the number of times you invoke the PRNG by keeping the bits you don't need in a buffer and reusing them. So for your example with a d20 since you only need 5 bits for each rejection sampling attempt, you can make 8 attempts with only 5 8-bit numbers. Because of the rate you have to try again for rejection (3/8) conveniently lines up, it means for a d20 specifically you will expect to need only one 8-bit random number on average for each dice roll if you use the random bits optimally.
Great Video! I used LFSRs to teach programming students random number generation and bitwise operations, never thought about an older system had to rely on these techniques for things now basically taken for granted. Excellent job!
Nice explanation of rejection sampling! Intuitively, if we had to pick 1-4 with a 6 sided die, we could roll it and reroll if we got 5-6, and this is the digital version of that.
I work in a field that use stimulations a lot. We generally store the random seed of a simulation's rng because we can then reproduce the entire simulation exactly with only the seed and the initial parameters.
Funny that the way I tested my RNG implementation was by writing the output to the $4011 register continuously at a decently fast rate to produce a sound with it. Since I pretty much remade what the noise channel does by default I heard the same white noise that repeats over a few seconds. But I never thought of rejection sampling, I was satisfied by masking off the bits and then looking for some value(s) to get chances of x over 2,4,8,16, etc.
The ability for PRNG to get the same results if you use the same seed can be abused in some interesting ways - look at procedurally generated games like Elite from 1984, or for a more modern example, No Man's Sky.
Literally it makes possible to generate and store huge worlds with procedural generation algorythm. Storing RNG seeds for generating smaller chunk of world, and getting exactly same map every time. Instead of just generate and store all at once. Result is much bigger worlds with same hardware resources usage.
3:43 I didn't quite understand this part: "Every time you perform this process you generate one random bit, repeat it 8 times and you get an 8-bit byte. This allows you to create all 256 8-bit numbers." My question is how you can be sure that this process generates all random numbers, and doesn't just generate, let's say, 10 in a cycle?
In general, it's not guaranteed. There are, however, feedback arrangements that are known to produce maximal-length sequences. You can search the web for "linear-feedback shift register" for more information.
It will occasionally generate repetitive bit patterns but kick itself out of it because of how the feedback function is chosen. Ultimately a run of repetitive bits isn't more or less likely than a run of "random" looking bits. The feedback function is chosen to have a maximum length sequence property, so every time it runs through until it repeats, it generates all the states once, basically providing a permutation of the number space, this is how you know it's not going to get stuck generating the same output all the time. There's basically a handful of known good feedback functions.
I think the proof has some deep ties with modern algebra and field theories. While I’ve taken a course in modern algebra 20 years ago I definitely don’t know it well enough to provide a proper proof. Though it does sound like a fun thing to do when on vacation sometime 😂
I don't have the answers as I don't fully understand the deeper math myself, but it has to do with Galois theory and primitive polynomials if you want to look into it further. Basically your choice of taps has to represent a primitive polynomial, which I believe means you need an even number of entries and they must be co-prime (here I believe that refers to the bit positions). Satisfying these conditions means, and here I get real hand wavey, that you can represent the entire space in terms of the polynomial? Similarly to how the span of a basis defines a vector space, ie the full space is defined by all possible irreducible linear combinations of the given polynomial. Or something like that. And the shift operation here is you stepping through each possible combination in your finite space, ie given a good starting point (primitive polynomial), you represent the entire space. A bad pick for the taps would have you spinning your circles and repeating some entries while skipping others
Good explanation of PRNG algorithms. FF1 NES actually doesn't use hardly any of these though, it has a set table of 256 values and cycles through them using the seed that increments once every other frame the menu cursor is visible in battle, and also every time it is used. To get random numbers for a given range, the function pulls the next value in the table, gets a 16-bit result by multiplying the 8-bit PRNG value by the 8-bit size of the range for results it wants, then takes the high byte from the 16-bit result and adds the minimum value in the range. If rolling a range, say from 20-30 it would take the next number and multiples by the range size (11 numbers from 20-30 inclusive). Lets say the seed pointed to 50 in the table, so would be 50*11 = 550 in this example, which has a high byte of 2, so we would add in the minimum of 20 and have a result of 22.
I made a short video about a 16-bit hardware pseudo-random number generator (PRNG) that uses two 74xx595 shift registers. It's pretty much like what you've explained here, but instead of software, it's all hardware-based. Is called an Xorshift PRNG, I think.
Wow, these videos are fantastic! I'm an Arduino programmer and it's awesome to see concepts from C/C++ in Arduino and what they have in common with Assembly in terms of their demonstrated applications in NES games. In Arduino, it's typical to just use a pin connected to the ADC chip to seed the RNG function and modulus math works fine as well. I'm doing my best to keep up with your videos (this one was a little easier for me - note, this isn't to say your videos aren't well explained, to the contrary, they're expertly explained; nevertheless, I don't grasp these concepts as quickly as others might since I have no background in computers at all, just what I had built myself through online learning) On to the next video!
To get a number from 0-19 out of a range (0-255) while it could look sloppy it could work. Make a table with all 256 output values. Manually assign each value in the table a return value 0-19. The random munber from 0-255 gets compared to the table and the return value is the result. Add 1 to the return and you have your d20. It would probably just be more efficient to. Just take the 8 bit random binary. Ignore the 3 bits for (32 ,64, 128) read the remaining 5 bits. (1, 2, 4, 8, 16). And keep re rolling until you get a value between 0-19. Add 1 to the result for a D20.
What I did when I needed to generate _sufficiently_ _random_ _numbers_ on a Linux-kernel based system: Get a bunch of dynamic content from the system that will be different every access (stuff in /proc/, such as uptime, RAM usage info, and various others, plus the output of dmesg, the date and time with microseconds, and various other system info and status commands), plus the previously generated hash, and a few random salt bytes (which I think I grabbed from the slow /dev/random on script launch). From this giant blob of textual data I used a hashing routine like sha512sum to produce a long string of hex digits. From this giant number I would use modulus to fit it into the small range I wanted. Using my RNG technique I spit multiple GB of random bytes into a file, then reported how many of each character was in the file -- it was almost exactly equal for each digit! It came out more accurate than all the well-known RNG algorithms, and was on-par with hardware chips. Of course it was not particularly efficient to run. It used plenty of CPU time producing the numbers. But for the task I wanted it for -- generating random hardened encryption keys in a particular way -- it worked great! Also, some will say it wasn't random because it is using fixed Linux kernel routines, blah blah, but with how many different pieces of the system I involved in producing the randomness, I don't see any way even an emulator could get it to repeat a sequence of numbers using my technique. It wasn't terribly slow like /dev/random, but just as random. I could produce around 200MiB/sec on my old computer, which at the time was faster than my hard drive could write the data out.
Creating different random numbers based on wich frame you start a certain game, is something very clever and well done to deal with such limited random combination of numbers on the nes or whether 8bit system. I personally always found those hammer brothers in SMB1 responding and appearing very random , as you would never know at wich alpatude platform they will appear because it could be the top, the middle or the lowest one,phew🤣
The first iteration of the Nintendo DS always picked the same seed. In games like Puzzle Quest you always started with the same board state. In games like "Deal or no Deal" (or whatever the game is called in the US), the maximum win was always in the same suitcase for the first game. On the Gameboy button presses where also considered for RNG. That's exploited for RNG manipulation in Pokemon Red/Blue/Yellow and probably also Gold/Silver speedruns. E.g., with this technique you can easily manipulate a male Nidoran (in Red) with (almost) perfect stats to be used during the run. And when believing Kosmic in his Mario speedrun videos for Super Mario Bros. and "Lost Levels" on the NES, the "wait until Press start", that was mentioned in the video, can be important for certain patterns in later levels of the games.
Another way to get a value in a range is to multiply the random 8-bit value with the top of the range (e.g 20) to get a 16-bit result where the top byte is between 0-19. Multiplication is still time consuming but on the whole faster than division on the NES.
2:01 They don't need to repeat. Simple example is calculating decimal expansion of pi - it never repeats. Another example is I think in video made by veritasium titled " This equation will change how you see the world (the logistic map) " about deterministic chaos but I am not fully sure
I kinda link when the randomness can be predicted / calculated. It's why I'm looking at putting "fixed" RNG in my game using the same algorithm the early Pokemon games used. So players can figure out what the next number will be if they know what's going on.
i forgot if it was iTunes or Spotify or whatever, but the story im trying to retell is that a Music Library had a lot of complaints from users that its "Shuffle" function wasnt Shuffling properly-- sometimes itd play the same song again, or would play more songs from a particular album or artist out of a much wider mix...so the Provider of that library (ie, Apple, if it was in fact iTunes) had to tweak the code, to make it LESS random...because it was actually Already Performing close to a "true random" playlist, but end-users dont realize that "true random" would mean some Repeats, or heavier distribution along a small subsection, so in order to "look" More Shuffled, they had to make it Less Randomized...tweaks like "blacklist recently played songs/albums/artists from queueing up as Next" for example...
I am blown by the ingenuity of those early RNG systems that had to be seeded with user input because there wasn't any other source of randomness such as RTC (unless added specifically to the cartridge).
I tried this but got different numbers? From 87 [01010111] shifted to 43 [00101011], since we removed 1 from end, did 43^184 (or [00101011] ^ [10111000] in BIN) with result of [10010011] = 147 🤔 next from 147 [10010011] shifted to 73 [01001001], last removed bit was 1, so [01001001] ^[01001001] gave result [11110001] = 241 .. So instead of sequence 87, 192, 201, 55, 32, 173, ... I got: 87, 147, 241, 192, 96, 48, 24, 12, 6, 3, 185, 228, 114, 57, 164, 82, 41, 172, 86, 43, ... and so on. Am I doing something wrong?😮 The sequence repeats itself after 255 values as there is no 0 (as explained in the video). Two annoying things about this generator: - even numbers get just shifted to right and therefore create very recognizable patterns of descending values in the sequence.. - sequence repeats itself with same numbers, so after a specific value you will always have the same next value as in previous run Maybe this can be fixed by getting not only "random" seed, but also "random mask" for XOR operation?
I thought NES devs saved some cycles by embedding tables with numbers on a seemingly random pattern and a counter that would cycle through it so fast that when it needed to select a number, it would look "random enough" with almost zero math operations involved. Speedrunners might break the pattern due to how fast and precise they are, but for the average player, looks random enough.
Correct. That is why hints like "10th enemy has the bomb" and other forced results always occur. 💪😎✌️ Additionally, enemy movement is almost always influenced by the player's inputs. In other words, if you're holding L, R, U, D, or "A" or "B", etc. However, there's SOOOOO much going on that not even speedrunners can force absolutely every behavior on every single frame, room, scenario, etc.
That 20 sided die is used on Dungeon and Dragon games is there any D&D games for the NES I know Zelda can be called a D & D game kinda is there any more ?
I got that calculator in 7th grade when I started Pre Algebra. Then, i liked it so much, i bought it later when I was studying for the ACT. I moved and couldnt find it so i bought it a 3rd time in college. I love that calculator!
question for programming peeps; when using a deterministic RNG like that found in most games... what's a way to reliably randomize what the 'first' seed is on power on?
this reminds me of the exploration Veritasium and Vsauce did a few gears back exploring random vs truly random. in short, no macroscopic natural process is truly random since knowing the initial conditions to a system and its properties theoretically makes it perfectly predictable. really hard to predict, but in theory not *truly* random. the only truly random systems we've discovered are quantum processes which have no discernable way to predict an outcome thanks to the ol Heisenberg Uncertainty Principle: the more you know about one part of a quantum process, the less you know about its other parts. which is one reason quantum computing is a big field of research. almost like a holy grail of encryption awesome video! now i wanna know how modern game consoles took things further than just using bigger numbers and faster processing
Im guessing XOR is used because there is a 50/50 chance of the bit being switched. I recently ready about a cipher algorithm that uses XOR because its reversable. Does reversing have anything to do with this? If not, could you use AND instead since that truth table is also 50/50?
I love it when games have rng systems that are easy to guess and exploit. GBA Fire emblem's rng system is derived from the cursor's movement and it's movement arrow's direction, which means that with savestates you can rig anything just by wiggling the cursor around a bunch Edit: it's actually.. not that. Pathing a unit's movement is done when you move the cursor and this requires a call to randomness so your unit realistically pathfinds around obstacles and units which causes a shift and changes every subsequent random number generated. Shoulda googled it
Did Pools of Radiance for the Nes use this kind of RNG? It is a port from other systems, that I assume also were 8 bit, but I'm not actually sure. Or could they have changed the math behind the system to not use d20s?
5:56 You didn't, by any chance, find any reliable data on the randomness of RAM on an NES, did you? At one point I tried to find good info to know what state to start my own emulator. I have code for all $00s, all $FFs, and all random values, but it seemed like random values caused problems in some cases, and observing actual hardware showed mostly $00 and $FF values. I might be completely wrong about this though. It was over a year ago the last time I looked into it. Just curious if you found anything worth looking into. I think for now I'll set a random state on boot, keep RAM the same on a simulated reset, and randomize on a simulated reboot. Also, funny enough, I'm using a LFSR for randomness in my emulator code as well. I wanted to learn how LFSRs worked rather than just using rand from cstdlib, so I borrowed (and cited) some code from Wikipedia. It's also used to create static when the emulator runs without a ROM.
Check out nesdev's article on "CPU power up state". Also note that this effect varies from machine to machine, so what you measured could still be completely legit (not to mention across variants, ie Famicom, top-loader, etc)
@@kirby0louise You're absolutely right. I did some more research last night, both on the forums and the wiki. This page in particular left me scratching my head because I've read through it multiple times before. I have no idea where I was getting mixed signals before. It's pretty clear that it should be treated as random noise. Different hardware can be less random, but system to system there's no consistency. I didn't do any tests on my own hardware since it's away in storage and I can't afford an Everdrive anyway. I've been dependent on online resources through the whole project, and somewhere I must have read something either outdated, non-technical, or misinformed. But at least it's just a hobby project not a commercial endeavor, so accuracy isn't mandatory. I just like it to be accurate because it helps me learn, and it feels freaking good. 😁
0:37 There is no such thing as a perfect unbiased die. Not to mention that even the way we throw the die and the die's starting position all influence the outcome.
I recommend you look at George Marsagela's paper on the xor shift algorithm. This could be implemented at any bit depth and produces a very large sample space while using no arithmetic operations simply bit shifts and logical xor. This is absolutely producable by using a memory location and a battery backed ram. It's a shame the paper wasn't published until 2003, this kind of algorithm would have been formative If used in the 1980s for video games or cryptography.
I've been programming for the nes for the last few years and random has always been a tough topic. But ill definitely be using the sample rejection method moving forward. Maybe pair it with a for loop to prevent an extended reroll time
I appreciate the comment about predictability being desirable. It's very common when people start making games to obsess over how random random is (because they see the effects directly) but will inevitably move on to more controlled randomness as more random is rarely more fun. Don't believe me? Procedural generation is all about making random numbers into something discernable, a Minecraft landscape for example. Now imagine that nice landscape is your chance to hit in an RPG and you'll start to notice what you want is not truly random, it's curated.
On other systems I programmed on I took the current position of the raster beam of the television for the seed. Wasn't that possible on the SNES? I mean having a register to read out that kind of information?
What if sprinkled around the game you regenerate a new seed from the player, instead of just from the title screen? Wouldn't that make it even more random?
Does the NES have some sort of uptime counter? If yes: wouldnt it be a good idea to use this for a prng-seed? As it is very unlikely to have exact the same timing again and again after the power-on of the console?
Yeah not built-in, like @D0Samp said and I mention in the video: you can program your own uptick counter by incrementing a memory location that holds the seed during the frame rendering VBLANK.
So without getting too into the weeds you generally don’t want to do that because you want the seed to provide entropy independent of the algorithm itself. There’s and interesting section on the Wikipedia page for PRNGs that roughly says that a good one will “extend” the entropy of another source out. So if you use the generators own entropy you’re actually losing some randomness. I’m not great with information theory though, so take this all with a grain of salt 😅
Sure does! I think a lot of synth chips did that back in the day, which is rad. I’m curious if something like the original Roland 606 drum machine uses an LFSR for its probability feature 🤔
I face same problem in arduino exsam. I made crystall ball and its start always in same answer. Then i learn what is pseudo rnd. The solution was to tie the seed number to the analog input, that gave good result 👍
Right, that's a much better way of doing it than I used in university. We were programming on GBA and were told that it didn't have rng like a pc did but because of the bias caused by the modulus division I ended up with really predictable rng.
The best way to get a truly random seed, is to measure the time from startup to the first user keystroke in microseconds, and convert that time to a seed number.
I was looking for a way to more smoothly scale 0..255 to 0..20 after watching this video. ⌈20×tanh(x/128)⌉ where x is between 0 and 255 and ⌈⌉ means the ceiling function seems to produce a nice smooth (as smooth as integers can be) curve. 🤓 Having said that I do realize it would be absolutely slow on that (or any) hardware 🤔
For a D256 can't you just define conditionals instead of writing a division algorithm? For example, if you get 0 through 15, roll again, if you get 16 through 28, that's a 1, if you get 29 through 40, that's a 2...
That food mnemonic for exclusive or is so good. Can't believe I never thought of it that way. No food on either side? Can't choose any. Food on each side? I can't decide, there's too many choices!
I think you're confusing the size of the generators state with the size of its output. If zero is not a valid seed then how could an 8-bit generator generate 256 different outputs, zero being one of them.
Yeah that was a convolution I noticed as a result of an earlier version of the script not being rewritten. Tried my best to ensure I used the moniker “internal state” where I could in the graphics to try and clarify it when making the graphics (as rewriting and recording that section would have delayed an already very delayed project). Sorry about that!
On systems with a real-time clock, they often use the current date and time as part of the seed. That's usually how it was done in DOS games for example. On modern systems, you'd just reuse whatever your programming language provides, as all standard libraries have support for random number generation.
But, if this RNG algorithm can’t start with 0 or it will get stuck, surely that means it can also never output a 0, since the output is the starting point for the next iteration? So wouldn’t the d20 code want to range from 1-20 instead of 0-19?
There's a relatively well-known bug in New Super Mario Bros DS where the random number generator can in fact get stuck. The odds of it happening are 0.0000001164% , though.
to be fair, that is pretty random.
0.0000001164% of the time it works every time
@@Max-jz2hf they've done studies you know.
Who are they? ☠️
@@themlgbrosftw4960they did
Using hammer bros as an example of 'fun' rng is... questionable
To be fair I said “hopefully”, which in retrospect kind of makes it and unintentional meta joke 😂
As an example, it is great. People understand.
* flashbacks from 8-3 *
This got me thinking "If you can dodge a hammer, you can dodge a ball..."
I will add up my experience, when mario bros (with duck hunt) was basicaly my first games i had hands on, i was 5 / 6 years old, and i agree that i did learn well basic mechanic without knowing it.
edit : 4:22 And that the part that blew my mind.
Even dice are pseudo random. If you could start it in the same position and throw it the same way every time in a vacuum, it would land on the same position every time. In a way that’s what speedrunners do - control the starting position and the throw.
Makes sense. At one point in the script I used the phrase "fair dice" but decided to do away with that part to keep things a bit more simple. Thanks for watching!
Speedrunners are all about the loaded dice
By that logic, everything is pseudorandom, from the daily weather, to the placement of atoms.
...which is uh, true, save for the Schrodinger stuff and the other quantum physics shenanigans...
Yes.. but really no.
The dice deform, so you can never know thier true starting position before a roll, while being shaken.
Then they generate heat as they are shaken and rolled, so any subsequent roll will have for all intents a totally diffrent random location based on the unkowable state and postion of all the atoms in the dice.
Of course without any mechinism for shaking the dice this is all moot, a free thrown dice can be manipulated by a person to roll fairly accuratly, they have to bounce off walls or be shaken in a cup to be fair throws.
And that adds a lot of additional chaotic movement.
So. yes, but youd have to make new dice for each roll, and not shake them prior to rolling.
I think the "unpredictable" part is what is important here, or at least, it's what I emphasize when explaining randomness. Even cryptographically secure PRNGs are breakable if you're able to extract the seed somehow, and typically a good CSPRNG is a combination of a PRNG that is hard to analyse combined with a way of generating a seed that is hard to guess.
Before CPUs had built-in systems for generating seeds, operating systems would "accumulate entropy" by measuring other hard to predict sources, a bit like the "waiting for the player to press start" method in this video. On Unix systems, the /dev/random special file would often accumulate data from things like mouse movements, disk read timings, keyboard interactions, network latencies, etc... Technically, an advanced attacker could try to guess some of these values and reverse-engineer the rest, but if the computer has been running long enough, it becomes unreasonably hard to do so.
Basically, the question isn't whether or not "true randomness" exists, but whether or not you're able to be unpredictable enough.
In the case of NES games, the fact that speedrunners are able to manipulate the PRNG shows that it's not unpredictable enough to beat a motivated attacker, but for a casual player, who are the intended audience for these games, it's sufficient.
On the other hand, if you're running an online casino, you're going to need some way to generate random numbers that is more secure than that. If the attacker is some sort of godlike entity capable of accurately simulating every physical phenomenon around you, then nothing you do will be random to them. For most attackers, whatever CSPRNG library is available for the programming language you're developing with is probably good enough.
We recently ran into this issue when coding a Yahtzee like game on the Game Boy where there were inherent biases when trying to use an 8-bit value for a 6 sided die. We used the truncate and rejection to account for that as well and are writing an article about it for our site. Great video!
Nice! Yeah it’s subtle but can have a huge impact if unchecked. One of the other commenters mentioned a method of reusing bits from rejected numbers to get the time cost down considerably (might be worth looking into if for nothing else that “fancy” points 😂)
Recently?
@@christopherr8441people still write game boy games
@@christopherr8441 Yes people still make Gameboy games for fun.
do you have any more info on the game? sounds cool!
While rejection sampling is good to avoid bias, there is an algorithm now that can largely avoid rejections. You multiply that 8-bit value with 20 (i.e. shift the value by 4 and 2 and add those with carry), perform some adjustment and just take the upper 8 bits of the resulting 16-bit value. (Without adjustments, you have the issue that four consecutive values come from 13 possible RNG outputs, but the fifth only from 12... which is still better than naive modulo, which discriminates against high rolls.)
That’s really clever. You know, sometimes I think I learn more after a video that during the research for it 😆
That's exactly how the NES Dragon Warrior games generate random numbers within an arbitrary range. They multiply the PRNG output by the desired range and then "divide by 256" by using the high-order byte of the product. Some of the early Square RPGs on the NES, Game Boy and SNES do it this way too (while others use modulo).
Also rejection sampling from 1..160 with a triple right shift achieves something similar as masking the upper three bits. It's a shame you probably don't want to do 1..240, there's no way for integer division by 12 (or modulo 20) that's significantly faster than repeated subtraction.
What are these adjustments you're referring to? Where can I find more information on this?
@@magicalgirlnicole Can't link it in a comment but there is a paper on this, "Fast Random Integer Generation in an Interval" by Daniel Lemire (arXiv 1805.10941). The included algorithm is defined for 64-bit RNG output with a 128-bit intermediary but works with smaller numbers, too.
I've done some exploration of RNG on a few games and systems. One that caught my eye was Entombed on the Atari 2600 - The RNG is seeded by how long you hold the fire button to start the game - but not by frames. It sits in a small loop rapidly incrementing the value. RNG manip would be CYCLE perfect, not frame perfect trick! It also had the odd effect that because it was stuck in this loop waiting for you to let go, the game would never start if you just... held down the button.
Interesting. Though it's not terribly different from a modern OS where if you click and hold on a button, it's effects don't take place until you release (well, unless you're going out of your way to handle MouseDown, but almost everyone uses Click)
Yeah that’s very interesting. Halting the game until a key was released sounds like something I’d do in a program as a kid because I fundamentally misunderstood how to write input code 😂
@@kirby0louiseon that, i really hate the modern touchscreen design of "all buttons are click not mouseDown and if the player shifts the cursor one pixel it doesn't register"
Seriously it's so infuriating to click quickly when you are required to stay perfectly stationary in order to click a button.. Rrr
@@NesHacker to be fair it's the bloody 2600
Awesome! Glad to see you finally tackle this topic in a video! I always find the "RNG manipulation" done in speed runs very fascinating
Yeah there's a lot of other videos that do that topic *way* more justice, just thought I'd mention it here so folks were aware of *what* was being manipulated exactly.
This channel is awesome … Im 22 but started collecting NES and other retro consoles when I was 12-13. I’m starting to get back into it and learning the ins and out, and have future hardware & software projects I want to start. Your channel has been so great for learning information in a digestible way especially as someone with a non technical background.
One technical note is that the major implementations of rand() in C would double the size of the working state internally so that the period was also double, but they'd only output half of the computed value so you would get numbers that repeat out of the assumed sequence. The biggest problem was that the seed value was the same for each run of a program, so even if the period was only partially known the same values would still be output for each run. This is why usually it's recommended to seed the RNG with time( NULL ). Although, this is more of a modern consideration because not a lot of C compilers actually target a 6502 and even fewer did back in those days.
Still, good information to share for those who are interested! Thanks 😊
FInal Fantasy games (even 8th one) used a simple array with pregenerated 255 bytes in static order. Whenever game expected to get random number, it outputed current number and increased the pointer of table by one, wrapping after 255th byte. Very random if you know that there is always 172 after 60.
I've using same, "lut" (lookup table) with 255 pregenerated perfect random numbers. Each time next number is taken. For games it is enough, no need for more complicated.
Downside is 255 bits of memory is reserved only for this.
Method shown in this video does the same only with 2 operations! Definitely is better.
@@DobinSergei It depends. If your game relies on random numbers it might be a bad idea because you have a simple list of numbers. As @martinchya2546 said your players might notice there‘s an order to your „random“ numbers. True randomness might give you the same number twice in a row.
Doom did the same thing.
@@arkadye you are right, but in Doom randomness has much different role. It doesnt decide whether enemy will drop super powerful sword, only stuff like shotgun spread or enemy behaviour (as dar as i remember). So Doom case is fine for this method.
Your videos are getting so polished these days!
Polished, he just blew away every statistics professor at community colleges. Thank God they aren't paid through patreon they'd try to corner the market
Almost 100K subs, and it still feels unfairly small. I think I cracked it; you make me _feel_ like I understand everything while I really don't. Compressing a vast amount of technical knowledge into easy-to-understand videos requires incredible understanding of the topic, and you've got it. Totally worth clicking the bell, keep it up!
P. S. If only you had a creator page allowing people to keep the channel running, hmmm...
Yeah I’ve been resisting setting up a RUclips membership page. But it really makes sense since I’m not able to shout out my own patreon when I have sponsorships ☹️
@@NesHacker Just do it, man. I may be wrong, but I don't think you're losing anything by doing it, and I'm certain that people would join the channel to help you out. I'd donate myself but our country is blocked from sending money to RUclips and Patreon, sadly.
great video! i was already aware that the nes has no hardware division routine but i still felt pretty clever for thinking of the "just reroll until you get a number that's in the range" method before you brought it up
i love how when a person thinks of how to generator random numbers, they instantly start off with circular logic
y u didnt call the video "randomNESs"?
cause they never thought of that
Good play on words. He's probably more scientific than creative, would make a good Statistics teacher.
This is a fantastic resource. I've not heard of the rejection sampling technique before, definitely going to use that in the future
I try my best to give a good amount of context rather than just showing some code and call it it a day. I’m happy you found it useful and thanks for the nice comment ☺️
It's kind of like a bubble sort, only you're not necessarily dumping identical values, you're simply axing the unwanted ones. Still, doing such a process wastes CPU cycles, so it's ideal to avoid it if you can. 🙂 Personally, I always loved a bub-sort when you don't want the same number to come up twice in a row (usually from a low range).
I have a good idea for a new video: "The code that makes Simon/Trevor climb stairs".
In both Castlevania and Castlevania III, there are many glitches involving stairs. There's even an interesting one in Akumajou Densetsu in stage 6 - 4 (Sunken City) which was fixed in the international releases.
A video explaining both how stairs work and how the stairs glitches happen, would be very interesting.
There are also stairs glitches involving the character swap
So interesting, i took a coding class in college and wanted to write a computer version of the board game “acquire” but couldn’t think of how to do a random number generator. Little did I know that someone had already written a computer version back in the early 80s
Using the internal clock as a seed helps as well. After all, it can be re-seeded from the clock at any moment, and that number should always be different every time it is queried.
As a classic Tetris player, I find this video really interesting.
Thanks to the seed being randomized before the game starts, we can have Tetris GYM and play with the same seed in two separate games.
4:17 depending on the taps the number of random numbers can be way less than the size of the container
When doing rejection sampling you can reduce the number of times you invoke the PRNG by keeping the bits you don't need in a buffer and reusing them. So for your example with a d20 since you only need 5 bits for each rejection sampling attempt, you can make 8 attempts with only 5 8-bit numbers. Because of the rate you have to try again for rejection (3/8) conveniently lines up, it means for a d20 specifically you will expect to need only one 8-bit random number on average for each dice roll if you use the random bits optimally.
Oh that’s super smart! Thanks for sharing 😀
This is my first video of yours. It was fun and educational!
Welcome aboard!
Great Video! I used LFSRs to teach programming students random number generation and bitwise operations, never thought about an older system had to rely on these techniques for things now basically taken for granted. Excellent job!
Nice explanation of rejection sampling! Intuitively, if we had to pick 1-4 with a 6 sided die, we could roll it and reroll if we got 5-6, and this is the digital version of that.
Ahhh, I hadn’t thought of it the other way around with dice. Clever! 🤓
Division method can work with dice too. If you need a number between 1-3, you can roll a 6 sided die and divide by 2, and round up any remainder.
I work in a field that use stimulations a lot. We generally store the random seed of a simulation's rng because we can then reproduce the entire simulation exactly with only the seed and the initial parameters.
Funny that the way I tested my RNG implementation was by writing the output to the $4011 register continuously at a decently fast rate to produce a sound with it. Since I pretty much remade what the noise channel does by default I heard the same white noise that repeats over a few seconds. But I never thought of rejection sampling, I was satisfied by masking off the bits and then looking for some value(s) to get chances of x over 2,4,8,16, etc.
Love your videos man! Look forward to every new one!!! ❤
I’m so glad! Sorry they take so long these days 😆
I love your work. Being a trained Mathematician and Videogame enthusiast, I love hearing the back end grit of game design
I’m a fake mathematician (read computer science BS😂)
The ability for PRNG to get the same results if you use the same seed can be abused in some interesting ways - look at procedurally generated games like Elite from 1984, or for a more modern example, No Man's Sky.
Minecraft as well with the world seed generation option and people using it to dig for quick diamonds, or was that a lie?
Literally it makes possible to generate and store huge worlds with procedural generation algorythm. Storing RNG seeds for generating smaller chunk of world, and getting exactly same map every time. Instead of just generate and store all at once. Result is much bigger worlds with same hardware resources usage.
3:43 I didn't quite understand this part:
"Every time you perform this process you generate one random bit, repeat it 8 times and you get an 8-bit byte. This allows you to create all 256 8-bit numbers."
My question is how you can be sure that this process generates all random numbers, and doesn't just generate, let's say, 10 in a cycle?
In general, it's not guaranteed. There are, however, feedback arrangements that are known to produce maximal-length sequences. You can search the web for "linear-feedback shift register" for more information.
It will occasionally generate repetitive bit patterns but kick itself out of it because of how the feedback function is chosen. Ultimately a run of repetitive bits isn't more or less likely than a run of "random" looking bits. The feedback function is chosen to have a maximum length sequence property, so every time it runs through until it repeats, it generates all the states once, basically providing a permutation of the number space, this is how you know it's not going to get stuck generating the same output all the time. There's basically a handful of known good feedback functions.
I think the proof has some deep ties with modern algebra and field theories. While I’ve taken a course in modern algebra 20 years ago I definitely don’t know it well enough to provide a proper proof. Though it does sound like a fun thing to do when on vacation sometime 😂
I don't have the answers as I don't fully understand the deeper math myself, but it has to do with Galois theory and primitive polynomials if you want to look into it further. Basically your choice of taps has to represent a primitive polynomial, which I believe means you need an even number of entries and they must be co-prime (here I believe that refers to the bit positions). Satisfying these conditions means, and here I get real hand wavey, that you can represent the entire space in terms of the polynomial? Similarly to how the span of a basis defines a vector space, ie the full space is defined by all possible irreducible linear combinations of the given polynomial. Or something like that. And the shift operation here is you stepping through each possible combination in your finite space, ie given a good starting point (primitive polynomial), you represent the entire space. A bad pick for the taps would have you spinning your circles and repeating some entries while skipping others
Good explanation of PRNG algorithms. FF1 NES actually doesn't use hardly any of these though, it has a set table of 256 values and cycles through them using the seed that increments once every other frame the menu cursor is visible in battle, and also every time it is used. To get random numbers for a given range, the function pulls the next value in the table, gets a 16-bit result by multiplying the 8-bit PRNG value by the 8-bit size of the range for results it wants, then takes the high byte from the 16-bit result and adds the minimum value in the range.
If rolling a range, say from 20-30 it would take the next number and multiples by the range size (11 numbers from 20-30 inclusive).
Lets say the seed pointed to 50 in the table, so would be 50*11 = 550 in this example, which has a high byte of 2, so we would add in the minimum of 20 and have a result of 22.
"All I have to do is find a very large prime number and multiply." - Bob Page
Awesome to see a Deus Ex quote in here! 💪😎✌️
2:39 Is that the byte of 87?
I made a short video about a 16-bit hardware pseudo-random number generator (PRNG) that uses two 74xx595 shift registers. It's pretty much like what you've explained here, but instead of software, it's all hardware-based. Is called an Xorshift PRNG, I think.
Nice that’s a fun idea :)
Wonderfully explained
Wow, these videos are fantastic! I'm an Arduino programmer and it's awesome to see concepts from C/C++ in Arduino and what they have in common with Assembly in terms of their demonstrated applications in NES games.
In Arduino, it's typical to just use a pin connected to the ADC chip to seed the RNG function and modulus math works fine as well.
I'm doing my best to keep up with your videos (this one was a little easier for me - note, this isn't to say your videos aren't well explained, to the contrary, they're expertly explained; nevertheless, I don't grasp these concepts as quickly as others might since I have no background in computers at all, just what I had built myself through online learning)
On to the next video!
To get a number from 0-19 out of a range (0-255) while it could look sloppy it could work. Make a table with all 256 output values. Manually assign each value in the table a return value 0-19. The random munber from 0-255 gets compared to the table and the return value is the result. Add 1 to the return and you have your d20.
It would probably just be more efficient to. Just take the 8 bit random binary. Ignore the 3 bits for (32 ,64, 128) read the remaining 5 bits. (1, 2, 4, 8, 16). And keep re rolling until you get a value between 0-19. Add 1 to the result for a D20.
What I did when I needed to generate _sufficiently_ _random_ _numbers_ on a Linux-kernel based system:
Get a bunch of dynamic content from the system that will be different every access (stuff in /proc/, such as uptime, RAM usage info, and various others, plus the output of dmesg, the date and time with microseconds, and various other system info and status commands), plus the previously generated hash, and a few random salt bytes (which I think I grabbed from the slow /dev/random on script launch).
From this giant blob of textual data I used a hashing routine like sha512sum to produce a long string of hex digits. From this giant number I would use modulus to fit it into the small range I wanted.
Using my RNG technique I spit multiple GB of random bytes into a file, then reported how many of each character was in the file -- it was almost exactly equal for each digit! It came out more accurate than all the well-known RNG algorithms, and was on-par with hardware chips.
Of course it was not particularly efficient to run. It used plenty of CPU time producing the numbers. But for the task I wanted it for -- generating random hardened encryption keys in a particular way -- it worked great!
Also, some will say it wasn't random because it is using fixed Linux kernel routines, blah blah, but with how many different pieces of the system I involved in producing the randomness, I don't see any way even an emulator could get it to repeat a sequence of numbers using my technique. It wasn't terribly slow like /dev/random, but just as random. I could produce around 200MiB/sec on my old computer, which at the time was faster than my hard drive could write the data out.
Fascinating video, thank you for going so in depth.
Creating different random numbers based on wich frame you start a certain game, is something very clever and well done to deal with such limited random combination of numbers on the nes or whether 8bit system.
I personally always found those hammer brothers in SMB1 responding and appearing very random , as you would never know at wich alpatude platform they will appear because it could be the top, the middle or the lowest one,phew🤣
The first iteration of the Nintendo DS always picked the same seed. In games like Puzzle Quest you always started with the same board state. In games like "Deal or no Deal" (or whatever the game is called in the US), the maximum win was always in the same suitcase for the first game.
On the Gameboy button presses where also considered for RNG. That's exploited for RNG manipulation in Pokemon Red/Blue/Yellow and probably also Gold/Silver speedruns. E.g., with this technique you can easily manipulate a male Nidoran (in Red) with (almost) perfect stats to be used during the run.
And when believing Kosmic in his Mario speedrun videos for Super Mario Bros. and "Lost Levels" on the NES, the "wait until Press start", that was mentioned in the video, can be important for certain patterns in later levels of the games.
did you check if you get an even distribution with this method?
Another way to get a value in a range is to multiply the random 8-bit value with the top of the range (e.g 20) to get a 16-bit result where the top byte is between 0-19. Multiplication is still time consuming but on the whole faster than division on the NES.
Super great content as usual!! 👊🏻
Appreciate it!
Great video, fascinating stuff
2:01 They don't need to repeat. Simple example is calculating decimal expansion of pi - it never repeats.
Another example is I think in video made by veritasium titled " This equation will change how you see the world (the logistic map) " about deterministic chaos but I am not fully sure
Thank you sir. That was a really good video ! Well explained
I kinda link when the randomness can be predicted / calculated.
It's why I'm looking at putting "fixed" RNG in my game using the same algorithm the early Pokemon games used. So players can figure out what the next number will be if they know what's going on.
i forgot if it was iTunes or Spotify or whatever, but the story im trying to retell is that a Music Library had a lot of complaints from users that its "Shuffle" function wasnt Shuffling properly-- sometimes itd play the same song again, or would play more songs from a particular album or artist out of a much wider mix...so the Provider of that library (ie, Apple, if it was in fact iTunes) had to tweak the code, to make it LESS random...because it was actually Already Performing close to a "true random" playlist, but end-users dont realize that "true random" would mean some Repeats, or heavier distribution along a small subsection, so in order to "look" More Shuffled, they had to make it Less Randomized...tweaks like "blacklist recently played songs/albums/artists from queueing up as Next" for example...
I am blown by the ingenuity of those early RNG systems that had to be seeded with user input because there wasn't any other source of randomness such as RTC (unless added specifically to the cartridge).
I love this video it helps me understand random numbers much more
I tried this but got different numbers?
From 87 [01010111] shifted to 43 [00101011], since we removed 1 from end, did 43^184 (or [00101011] ^ [10111000] in BIN) with result of [10010011] = 147 🤔
next from 147 [10010011] shifted to 73 [01001001], last removed bit was 1, so [01001001] ^[01001001] gave result [11110001] = 241
..
So instead of sequence 87, 192, 201, 55, 32, 173, ...
I got: 87, 147, 241, 192, 96, 48, 24, 12, 6, 3, 185, 228, 114, 57, 164, 82, 41, 172, 86, 43, ... and so on. Am I doing something wrong?😮
The sequence repeats itself after 255 values as there is no 0 (as explained in the video).
Two annoying things about this generator:
- even numbers get just shifted to right and therefore create very recognizable patterns of descending values in the sequence..
- sequence repeats itself with same numbers, so after a specific value you will always have the same next value as in previous run
Maybe this can be fixed by getting not only "random" seed, but also "random mask" for XOR operation?
I got the same result as you, I don’t understand what we are doing wrong 🤔🤔🤔
I thought NES devs saved some cycles by embedding tables with numbers on a seemingly random pattern and a counter that would cycle through it so fast that when it needed to select a number, it would look "random enough" with almost zero math operations involved. Speedrunners might break the pattern due to how fast and precise they are, but for the average player, looks random enough.
I think Zelda does something similar to what you’re describing.
Correct. That is why hints like "10th enemy has the bomb" and other forced results always occur. 💪😎✌️
Additionally, enemy movement is almost always influenced by the player's inputs. In other words, if you're holding L, R, U, D, or "A" or "B", etc. However, there's SOOOOO much going on that not even speedrunners can force absolutely every behavior on every single frame, room, scenario, etc.
Great explain !
I always wanted this video!
And now you have it! Glad I could deliver 🤓
thanks for description references
That 20 sided die is used on Dungeon and Dragon games is there any D&D games for the NES I know Zelda can be called a D & D game kinda is there any more ?
There are d&d games for the NES! Check this Reddit post out for more details: www.reddit.com/r/retrogaming/comments/8o4e8u/advanced_dd_nes_games/
Very clear and thorough explanation. Do you have any plans to talk about how sound works with the NES? In my opinion, that would be a fun video
another good seed or way to get a RN is to incorporate the x or y position of the player at any given time.
Great video, great channel find!! Keep it up, my friend! ❤️
I got that calculator in 7th grade when I started Pre Algebra. Then, i liked it so much, i bought it later when I was studying for the ACT. I moved and couldnt find it so i bought it a 3rd time in college. I love that calculator!
question for programming peeps; when using a deterministic RNG like that found in most games... what's a way to reliably randomize what the 'first' seed is on power on?
this reminds me of the exploration Veritasium and Vsauce did a few gears back exploring random vs truly random. in short, no macroscopic natural process is truly random since knowing the initial conditions to a system and its properties theoretically makes it perfectly predictable. really hard to predict, but in theory not *truly* random. the only truly random systems we've discovered are quantum processes which have no discernable way to predict an outcome thanks to the ol Heisenberg Uncertainty Principle: the more you know about one part of a quantum process, the less you know about its other parts. which is one reason quantum computing is a big field of research. almost like a holy grail of encryption
awesome video! now i wanna know how modern game consoles took things further than just using bigger numbers and faster processing
Im guessing XOR is used because there is a 50/50 chance of the bit being switched. I recently ready about a cipher algorithm that uses XOR because its reversable. Does reversing have anything to do with this? If not, could you use AND instead since that truth table is also 50/50?
I love it when games have rng systems that are easy to guess and exploit. GBA Fire emblem's rng system is derived from the cursor's movement and it's movement arrow's direction, which means that with savestates you can rig anything just by wiggling the cursor around a bunch
Edit: it's actually.. not that. Pathing a unit's movement is done when you move the cursor and this requires a call to randomness so your unit realistically pathfinds around obstacles and units which causes a shift and changes every subsequent random number generated. Shoulda googled it
Did Pools of Radiance for the Nes use this kind of RNG? It is a port from other systems, that I assume also were 8 bit, but I'm not actually sure. Or could they have changed the math behind the system to not use d20s?
5:56 You didn't, by any chance, find any reliable data on the randomness of RAM on an NES, did you? At one point I tried to find good info to know what state to start my own emulator. I have code for all $00s, all $FFs, and all random values, but it seemed like random values caused problems in some cases, and observing actual hardware showed mostly $00 and $FF values. I might be completely wrong about this though. It was over a year ago the last time I looked into it. Just curious if you found anything worth looking into.
I think for now I'll set a random state on boot, keep RAM the same on a simulated reset, and randomize on a simulated reboot.
Also, funny enough, I'm using a LFSR for randomness in my emulator code as well. I wanted to learn how LFSRs worked rather than just using rand from cstdlib, so I borrowed (and cited) some code from Wikipedia. It's also used to create static when the emulator runs without a ROM.
Check out nesdev's article on "CPU power up state". Also note that this effect varies from machine to machine, so what you measured could still be completely legit (not to mention across variants, ie Famicom, top-loader, etc)
@@kirby0louise You're absolutely right. I did some more research last night, both on the forums and the wiki. This page in particular left me scratching my head because I've read through it multiple times before. I have no idea where I was getting mixed signals before. It's pretty clear that it should be treated as random noise. Different hardware can be less random, but system to system there's no consistency. I didn't do any tests on my own hardware since it's away in storage and I can't afford an Everdrive anyway. I've been dependent on online resources through the whole project, and somewhere I must have read something either outdated, non-technical, or misinformed. But at least it's just a hobby project not a commercial endeavor, so accuracy isn't mandatory. I just like it to be accurate because it helps me learn, and it feels freaking good. 😁
0:37 There is no such thing as a perfect unbiased die. Not to mention that even the way we throw the die and the die's starting position all influence the outcome.
I recommend you look at George Marsagela's paper on the xor shift algorithm. This could be implemented at any bit depth and produces a very large sample space while using no arithmetic operations simply bit shifts and logical xor. This is absolutely producable by using a memory location and a battery backed ram. It's a shame the paper wasn't published until 2003, this kind of algorithm would have been formative If used in the 1980s for video games or cryptography.
I've been programming for the nes for the last few years and random has always been a tough topic. But ill definitely be using the sample rejection method moving forward. Maybe pair it with a for loop to prevent an extended reroll time
This reminds me a lot of the birthday paradox. Thank you for this.
I appreciate the comment about predictability being desirable. It's very common when people start making games to obsess over how random random is (because they see the effects directly) but will inevitably move on to more controlled randomness as more random is rarely more fun.
Don't believe me? Procedural generation is all about making random numbers into something discernable, a Minecraft landscape for example. Now imagine that nice landscape is your chance to hit in an RPG and you'll start to notice what you want is not truly random, it's curated.
5:42 the lick
Lick confirmed
On other systems I programmed on I took the current position of the raster beam of the television for the seed. Wasn't that possible on the SNES? I mean having a register to read out that kind of information?
What if sprinkled around the game you regenerate a new seed from the player, instead of just from the title screen? Wouldn't that make it even more random?
What's more fun than maths + algorithims + viedo games! a good of explanation of all this
Thanks so much, that’s really my goal: talk technical while trying to keep things accessible 🙂
Does the NES have some sort of uptime counter? If yes: wouldnt it be a good idea to use this for a prng-seed? As it is very unlikely to have exact the same timing again and again after the power-on of the console?
If you want one, you have to count them inside the VBlank routine yourself.
Yeah not built-in, like @D0Samp said and I mention in the video: you can program your own uptick counter by incrementing a memory location that holds the seed during the frame rendering VBLANK.
What if you used a RNG to generate the seed, for the RNG the player is effected by?
So without getting too into the weeds you generally don’t want to do that because you want the seed to provide entropy independent of the algorithm itself.
There’s and interesting section on the Wikipedia page for PRNGs that roughly says that a good one will “extend” the entropy of another source out. So if you use the generators own entropy you’re actually losing some randomness.
I’m not great with information theory though, so take this all with a grain of salt 😅
Fun fact, the 2A03 (NES' soundchip) also uses LFSR to generate its noise
Sure does! I think a lot of synth chips did that back in the day, which is rad. I’m curious if something like the original Roland 606 drum machine uses an LFSR for its probability feature 🤔
And other chips like the Atari POKEY and MIKEY used LFSR to generate *everything*
Does nes has floating point or fixed decimal ALU ?
Very consumable! Very understandable! Very Nice!
I face same problem in arduino exsam. I made crystall ball and its start always in same answer. Then i learn what is pseudo rnd. The solution was to tie the seed number to the analog input, that gave good result 👍
Right, that's a much better way of doing it than I used in university. We were programming on GBA and were told that it didn't have rng like a pc did but because of the bias caused by the modulus division I ended up with really predictable rng.
what are the taps for the 16 bit generator?
yeah you can measure the button press time to get the random noise value of the player
The best way to get a truly random seed, is to measure the time from startup to the first user keystroke in microseconds, and convert that time to a seed number.
I was looking for a way to more smoothly scale 0..255 to 0..20 after watching this video.
⌈20×tanh(x/128)⌉ where x is between 0 and 255 and ⌈⌉ means the ceiling function seems to produce a nice smooth (as smooth as integers can be) curve. 🤓
Having said that I do realize it would be absolutely slow on that (or any) hardware 🤔
Cool channel. Subbed!
Thanks! I appreciate it 😀
Nice camera work on those TVs! Can't tell if it is a 3D render or actual filming, but it looks great either way.
"IT'S A SECRET TO EVERYBODY" xD
So what does a NES do when you you feed it an endless string of 0s for it's seed?
Awesome preamble to the id fast inverse cube root, love this bit shifting binary maths :D
For a D256 can't you just define conditionals instead of writing a division algorithm? For example, if you get 0 through 15, roll again, if you get 16 through 28, that's a 1, if you get 29 through 40, that's a 2...
Oh that’s a clever way of doing it, similar to lookup tables as mentioned by others. Kudos 👍🏻
That food mnemonic for exclusive or is so good.
Can't believe I never thought of it that way.
No food on either side? Can't choose any.
Food on each side? I can't decide, there's too many choices!
I think you're confusing the size of the generators state with the size of its output. If zero is not a valid seed then how could an 8-bit generator generate 256 different outputs, zero being one of them.
Yeah that was a convolution I noticed as a result of an earlier version of the script not being rewritten. Tried my best to ensure I used the moniker “internal state” where I could in the graphics to try and clarify it when making the graphics (as rewriting and recording that section would have delayed an already very delayed project). Sorry about that!
What's thaf Chrono Trigger thing? Doesn't appear to be the game. 0:43
On systems with a real-time clock, they often use the current date and time as part of the seed. That's usually how it was done in DOS games for example.
On modern systems, you'd just reuse whatever your programming language provides, as all standard libraries have support for random number generation.
Does division HAVE to be a hard thing for hardware to do, or is it just that no-one figured out a fast way to do it yet?
Which NES games used random?
1:07 that empty() function bothers me. Just return (s.size == 0)
But, if this RNG algorithm can’t start with 0 or it will get stuck, surely that means it can also never output a 0, since the output is the starting point for the next iteration? So wouldn’t the d20 code want to range from 1-20 instead of 0-19?