Teach a Computer to Play Heroes, Part 1: Building

The old Heroes games developed by New World Computing. Please specify which game you are referring to in your post.
User avatar
Alamar
Golem
Golem
Posts: 605
Joined: 06 Jan 2006

Unread postby Alamar » 26 Feb 2008, 23:21

Jolly Joker wrote:For several reasons I could list, if someone wishes so I think that letting the AI simply cope human behaviour is impractical.

I think that the way to build the best AI possible would be a way akin to the way a Random Map generator works. Modules or Templates of AI behaviour should be written, that could be combined. For example, there might be different AI modules or "modifier" for different behaviour depending on
a) map size
b) number of human/computer players
c) Objective (kill all, find Asha's Tear/Artifact, TaKe Object and so on)
d) race
e) difficulty level (starting resources)

On top of that there might be something like a personality modifier (variations in acceptable battle odds, for example, making one AI more careful than others).

Furthermore, something like "failsafes" might be interesting. Just for the heck of it I'd like to see a feature telling the human player while he is waiting for the AI to finish its turn:
"Reloading... AI lost main hero in a miscalculated fight..." :)

I tend to agree with JJ that at a certain point [that point is debateable] we should stop using hueristics && AI and fall back onto canned sets of scripts in some manner or another. Then we can allow the AI to slightly modify these scripts as appropriate but the script would act as a decent guideline ....

BTW: The failsafe that you're talking about would be a very nice feature for map makers so they can test their maps and [without doing a map reveal or other cheat] know what's going on.

********************************************************

As far as a good set of AI goals I would shoot for:

1. The AI should give the human its best effort. The AI should try to win in other words.

2. The AI should give, as much as possible, an appearance that it is playing by the same rules that we are.

3. The AI should be as configurable as possible to tailor it's behaviour to what the player wants. I.E. if they want it to cheat like mad to give a more competitive AI then good. If they want a minimum of cheats then that should be allowable also.

*******************************************************

If I was a HoMM playing AI and I had [literally] infinite resources I would:

1. Build tier 1-7 creatures in order as soon as possible.
2. Build structures to increase production [wells/castle/etc.] ASAP.
3. Build spell tower to increase spell casting power
4. Build any special buildings that increase total army power.
5. Build any defensive structures [walls/moats/turrets/etc.] possible
6. Build economic structures.

There can be exceptions to the above but 1-6 is the general order of importance that I would assume that you'd use for most factions. If you want hueristics instead of scripts I would tend to give HIGH weights to buildings that would directly impact my army strength [creature producers, enhancers, spell towers] ... I would give lower weights to economic structures because in this example you don't even need them.

As JJ points out there are lots of factors that would change the above ... map size / personality type imposed by map maker / hints given by map maker / available funds / expected duration of game / etc. These can change the weighting of everything dramatically. If we can come up with a good way to handle turn-by-turn dynamic weighting of building values I think we can end up with a decent general purpose building system.

**************************************************

While I'd love an AI that can hold it's own with a human I'm perfectly happy with "cheats" [bonuses] that don't break the illusion that the AI is playing by the same rules that humans are.

As was pointed out I think that AI should, at least, have perfect map knowlege. By perfect I mean that they know everything POSSIBLE that there is to know about the map [creature counts / join disposition / # of resources in a pile / amount of $ in a chest / terrain that they'd fight on if they attacked neutrals / etc.]. Granted you might choose not to act on all of the information but the information should be available to the AI should it be needed ...

User avatar
Darmani
Blood Fury
Blood Fury
Posts: 479
Joined: 06 Jan 2006
Location: Cambridge, MA

Unread postby Darmani » 27 Feb 2008, 00:00

To those who say an AI cannot play like a human, I hope you're not operating under the assumption that the programmer would have to write the behavior out.

What is the best move is completely dependent upon the game rules. And a computer can use the game rules just as well as a human can.

Many game AIs are implemented using a hand-built finite state machine. Somewhat sits down and manually create rules like "If my opponent has a bunch of aircraft and I don't have anti-air defenses, I should build anti air defenses" or "If my opponent has a bunch of aircraft and I do have anti-air defenses, I should build an attack force that includes anti-air tanks."

In the past, if you were to write a program that could, say, change the raw input "a*(b-500/(c-d*(e+10)))" into a computer-understandable form, you would also hand-build a finite state machine. You would make rules such as "If I just read a digit, and the next character is not a digit, the last several digits were a number" or "If I just read a subexpression, and the next character is a multiplication sign, I will be producing a multiplication expression, and should expect an open parentheses, a digit, or a variable name."

Nowadays, you don't mess around with all those rules. You just express them in a higher-level, more natural form, and let a program (called a parser generator) make them for you. For example, you might have something like (in pseudocode):

Code: Select all

expression = expression PLUS_SIGN expression
OR
expression = expression MINUS_SIGN expression
OR
expression = expression TIMES_SIGN expression
OR
expression = expression DIVISION_SIGN expression
OR
expression = OPEN_PARENTHESES expression CLOSE_PARENTHESES
OR
expression = VARIABLE
OR
expression = NUMBER
If you want to create all the little rules yourself, you'll probably end up with something only slightly better than what we have now. The best approach is to think "What is the general principle behind all of this?" and then solve that problem. That's how we got from writing parsers to writing parser-generators - the parser-generator creators understood how to get from the formal grammar in your head to little rules the computer can follow.

For Heroes, the most general problem is "Given the game mechanics, how do we win?" I can't think off the top of my head how to attack that problem (solving the general case is always harder than solving for specifics) but I do have a good answer for a sub-problem: the battle system. A battle AI isn't too difficult to represent as a finite state machine - if you create a bunch of random ones, have they play each other in simulations, and use an evolutionary algorithm on them, you will eventually end up with a state machine that produces a highly competent AI.

I'm not giving promises on how long such an approach would take, but it's an example of how theoretical computer science can produce superior results without messing around in the details. It's certainly not the only way to do such a thing.

Everyone in this thread might want to take a look at Wikipedia's article on artificial intelligence: http://en.wikipedia.org/wiki/Artificial_intelligence.

User avatar
Alamar
Golem
Golem
Posts: 605
Joined: 06 Jan 2006

Unread postby Alamar » 27 Feb 2008, 00:26

In the end your AI is only going to be as good as your rule base / state machine / whatever is going to be.

I think that we should concentrate on the general rules that would be needed to govern the AI and then we can go back and look at what sorts of ways we would have to implement / execture the rules.

*******************************************************

I won't argue that you CAN do better than some [all?] of the AIs that we've seen with prior HoMM releases. I do think though that there may not be enough development or run-time resources allowed to get a really great AI going. That's why I'm of the position that you should lay a good groundwork and then fall back on "templates" / scripts and possibly "cheating" to get the AI to be competitive while maintaining the illusion that it is playing by the same rules that you are ....

*******************************************************

As far as setting priorities on what to build I prefer coming up with a system that can help us assign a value [dynamically?] to each building. Then based off of the values AND the best estimate of the resources that we will obtain & when then we should be able to hammer out a reasonable way to govern building.

You can generalize this theory a little bit by even using weights or values on map objects to determine if we should visit those. For example an unvistited tomb may have a nice positive weight while a known visited tomb would have such a huge negative weight that it would be impossible for the AI to visit it. Dynamically reassigning weights to such things could be a very important factor in getting a good AI.

User avatar
UndeadHalfOrc
Cyber Zombie
Cyber Zombie
Posts: 1362
Joined: 13 Mar 2007

Unread postby UndeadHalfOrc » 27 Feb 2008, 00:56

Small out-of-the-blue question:
Did the WoG makers ever bother to upgrade H3's AI and make it work with its numerous little add-ons ?

If yes, maybe they could share their knowledge with us.

User avatar
Darmani
Blood Fury
Blood Fury
Posts: 479
Joined: 06 Jan 2006
Location: Cambridge, MA

Unread postby Darmani » 27 Feb 2008, 02:29

Alamar wrote:In the end your AI is only going to be as good as your rule base / state machine / whatever is going to be.
Exactly. That's why, instead of talking about various individual rules, we can just go use an evolutionary algorithm, or look at approaches that does not focus on individual cases.
As far as setting priorities on what to build I prefer coming up with a system that can help us assign a value [dynamically?] to each building. Then based off of the values AND the best estimate of the resources that we will obtain & when then we should be able to hammer out a reasonable way to govern building.
That certainly is an imperfect simplification, but overall I think that's a pretty good approach. Good job, Alamar!

Viewing a building in isolation and assigning a weight to is a heuristic that should rarely completely fail. We could then divide this weight by the cost in all resources to get its value per each resource. Then, we could compare the resource scores between buildings, change the attention given to each resource score depending on how scarce the AI expects resources to be relative to each other (hmmm....that'd be how to get the weight for the Marketplace), and build what gets the most bang for the buck.

User avatar
Jolly Joker
Round Table Hero
Round Table Hero
Posts: 3316
Joined: 06 Jan 2006

Unread postby Jolly Joker » 27 Feb 2008, 06:27

But that is exactly the problem. I doubt that anyone here has a problem with the H5 battle AI. Sure, there still are some blind spots in AI behaviour, but all in all it's acceptable - certainly no spoiler of the fun.
What people complain of is the (cheating) adventure AI.
Letting the AI "play to win" is all nice and well, but as Darmani said, "Given the game mechanics, how do we win?"
To illustrate how difficult this is I'll say the following: winning 1 on 1 means having the best possible hero and the best possible army at a time when the map "is done", i.e. the hero has visitited all buffers, got all experience possible and AT THAT TIME is able to recruit ALL town creatures without having even one goldpiece left. Note, that this is a synchronizing problem - the time is crucial: it makes no sense to put money into upgrades and high creature levels when this will lead to not being able to get all your troops into action when the hero is ready - you don't want to be caught pants down: good hero, fully operating economy, but no money to recruit, having a POTENTIALLY superior army but in reality an inferior one. There is the additional problem of when and how to "waste" money with upgrades, as long as you did not build every tier and have hired every creature.
The same problem arises, when you capture a 2nd town: the income won't allow the full support of BOTH towns (if they are of the same alignment), so will you put the additional money in raising one completely for quality or will you go for greatest mass? Answer: it doesn't matter, as long as you can bring everything to bear when it counts (i.e, battle against abother main hero).
And the logistics of building basic dwellings in the 2nd town only and caravan them to the 1st for upgrade and so on are not even counted in.

But the point I want to make is the following: if you play 1 on 1 this is fairly clear-cut. But now change to a 4-player map with no extra objective, only kill all. How to win now? Who to attack first? When to attack? Depending on what?
I think that this is extremely difficult: you don't want to play a game in which the AIs eliminate each other and you simply move around and pick up the pieces.
ZZZzzzz....

User avatar
Alamar
Golem
Golem
Posts: 605
Joined: 06 Jan 2006

Unread postby Alamar » 27 Feb 2008, 14:58

@JJ: I tend to agree that the battle AI in H5 isn't bad. I do wish a few of the blind spots were fixed but overall it's not too bad.

As for the hero building thing I believe that this problem would be fairly easy to solve so there's no need to worry here.

As for maximizing army strength in a 1-on-1 situation [what to build vs. what creatures that I can recruit && when] I don't think that this is a terribly difficult issue. The key factor he is to get a general idea of on what day does the AI need to be at this peak strength and efficiency and then build towards that. To help better determine this date I would hope that the mapmaker can help the AI out and give some hints when it is supposed to reach this maximum efficiency so it can be ready to go.

Obviously as you increase the number of variables [from 1-1 to 4-4] then the potential difficulty of the job increases exponentially. However I believe some rules of thumb can be devised that should allow us to give a weight to developing each of the castles and we can take it from there.

As far as the AI beating itself up too badly this is something that can be worked on. I would think variables like AI-AI agression vs. AI-Human agression can be tweaked [esp. on higher difficulties] so that a human has to do more than "just sit back" and watch the AI tear itself apart.

User avatar
Jolly Joker
Round Table Hero
Round Table Hero
Posts: 3316
Joined: 06 Jan 2006

Unread postby Jolly Joker » 27 Feb 2008, 15:30

Alamar wrote: As for maximizing army strength in a 1-on-1 situation [what to build vs. what creatures that I can recruit && when] I don't think that this is a terribly difficult issue. The key factor he is to get a general idea of on what day does the AI need to be at this peak strength and efficiency and then build towards that. .
*Faints from shock*
You mean, you think you can paint a roadmap for a complete dummy of how to play the game better than a human without cheating? Didn't you overlook the second important question? In what week to peak is one, but the second is how strong can you be.
I mean you can peak in week 5, having bought all creatures, but it's only level 1-6 with 3 upgraded. And you could peak with levels 1-7 and 5 upgrades, for example, having a couple lower tier units less because you lost them in tough fights. That is exactly what the game is all about, isn't it?
ZZZzzzz....

User avatar
Alamar
Golem
Golem
Posts: 605
Joined: 06 Jan 2006

Unread postby Alamar » 27 Feb 2008, 21:07

Jolly Joker wrote:
Alamar wrote: As for maximizing army strength in a 1-on-1 situation [what to build vs. what creatures that I can recruit && when] I don't think that this is a terribly difficult issue. The key factor he is to get a general idea of on what day does the AI need to be at this peak strength and efficiency and then build towards that. .
*Faints from shock*
You mean, you think you can paint a roadmap for a complete dummy of how to play the game better than a human without cheating? Didn't you overlook the second important question? In what week to peak is one, but the second is how strong can you be.
I mean you can peak in week 5, having bought all creatures, but it's only level 1-6 with 3 upgraded. And you could peak with levels 1-7 and 5 upgrades, for example, having a couple lower tier units less because you lost them in tough fights. That is exactly what the game is all about, isn't it?
I think we both KNOW that I'm not trying to create a non-cheating AI that will outplay a human :) The prospect of doing that with realistic time / $ / development budgets / computing budgest is not reasonable.

What I am trying to do is to create an AI that will do its best with a minimum of cheats [view all is an assumed cheat]. Then we should evaluate performance and then come up with some AI cheats and bonuses that won't offend the sensibilities of most other players. Being able to customize the level / types / amount of cheats is also a good idea so everyone can play how they like.

As to your point of what is better the AI will NEVER choose a perfect option. The best we are likely to do is to assign a weight to what capturing a mine [or whatever] would be at a certain time and measure that against the reduction in total army strength that's expected if we take the mine with losses.

The goal is to get the AI to make reasonable decisions about what to take and when. If a dungeon AI sees that it will only lose a few L1 & L2s to get a sulfer mine in the first week [assuming they need sulfer for builds] then it should always do that and go from there.

Later on we'll have to balance off the value of capturing the mine and how much that will increase our overall strength vs. how the losses in troops will project out over the next X number of days.

******************************************************

For example one of the critical sorts of things that my view depends on is getting help from the map maker. Any hints that they can give as to personality / time for breakout / etc. would be a good idea. This lets the AI know when it needs to be "at peak strength" ...

I do propose cheats that will help the AI manage this:

-- AI with a "view all" of the map .... basically "perfect" map knowledge
-- Allow the AI to know EXACTLY how many losses it would take if it does XYZ before it commits to that action [assuming it's not against a player]

Without the above cheats I wouldn't know how to get an AI to plan even reasonably well.

Of course if the AI doesn't perform well enough I'm all for setting up some cheats / bonuses to allow it to compensate for blind spots in its performance.

User avatar
Alamar
Golem
Golem
Posts: 605
Joined: 06 Jan 2006

Unread postby Alamar » 03 Mar 2008, 17:33

Now that we have "sort of" decided on a possible way to go about doing this does anyone want to volunteer their time and whip up something in C / C++ / pick-your-scripting-language / etc.???

A proof of concept would be a good step forward to seeing if it could effectively be done and what sorts of assumptions need to be made ....

User avatar
Pol
Admin
Admin
Posts: 10056
Joined: 29 Nov 2005
Location: IN SOMNIS VERITAS
Contact:

Unread postby Pol » 03 Mar 2008, 17:43

You mean, you think you can paint a roadmap for a complete dummy of how to play the game better than a human without cheating?
If I would be knowing the art of programming, I would be able to create perfect AIs, just as mirrors of me in different mood and never tired.

That should be enough to strike any player very hardly and provide a challenge.

(But I do not belive that here are tools and language to accomplish this in desirable offset of time .)
"We made it!"
The Archives | Collection of H3&WoG files | Older albeit still useful | CH Downloads
PC Specs: A10-7850K, FM2A88X+K, 16GB-1600, SSD-MLC-G3, 1TB-HDD-G3, MAYA44, SP10 500W Be Quiet

User avatar
Alamar
Golem
Golem
Posts: 605
Joined: 06 Jan 2006

Unread postby Alamar » 03 Mar 2008, 19:03

Pol wrote:
(But I do not belive that here are tools and language to accomplish this in desirable offset of time .)
And there's the rub :)

Given infinite time, resources, and computing power I would assume that we could come up with a pretty decent AI.

However given limited development and end-user computing time we're left with just using some rules of thumbs / settings weights to goals / hopefully doing some decent alpha-beta pruning when necessary / etc.

Basically we'll have an AI that might beat a total newb without cheating but isn't likely to beat an expert player on a balanced map without getting seriously lucky. Therefore this is why I recommend designing in the right sorts of bonuses [cheats] that the AI gets so it is at least more competitive.

User avatar
Darmani
Blood Fury
Blood Fury
Posts: 479
Joined: 06 Jan 2006
Location: Cambridge, MA

Unread postby Darmani » 03 Mar 2008, 23:12

I'm guessing that everyone making mentions of development time isn't a computer scientist.

Darn! I come across articles and anecdotes discussing the lack of a relation between quality of software and development time, but I could only think of two off the top of my head, and could only track down one. Still, it is a rather dramatic example: http://www.metromodemedia.com/blogs/pos ... e2037.aspx

Anyway, I'm just bringing this up to mention that any discussion of resources is moot - the way to solve a problem is to throw cleverness at it, not time and money. It may take more mental exertion to create an AI more abstractly, but a more abstract approach could easily take less time (and certainly less people) and would definitely be more competent.

Talking to non-computer scientists about computer science is like teaching adult hunter-gatherers atomic theory.</grumble>

User avatar
Alamar
Golem
Golem
Posts: 605
Joined: 06 Jan 2006

Unread postby Alamar » 04 Mar 2008, 15:31

Darmani wrote:I'm guessing that everyone making mentions of development time isn't a computer scientist.
Actually I've got a Master's Degree in Computer Science [GA Tech] and worked as a professional programmer for > 10 years.

I would like to claim a lot of knowledge on the specific subject of AIs but honestly I've almost exclusively worked at the OS level and there is a day and night difference between creating a high level AI and writing bare-metal-OSs :)

Either way I know how the seemingly smallest and most innocent sounding task can turn into a manpower black hole so I wouldn't underestimate how long it would take to try to come up with a "true HoMM AI".
Anyway, I'm just bringing this up to mention that any discussion of resources is moot - the way to solve a problem is to throw cleverness at it, not time and money. It may take more mental exertion to create an AI more abstractly, but a more abstract approach could easily take less time (and certainly less people) and would definitely be more competent.
I agree that the proper way to attack an issue is to throw cleverness at instead of bulk manpower and money. But of course you know quite well that really clever people cost about 3x more than J6P and I strongly suspect that is one potential issue.

Because I'm not convinced that the proper resources [super clever AI guys, time, $, etc.] will be thrown at the project we should come up with a solution that would be dooable with the resources we expect to be devoted to the project.

Of course if we did come up with something as a group of people we could always donate the work to UBIVAL ..... [Yes that's a sugggestion if clever people can be found and want to devote their time to it]


Return to “Heroes I-IV”

Who is online

Users browsing this forum: No registered users and 28 guests