So I was reading "A Theory of Fun for Game Designers" and one idea particularly resonated with me. Idea is: "Games are like story generators".
The book elaborated on the distinction between "stories" and "games". If you take, say, a book, the story is there on purpose and you consume it by reading. Most computer games (the non-abstract ones) have their storylines, and - in similar manner - you learn the story by playing. That's not what I mean. This is not "story generation" because the story is sort of already there. Non-abstract games tend to be like movies and books in this regard, even if the story branches off into different variants in predefined monents. The best stuff happens when it's not the game designer, but the game and the player who create the story together.
Story of a game
I went to my first Go torunament when I was a high schooler and a beginner Go player (around 17 kyu at the time, a few weeks of experience). I tagged along with a group of friends, most of them stronger than me. We played a few rounds and had plenty of fun. I remember one of the games especially well because of how it diverged from the normal mode of play. A typical game of Go begins with several localised conflicts in different parts of the board - you might lose some points in one area, then make it up in another, then as the endgame nears everything gets connected together. In that particular game, I was about to lose a small group in the beginning. Instead of letting it go, I desparately tried to save it, investing a lot of moves in it and evenutally escalating the local confrontation in a conflict that encompassed the whole board. I attempted, in sequence, many routes of escape; every time I failed, lost my hopes for a while, then noticed another opportunity and pursued it. In the end I lost half of my stones and lost the game. I remember this moment because of how hyped up I was right after the game - "wow, what an incredible fight!" My opponent was calmer than me, had already seen this scenario unfold many times and just calmly explained "you should have given up this group at the beginning". I couldn't disagree, but I had no regrets - the fight over the meaningless group was so entertaining that I ended up seeking all my friends and boring them with the story of my colorful defeat.
This is interesting: Go is a prime example of an abstract, barebones game (even more so than Chess, where there's at least a clear metaphor of "King and his soldiers"), yet it displayed the capability to spontaneously generate a story that made me excited enough to repeat it over and over. It didn't stop there: The more experienced I got, the more elaborate stories unfolded with each game.
This situation repeated many years later with numerous video games I had a go. I remember when I discovered FTL and played it regularly for a few weeks. FTL is a "losing is fun"-style game. It becomes the most exciting when things become bad: your ship is on fire, there's no oxygen in three sections and you're being boarded by space pirates. Every defeat was interesting in its own way and I often remember hitting Facebook right afterwards and quickly jotting down a 4-paragraph rant "WOW, that was a good FTL game! Here's how I lost this time..." then proceeding to describe how my whole crew ended up trapped in Med-bay, with the whole ship depressurised and doors not working.
Spelunky is another game that got me glued to the screen for a long time. Sessions varied wildly in length, from 5 minutes to over an hour, and were always spectacular, full of random encounters, often tragic and hilarious. Every time I failed in a new spectacular way or discovered something new about the game, I stood up from the machine and was like "Whoa, that was a good one!". In general, short, self-contained, diversified playthroughs are a great indicator that I'm going to have an awesome experience with a game, even if I invest very little time. (Compare and contrast with many modern AAA games, where starting it, going through publisher logos and loading the last save already takes a few minutes, and if you include the cinematic intro and tutorials, you end up needing more than an hour or two to actually get a hang of the gameplay.)
Story inside a game
I wouldn't go as far as to diss all the AAA games and their trademark cinematic story-telling. I mean, I had a great time playing Mirror's Edge (just recently). The game's plot was simple, but very immersive and well delivered. And yet I often ended each individual game session with a tiny Story of My Own - how I attempted to pass That Hallway Scene multiple times with many different approaches before finally finding out a good approach and nailing it.
I didn't play that many story-oriented games, but I do remember having a great time with Morrowind, and many years later, Fallout 3. Open-world games always struck me as impressive, but I display a tendency to drift away from the main plot and just wander around, exploring and doing side quests. Again, this kind of game doesn't tend to create a new story as I'm playing it - rather, I'm just picking up random fragments of stories that the original writers had placed here and there. One could say I would assemble my own story from existing bits and pieces lying around. This isn't exactly writing my own story, but provies good enough to keep me immersed.
"Metroidvania" games (my pet genre) have a similar effect. Both the gameplay and the storyline are quite linear: go to place X, defeat boss, get skill Y, then go to Z... However, as I'm progressing, the way forward is not obvious - I need to work it out myself, explore a semi-open world (that tends to become more and more open further on) and often backtrack to places already visited. On top of that, the level design rewards leaving the obvious route and exploring. It all sums up to a gaming experience where I'm engaged and I feel I'm writing my own story, even while I'm actually reenacting the major route.
Okay, I admit I've burned a significant part of my lifetime in online shooters like Quake 3 and CS:GO. If I squint really hard, I can see some "write your story" phenomenon here too. I get most of my satisfaction just from the challenge and competition - there's this addicting spike of endorphines whenever I get a few good headshots in a row. This is a completely different kind of fun. Still, on a good day there's so much more that can happen. Sometimes one successfully manages to push the game to its limits and pull off something one level crazier than normally. Every few games you see something special, like a super-fast flagrun in CTF, like finally nailing these wall-cancel combos in ol' good Gunz Online, or just your friend saving a seemingly lost round with good cheese... Something that doesn't just make you not brag about it, but actually stand up from the PC and talk to people like "DID YOU JUST SEE THAT?". One could complain that competitive games are more and more routine the deeper you're in, but these moments still occur and leave you with the kind of good memories that will stay with you long after you're done with the game for good.
There's a great potential in games that produce stories, rather than just telling them. I didn't realise until now that it's this phenomenon that made me prefer titles like Angband over mainstream games for such a long time. I wouldn't go as far as to claim that "a game's quality is measured by how good stories it can spontaneously create", but hell, there's a correlation and I like it.