Cooper's more technical thoughts

A record of what I'm thinking about and working on regarding computer science and software development color scheme: http://ethanschoonover.com/solarized

[lavosprimecs]

Regularity

I started this blog at the beginning of an academic quarter with the assumption that I would be posting several paragraphs almost daily. Then the quarter actually got started, and I discovered that spending a half hour or more every day writing in-depth posts was impractical.

I'm very happy and excited to report that for the first time ever in my academic career, I am learning completely new information and skills every day in every class I'm taking. On top of this, the scale of the homework in my CS classes is greater than it has ever been; I spend almost as much time per week on assignments for my 1-credit tools seminar as I did for my 4-credit intro programming class a year ago, to say nothing of the two larger CS classes I'm taking. I love how much I'm learning, but I need to spend proportionally more of my free time playing games so I don't burn out.

A key motivation for this blog was to be able to put it on my resume and demonstrate to potential employers that I'm thinking about CS and tech even outside class and that I'm capable of writing. But I was unable to build up a significant catalog of posts before recruiting season hit, and now I have to focus on the actual mechanics of talking to companies and getting an internship, so that's another impediment to regular posting.

I'll try to write shorter posts every couple of days, but by the time you read this, I will have removed "(mostly) daily" from my blog description so I don't get your hopes up.

[lavosprimecs]

Windows Explorer

Last quarter, I must have misconfigured something or allowed CCleaner to delete something it shouldn't have, because StarCraft II and Dota 2, among other programs, would crash frequently. Additionally, the Store app wouldn't open, so I couldn't upgrade to 8.1. I didn't have time during the quarter to dedicate to my computer being unusable for a reinstall or some other kind of maintenance, but I did take my hard drives home with me over break and use my old desktop to reinstall Windows. Then the fun began...

After about a week of smooth sailing, I booted it up one day to find that logging in took about 30 seconds, my desktop background did not appear, and the taskbar was blank except for the 8.1 start button, which is supposed to open the Metro start screen but instead did nothing. After some exploration, I found that I could open the task manager and just about any other program, but not Windows Explorer, the superprogram that controls the file browser and the taskbar and countless other functions. A few hours of Google and several reboots to and from safe mode did nothing. I tried to reinstall the OS from scratch, but I couldn't; according to the installer, "the drive where Windows is installed is locked." I certainly didn't give Windows permission to lock my SSD.

Luckily, a friend of mine recommended Process Hacker, a third-party task manager. From it, I was able to force-terminate Windows Explorer and run it again as an administrator. This solved my problems in desktop mode, so everything was fine for a while. But a few days later, I wanted to type something in Japanese, and the program in which I was typing locked up a few characters in. I tried again in a few other programs, and they locked up at the same point. It wouldn't be a problem right away, but it will certainly become one when I need to type for Japanese homework.

Then I came back to UW, and I knew it was entirely possible that the OS would develop even more problems migrating to new hardware. But, in fact, everything worked exactly how it did on my computer back home. The problem now was activation. I have another product key, so that's fine. I was expecting to have to type it in as soon as I booted. But the only place to type it in is the glorious Modern UI Settings app, which isn't starting. In fact, no Metro apps are starting, because they can't open when Windows Explorer is running with administrator privileges.

But recall that I can't open the start screen when Explorer is not running with administrator privileges. I dug around for the actual executable for the Store app to confirm that Metro doesn't work at all. But it only superficially works when the rest of Explorer is usable. It also doesn't work in Safe Mode. So it is impossible for me to enter my product key and get rid of the full-screen "Activate Windows" prompt that pops up every few hours when it's least convenient and forces me to wait before it gives me any way out.

Why is so much of the OS baked into one process? Why isn't it possible to use Metro when Explorer has admin privileges? Why isn't it possible to use Metro when Explorer isn't working? Why can't I enter my product key in the Desktop paradigm? Why does typing "ku" in Japanese mode freeze any program that's reading text input? Why did Windows lock my SSD? Why is Microsoft convinced that desktop operating systems are supposed to be obsolete? Once I figure out how to unlock my SSD, why should I ever use Windows again?

[lavosprimecs]

RNG, part 2: Options

As I alluded to in part 1, there are very definite, standardized solutions for cryptographically secure RNG. There are sophisticated hash and generator algorithms that flourish because of a trade-off: they can guarantee that the only way to break them is for the NSA to sneak a backdoor into industry standards, but they must be implemented perfectly according those standards in order to do their jobs. The Linux kernel RNG achieves some algorithm agnosticism by gathering "environmental noise" from low-level operations and returning a hash of it, but even that is far beyond what I need.

On the next level down are very good RNG algorithms that are not cryptographically secure. The most popular is the Mersenne Twister, which passes many statistical tests for randomness and has several other desirable properties. Its best-known implementation, MT19937, is so-called because it produces a sequences of numbers with a period of 219937 - 1. But in order to do this, the RNG must store an array of 624 integers, seed it initially, and reseed it on every loop through. I would use it for a PvP game or for procedural content generation, but it's not appropriate for PvE games, especially not on a Game Boy Advance.

I almost decided to use a linear feedback shift register, so I'll detail how it works. Store (usually as an int) a queue of bits. Each cycle, dequeue the bit at the front, xor it with the bits at certain other positions in the queue, and enqueue the result. When randomness is desired, return some amount of the queue's state. I decided against it, though, because it requires slightly more computation that the other option, it still requires particular constants to work, and it has a chance to collapse to a stream of 0s if I end up factoring input into the RNG.

I will be using a linear congruential generator because it's the simplest, fastest, most flexible option. Given a multiplier and an increment with certain properties in relation to each other and to the range of the seed, add the increment to the seed and multiply it by the multiplier to get the new seed each cycle. seed = (seed + incr) * mult. That's it. There are many options for the multiplier and increment, and even if I factor in input for reasons I'll detail later, the RNG will recover and spin along on its merry way to a full cycle of the integers. It may not be an especially controversial or obscure choice, but that's the one I'm making.

[lavosprimecs]

GBA, Part 1: Motivation

I tend to romanticize the Game Boy Advance somewhat because it was the last pure game system from a major manufacturer. It has no operating system or user-editable BIOS. If no cartridge is inserted, it doesn't even play the full splash screen. It boots directly into the game immediately when the system is turned on, and it gives full trust to whatever program it reads.

It's also pretty simple. It has 10 bits of input, with no touch or motion controls. It is usually programmed in C, unlike earlier consoles which were often programmed in platform-specific assembly. And, again, it has no OS to contend with.

For these reasons, the Game Boy Advance interests me as a programmer. I want to do some kind of project with low-level systems code targeted at a specific device, and I want to do some game programming in C. Doing these at the same time would be awesome, so my goal for the next several months is to learn enough to make a decent-sized program that will run on a GBA and then run it on a GBA.

I was almost done with RNG, Part 2 when my PC crashed today. I don't really have the motivation to rewrite it now, and I might be very busy tomorrow, so I will probably rewrite it on Thursday.

[lavosprimecs]

RNG, Part 1: Motivation

Tales of RNGesus on /r/dota2 and last week's Awesome Games Done Quick (AGDQ) charity speedrunning marathon have gotten me thinking about the role of (pseudo)randomness in games and game-like software. I'm of the opinion that the pseudorandom number generator (RNG) in games should be robust against player influence in player-vs-player (PvP) games but not in player-vs-environment (PvE) games, to the extent that games in which both are important, such as Pokémon, should maybe use separate RNGs for the separate modes. I speak as someone who watches both esports and speedruns; in general, casual play will not involve RNG manipulation anyway, so this discussion doesn't really matter when designing only for that purpose. Randomness in graphics, such as in particle effects, is also outside the scope of this discussion because it doesn't affect gameplay mechanics.

PvP games should be a level playing field as much as possible. RNG elements in competitive games don't usually appeal to me at all (one of the reasons I prefer to turn off items in Super Smash Bros.), but when they do exist, they work better in actions that happen frequently, such as crit and miss chances in Dota. In those cases, banking on one lucky shot is a calculated risk, but the benefit is reliable long-term in extended fights. RNG manipulation, if possible for high-level players, has several undesirable affects here. It makes those aspects of the design pointless, removing a potential method of game balance. It encourages players to play in unintuitive ways to exploit engine mechanics. In a networked game, it gives an unfair advantage to players whose connections to the host have more consistent latency. I don't want to watch a game of Dota where evasion means invincibility or a game of Smash where people compete to spawn overpowered items next to themselves instead of killing each other.

PvE games are a different beast. Randomness can add variety to casual play, but for the most skilled players, RNG is the enemy because the most impressive way to express their skill is to demonstrate it against reliable behavior. Strong randomness reduces the potential for speedruns to be consistently optimal. But if the RNG can be influenced, or if RNG-determined elements can be identified before they matter, more room is available for runners to master the game's mechanics and produce impressive runs. I don't know the details, but I've heard of RNG manipulation being possible real-time in several games. Failing that, at least tool-assisted speedruns (TAS), done by recording and replaying input frame-by-frame on an emulator, have the potential to showcase a "perfect" run through the game by abusing the RNG. I don't want to watch a run where the runner has to wait several seconds for a boss's weak point to be exposed or try several times to generate the right encounter purely at the mercy of RNGod.

I consider myself lucky that most games I'm interested in prototyping in the near future are PvE. Strong RNGs are challenging to implement correctly and expensive to compute, but they're a less interesting problem to me, because at any given time there's probably a state-of-the-art best solution. "Weak" RNGs are more fault-tolerant, easier to make small, and brimming with design decisions, most of which distill to one question: how weak?