Exploration in NetHack With Secret Discovery

Abstract--Roguelike games generally feature exploration problems as a critical, yet often repetitive element of gameplay. This paper presents an algorithmic approach to exploration of roguelike dungeon environments. Our design aims to minimize exploration time, balancing coverage and discovery of secret areas with resource cost. Our algorithm is based on the concept of occupancy maps popular in robotics, adapted to encourage efficient discovery of secret access points. Through extensive experimentation on NetHack maps we show that this technique is significantly more efficient than simpler greedy approaches and an existing automated player. We further investigate optimized parameterization for the algorithm through a comprehensive data analysis. These results point towards better automation for players as well as heuristics applicable to fully automated gameplay. ANY video games place emphasis on the idea of exploration of the unknown. In roguelikes, a popular subset of Role-Playing Games (RPGs), exploration of the game space is a key game mechanic, essential to resource acquisition and game progress. The high level of repetition involved, however, makes automation of the exploration process useful, as an assistance in game design, for relieving player tedium in relatively safe levels or under casual play, and to ease control requirements for those operating with reduced interfaces [1]. Basic forms of automated exploration are found in several roguelikes, including the popular Dungeon Crawl Stone Soup. Even with full information, however, ensuring complete coverage can result in significant inefficiency, with coverage improvement coming at greater cost as exploration continues [2]. Diminishing returns are further magnified in the presence of "secret rooms," areas which must be intentionally searched for at additional, nontrivial resource cost, and which are a common feature of roguelike games. In such contexts, the complexity is less driven by the need to be thorough, and more given by the need to balance time spent exploring with respect to amount of benefit accrued (area revealed, items collected). In this work we present a novel algorithm for exploration of an initially unknown environment. Our design aims to accommodate features common to roguelike games. In particular, we aim for an efficient, balanced approach to exploration, considering the cost of further exploration in relation to the potential benefit.