It is often said that games should be easy to learn so that new players can "jump right into" the action. Recently I've been through a couple of discussions that refined my ideas on what makes a game enjoyable after the tutorial-mode phase of "these are the basic concepts." I think learning plays a substantial role, and I think this may be an excellent test for defining a "good" game. I haven't found a failure case yet. The general idea that I've whittled it down to is that, in an ideal game, each progressive step in mastering the game should feel as accessable as the previous one. Players should be able to evaluate their progress easily. Advancement should help to uncover new aspects of play, and ideally should offer some sense of accomplishment. My rationale is this: Players are not frustrated by chance failure(unless it's of the kind where you lose some game record of your progress like stats or plot advancement, or when failure is built into specific mechanics). What *does* make them frustrated is repeated failure and being incapable of understanding why, or how to overcome the specific challenge. And people can become addicted to a game they otherwise hate because they always think advancement is just around the corner. In FPS games, there is a division between obvious failure(in straight deathmatch) and non-obvious failure(the realistic/semi-realistic games). When I think back to games like Counter-Strike, it now seems like everyone playing is gambling - hoping for the big round. Few people have any idea of how to advance their skills, so they let probability do the work for them. Sooner or later, the big round comes, and there's satisfaction, but it's only temporary. Games like Quake don't allow this because the skill division is always entirely clear; no(or infrequent) teamplay, no randomized shooting, and a complete focus on comparing abilities. As a result fewer people play the traditional games now because it's painfully obvious just good a 'good' player is, and the learning process feels particularly arduous since it requires going out and getting beaten over and over. In any RPG the advancement is almost entirely through stats and plot; this makes them very accessable to anyone who is willing to put in the time, leaving only the caveats of grind. In Bemani(music games), the progression from the most simple songs to the most complex ones and the process of getting perfect scores is always straightfoward; reading abilities, dexterity, and timing are all tested in as direct and obvious a fashion as possible. The difficulty and grading systems always leave enough room(up to the designed limits) so that advancement is "just around the corner." For most people, it really is; the component skills are practiced 100% of the time the game is played, with very little downtime, so even small, irregular play sessions can add up. Anecdotally, many players of these games claim not to have started out with great interest, but found it so addicting that their interest became second-nature. The reason why our tastes in gaming all vary, if this concept is taken as fact, must be because of our differing learning abilities. Only a minority of people will ever be great at any one game, but people are turned off not by their maximum potential, but the marginal difficulty of advancement. Whether or not the game is actually easy isn't really the issue; it's the illusion of accomplishment that's the key. And the most accessable games will offer this hope to a broad range of players. Also, this implies that story and scripting aren't really factors to help or hurt replayability unless they are constraining the game's challenge. If by the end of the first game the player is playing to finish and not out of addiction to the gameplay, they aren't likely to play again unless they can easily return to some area they liked or make a different choice.

The basic gameplay mechanics and concepts should be (or be made) obvious very fast to the player. HOWEVER as the game progresses, the challenges/environment must step up in difficulty by a reasonable amount. This is pretty hard to achieve, and there are a few ways to circumvent problems like this :)

1) Intensive testing with non-developer relate people -being a developer and even a QA guy makes you lose focus on a game after playing through it for 1000000 times. External people help iron out potential problems, especially difficulty/gameplay learning issues.
2) A fun way for the player to improve his personal skills. There is one game that did this better than anybody else: Revenant. This was an isometric diablo-like game, that had the player controlled Mortal-Kombat style. You could execute a series of different attacks, move freely around the map, jump, dodge, do combos, etc. Attacks (or moves) were rewarded as the game progressed, AND the most important thing: you learned them during sparring sessions with your master. The player could go and spar with the master whenever he wanted, and the fights were very fun, even when you had only one basic attack to use against him. Basically, during the game, if you ran into a new monster, you could go back to the sparring session and practice some new attack combos and dodging strategies before going back and test on the monster. Other games that did this nice was X-Wing/Tie Fighter with their tunnel practice sessions that were also awarding medals on your uniform depending on your performance.

This second method might also help the player go through some poorly tested/more difficult areas since he gets really attached of learning how to play the game.