> The implications of this competition are techniques for greatly increasing the replayability of games,
> since each gameplay session could present new levels to the player."
Utterly incorrect. People have this conceptual idea that gameplay is about merely providing a framework in which people exercise their skills. It's utterly wrong and I'll demonstrate why.
Back in the 80's, there was an air-combat game. Think it might've been F15-Strike Eagle... which included the concept of random missions in which you were sent out to hit one random air target and one random ground target for each mission.
It was the most boring thing I've ever seen. One random target is the same as another. And it very quickly becomes a case of "Why bother?". There's no progression, no reward. It's just a way of playing the same thing over and over again.
In the ensuing years, I've viewed a lot of games. And the one truism I've always found is that the length of the game and the amount of enjoyment I get out of it is directly related to the amount of information content the developers put into the game.
This is why the various Sim games bored me rigid. They have no information content. They provide a sandbox, a set of rules and let you go. To a certain extent Civilisation suffers the same problem, although the campaigns mitigate this to a degree. That's all very well if you want to play around but most of the games I enjoy playing most contain unique scenarios and ideas put forward by the developers which contribute to the information content inherent in the game.
Think of information content as the number of decisions and sets of consequences which the developers have explicitly coded for. For example, take a game like Uncharted 2. Say you have the possibility of collapsing a bridge as a gameplay goal. The game plays out with you either having collapsed the bridge or not. In the context of the story it could potentially shift between two opposite extremes, but in either case, the developers have explictly developed further decisions and consequences.
Now I know that branching pathways have a finite limit, because the development effort is effectively the sum of all the branching pathways that decisions allow. But I'd argue that a finite set of pathways is vastly preferably to a bunch of decisions which have a totally arbitrary effect on the outcome.
For example, in Civilisation, the exact placement of your home city has many potential possibilities, but to a large degree there's very few differences between them. Oh, the placement relative to resources and the coast is relevant, but on the whole it's a reaction to the randomness of the game. As such, it's exercising a skill, not giving you an opportunity to make meaningful decisions.
I've played CIV and enjoyed it, but I can't play it more than once every six months or so. It's just not interesting to me to repeat the same fundamental operations over and over again. I prefer Fallout 3 or Dragon Age. Dragon Age has extraordinarily high information content which is why it provides entertainment for so long. Fallout 3 actually has low information content relative to Dragon Age. Random encounters aside, there's just not that much to do beyond exploring or following the main narrative. And that narrative is not long. You'll find that most of your time in Fallout 3 is spent digging through minutiae in various locations, not exploring the game itself.
So the idea that you'll get extra replayability out of random generation of levels is completely false. You'll get a random experience which has no information content behind it. It'll be valueless except as a reaction test.