Based on the first video you link (F9t3FREAZ-k), it seems Notch has a very distinct advantage already (a game-like element). In that video, he wanders around the cave systems for a long while, and always finds a path through. I assume that 'Cave game tech' demo is generated (not static as the Skycraft demo appears). But it's not just randomly generated. It's generated in a way that always affords a path through. This isn't even common IRL. Spelunking real caves is partly about finding ones that are non-trivial and traversable by humans (vertical faces and narrow sapces tend to inhibit that).