• Advertisement
Sign in to follow this  

What does the "Most Constrained" heuristic mean?

This topic is 713 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am currently reading <Artificial Intelligence for Games (Second Edition)> written by Ian Millingto and John Funge. In Chapter 2, I have some difficulty understanding the "Most Constrained" heuristic. The words in the book are as follows:

 

Given the current state of the world, one item in a set needs to be chosen. The item chosen should
be the one that would be an option for the fewest number of states.
For example, a group of characters come across an ambush. One of the ambushers is wearing
phased force-field armor. Only the new, and rare, laser rifle can penetrate it. One character has
this rifle.When they select who to attack, the most constrained heuristic comes into play; it is rare
to be able to attack this enemy, so that is the action that should be taken.

 

 

Well, basically I have two questions: First, what does it mean? Especially, the "states" in Paragraph 1 and the "enemy" in Paragraph 2 confused me. Second, what is the reason for this heuristic? Why does the fewest number of states has the greatest priority?
 
So can somebody help me? ^_^
 

 

Share this post


Link to post
Share on other sites
Advertisement

looks like:

 

states = possible situations in the game.

 

heuristic = rule of thumb or possible AI move

 

most constrained = is applicable to the fewest possible number of situations that can occur in the game.

 

and he seems to be saying that (roughly translating)...

 

" given the current situation you need to pick a move (or weapon? its somewhat unclear). the move (weapon?) should be the one you can use the least often on average given the different situations you run into in the game, and how often you run into them. "

 

so if you finally run into a monster that isn't immune to your "+3 billion sword of one purpose only", it might be a good time to use it.

Share this post


Link to post
Share on other sites

The world is always in a 'state', you perform actions on a 'state' for example opening a door and that changes the world to a new state - the world with an open door. To get from one state to a more different state for example, the state of a world without a cup of tea to the state of the world with a cup of tea requires many transitions - boil kettle, put tea bag in cup etc etc.

 

Imagine there was a finite number of world states, from each state you have a number of actions you can perform. A state where the door is closed you can choose to perform the action of opening a door. Similarly in a state where the door is open you can choose 'close door'. Some actions might be quite common and available in many of the world states - opening/closing a door might be quite common but other actions might be very rare.

 

In the example given, imagine there are 100 possible world states and being able to shoot that force-field armoured enemy with that laser rifle is only possible in 1 out of those 100 states then that is quite rare. Shooting some other enemy might be 20 out of every 100 states.

 

Your world might be in a state and you have the following actions:

Shoot generic enemy (20/100)

Shoot force-field armored enemy with laser rifle (1/100)

 

The suggestion is that you should choose the rarest action, to take advantage of it while it is available. That's what they mean by 'Most contrained' - the action that has the pre conditions/is the rarest. It's certainly not the only choice and I see it is only one of the heuristics they suggest.

 

It might be worth reading a bit more about world states.

Share this post


Link to post
Share on other sites

Basically, the point is you proceed from the most specific usage to the most generic. In the example, the dude with the special gun should be assigned the task of shooting the dude with the special armor, you proceed through your assignments in decreasing specificity until you get to the end with, "and you there... you are boring. Attack whoever is left."

Share this post


Link to post
Share on other sites

It should be noted that it is an heuristic, and a cheap and dangerous one. There is no guarantee it approximates the optimal course of action, because it doesn't account for action utility.

 

In the example, if Mr Armor is a minor threat (e.g. he needs a free hand to fiddle with his phased force-field device and therefore he's armed with a little knife) Mr Rifle should shoot (like everyone else) the most dangerous enemies instead. After successively switching to generic enemies of decreasing priority, Mr Rifle should start shooting Mr Armor when it becomes more useful than contributing to killing another enemy faster. Meanwhile, the rest of the team switches from the last enemy they could attack to protecting and supporting Mr Rifle, since it's the most useful action they can perform.

On the other hand, if Mr Armor has a very high priority (e.g. he throws phased force-field grenades) everyone should target him; of course Mr Rifle figures out he can do it, while the rest of the team, knowing that they cannot attack Mr Armor, can either protect and support Mr Rifle if it's useful enough or attack generic targets; no need for a premature heuristic decision.

Edited by LorenzoGatti

Share this post


Link to post
Share on other sites

I agree that using this heuristic alone will lead to some stupid decisions. Instead, create all combinations of available weapons/attacks and enemies/bodyparts. Score them all, then select among the top 5 or so, to give little randomness.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement