Efficient state-space exploration has a significant impact on reachability analysis in explicit model checking and existing tools use several variants of search heuristics and random walks in order to overcome the state-space explosion problem. We contribute with a novel approach based on a random search strategy, where actions are assigned dynamically (on-the-fly) updated potencies, changing according to the variations of a heuristic distance to the goal configuration as encountered during the state-space search. We implement our general idea into a Petri net model checker TAPAAL and document its efficiency on a large benchmark of Petri net models from the annual Model Checking Contest. The experiments show that our heuristic search outperforms the standard search approaches in multiple metrics and that it constitutes a worthy addition to the portfolio of classical search strategies.