Adventure AI - plans and challenges

International board Development
#1

I wanted to improve AI like forever and finally got down to it.

First of all, VCAI class appears complicated and it’s responsibility got blurred. Also, the code is hard to manage.
Some functions belong to class, some do not, however even helper functions often refer to VCAI class with unrestricted access.

I’d like to decouple four things:

  • AI core interacting with engine (callback functions)
  • AI logic (Goals) - reasoning and choosing best strategy
  • Simple functions that arise from game mechanics or our engine, like checking accessibility, paths or army strength
  • Utility functions and tools, like wrappers, templates etc.

Last two points belong to AIUtility files right now.

Another option is to move all evaluation functions to VCAI itself, but then it must be explicit decision and not just lazy solution.

Second issue is AI reasoning itself. Simple idea was to take main goal, decompose it into elementary goals (often moving hero to certain tile) and executing that elementary goal.
However, there are some issues with it:

  • Decomposition algorithm is greedy, that is it chooses first available sub-goal and tries to execute it, ignoring all the others
  • There is no way to backtrack decomposition chain to make sure what we do still makes sense for primary goal.
  • Game mechanics and AI logic is mixed. This issue was not obvious for me so far, so let me explain it:
    Game mechanics tell us what sub-goals could logically support our primary goal. For example, the goal to “gather army” may involve visiting town, viisting external dwelling or visiting allied hero. However, it tells us nothing about which of these actions is the best. Decision belongs to AI logic, which may want to test availability of creatures, our resources, hero movement points etc. Once multiple possibilities were compared, only THEN AI chooses best one to execute.
    real problem arises as each of sub-goals itself can also be decomposed and one or multiple sub-goals must be evaluated. There needs to be a mechanism which tells clearly when to decompose goals logically and when to evaluate solutions. Also, it should prevent loops or endless recurrency.

I believe some kind of solution would be to remember or primary goal we actually wanted to achieve, then determine if last sub-goal can fullfill it and not only precending goal. If it can’t, further decomposing the goal is pointless and we should evaluate proposals given so far, choosing best one to execute.
Still, it’s blurry vision. - hard to determine relation between multiple goal types and their chain (or tree).

Additional complexity is to make AI remember its goal - at the moment assigning goals to heroes (“reserving” heroes) and freeing them is quite scattered all over the code. Would be better to have one uniform entity that manages all heroes and their tasks. For example, if we have one main hero, one exploring without army and one on the other side of the map, which of them should capture object with weak guards?
There are many scenarios:

  • Main hero attacks the object, though he needs to abandon some more important objective for that reason
  • Scout grabs some army quickly from nearby dwellings and defeats guard, though he would stp his own goal, which is exploartion
  • Distant hero, who has currently no tasks assigned, can capture object but it would take one week to do so, which is waste of time.

Many of such factors need to be taken into consideration, but to choose one, we need to compare them in parallel and not just perform in-depth search for first possible sub-goal.

#2

There was this Quantomas who improved the H5 AI… Maybe try to get a hold of him for a discussion?

forum.eternal-essence.com/index.php

#3

I know what Quantomas did, but at the moment VCMI AI is very, very different and quite unique system on it’s own. As yet we don’t have any kind of factoring or objective evaluation at all.

#4

how well made are the AI at the moment?

#5

I want to take an interest as there is a work in this direction?

(Don’t consider for impudence).

#6

Yeah, but to actually improve AI in the way I planned is a huge task so don’t expect it any soon. So far it’s just cosmetics.

#7

I can’t compile VCAI with latest revision 3618. I use clang 3.3 as a compiler.

This line produces an error:

template <typename T = CGoal> class CGoal : public AbstractGoal

I think you can’t set a default value for template parameter T, as CGoal is not defined. So I removed = CGoal.

Then I get errors for any uses of the function sptr:

return sptr (Goals::GetArtOfType(vc.objectId));

defined as this:

template <typename T> shared_ptr<CGoal<T>> sptr(CGoal<T>& tmp)

The error message is that the parameter can’t be converted to CGoal&. I think you can’t get a non-const reference from a temporary type. If I write const &, it compiles fine. Are these changes OK?

#8

Okay, should be fine. Will tell you more once I set up Visual Studio back, seems it got corrupted.

Actually I spend more time trying to compile it than writting actual code :stuck_out_tongue:

#9

I commited changes to SVN.

… and I learned a few new things about templates. That’s sometimes a disadvantage about C++, it’s better to focus the creativity on solving problems than on formulating the code nicely (which is important too somehow) and playing around with memory management. (don’t want to start a discussion about C++ :slight_smile: )

#10

I’m still having problems with Goal class hierarchy. Function whatToDoToAchieve() is never called for derived classes even though it’s explicitelly stated as “override” for “virtual” base function :confused:

In fact, most of what I did in last weeks was trying to make it work with old algorithms.

#11

Why do you have this:

class VisitHero : public CGoal<VisitHero>

in the same time as this:

completeGoal(Goals::AbstractGoal(Goals::VISIT_HERO).sethero(secondHero));

Shouldn’t the latter create VisitHero instance instead of AbstractGoal?
BTW - you’re missing virtual destructor in AbstractGoal()

Maybe even turn AbstractGoal into actual abstract class without own implementation of whatToDoToAchive()?
My guess is that somewhere you’re creating copies of AbstractGoal instead of passing concrete goals. Turning AbstractGoal into abstract will force compiler to detect all places that have this.

#12

Indeed it looks like shared_ptr was never constructed properly with arguments and types I wish it had. Still, it’s a puzzle.

#13

Okay, it works! What a hell of challenge it was, nonetheless it ok now.

One disadvantage is that serializer can’t handle base abstract class so I needed to disable AI rmemebering it’s goals :confused:

#14

I can’t compile revision 3623 and higher. The error is in Goals.h on line 148.

void accept (VCAI * ai) override
{
	//FIXME access to incomplete type VCAI
	//ai->tryRealize(static_cast<T&>(*this)); //casting enforces template instantiation
}

I comment the ai->tryRealize out. If I include VCAI.h it complains about incomplete type CGoals because VCAI.h includes Goals.h.

#15

Yeah, I got same problems when trying to include Goals.h in Fuzzy.cpp/h, however trunk version still compiles for me.

The trouble comes from usage of typedef in namespace, however I couldn’t find a way to fix it as yet, error messages are ambigious at least.

#16

I committed fix that works for me - moving that method to .cpp seems OK on my side.

#17

Too bad it stopped compiling for me - unresolved external symbol :stuck_out_tongue:

#18

… and now it works for me :slight_smile:

#19

It turns out that MVS does not instantiate some templates for unknown reason. First person who figures out why wins a cookie.
I had to add them manually, hopefully it works for you too?

#20

Almost. To make gcc happy I had to do this:

namespace Goals
{
	//TODO: find out why the following are not generated automatically on MVS?
	template<>
	void CGoal<Win>::accept (VCAI * ai)
	{
		ai->tryRealize(static_cast<Win&>(*this));
	}

	template<>
	void CGoal<Build>::accept (VCAI * ai)
	{
		ai->tryRealize(static_cast<Build&>(*this));
	}
}
  1. Put them into Goals namespace
  2. Add template<>

I hope that MSVC is OK with this :slight_smile: