RE: AI (very long)

["Stanley Sutton" <sutton at earthdecision dot com>]

> -----Original Message-----
> From: xconq7-owner@sources.redhat.com 
> [mailto:xconq7-owner@sources.redhat.com] On Behalf Of Stan Shebs
> Sent: Monday, January 13, 2003 11:50 PM
> To: Lincoln Peters
> Cc: XConq Mailing List
> Subject: Re: AI (very long)
> 
> 
> The hard part about doing Xconq AI is that not only do you 
> have the n basic considerations, you then have n^2 
> interactions between all those, and n^3 effects on the 
> interactions.  Or to put it more concretely, a truly generic 
> AI would have to have to examine nearly every GDL parameter 
> in some way.
> 
This is a general problem with all Ais, the trick is in pruning
At useful levels.

> Pathfinding is a good example.  Sure you can do a 
> maze-solver, but terrain can be slow and/or use up fuel - how 
> do you weigh those consideration against each other when 
> doing A*?  It may be faster to be carried, but then you have 
> to wait for the transport to arrive, so maybe it's not faster 
> after all, or maybe even deadly, if you're on terrain that 
> consumes your fuel even while you're waiting.

Simple A* pathfinders handle parts of this, but they start getting 
Complicated with transports involved, but they are still solvable.  
That's why there is an exact cost as well as an estimated cost at 
each step in the heuristic.  There are ways to speed things up by using
the GDL to better effect.  Most of the games I've looked at group units
and terrain in order to treat them similarly.  So most armor has similar
costs to enter certain groups of terrain.  During intialization, you can
pre-calculate the costs of moving into a cell for a group of units.
That cost would only change for terrain modifications (building a road
into a cell), or an advance that changes costs for moving into a cell (
such as a mobile infarntry advance, which reduces cost of infantry
movement by 25%).  It would take one or more layers of memory
structures, but could reduce compute time considerably.  You can also
keep your trees in a scratch layer for a side, since moving units from
the same general location to the same general destination will probably
share a lot of common data that may not need to be recalculated.

Of course, there are still problems.  Even if you identify possilbe
transports that can make a path possible, or reduce the 'cost' to reach
the destination, the pathfinder still needs to pass a suggestion that
the transport be used to a higher level.  The same transprot could be
tapped for more troop movement than it can handle, or for different
destinations, etc.  All that has to be evaluated at a higher level for
priorities (Is it more important to move a tank to an isolated island,
evacuate your last colonizer from an endangered city, etc.)  Sp the
pathfinder has to be integrated into a lot of other places.
> 
> I think the generic AI is always going to be disappointing; 
> it needs to do rather deep analysis of game designs just to 
> decide how to use different units (should a floating city 
> with weapons go into combat? Maybe so, or maybe not).  Once 
> you've got past that, then you've got to do all the usual 
> strategizing algorithms, but parametrized. So the task is 
> harder than has ever been done for any game system, but 
> there's no team of a dozen hackers working fulltime for a year on it.
> 
> The more promising direction is specialized AIs for 
> particular game designs.  Tactical stuff is mostly factored 
> out into unit plans, so the specialized AI can still use that 
> (and people interested in tactics can make unit planning 
> smarter and improve all AIs), and its primary role can be to 
> decide theaters, build mixes, and so forth.  You can also 
> evaluate your progress by matching the generic AI against the 
> specialized one; the generic AI should always lose against an 
> AI with built-in understanding of how a game design really works.
> 

The current AI has a lot of good points to it, according to a friend of
mine that does AI development for a living.  Making it table driven
helps a lot if you want to incorporate a genetic algorithm system into
the AI.  He suggests that the first step would be to develop a
standalone system for learning by tweaking the game designers initial
estimate of the values of units and plans by playing Ais against each
other.  According to him, most game companies keep their AI team pretty
separate form their game designers.  Game designers are very good at
developing interesting and playable sets of rules for games but tend to
not be very good at figuring out how to make an AI competitive with real
people, and vice versa.  The groups use highly divergent skill sets.

I think doctrines were a good start for developing more intelligent AI,
but what is really needed is taking the current AI apart, refactoring it
into smaller pieces, and building new tables to combine the pieces in
GDL controllable ways that can be used to build game specific Ais from
the pieces currently available.

Some day, I really would like to build a GA system to tweak the table
values to help determine optimum values for the valuations on plans and
actions.  Even more interesting would be to use the Lisp enginge to
actually do a bit of GP for an AI, or provide a mechanism for saving
human/AI games and evalualting them by trying to guess the values the
human player used to reach their solution to the situations encountered.
Then feed that back into the GA systems to evolve better results in the
AI over time.

> Stan
> 
> 
> 
>