Re: Bag of Tricks: Choosing actions via the matching law

baylor wrote:

> Maybe i should move this to a new thread as we've kinda left the
> matching stuff behind
>
> On Wed, 26 Nov 2003, Eternal Vigilance <[EMAIL PROTECTED]> wrote:
> > Sword might be a better example because it allows many swings (attempts)
> > during a fight, while spells are usually more singular/massive attacks that
> > dont recharge fast...
>
> i want to do my test and, after a fair amount of thought, i think i'm
> going to take your suggestion and switch to swords. The wands and
> spells thing was introducing too many problems with people bringing in
> outside information
>
> And i didn't think of testing switching costs before, but when you
> mentioned sword vs. mace, that made me think i should test both the
> matching thing with swings/sword stuff and with a switching cost.
> Thanks for the help!

Some situations have a switching cost  ie- mace/sword    and others dont
stab/swing.   A prolog/epilog of an action have cost associated with them
and how fast to do mode switching becomes yet another piece of the puzzle.
Its one more factor for the decision, just as swing might have
more power (many medievel swords were more like crowbars) but stab
might be faster to repeat, and be more accurate, etc..

>
> > This is the reason why game AI is going to take a while to develop -- the
> > complexity increases fast
>
> i *think* most AI stuff (thinking, not perception) is pretty simple
> and the leaf node (the code to decide what to do for a specific
> situation) is probably only a few lines long (and not terribly
> generic/re-usable). The tricky part is that we don't have one big
> magic hammer, we have a bunch of specialized tools for the bunches of
> types of situations we find ourselves in
>
> So the trick, i suppose, is to identify what all those little
> situations are, meaning we track what we do in our lives (or at least
> our gaming lives) and see how we can group those things to find the
> common patterns
>
> Which is something i'm thinking about but don't have a rock solid plan
> for yet.

'Plan'  as in the planning type AI stuff, except a game situation is dynamic
where situations change  and they may be alot of  uncertainty. Where
'best' paths of action leave the object is a position with more options
or future potentials (versatility, opportunism, preparation...)

I agree that the actions themselves (local situation) are not too complicated,
but these game mechanics work through sequences of interrelated actions.
Planning trees with alot of nodes/leaves that are only estimations ...

The system Ive been working on has low level actions, and then task
sequences of those actions.  Some tasks are defined purely with other
more specific tasks (hierarchical tasking, with cost estimations and
evaluated uncertainty factors at each level).
Those evaluation functions are the sticky bit, and trying to work out a
simple metric to compare one solution with another (where cost/uncertainty
is a vector of  more than a few values) hasnt been easy.
There is  problem of how soon you try a different solution (abandoning effort
and resources that have already been spent etc...) and some kind of budget
(expressed in the same cost vector) to track (and save as histrory statistics).
Of course the root problem being solved has a payoff (also a vector) and
probabilities of success times payoff   is evaluated against risk(cost) times
probability of  failure.
A nice system of preferences and tendencies of the object (doing the actions)
adjusts the evaluations.  ie-  cautious = decreasing modifier as risk increases
or greed puts a higher valuation on material goods (lost or gained) in the
overall  linear evaluation metric of  a decision .

example  cost Vector
        ( time, material value, social standing, utility, psychological, self)




> It's pretty easy to write a mod or game that tracks user
> stuff. As small as it was, i was happy that Baldur's Gate tracked the
> % of experience and kills generated by a given character, their
> favorite weapon, favorite spell and strongest enemy defeated. Easy
> stats to track but neat to see. The point is, it's really easy to log
> most user information
>

until you start tracking what specific problem was being solved
(tupples of which spell used on what object or what situation)

Looking at how many factors there are in game situations, the
logging can be done real time, but the building of the  behavior
logic(+statistics) will be done off line (at least until the CPUs run
in the TeraHertz speeds)

>
> Another nifty use of this is William van der Stern's terrain analysis
> stuff. He overlays a grid on a map and tracks statistics about that
> grid - number of people who died there, got hurt there, killed someone
> from there, moved through their, camped there, etc. In the end, you've
> got something pretty good for determining where a map's choke points,
> ambush points, sniper spots, etc. are. For William, his CGF Quake 2
> bots would use the data to determine where to snipe from, where
> enemies were most likely to walk (ie, potential ambush/guard points)
> and spots to avoid when navigating the map

Ive also heard of brute force methods just analysing the map to find
spots with best cover/ shooting opportunity/ powerup accessabiliity,
but that can be flawed if wrong assumptions are made in the evaluation
logic...

Much simpler doing the observation of a players who are assumed
to be inteligent.  But I wonder whether it can be applied to tactics more
dynamic than where to snipe from.  I have a feeling that most of the smarts
comes from the programmer building the observation analysis, with the
tactics hand crafted to match the patterns.   Would ne niftier if such a system
could build terrain-tactic meta patterns and then apply them to a map never
previously played on (and do well).


>
>
> So logging stats is easy and useful. The big problem, obviously, is
> knowing what to log
>
> Although i didn't know it at first, after a couple of experiments it's
> become clear that a lot of the good information is derived.
> Non-derived data is stuff like hit points, current weapon, stuff that
> the network packet or game engine will hand you. Derived data requires
> a formula or two and is stuff like reaction time (time shot - time
> saw; is often negative), % time camping (% seconds velocity=0),
> relative strength (enemy units / friendly units), visibility distance
> (ray to closest opaque object in view range), cover (visibility
> distance by degree), backstabbing (% and likelihood of attacking when
> enemy FOV not include you) and all sorts of stuff like that
>
> It's in my plans to, sometime before i finish my PhD, write a mod (or
> plug-in for games supporting it, like AdminMod for CS) that tracks
> info about human players. It has three purposes. One is to profile
> players so you can tell them about themselves (you're a camper, you're
> aggressive, you're cautious, etc.). Just for fun. The second is to
> profile them so you can use that profile in your bots (if
> enemy=type(X) then do strategy Y). The third is to collect information
> to make decent game AIs
>
> i haven't got a clue how to do this, of course :) Well, maybe a few
> clues. One thing i'll try is a brute force "track everything i can
> think of" and then do the standard data analysis thing to see which
> variables were worth tracking. Also, i've already done some
> experiments and have some clues as to what i think will be useful. the
> ones that i think are useful are FOV (field of vision), variability
> per second of FOV (do they look around or in one direction; determines
> how easy it is to sneak up on someone), variability in velocity (do
> you always run, always camp or mix it up), force ratio (enemies to
> friendlies) and something about maps (mostly bottlenecks, visibility
> distances and number of avenues of approach; not sure how i'm going to
> track this)
>

which way do they run when under attach (forward/back right/left/dodge)
do they stand and fire or  popup/potshot
do they stay near walls/corners/cover (or move to)
preference for longrange/shortrange
run for powerups when damaged   stand near powerups

alot is movement/action  in relation to the opponent

>
> i'm mostly looking at FPSes but frankly i'm not sure if there's that
> much intelligence in FPSes, unless you talk something strategic like
> Tribes. The biggest failing in FPSes is that they're not very team
> oriented, at least not outside clan play. i might switch to RPGes or
> perhaps RTSes. A big issue with the latter is the team stuff - which
> units do i build, how do i group them, how do they move, how do they
> interact, etc. Another good view of this is the cleric in D&D games.
> That's a healer that is mostly there to help the other guys. Ditto
> mages that cast enabler/disabler spells (speed up my team, remove
> magic from the other team, etc.). Understanding how teams work would
> be neat to know

Just improving the logicl/behavior of a lackey/follower NPC  -- a simpler
problem because the initiative is with the player and the follower
will react to the players situation (shallower planning/decision trees).
(Logical that we may have to utilize follower NPCs into these games
to fill out a well balanced party -- hard time getting friends together
at the same time for any length of time to play these games online
and pickup players are too untrustworthy ...)



>
>
> So i hope to collect info, find the meaningful stuff, try to
> generalize from the specific data, create hypotheses, test them in
> special test thingies and then put the good ones to work in an AI.
> And, of course, post anything i learn on this newsgroup :)
>
> > Puzzle solvers - ack! -  analogy matching -  double ack!!
>
> Hey, i like analogy matching!

I do to, but getting a program to do it is the hard part.


>
>
> > Orcs are closer to animals.... (if you cant replicate a human with IQ 100,
> > Ill be happy with Orc IQ 40...)
>
> *sniff* my 6-person party in BG has 4 half-orcs :(
>
> And i named them after my daughters!

Half orcs are supposed to be smarter - arent they (prob lose
constitution/strength..)

>
>
> > Which means a good situation filter and only a few options for each
>
> Yup
>
> > (did I just move the ugliness back to the filter system???)
>
> Yup :)
>
> i think that's probably the way it works, though
>
> i'm still doing a lot of research into this. It's full of terms like
> stimuli-response, belongingness, instictual drift, learning
> preparedness, variable schedules, generalization and habituation. i
> still haven't found a good explanation as to how we describe
> situations, and if we don't know how we describe a situation, it's
> hard to know what attributes can be used in filtering and matching
>

I have this nightmare vision of a 'Situation' being a mesh network
of 100's  interrelated  factors  (my damned vector is bad enough)  and
the evaluation functions  tracing the shapes/links within that 'network'
looking for similarities/ignoring gaps --- classifying, subclassifying the
situation building its own 'significaant' links (mutating the network
substituting simplifications, filling in gaps with best guesses, diguarding
irrelevancies to the current solution test).
Links lead back to past situations (and outcomes) and forward into a
foggier set of future node (that have higher and higher uncertainty
attributes )  ...A rats nest of links to tendencies/preferences/previously
evaluated synthetic factors/generaizations

 Remember I said more links than you can shake a stick at...


>
> > And most 'training' being from inherited patterns/expectations  (traditions??)
>
> i've been reading about something called "evolutionary memory" and the
> similar terms belongingness and preparedness. Apparently, every
> species is hard wired to accept certain relationships (preparedness)
> and refuse a few others (contrapreparedness). Most possible
> relationships, of course, aren't specified
>
> So it is much easier to learn to fear snakes than umbrellas. And it is
> much easier to learn that a given taste causes sickness than a given
> sound
>
> Now here's the question - what on earth are those things? What rules
> are primed inside of us? And aside from several mentions i've seen on
> taste aversion and a fear of snakes, i haven't found anything that
> says. Which means that maybe i actually have to do the
> research/testing for that myself. Which is a bummer because i'm
> really, really lazy

Cultural training -though there may be strong triggers from brain
architecture (lower brain aversion to squirmy-ness/ rippling patterns
picked up by the optic subsystem)


>
>
> The implication for game programmers, of course, is that you have to
> hard code some of the logic. Not all of it, but some of it. And you
> can't just write one little module like a neural net. You can't even
> "evolve" one with a "genetic" algorithm because you have to tell the
> GA what attributes there are that can mutate and hold values. So
> what's probably gonna happen is that we programmers will have to write
> lots and lots of little functions. Did i mention the part where i'm
> really lazy?

Or even if we make the 'primitive' actions easily (maybe alot of endcases
if the game mechanics are complex)   and the task system/planner
/sequencer mechanism with a bit more work, Im still stuck at the evaluation system
that makes the decisions work --  way too much special case patterns
and specific situational preferences...



>
>
> By the way, i did a search for "cognitive modeling", which is where
> you make a computer model of a human mind. A few schools (Carnegie
> Mellon, Georgia Tech, Penn State) offer classes in this, but it turns
> out it's not terribly useful for me. It's either really, really low
> level stuff (ACT-R) or bare-bones low level stuff (Soar). It doesn't
> come with a big built in set of rules or logic, you still gotta
> provide those yourself. None of this is helping my laziness one bit

My crystal ball says they will one day be selling behavior logic like they do
3D human articulated meshes and animations  (but the date is too foggy to
read)



>
>
> > > OK, so how do humans handle situations in which hundreds of options
> > > exist? One word: bias
>
> Yup again
>
> (i'm saying that a lot, aren't i?)
>
> > Since we are simulating that 'human' way of problem solving, the process
> > of pattern matching/filtering in parrallel (which our brains do adaquately)
> > has to be done on these funny silicon things that operate in a narrow serial
> > way.
>
> You know, i've heard a lot of people complain about serial computers
> and the need for things like the old connection machines (with a
> whopping 64,000 CPUs - whee). But frankly i don't think that's a big
> deal. Given how whoppingly much faster computers are to
> brains/neurons, and given that neural nets aren't synchronized (i
> think; frankly i have no idea), i don't see any reason why you
> couldn't produce just as many results per second either serial or
> parralel. As far as software goes, just create 1,000 threads and let
> the scheduler worry about the serial stuff. Of course, the OS might
> whine a little about all those threads :)

You can always emulate parallel with a serial architecture, but if  the
fastest (reasonably priced )cpu is  X,   its still faster doing 64k * X
even though it doesnt scale linearly (lots of communication overhead).
And thats where the brain has its advantage it has a huge amount of internal
bandwidth (besides the fact that its also self programming....)

Mesh network pattern matching may actually be a good fit for a
parrallel solution (easily batched and alot of crunching with little
communuication - lots of memeach  though to hold the interpretation meta
data (which may be really huge)

>
>
> Most modern UNIXes, though, support MxN threads and several support
> processes smaller than threads (the ones i've seen are called
> microthreads and fibers) and Windows supports thread sharing (assuming
> you don't use Thread Local Storage), so maybe it's doable. On a PC.
> Probably not a Game Cube. i've never actually tried running a program
> with 1,000 threads so i'm just guessing here. Given the overhead, i'm
> betting a normal computer could do a decent job of simulating a human
> but would probably bog down in games with 50 NPCs
>

maybe with light weight threads (otherwise too much OS overhead)
but only certain problems break up neatly into parrallel efficiently
and even then most sit idle waiting for partial results from another thread.
(which is ok on a emulation but horrible on true parrallel hardware)
AND of course you almost have to handle tailor the program to the task
as the compilers/Interface do a lousy job of breaking problems down
(still manual operation)


>
> > I think we are back to the problem of getting the right data into the
> > computer
>
> Yup
>
> -baylor

Yup