One thing I know is this doesn’t belong to this thread.
Okay, I found a solution to stop AI from checking exploration possibilities many times with same hero, without loosing funcionality. This limits most extreme turn times, however does nothing to improve average AI speed.
The conditions are listed in r3819:
I optimized most expensive function in r3834. Apparently pathfinder was crippled by recalculating hero bonuses for every tile.
Huh… such cases should be covered bonus system caching. Wasn’t it working at all or was it just too slow?
Well, actually getting catched bonus was the function that caused significant CPU usage. Reading catched string is of course faster than navigating bonus tree, but still can take time if called thousands of times. Streams are slow.
I found another bottleneck specific to water-based maps only. Fixed in r3830.
Is it possible to change the enemy movement speed?
In the in-game settings menu there is an option, to change your own movement speed, but the movement speed for the enemy is disabled.
Additionally in Heroes II is an option the change the whole ai speed.
This option works for AI heroes as well.
Okay, are you happy with AI speed in 0.95b?
Nope. In case AI generates a lot of heroes with 1-4 creatures on a small area, it produces a lot of warnings like: Another allied hero stands in our way
and it becomes extremely slow. Makes me annoyed.
But this is exactly how it worked since 0.95 and no one reported such issue.
The AI is much faster than in previous version and this is definitely noticeable. But there is one thing that really bother me - heroes which belong to different players don’t fight each other.
+1 for Kantor
About AI, it definitely became better, but it becomes very slow in such cases I’ve described.
In scenarios where you play with Gelu everything is ok, in scenarios where you play with Sandro the area is quite limited and it becomes such a pain to wait 5-6 mins for 1 turn.
I also noticed it. Even if my hero is much weaker, AI heroes pay no attention to mine hero and don’t kill him on map. And enemy heroes don’t recapture mines and dwellings taken from AI by me.
@ Warmonger: I’ve got one suggestion about AI turns:
sometimes there is a situation when a hero is blocked on one cell, he can’t move anywhere (for example due to scenario he is blocked and we need to free him), but he still eats some time trying to evaluate what to do - about 15-20 seconds, not that much, but a simple if-else condition for such situations can help to reduce this time, nice profit, little changes in the code 
For example, right now he did 11 evaluations, changed goal and finished his turn without doing anything.
Hmmm, well, in fact i have this problem, too. I’m trying the RoE campaign, first scenario. The first AI turn now runs for about 1 hour, and it is still not ready. That is indeed way too long.
My PC is a laptop, a samsung R70. It is not the strongest, but should be well powerfull enough. As far as i have read in the log from previous tries it is as Warmonger said: 2 heroes meeting causes some endless loop.
I too tried the vcmi test map. AI turn still took quite some time, but it was only minutes, not hours.
Map size cannot be the problem. The first RoE scenario has a quite small map.
Recalculation: I doubt if it is really necessary to recalculate goals on every tile. It should be enough to once per round calculate all goals within sight and then simply move there. This does not change any conditions. Any tile visited should not change any game state until the hero reaches his final point. Map/game conditions may change during the next turn, so it is necessary to reevaluate any goals then, but it should not be necessary to reevaluate them each turn
I’ll give it a try during night. We’ll see if it is an endless loop or if it just takes too long. If it’s still busy tomorrow than it is probably an endless loop.
BTW, is there a “cheat code” to reveal the map? Seeing what the AI does might help finding out what exactly takes that long.