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.
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.