Hacker News Reader

Comment by chongli | Hacker News Reader

I would be genuinely surprised if anyone can build an agent that can solve Zelda for the NES without any foreknowledge of the game. So much of that game is bound up in the human cultural tropes associated with the monomyth. To finish the game you need to have at least a basic working knowledge of what it means to be a hero. There is no obvious, short-term indicator of progress the way there is in Mario (increase the x position to win).

The process of obtaining just a single piece of the Triforce (the primary indicator of progress) is so complicated that you'll essentially never see it happen with random button-pressing. So any agent attempting to play and win Zelda is going to need to develop its own model of the game world and try to understand things that way. I don't see how that is supposed to happen though, without any context.

View on HN

As I mentioned in the other post, the curiosity bots can help with this.

They're rewarded by exploring, not by values in game.

Maybe alone they're not enough, but in conjunction with other things, I bet we could beat Zelda. I had the bot exploring enough to find the first dungeon of LoZ.

I just took a look at the curiosity video. It's funny, I think with enough refinement something like this could beat Zelda. Except it wouldn't actually know it beat the game! I feel like that is cheating, somehow.

Like maybe you could get American Fuzzy Lop [1] to beat Zelda. Isn't that the same thing, in principle?

[1] http://lcamtuf.coredump.cx/afl/

AFL might eventually get lucky, but I'm guessing you'd want a hybrid approach that combines symbolic execution with a fuzzer like AFL, e.g. QSYM [1].

[1] https://www.usenix.org/system/files/conference/usenixsecurit...

Zelda was simply a means for Nintendo to sell Nintendo Magazine subscriptions. They had to have made a killing on subscriptions, and they were absolutely required for solving games like Zelda. For example, you have to place a bomb in this one obscure location without any in-game clues as to said location. Or burn a tree.

Here's the connection to your post. I think a human and a computer have about the same chance of solving Zelda. At least a computer could be programmed to drop bombs in every rock wall in the game. For a human, that would be too brain-numbing hard.

At least a computer could be programmed to drop bombs in every rock wall in the game. For a human, that would be too brain-numbing hard.

Programming the computer to drop bombs everywhere is giving it way too much foreknowledge. I'm envisioning a computer agent not even knowing what a bomb is. Having to figure out how to beat Zelda without any context for the shapes and colours on the screen, let alone what bush to burn to find level 8 or where to play the recorder to open level 7.

This would be a test of general intelligence so I have no problem giving the agent access to the Internet. If it can figure out how to find an FAQ for Zelda and make sense of that information well enough to win the game then more power to it! That's much harder to achieve than building a bot with all of the rules of Zelda pre-programmed in.

You definitely do not need external hints to solve Zelda games. I've finished many Zelda titles without ever getting any hints. I've even finished A Link to the Past in German by using a dictionary to translate dialogue. Before that, I had not known a word of German.

He is talking specifically about Legend of Zelda, or Zelda for short, the first game in the series. https://en.wikipedia.org/wiki/The_Legend_of_Zelda_(video_gam...

Fair enough. The tree burning should had given me the hint.

That said, I did finish the original LOZ without hints too.

Riffing on this, what about Zelda-like games /with/ foreknowledge? Let's say the game has items that serve as unique keys (like boss keys or the hammer), items that serve as interchangeable keys (like regular keys or triforce pieces), and maybe specific items that modify movement directly (ladder, hookshot, pegasus boots). Additionally it has switches that toggle certain walls.

This is a stateful pathfinding problem, you can solve it with Dijkstra's. But how fast can you find the shortest route through 100 Zelda-likes?

Or take a page from maze-running bots and not provide the map up-front, but require an agent that actually explores to get information, and judge results on the sum of three times through the same game.

I don't think the with-foreknowledge case is all that interesting. We already have an expert system agent [1] that can win at the game NetHack [2]. This is a far more complicated task than any of the Zeldas, given foreknowledge.

Without foreknowledge, on the other hand, Zelda becomes a whole mess of meaningless pixels and sound waves whereas NetHack retains a level of intelligibility due to its ASCII interface.

[1] https://www.reddit.com/r/nethack/comments/2tluxv/yaap_fullau...

[2] http://www.nethack.org/

Reply on news.ycombinator.com