search

ihhub / fheroes2

fheroes2 is a recreation of Heroes of Might and Magic II game engine.
https://ihhub.github.io/fheroes2/
GNU General Public License v2.0
2.71k stars 375 forks source link

AI uses non optimal path to capture several targets. #8164

Open kitovyj opened 10 months ago

kitovyj commented 10 months ago

Preliminary checks

Describe the problem requiring a solution

AI green hero Ruby uses non optimal path to capture several targets. She attacks a hero first, then goes back to a castle, then goes to some other target. The castle and the attacked hero are weak and it makes no sense to attack hero first here knowing that the next target will be the castle. nonoptimalsequence.zip

Describe the possible solution

The sequences of all nearby possible targets of AI should be permuted and the most optimal in terms of the target function should be chosen.

Additional info

No response

oleg-derevenetz commented 10 months ago

The sequences of all nearby possible targets of AI should be permuted and the most optimal in terms of the target function should be chosen.

This is unrealistic. Just 15 nearby objects will give us 1 307 674 368 000 options for their consecutive visits in various combinations. And if the hero has spells like Dimension Door or Town Portal, then the number of reachable objects will be much higher. Going through all the possible sequences of visiting objects is just not an option.

kitovyj commented 10 months ago

The sequences of all nearby possible targets of AI should be permuted and the most optimal in terms of the target function should be chosen.

This is unrealistic. Just 15 nearby objects will give us 1 307 674 368 000 options for their consecutive visits in various combinations. And if the hero has spells like Dimension Door or Town Portal, then the number of reachable objects will be much higher. Going through all the possible sequences of visiting objects is just not an option.

I think we can evaluate the attractiveness of all objects and then take top 3-4 for path permutation. In all cases I saw so far it would solve the issue.

oleg-derevenetz commented 10 months ago

I think we can evaluate the attractiveness of all objects and then take top 3-4 for path permutation. In all cases I saw so far it would solve the issue.

Object attractiveness is not some kind of value that does not depend on anything. It depends (among other things) on the distance that the hero needs to overcome to reach this object. It also may depend on number of movement points left (e.g. Stables) or number of spell points left (e.g. Well), current state of the hero's army (castle or monster dwelling), etc.

kitovyj commented 10 months ago

I think we can evaluate the attractiveness of all objects and then take top 3-4 for path permutation. In all cases I saw so far it would solve the issue.

Object attractiveness is not some kind of value that does not depend on anything. It depends (among other things) on the distance that the hero needs to overcome to reach this object. It also may depend on number of movement points left (e.g. Stables) or number of spell points left (e.g. Well), current state of the hero's army (castle or monster dwelling), etc.

Initially the attractiveness can be estimated as it is using the current location of the hero. After dealing with each object in the sequence the sequence itself and the targets should be reevaluated. I think in most cases it will keep the sequence of the actions sane. Computationally it still looks realistic to me.

The attractiveness function and the target function of course will be something to tweak and in the end they can become really complicated. The actual value of the resource pile can depend on the castle type we posess and so on.

At least we will have something to tune and to work with. One step ahead thinking can't solve the issues of non optimal sequences of action.

oleg-derevenetz commented 10 months ago

Initially the attractiveness can be estimated as it is using the current location of the hero. After dealing with each object in the sequence the sequence itself and the targets should be reevaluated. I think in most cases it will keep the sequence of the actions sane. Computationally it still looks realistic to me.

The attractiveness function and the target function of course will be something to tweak and in the end they can become really complicated. The actual value of the resource pile can depend on the castle type we posess and so on.

At least we will have something to tune and to work with. One step ahead thinking can't solve the issues of non optimal sequences of action.

You are free to propose the proof-of-concept implementation.

kitovyj commented 10 months ago

Initially the attractiveness can be estimated as it is using the current location of the hero. After dealing with each object in the sequence the sequence itself and the targets should be reevaluated. I think in most cases it will keep the sequence of the actions sane. Computationally it still looks realistic to me. The attractiveness function and the target function of course will be something to tweak and in the end they can become really complicated. The actual value of the resource pile can depend on the castle type we posess and so on. At least we will have something to tune and to work with. One step ahead thinking can't solve the issues of non optimal sequences of action.

You are free to propose the proof-of-concept implementation.

Ok)