First of all, it helps to actually use a proper compiled Prolog implementation like SWI Prolog.

Second you really need to understand and fine tune cuts, and other search optimization primitives.

Finally in what concerns Game AIs, it is a mixture of algorithms and heuristics, a single paradigm language (first order logic) like Prolog, can't be a tool for all nails.