Я как-то писал логику бота в игре, по сложности малоуступающей шахматам, а то и превосходящей...
Смысл
тут. Очень большое поле для подумать.
Но написал на основе перебора вариантов и предположительного предугадывания действий соперников.
В итоге оказалось, что бот очень умный) пришлось умность рандомайзить. Вернее ввести для разных ботов степень "умности".
Т.е. простой пират был "тупой", а вот боссы уже считали вовсю.
вот тупые боты:
http://www.islandsworld.ru/sea_battle.html
PS - для выбора лучшего варианта юзал astar.
Сложность была в составлении графа в основном.