Le pathfining dans advance wars c'est juste du a*, je vois pas ce qu'il y a de lourd 
Les IA d'échecs regardent bien toutes les possibilités sauf pour les openings pendant quelques tour et la difficulté ça revient souvent à régler le nombre de tour à prédire.
Les ordi/smartphone sont très doués pour ce genre de trucs, et pour un jeu au tour par tour pas besoin d'optimisation, tout bruteforcer prendrait sûrement moins d'une seconde 
Après ouais c'est peut être pas le mieux 