If you want nonstandard search or other nonstandard semantics for Prolog, you typically write a metainterpreter. See some examples at https://www.metalevel.at/acomip/ (from the same author as the Lisp interpreter discussed here). It's really easy to implement something like breadth-first search, or depth-first search with iterative deepening, or random search, or some sort of best-first search.