reactive vs. predictive AI

[intently]

I just picked up AI War during the 50% off sale over the weekend, and I'm enjoying it quite a bit.  I just read this thread (http://arcengames.com/forums/index.php/topic,3036.0.html) about making the AI more predictive, and I have to say that I agree completely with x4000 when he writes:

Trust me -- my way is better.  There's a reason why the AI in AI War is generally better than most any other RTS.  If you leave it open and evolutionary, it will generally provide a more interesting, varied game.  If you try to constrain it too closely, it starts getting predictable and trickable.  I know that's hard to believe, but there are nth order effects to any rule that have to be weighed fairly carefully.  The AI in AI War doesn't use historical data or scout data in any way -- it's like a grandmaster looking at a chess board with a fresh pair of eyes each time.  The fact that more RTS AI programmers think they should make fixes like this is why you end up with variants on the "gap in the wall" problem that I've written extensively about (see the articles section).  My approach is radically different, and occasionally you do end up with an issue like the one described here, but in general it does a much better job.  In a situation like that, who's so say that the 6th time wouldn't be massively successful?  Past failure is not predictive of future failure because the board state is constantly changing.  That's another reason why most RTS AI is so ridiculously sluggish to react, whereas the AI War AI -- the tactical AI, I mean -- reacts instantly.

See also "Rodney Brooks" and the ideas behind his Subsumption Architecture (http://en.wikipedia.org/wiki/Subsumption_architecture).

I have a PhD in artificial intelligence and I build AI systems for a living, and I have consistent success developing reactive systems that do very little prediction.  There are all sorts of reasons for this, but the primary one is this:  it's very hard to predict the future, and most of the effort you invest trying to do so will end up wasted.  The more dynamic, complex, and adaptive an environment is, the less valuable prediction becomes.

[RCIX]

Glad to hear you like the game, welcome to the forums

Quite interesting to have an AI war player that has a PhD in AI, it would be really nice if you stuck around some to help with some suggestions!

[intently]

Glad to hear you like the game, welcome to the forums

Quite interesting to have an AI war player that has a PhD in AI, it would be really nice if you stuck around some to help with some suggestions!

I wouldn't presume to offer suggestions until I'm far more experienced with the game   I'm sure the developers have a vision and don't need my $0.02.

Side note: the last game I enjoyed so much for the AI was Dwarf Fortress (http://www.bay12games.com/dwarves/dev_now.html).

[Black]

Ooh, can we see some of your papers?

[RCIX]

Glad to hear you like the game, welcome to the forums

Quite interesting to have an AI war player that has a PhD in AI, it would be really nice if you stuck around some to help with some suggestions!

I wouldn't presume to offer suggestions until I'm far more experienced with the game   I'm sure the developers have a vision and don't need my $0.02.

Side note: the last game I enjoyed so much for the AI was Dwarf Fortress (http://www.bay12games.com/dwarves/dev_now.html).

Don't worry all suggestions are thoroughly talked over, another voice is always welcome!

Ooh, can we see some of your papers?

I agree!

[intently]

Ooh, can we see some of your papers?

Sure, if you can figure out who I am

Edit: This is not some sort of challenge.  I am not anyone important, and you will not be impressed if you discover my identity.

[RCIX]

Ooh, can we see some of your papers?

Sure, if you can figure out who I am

We'll need more then your time zone to do that!

[carlosjuero]

Ooh, can we see some of your papers?

By the law of internet averages and coinkidinks I dub thee Bob. Bob is the universal name for all things that are not named Blue.

Sure, if you can figure out who I am

[intently]

Ooh, can we see some of your papers?

Sure, if you can figure out who I am

We'll need more then your time zone to do that!

I'm not really anyone important, so I hardly think it's worth your time.  I'm not an academic anyway, so most of my work is proprietary.  This wasn't intended as some sort of challenge.

[raptor331]

Ooh, can we see some of your papers?

Sure, if you can figure out who I am

Edit: This is not some sort of challenge.  I am not anyone important, and you will not be impressed if you discover my identity.

Rumplestiltskin!!!!!!

[x4000]

Thanks for your support, intently, and for stopping by.  It's always nice to run into other programmers, and other AI developers in general, also.  I keep in general touch with a few other AI programmers, and a few months ago I did a two-hour interview over at AIGameDev.net, if you are a member there.  If you check out the articles section of the forum, I get into some of the more nuts-and-bolts of the design of this particular AI, too, which you may well have already found.  I don't really consider myself a true AI programmer as I pretty much just did a bit of research and then went my own way to create AI War after not liking the industry standards methods, but I think my results are pretty interesting.  New to the RTS genre of the games industry, at least, whether or not they are new to academia/non-game-related-AI.

Anyway, thanks again for your support, and I'm glad you're enjoying the game!

[intently]

I'm interested in the distance approximation heuristic you mention in your optimization article.

[x4000]

I'm interested in the distance approximation heuristic you mention in your optimization article.

It's very simple.  Here are the two that I use:

Code: [Select]

        public static int ApproxDistanceBetweenPoints( Point P1, Point P2 )
        {
            int dx = P1.X - P2.X;
            int dy = P1.Y - P2.Y;

            int min, max, approx;

            if ( dx < 0 ) dx = -dx;
            if ( dy < 0 ) dy = -dy;

            if ( dx < dy )
            {
                min = dx;
                max = dy;
            }
            else
            {
                min = dy;
                max = dx;
            }

            approx = ( max * 1007 ) + ( min * 441 );
            if ( max < ( min << 4 ) )
                approx -= ( max * 40 );

            // add 512 for proper rounding
            int val = ( ( approx + 512 ) >> 10 );
            if ( val < 0 )
                return -val;
            return val;
        }

The above one is for doing true approximation.  It basically gives wrong results in a few cases, but is not off by a terribly amount and is vastly more efficient than the regular method involving Sqrt.

Code: [Select]

        public static long RelativeDistanceBetweenPoints( Point P1, Point P2 )
        {
            long dx = P1.X - P2.X;
            long dy = P1.Y - P2.Y;

            return ( dx * dx ) + ( dy * dy );
        }

The above one is for doing relative distance checks with a perfect degree of accuracy.  In other words, this won't help you tell how far apart two things are, but it WILL tell you which of two things are further apart if you compare the results of two calls to this function.  In AI War, usually I just need to choose the closest target or similar, and so this method lets me identify what is closest in a simple way.  Whichever target has the lowest result from this function, basically.  Of course, if you need to tell how much closer the targets are, this method is useless, but for my purposes it works quite well.

Incidentally, while we're on the subject, sometimes I use the following for quick exclusions:

Code: [Select]

        public static bool BasicRangeCheck( Point P1, Point P2, int Range )
        {
            if ( P1.X > P2.X )
            {
                if ( P1.X - P2.X > Range )
                    return false;
            }
            else
            {
                if ( P2.X - P1.X > Range )
                    return false;
            }

            if ( P1.Y > P2.Y )
            {
                if ( P1.Y - P2.Y > Range )
                    return false;
            }
            else
            {
                if ( P2.Y - P1.Y > Range )
                    return false;
            }
            return true;
        }

Very simple and crude, but can work to toss out results that are definitely too far away.  I use all three of the above methods, plus some other caching and just general trickiness in order to maximize performance (basically, doing things like calculating distances to guard posts, and then using that as an approximation of the distance to all the guards of that post, things of that nature).  Hope that helps!

[intently]

Thanks.  The first was what I was most interested in, I'll have to try it out.

[NickAragua]

Out of (more academic than anything else) curiosity, how did you arrive at the 1007 and 441 numbers? It looks like they're just there to help deal with inexactness in the low end of dX/dY (since they become insignificant when dX/dY grows large enough).

Heh, one thing I miss about academia is the fact that I got to work on actually challenging problems.