Ok, I need some help.
For now, I think that there should be two types of heroes in the eyes of the AI: strong and weak.
For each, what should be the secondary skill preferences?
List in order of importance for both types of heroes.
Thanks.
I’m not an expert in analyzing the AI, but here’s my guess of what skills might be the best for the two types of heroes (I’m not sure about the order, I’ll edit my post later on if I’ll think of arguments that should push one skill or the other up/down the list):
Strong AI hero:
[size=75](best equipped to handle battles)[/size]
- Wisdom
- Diplomacy
- Leadership (or Necromancy for Necropolis)
- Logistics
- Earth Magic
- Water Magic
- Air Magic
- Intelligence
- Offence
- Mysticism
- maybe Tactics
- Fire Magic (only useful if you have the right spells)
- only on maps with lots of water & many islands: Navigation
- and lastly Ballistics, of some use for sieges (though incomparably weaker than Expert Earthquake)
Weak AI hero:
[size=75](best equipped to collect resources, transport troops, Witch Hut lab rats and maybe teach spells to the main hero)[/size]
- Logistics
- Pathfinder
- Tactics (to be able to retreat before the enemy inflicts any damage)
- Estates (though unfortunately they’ll hardly become experts at this in order to be worth it)
- Navigation (only on maps with at least 10% water, to be worth going for resources)
- Scholar (again, they’ll need to be experts to bring the higher level spells to the main hero, though they could at least collect the low spells from the shrines in the beginning)
- Wisdom - only in combination with Scholar (so only once they or the main hero gets Scholar, otherwise pretty useless for them)
- Diplomacy (to reduce the costs of surrendering, though usually such heroes are not worth keeping)
- Scouting
- and lastly, Air/Water/Earth Magic, maybe even Fire Magic, may benefit the AI weak hero to defend a town in case of a surprise attack when the main hero cannot make it in time.
[size=84]And I hope I didn’t misunderstand your request: you wanted the best skills that a weak AI hero can benefit from, and not the worst skills that would make an AI hero the weakest, right? 
Suggestion: for a good AI, maybe we can have another thread to discuss which would be the best hero specialties for the strong/weak AI heroes (i.e.: resource specialists for weak heroes), to make the best choice of starting/recruited heroes for the AI. ;)[/size]
Interesting choices.
Yes, that’s pretty much what I wanted, but definitely things are left out, even weak skills should be included in both lists.
Also, a cutoff point where the AI should reject if the skill is offered but not forced might be a good heuristic. For example for strong heroes, maybe intelligence is the cutoff, so if the AI has a chance to get Tactics (in Zamolxis’ list), it chooses a skill upgrade if available instead.
Also, I know this is thinking ahead, but what about for WoG?
Any ideas from others?
average/strong?
attack
defense
logistic
leadership
luck
intelligence
and wog war balistics-tent-smthg set 
rest whatever 
For me my skill choices are influenced by what faction I play. With Dungeon and Tower I typically have a magic hero, and Stronghold and Fortress a might hero for my strong. For a strong might hero with Stronghold and Fortress I keep my eyes out for Ballistics, as neither faction has a powerful level 7 flier that could just fly inside the walls and wreck havoc.
The choice of secondary skills in this sense is to patch up inherent weaknesses of that faction.
Then there’s choice of skills that can realize the potential in things. If I have Bless and Prayer on a hero I wouldn’t pass up on Water Magic. Also with Inferno I might just go with Fire Magic instead of say Earth Magic since their mage guilds are more keen on giving out fire spells.
Finally, there’s those skills that are simply great, like Logistics and Diplomacy.
For a complete list, with all skills ordered for the strong/weak AI heroes, I’ll give it some thought when I have more time (which rarely happens, so prolly it won’t be soon :p).
But until then, I’d like to discuss 3 skills which IMO should not be placed on a general hierarchy among the others, but should actually depend only on terrains & map size: Logistics, Pathfinding & Navigation.
Logistics
This is a skill from which both the strong and the weak AI heroes could benefit. And it should depend on the map size (MS) and the percent of passable terrain tiles (PT). If that is hard to identify, the formula could be adjusted to depend on the percent of land on that map. The formula could be something like this:
Chance to get Logistics = MS x PT%
Where MS would have the following values depending on Map Size:
Small : MS = 0.25
Medium: MS = 1
Large : MS = 2.25
XL : MS = 4
Example: that means that for a Medium map with 70% land (50% passable land + 20% non-passable land + 30% water), the chance of getting the skill would be 1 x 50% = 50%. I know that on Large & XL maps the formula would easily top 100%, but I guess most of you agree this is a great skill, which should be a must for AI heroes on maps with enough land coverage (AI should be given the chance to catch up on us or runaway from us, depending on their army).
Pathfinding
This is again a skill from which both the strong and the weak AI heroes could benefit. However in case of the strong hero it should probably be sacrificed in favor of other skills more useful in combat. Therefore I’m going to propose two separate formulas for the two AI hero categories.
Here the Map Size and the percent of passable terrain play a smaller role. What counts is the terrain type. Depending on the skill level (none/basic/adv/expert), 4 terrains give penalties. The worst is Swamp (175/150/125/100%), followed by Sand & Snow (150/125/100/100%) and finally Rough (125/100/100/100%). As you can see, the Rough penalty is almost ignorable and because as of Basic Pathfinding there’s no added value in advancing in skill for this terrain, I’m not even going to include it in the formula for the strong AI hero:
Chance to get Pathfinding for the Weak AI hero = (MS x PT%) x 0.01 x (2 x Swamp% + Snow% + Sand% + 0.5 x Rough%)
Chance to get Pathfinding for the Strong AI hero = (MS x PT%) x 0.001 x (2 x Swamp% + Snow% + Sand%)
On an XL map with 50% passable terrain, of which the 4 penalty ones represent each 10%, that would mean 90% chance for the weak hero, but only 8% for the strong hero. Or alternatively it can be the same formula as for the weak hero, divided by 10.
You also mentioned some “cutoff points” in your post. I’m not sure if I understand exactly what you’re referring to, but this is how I would see blocking the AI to gain or advance in Pathfinding depending on terrains on the map:
- No penalty terrain on the map (or less than 1%): AI heroes never get Pathfinding
- Worst penalty terrain is Rough (>1%): only Weak AI hero can get Pathfinding, but does not advance above Basic (unless “hypothetically” all other skills are Expert)
- Worst penalty terrain is Sand or Snow (>1%): all AI heroes may get Pathfinding, but they don’t develop above Advanced, unless all other skills are Expert
- Worst penalty terrain is Swamp (>1%): all AI heroes may get Pathfinding, with no penalty in advancing till Expert
[size=75](I’m not at all sure about that 1%, but like all numbers in this post, it’s of course open for debate from your side) [/size]
Navigation
Maybe I haven’t played enough maps with lots of water, but my perception so far of this skill, is that it’s pretty much useless for the main hero, unless we’re talking about an XL map full of quests on 20 different islands. Provided such maps (will) exist, I’m gonna propose a formula for the strong AI hero as well, but in most cases I would say this skill should be a no-go for him. It may be however of use for the weak AI hero, to collect resources/artifacts, or when water is the shortest (or only) way to bring troops/artifacts/spells to the main hero:
Chance to get Navigation for the Weak AI hero = MS x W% (same as Logistics, but depending on how much water covers the map)
Chance to get Navigation for the Strong AI hero = MS x (PT% - 50%) x IC (where IC is Island Count or Islands & Continents)
Basically what I meant by the last formula, was to say that if we don’t have at least 50% water coverage, the strong hero should definitely not get this skill. But once more than half map is water, the number of islands/continents should count. But I’m really not sure about this last formula, so again, feel free to come with other proposals & arguments.
I’m not very sure if it’s a good idea to start thinking about WoG in regards to the above, for at least 3 reasons:
-
First I feel that thinking in parallel about the H3 & WoG skills might get quite confusing. Plus we may need a good starting point, meaning to have the formulas/algorithms for H3 well defined and tested in the standard game. And then, based on the WoG boost of a skill, to decide how the formula needs to be adjusted
-
Then I’d say we better wait and see when will VCMI be ready to support all WoG scripts (or scripts from other mods). That could be in 6 months from now, but it can as well be in 2 years from now. Depending on that but not only it can be that at that time WoG 3.58f will still be the most popular H3 mod out there or not. And depending on that we’ll see then if the WoG 3.58f tweaked skills that we need to take into consideration, or something else.
-
And lastly, let’s suppose it’ll be WoG 3.58f, choosing the best skills for the AI in WoG seems to me like a close to impossible task. Every Single Player uses a different set of WoG Options, with almost each of them having in impact to an ideal hierarchy of Secondary Skills that the AI should have. Because we’re not talking only about the skill boosting tweaks. The simple banning of spells like Fly/DD/TP suddenly make the 3 skills I analyzed above more useful, while using the “heroes have double movement” option makes them less useful than in H3. Or scripts like “all creatures attack twice” or “have a breath weapon” might raise the importance of skills like Offence or tweaked Armorer, hence lower some of the others. And so on…
So basically I feel that without better knowing where we stand with (1) and (2), starting already with (3) - aka complicated formulas depending on each and every script enabled - can only make us lose focus and possibly even waste time (in case in 1 year from now - even if just hypothetically - some revolutionary mod would come, with even better solutions to tweak skills & everything)
[size=59]Wow… that was long… :P[/size]
It’s great to see discussions (and work being done) on the Ai - it’s certainly one of the most challenging parts of VCMI, but also one where VCMI could provide improvements that neither the original game nor WoG or any other mod were able to offer.
Some thoughts about the skills: I think the value of many skills is situational. Navigation is an obvious example (useless if no water on the map), and I agree with Zamolxis’ analysis above that the usefulness of Logistics and especially Pathfinding depend on the map.
Further, especially in the early game, the usefulness of magic schools is highly dependent on which spells one has access to. Earth and Water magic are usually a safe bet since they have so many useful spells that you’re unlikely to miss out on all of them. Air magic can be very useful for Haste and later Dimension Door / Fly, but if you don’t get Haste, it might be useless for a long time. Fire magic can be decisive if you have Blind and Berserk, mildly useful if you only have Curse, and next to useless of you only have direct damage spells. A bit less obvious than that, I think that the amount of cities on the map is also a factor in determining the usefulness of magic schools - on a map with many cities, you can be certain that you will get all (or nearly all) spells in the long run, so it’s not a bad decision to go for a magic school even if you don’t have the spells for it yet (it depends on which other skill is offered).
Leadership can be very useful, but its effect can be gained by artifacts as well, and having the skill in addition to artifacts which already boost morale to +3 doesn’t provide any further bonus. Hence, the availability of such artifacts reduces the importance of having the skill. (The same goes for Luck, but Luck is a pretty weak skill to begin with.)
Intelligence is totally obsolete when the map has many wells, and/or many cities, and/or the player has access to Town Portal. It’s also less useful for Dungeon players since they can get a spell point boost from their special building anyway.
I’d also put Archery and Armorer in the skills useful for the strong hero. Archery is a bit situational as well (its usefulness depends on how important your ranged units are), but since you’ll usually want to have strong ranged units anyway, I’d rate it as useful. Armorer has fallen out of favor mainly due to a bug that doubles siege defense damage to your units, but since VCMI won’t have this bug, a reconsideration of its usefulness might be in order. In any case, Archery and Armorer have the advantage that they will always contribute their bonus, whereas some magic schools are actually wasted skill slots as long as you don’t get the right spells for them.
All these things could be coded, but you’ll probably have to make a cut at some point unless you’re able to put thousands of hours into the project. In any case I’m happy to offer my thoughts on the subject, and certainly won’t be miffed if you think differently or simply have higher priorities.
As far as I know, most of AI implementations base on some combination of IF blocks and decisive tables. But complex game like Heroes requires understanding of purpose for pecific object to create efficient tactic. or, at least, any tactic.
It requires combinationing and choosing priorities based on ‘key’ describing a specific item.
Let’s consider Fire Magic once again:
You are offered Fire Magic and Water Magic on level-up. In such situation choice depends mostly of the spells already avaliable to you in mage guild and nearby shrines.
But situations changes in hero discoves Orb of Tempstuous Fire - in such case learning fire magic becomes a priority. On the other hand, if you already learned water magic, fighthing for orb may not be interesting.
You may also change magic priorities depending on immunities of nearby stacks…
In fact all game items are linked in quite simple way - they match element, they match use, they match tactic, they stack. I would consider providing such simple info about every item and process them in order to get priorities and some kind of tactic. Not to mention such info can be extracted straight from existing data about spells and abilities. This may give diverse, unexpected results - but if done well, they will result in really clever oponent.
That’s just a sketch, let me know if you would like to create such system. Of course I may help, but my knowledge of algorithms is shallow.
Wow. Warmonger stoled my idea
Such system have large possibilities(and can be universal for all heroes) , but pretty much difficult to implement.
Adding to skill priority formulas (Hero army/AI total army) allow to remove “weak and strong” heroes system, adding (hero attack+hero defense /hero spellpower + hero knowledge) leads to might and magic heroes and so on.
Of course, it require a lot of time to balance this system, but nice AI a bit later is better then bad AI but early.
Hmm, when I started this topic, I was thinking that secondary skills were not very dependent on the state of the rest of the game. The way I play, I have skills that I believe are useless, and skills I believe are good, when offered a choice between basic and advanced/expert, I only choose basic if I like the skill. I was going to program that heuristic into the game.
Being that everybody thinks it is not that way, I think I am going to do for secondary skills what I have been doing for all other choices that the AI can make. Teach a neural network to give each choice a value, and pick the best available option.
I am in the process of designing such a system. For each choice, the neural network takes as input a list of specific features of the game state (how many of each resource, what spells are available, the date of the game). For example when deciding how much fire magic is worth, the game might take into account the strength of the hero, and whether blind is available. The output of the neural network is how much the option is worth.
So maybe this topic isn’t necessary any more (although it was informative). Thanks guys!
That’s certainly an interesting approach, but now I’m curious - how are you planning to provide the feedback necessary to train the neural network? During training you’ll need to evaluate each decision that the network takes, so that it can adapt its weights accordingly. Doing these evaluations by hand would amount to a lot of work, while evaluating the general gamestate after each decision (and trying to maximize this value) won’t be able to capture long-term effects of decisions. So how are you planning to do the training?
(Btw, feel free to ignore this question if you don’t think it’s helping much at this stage - I’m really just curious because I always found neural networks very interesting, but never found a viable way to implement them into complex strategy games where the “quality” of the current gamestate is so hard to determine, and decisions responsible for a good or bad current gamestate might have been taken a long time before their effects surface.)
Thanks.
I plan to program the AI to watch the decisions real people make (during some training phase, not during real games). The AI will learn what choices people think are good.
I will definitely need help from expert players.
BTW, the game might still be able to do better than a human (in theory) because some search is employed. In practice, still probably not, but here’s to hoping.
Hopefully this is enough to make for challenging AI, but in the event that it’s not, maybe some sort of evolution algorithm from there.
How can you achieve that? Do you plan to build not only Artificial intelligence, but even Artificial Mind? Wow, it would be breakthrough!
I’m joking, but really, is it possible? It would be really, really great. But I can’t image how it would be prepared (maybe because I have only turbo pascal’s programming experience ). The program could learn – itself, after observations - how to play and remember that? What else? I’m really scared! And excited
it’s nothing special. It only works in the very constrained world of heroes 3. A world in which there are only a handful (maybe 50) of reasonable choices to make at any given time, and there are only a finite number of reasonable choices that can be made per round.
Just think of it like this, for each of the 50 choices there is a small (read like >20 nodes) neural network that is simply an approximation to a function that is how good each option would be given a few features describing the state of the world right now (I.E. how good would it be to visit town right now, given that the hero would learn blind, and be able to take 50 Archers). It can learn how good an option is by watching people play if people often go to their towns in certain situations, the computer will learn that visiting town in those situations has high value.
Well, that’s an interesting aproach, but I was thinking about something little different. Actually the network would be build during game time, and its nodes are game items avaliable to AI. Algorithm looks for the best (or just good) way of combining the nodes to create path - prior strategy.
If I understand what you are referring to, you want the AI to run a search algorithm to find the sequence of actions that leads to the most desirable state.
To me, these issues are orthogonal. On the one hand, we have the problem of how to recognize a good state. On the other, we have the problem of how to reach the best state given the ability to recognize how good a state is.
The ladder is search, and it relies on the former. You must know what game elements are good to before you can find a state with good game elements.
Ideally, the AI would search, and I have programmed the AI with searching in mind, but it is unclear how long it will take for the AI to search deeper in the decision tree than the immediate options. Because of the nature of the decision tree (~50 options for every choice) it might just be too slow.