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

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"

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


> 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

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

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

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

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

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

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

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

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

-b