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

baylor wrote:

> Eternal Vigilance <[EMAIL PROTECTED]> wrote:
> > A more complicated mechanism might be needed to  figure out what to try next
> > after that first  Stonestorm fails
>
> One thing i find most AI algorithms lacking but which is critical to
> animals is monitoring feedback. Technically, i believe people make a
> prediction, act, match the result to the prediction and only pay
> attention or do anything if the prediction is significantly violated
>
> One issue i'm wrestling with is the examples to use. What if it
> weren't a spell but a sword. If you attempt to stab someone with a
> sword and you miss, you don't assume the sword is a bad option, just
> that you need to swing at him a few more times. i believe (but can't
> prove) you store a numAvgAttemptBeforeSuccess number and try at least
> that many times before considering another option (unless the
> environment changes; i.e., there's a shock to the system). So if you
> normally hit someone within the first 20 sword swings, you'd be
> willing to miss 20 times or so. After that, you might re-evaluate your
> options. Of course, if every time you stab someone they bleed and you
> do hit the monster and he seems unfazed, then you'd say "well, this
> isn't working, time to think of something else"

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...

But besides that a sword swing vs sword stab vs pommel crush etc...
are individual solutions just as casting a spell would be.

If and when I get back to working on my solution solver code (which will
keep statistics similar to your algorythm) I was going to consider the problem of
selecting  second and additional choices (as well as what best-first choice to
pick...)

How quick to move to a second choice after a  sequence of attempts using the
first-choice appears to be performing poorly -- quicker if the second choice's
history
indicates  an effciency fairly close to the first choice and less likely to switch
if the
efficiency isnt close  (ie-  maybe switch to stab after 5 poor swings if
swing_eff = 80%
and  stab_eff = 75%,   but might stick with 10 swings  if  stab_eff = 50%
(significantly lower expected result))

Actually with your proposed system 80% and 75%  the swing/stab would probably
alternate which may give a better quick test of effectiveness -- an exploratory
phase
(as long as the mode switch has little cost).  After analyzing just a few varied
attacks in the
current situation (choices recommended by the history - solution best fit stuff)
the decision
to use a particular attack more could be made.   Short term statistics vs long
term statistics.

Now that I think of it  Sword swing  vs Sword stab might still be an insufficient
example
because its too easy to switch -- maybe  Sword  vs Mace  which has a switching
cost...

This is the reason why game AI is going to take a while to develop -- the
complexity
increases fast (and the CPU requirement geometricly).   The system Im
investigating
takes into account a solutions cost as well as its expected effectiveness (throw
in
uncertainty factors and it get ugly fast).   Cost can include:  time, risk of
damage,
destroyed equiptment/expended equiptment, position (being in a poor position for
subsequent actions), energy   --- effectiveness may be a vector including all
these.




>
>
> Then there's the issue of context. Remember the end of half-life
> (spoiler alert!) when you fought a big stupid head but you couldn't
> hurt it until you blew up some crystals or something like that? So
> you've learned rocket launchers don't hurt this big monster, but the
> actual rule is that you can't hurt it with a rocket launcher IF the
> crystals are intact. Once you blow up the crystals, you can kaboom it
> with a rocket launcher. i haven't quite worked out how to get a
> computer NPC to handle situations like this, although i'm looking at
> it
>

Puzzle solvers - ack! -  analogy matching -  double ack!! --  this is far
out in  AI-Land   (enuf for a language parser to analyze verbal clues and/or
common sense patterns of object properties to guide solving complex
problems).    Expect Blocks World like subsystem to solve jumping puzzles
first (and longer if the components move/swing...).



>
> > Does the system become unworkable if there are too many options to test
> > (not just 3 spells but many more )
> > Hopefully the race of Orcs isnt made extinct  before the learning system can
> > adjust itself.
>
> Do we need way too many tests to determine what to do? In humans, not
> always (not often?). In traditional AI programs? Oh hell yeah. It's
> one of the big complaints about reinforcement learning algorithms,
> which are the only AI adaptation algorithms. It's a problem for
> discovery algorithms too, but i don't think there's really too much
> value of discovery algorithms (neural nets, genetic algorithms, etc.)
> in games

genetic mechanism might be applicable to matching the situation factors
( GA to control the filter system to pick which set of solution_statistics..)



>
>
> Humans use "fast and frugral" algorithms, which means that what we
> call human intelligence is just a bag of quick and dirty tricks. We're
> great at approximations but lousy at getting precise numbers. This is
> because real life rarely needs precision and often needs answers
> quickly. Which goes into how animal decisions are significance-biased
> which means we tolerate false-positives far more than false-negatives
> in many situations but i'm going off on a tangent so i'll slap myself
> and stop

Orcs are closer to animals.... (if you cant replicate a human with IQ 100,
Ill be happy with Orc IQ 40...)

When you think of it humans operate 99%+ of the time with what they already
have learned.   Most soldiers have a few basic attacks (that they are trained
to effectiveness) and will thus try to hack any enemy into tinypieces and if that
fails
run-away.  They are trained til they do it almost by reflex. There still is a
complex
set of motions, but they are pretty much reactions to specific actions by the
opponent.

We dont have vto aim at reproducing Aragorn with his 50 different attacks...
(at least yet)



>
>
> Question: How does a human (orc, elf, etc.) learn a strategy/tactic in
> a small number of trials (i.e., with very incomplete information)?
>
> First, the caveat: some things humans do not learn right away. For
> example, the pincer maneuver is not learned in a single person's
> lifetime unless trained in it. Chess for humans is really hard and you
> don't learn a lot of chess patterns unless you play hundreds or
> thousands of games. We shouldn't expect a decent human-simulation
> (natural computation) algorithm to come up with that sort of thing
>

Which means a good situation filter and only a few options for each
situation, then a quick effectiveness evaluation based on short term statistics
(did I just move the ugliness back to the filter system???)
And most 'training' being from inherited patterns/expectations  (traditions??)



>
> OK, so how do humans handle situations in which hundreds of options
> exist? One word: bias
>
> i've been studying walkthroughs and study guides and have noticed that
> people tend to pick one approach and stick to it. At the begining, you
> have a choice between wizard and cleric and thief and fighter. You
> might toy with each when you start, maybe study the stats, but people
> tend to have a bias towards one class or another and once they start
> using them they stick with them

I played UO as a tank-mage for 5 years (but then I played solo and
needed the versatility).


>
>
> So in my current game of Baldur's Gate 2, i have 15 level 7 spells to
> choose from but i can only memorize 6 spells. i think right now i've
> memorized 2 instances of 3 spells (prismatic spray, summon deva and
> mordraken's sword). Assumedly, all level 7 spells are roughly equal in
> value, and i think i even tried a few of the other ones when i first
> got spells (i think to view the animations :) ), but pretty quickly i
> settled on my favorites and have forgotten the rest
>

Versatility being a significant consideration  -- available attacks effective,
usually not optimal but across a broad spectrum of situations.
(again the cost of switching being significant - inconvienece factor)



>
> To make it a bit trickier, i experimented more with level 1 spells,
> which i started the game with, than level 7 spells, which i didn't get
> until much later. i decided that spells fit into certain categories -
> attack, defend vs. spells, remove magic, summon and beef up party.
> It's a heirarchy of course. Attack spells can be broken into one
> person or area effect and under that (or maybe above it; i'm not sure)
> is damage type - acid, fire, cold, other
>
> Where did the categories come from? Not from the game - BG didn't tell
> me those were my type of spells. Those were categories i as a human
> divided the spells into and therefore we should assume an NPC/AI would
> do the same. The divisions were made by goal/effect and by situation.
> Defend vs. attack vs. remove magic protections from enemies are goal
> driven - make them weaker, make me stronger, hurt them. Clerics can
> also heal. So that's goal-driven
>
> i also have situation-specific spells. For whatever reason, i tend to
> use fire spells. i think it's because most of the attack spells are
> fire-based, but i could be wrong. i also memorize the occassional acid
> and cold spell. Why? Because certain monsters are immune to fire
> damage. For those *and only those* monsters, i use non-fire-based
> attacks
>

Because of uncertainty of possible situations, a  'few solutions fits all
approach'
(swords are versatile instruments, leading to their selection in the darwinian
evolution of weapons...)
Overlapping selection of actions that at least one is effective in the expected
problem set.

>
> i also mix direct effect and area effect spells. Area effect spells
> are weaker and sometimes hurt my team, so i actually prefer to use
> direct target spells and rarely use area effect spells. So why
> memorize them? Because some monsters cannot be hurt by magical attacks
> directed at them (unless you spend a lot of time to lower their magic
> resistance) but are still hurt by area effect spells
>
> So here's how i think i learn how to play this game. i fight a lot of
> monsters, read the notes and build up a mental model of what the
> important factors of the game are (some monsters are resistant to
> certain types of damage, lots of bad guys are magic resistant, if my
> magic user is in melee combat they'll probably get crushed, my magic
> users won't rush into melee if i cast melf's magic meteors which gives
> them 20 fireballs to throw, etc.). i build a mental model (a set of
> rules?) based on my experience. Once that model is semi-gelled, any
> time i find a new magic item or spell, i slot it into some part of my
> model (that is, i group spells like lightning and fireball and death

**design note to self - parallel filters point to grouped solution sets
(beat that pesky XOR situation...)

Yets another object attribute -- training limitation:  (  battleIQ 40(Orc) = 4
sets,
battleIQ 100 = 10 sets,   battleIQ 140(Aragorn) = 50 setsn   )


>
> finger with acid arrow and magic missle). Now all 200 spells and magic
> items are categorized into maybe 5 groups broken out by goal. Within
> those groups i sort spells by magnitude (finger of death does a lot
> more damage than magic missle) and annotate (or maybe make special sub
> groups for) my special spells that i only break out for special
> occassions (e.g., cone of cold for fighting fire elementals). When i
> fight, i match the number of hitpoints in the monster with the number
> of hitpoints of damage caused by a spell (do NOT waste a 9th level
> comet on a 1st level kobold; i hate it when games do that). When i
> recognize special situations (oh look, a magic resistant demi-lich), i
> break out the special spells for that situation
>
> OK, so i run into a dragon of some sort and use my biggest damage
> spell i have. Let's say it's column of flame. i get a status message
> "dragon was immune to your damage". Or maybe i do damage but the
> status message says "you do 2 points damage to dragon" when i know
> that spell normally does 60 points. OK, i've violated expectations and
> that forces me to think - hey, maybe fire spells don't work on this

And can I (likely) die if I dont switch and an attempt fails again.....


>
> doofus. So rather than try another fire spell, and 80% of my attack
> spells are fire spells, i switch to cone of cold or lightning since
> those spells are *qualitatively* different. It's hypothesis testing -
> if column of flame didn't hurt him, make a guess that he's immune to
> fire and test it. If he's hurt by lightning, great, i assume my
> hypothesis was correct and keep shooting that at him. If he was immune
> to that, assume my hypothesis is wrong and form a new one, such as he
> can't be hurt by magic. If so, i have two options, either lower his
> magic resistance of use an area affect spell. i've used both in the
> past and, for whatever reason, have had better luck with effect
> spells. Once area effect spells started to show themselves to be the
> winner, i got biased towards it and spent most of my time with that
> approach. So i try the area effect fireball spell on the dragon. Does
> that work? Great, keep hitting him with area effect spells. If it
> fails, make a new hypothesis and test. When out of hypothesis, run
> away and go talk to a bard or something and ask why i can't kill that
> stupid dragon

And if it works you add another specific situation pattern filter (dragon)
and add  a soluution that was effective,
or if nothing worked -- still add a new filter+solution :
      dragon-->avoid/experiment/research_solution



>
>
> Anyway, that was a really long winded explanation, but the point is
> that i think we structure things in such a way that we only percieve
> ourselves to have 2-3 options at any given time at a given level of
> problem/abstraction. i think we actively force the world into
> collections and heirarchies so that we never have to make a choice
> between 100 choices. And once we find a choice that works for us, we
> tend to be biased to that and keep trying it, within (assumedly) the
> confines of the matching law
>
> Compare to magically entering a room with 100 doors. How do we pick
> the door to use? It's too many choices. Humans, unlike computers,
> don't handle huge sums of unique objects well (working memory can
> supposedly only operates on 5-7 items at a time). So we keep
> rephrasing the problem until it gets down to a level we can manage.
> There is no such limit on computers and so computer AI algorithms tend
> to place very little emphasis on data structure/data conversion and
> tend to be very memory intensive. And it's why it solves certain
> problems (addition, chess, TSPs, etc.) better than we do. It handles
> problems with a huge but finite number of items better than we do. We
> handle problems with a near infinite number of items that have logical
> relations and thus can be compressed/mentally re-ordered/mentally
> re-envisioned much better than computers

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.
(more data pointers than you can shake a stick at)
The CPU+ memory capacities should be enough (or soon will be) but
I think we are back to the problem of getting the right data into the
computer (just the predecided 'traditional' solutions add up to
alot, even in the current game complexity -- think of a solution set for
'Acquire a Knife' .
Once an assortment of solution patterns  are available, preference testing
systems should be able to automate testing 'ordinary' situations (to match world
game mechanics better than the behavior programmers guess)

Exceptional situations (that dragon) will require the puzzle solving
monstrocity...



>
>
> i really hope that helps. Sorry if it didn't :(
>
> -b

--  ----- - - - - - - --- - - - - - - - - - - - -

Acquire a Knife :
   Steal Knife   (negative social impact)
   Make Knife
  Buy Knife   (get someone to produce one, trade)
  Borrow Knife (trade a future obligation for it)
  Find Knife  (if one was previously lost??)
  Already have Knife  (usefull equiptment maintenence task )
  Get Cached Knife  (maintained ahead of potential need...)


*** note each is a task with its own solution set