For a concrete example, I'll nominate the very first video game I ever played: The Legend of Zelda for the NES. This is by no means an easy game, however, so I'

For a concrete example, I'll nominate the very first video game I ever played: The Legend of Zelda for the NES. This is by no means an easy game, however, so I'd alter the win condition: you don't need to beat the whole game, just collect a single piece of the Triforce. As a kid I was able to gather the first 6 pieces of the Triforce without any outside help. I think an AI should be able to get at least one, given that it's playing a video game for the first time. As for the "embedded knowledge", I'm happy to talk about context in terms of cultural references, heroes, the monomyth, etc. The Zelda series draws heavily on these concepts, though I am not sure how much I knew of them as a 6-year-old.