In a game, there's always a tradeoff between having a simple set of rules that can be learned quickly, and more complicated rules that allow for more complex interactions. Measuring complexity isn't as simple as just counting the number of possible actions, since games like Go come with very simple rules but a baffling number of possible moves, making it quite inaccessible to novice players. The goal of minimal games, then, is to restrict the number of controls and mechanics that must be learned to participate in a game, while creating a reasonably-sized action space in which gameplay takes place.
Following the recommendation of Andy Nealen (@nealen) I've started playing Spelunky, a very unique platformer game that has many minimal aspects. Andy plays a lot of games, both on computers and not, and is a coauthor of a paper on minimalist games (see Towards Minimalist Game Design).
The minimalism of Spelunky quickly becomes apparent: the game has a single developer, Derek Yu. It's possible that many of the game's features are the result of the fact that a single person only had so much time to add complexity to a project.
At first glance, the level design in Spelunky looks familiar to anyone who's ever played a platform game, such as one of the Mario series. But unlike in Mario, each time a game begins in Spelunky, the levels are completely new. This process is known as procedural level generation, in which some constraints and motifs are explicitly designed but most of the actual layout of a level falls to chance.
The randomness of the levels makes learning the game consist more of mastering game mechanics rather than memorizing maps. I think when most people play traditional platformer-style games, they either implicitly or explicitly learn the exact locations of enemies and powerups, and how to avoid tricky situations, which isn't possible in Spelunky. The ephemerality of the levels greatly reduces the complexity of the game, because as a player you focus less on the particulars of levels and more on pattern recognition and taking actions.
While each engagement is a novel combination of features, over time you learn how to engage particular combinations of enemies or traps.
Another unique feature of Spelunky's gameplay is the insane rate at which the explorer dies. There are dozens of ways in which the game ends, such as falling from a tall height, getting attacked by snakes, bats, or spiders, getting shot by arrows, etc. And the game is coldly calculating regarding health -- once you lose the 4 units of health you're given, the game ends and you have to start from the very beginning.
One would think that such challenging gameplay would be frustrating, but I've found is to be the opposite. Since an individual game is up to both chance and skill, the ease with which you "lose" moves the focus on the game as a whole.
In an abstract way, Spelunky has a lot in common with skateboarding. When you skate, you're constantly failing, particularly when you're skating somewhere unfamiliar or trying new tricks. But in both skateboarding and in games like Spelunky, you have to just accept that failure is an integral part of learning and that a given combination of factors (eg. level layout, board position) won't occur twice.