Most, if not all games, contain some element of randomization. I'm talking games here, all games, not just video games. Ball bounces, dice rolls, card shuffles, are all complex enough equations that, as far as the average human brain is concerned, they are effectively random. Often, as is the case with chess or checkers, the random element is provided by a second human. Maybe this is not so much "random" as it is simply the obscured or inscrutable tactics of another human player. The end result is the same. We simply don't know what will happen moment to moment, and we need to react to events as they unfold. Successfully predicting, or reacting to a random event makes people feel excitement, elation, a sense of accomplishment. Otherwise known as fun.
In a round of space invaders, while the enemies will always march back an forth across the screen and descend one step at a time until they reach the bottom, apparently crushing the feeble defenses the earth has mustered against them.
That is all you know for certain.
When will the enemies excrete their squiggly bombs. When will the mother-ship grace the screen, enticing you to chase it for some easy points, even if it means leaving protective cover. That information is completely obscured from the player. These moment to moment reactions create the tension required to make you feel like you have bested the invaders. They attacked. You out thought and out fought them. It was probably fun.
Fielding a few grounders can be fun, but you can't really call it a game. Randomization alone won't hold a players interest for long. You need a second element. Engagement. By keeping the randomization hidden from the player, it's easy for them to interpret an invaders random bomb drop as a deeply malicious and directed attack. I'll dig into that in a bit.
There is, seemingly, an alternative to the randomization = fun theory. Puzzles. Puzzles are a strictly linear problem to solve. They are, in fact, not random at all. In practice however the effect is the same. The solution to a puzzle is hidden from the player in such a way that it may as well have been random. A puzzle is like a dice roll that comes up 4 every time. Predicting or reacting to the dice roll the first time will provide the player with that feeling of fun. Once. Working through, and solving a puzzle will also provide the feeling of fun once. Puzzles by themselves are like fielding grounders. They aren't games, but string a bunch of puzzles together and you start to see the makings of a game.
So if randomization can create fun, but random events aren't, in and of themselves, games, what else is required?