Portal de Periódicos da CAPES

Exploration in NetHack With Secret Discovery

2018; Institute of Electrical and Electronics Engineers; Volume: 11; Issue: 4 Linguagem: Inglês

10.1109/tg.2018.2861759

2475-1510

Jonathan Campbell, Clark Verbrugge,

Optimization and Search Problems

Roguelike games generally feature exploration problems as a critical yet often repetitive element of gameplay. Automated approaches, however, face challenges in terms of optimality, as well as due to incomplete information, such as from the presence of secret doors. 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 toward better automation for players, as well as heuristics applicable to fully automated gameplay.