Sounds very familiar. I once made a planning AI for the xlockmore / xscreensaver Pacman. It was never included since it would require too much CPU on low-end machines. Nevertheless, it took me quite some time to debug a strange behavior while writing it. The planning system would plan around 50 steps ahead, minimizing the risk of being eaten by a ghost while maximizing the number of dots eaten. Strangely enough, it would continually decide to go towards the ghosts, instead of evading them. Every time I saw this happening, I decided to stop the game and debug my code. Looking through it for the umphth time, I became weary-eyed and let the simulation run for a bit longer. Awe-struck, I saw what Pacman was planning all along: have the ghosts closely follow behind him. This would minimize the probability of being fenced in by the four ghosts.

And this reminds me, I wrote that code 12 years ago, and I still want to incorporate it (with a switch) into the xscreensaver code, but never came to it...