Mirai Senshi: Lios (1989)

Future Wars: Lios is a turn-based strategy game developed and published by Pack-In-Video, the same developers who brought us Die Hard (NES). In this game, you play as Cecilia and her army of robots. You must make it to Goinkia's castle and stop him from taking over. To do this, you must travel the overworld and select a location. Once you do, you must take out the enemy's commander robot and then the enemy's base. Then you will win and will be allowed to progress. Sometimes defeating enemies unlocks new weapons.