Shortest path and skill levels.

Shortest path and skill levels.

Post by Alex » Tue, 02 Sep 1997 04:00:00



Hello once again. I've implementated a 'skill' level to my A* code which
determines if each path node was worked out using the A* method or simple
abs values. Ranges of 70%-99% success work quite well, but I was wondering
if there is a better method (maybe by varying the heuristic)?

Also I've been working on an 'explorer' class for fog of war settings which
tries to find the furtherest it can go in the least possible moves, unless
if spots something interesting away from base. Has anyone any advice on
this?

(Sorry to go on about this stuff, but I'm really enjoying coding these
things)

Cheers
        Sasha

PS Thanks Gareth Davies for answering my queries about influence mapping!
I've played around and your spot on, in the end I disregarded nodes that
enemies could visit in my safest path method.

--
+------------------------------------------------+

 The Biltons at home - www.myraid.demon.co.uk
 The way to mans heart,
 Is through his chest. - Iain M. Banks
+--------------------Death-to-all-fanatics-------+

 
 
 

Shortest path and skill levels.

Post by Bjorn Ree » Wed, 03 Sep 1997 04:00:00



Quote:> Sorry let me re-explain, If I have an AI general at x1 who wishes to goto a
> location x2 then he has a skill level in finding the shortest path. This is
> a percentage chance of each node (on a grid) on the path being calculated
> by the A* algorithm or another, less accurate, algorithm such as
> abs(x2-x1). However do I need two algorithms or can A* be made to be less
> accurate? (maybe by a more pesimistic heuristic?)

Ok, you are very much on the right track.

The important thing to remember about A* is that the (estimated) cost
anywhere along the path consists of two parts -- how much we have paid
to get to the current node, and how much we estimate the rest of the
journey will cost. The latter is done by heuristics (typically the
euclidean distance, ie. d = sqrt(dx^2 + dy^2) for the 2 dimensional
case.)

What you're trying to do, is to degrade optimal performance, and I
somewhat doubt that anybody has been doing such a thing to A* before.
The usual way to deal with it is to add noise, ie. choose the optimal
path with a certain probability. This is exactly what you're doing
(provided I didn't misinterpret it.)

Another (related) method is to adjust the value returned by the
heuristic function (which is more or less what you suggest with a
pessimistic heuristic.) Adding a random (positive) value to the heuritic
value results in a more pessimistic estimate, and subtracting a value
results in an over-optimistic estimate.

The tricky part is to select the random value. It must not be totally
random. Otherwise the movement with be totally random too. If it is
zero you have a normal A*. What we want is a random value which is
mostly close to zero, and the more 'skilled' an entity is the closer
to zero we want it to be.

The solution to this is to use non-uniform random distribution
functions. Several distributions are possible, but my guess is that the
normal (gaussian) distribution will be well suited.

There are several standard (freely available) libraries that has
such functions. CNCL springs to mind. See

  http://www.desy.de/ftp/pub/userwww/projects/C++/Projects.html
  http://www.comnets.rwth-aachen.de/doc/cncl.html

If you want a description of how it works, the best reference I know of
is "Numerical Recipes in C" by Press et. all (Cambridge Press, ISBN
0-521-43108-5)

 
 
 

Shortest path and skill levels.

Post by Bjorn Ree » Wed, 03 Sep 1997 04:00:00



Quote:> Hello once again. I've implementated a 'skill' level to my A* code which
> determines if each path node was worked out using the A* method or simple
> abs values. Ranges of 70%-99% success work quite well, but I was wondering
> if there is a better method (maybe by varying the heuristic)?

I didn't understand what the 'skill' level is from this description.
Would you care to elaborate? (you can safely assume that I have
knowledge about A*)

Quote:> Also I've been working on an 'explorer' class for fog of war settings which
> tries to find the furtherest it can go in the least possible moves, unless
> if spots something interesting away from base. Has anyone any advice on
> this?

Anthony Stentz, CMU, has generalized A* to find a path in an unknown
and changing environment. His algorithm is called D* and can be found at

  http://www.frc.ri.cmu.edu/~axs/doc/icra94.ps
  http://www.frc.ri.cmu.edu/~axs/doc/ijcai95.ps

D* requires (as A*) that the location of the destination is known,
but you could select random destinations for the sake for exploration.

 
 
 

Shortest path and skill levels.

Post by Alex » Wed, 03 Sep 1997 04:00:00





> > Hello once again. I've implementated a 'skill' level to my A* code
which
> > determines if each path node was worked out using the A* method or
simple
> > abs values. Ranges of 70%-99% success work quite well, but I was
wondering
> > if there is a better method (maybe by varying the heuristic)?

> I didn't understand what the 'skill' level is from this description.
> Would you care to elaborate? (you can safely assume that I have
> knowledge about A*)

Sorry let me re-explain, If I have an AI general at x1 who wishes to goto a
location x2 then he has a skill level in finding the shortest path. This is
a percentage chance of each node (on a grid) on the path being calculated
by the A* algorithm or another, less accurate, algorithm such as
abs(x2-x1). However do I need two algorithms or can A* be made to be less
accurate? (maybe by a more pesimistic heuristic?)

Quote:> > Also I've been working on an 'explorer' class for fog of war settings
which
> > tries to find the furtherest it can go in the least possible moves,
unless
> > if spots something interesting away from base. Has anyone any advice on
> > this?

> Anthony Stentz, CMU, has generalized A* to find a path in an unknown
> and changing environment. His algorithm is called D* and can be found at

>   http://www.frc.ri.cmu.edu/~axs/doc/icra94.ps
>   http://www.frc.ri.cmu.edu/~axs/doc/ijcai95.ps

> D* requires (as A*) that the location of the destination is known,
> but you could select random destinations for the sake for exploration.

Thanks, I'll look into D*, and thanks for replying.

Sasha

 
 
 

Shortest path and skill levels.

Post by Amit Pate » Tue, 23 Sep 1997 04:00:00



Quote:

> Sorry let me re-explain, If I have an AI general at x1 who wishes to goto a
> location x2 then he has a skill level in finding the shortest path. This is
> a percentage chance of each node (on a grid) on the path being calculated
> by the A* algorithm or another, less accurate, algorithm such as
> abs(x2-x1). However do I need two algorithms or can A* be made to be less
> accurate? (maybe by a more pesimistic heuristic?)

I've done a little experimentation with this.  If you use very simple
cost and heuristic functions with A*, it will just find a straight
line.  For example, try giving it a cost function that tells it that
ANY step is cost 1.  Also give it a heuristic using distance.
(Alternatively, leave the heuristic alone, but make sure it's scaled
so that each step costs 1.)

Now A* will have no reason to find a longer path, because it never
finds expensive steps.  The most straightforward path will be the
shortest.

You can also produce things in-between by interpolating between the
simple constant-1 function and the actual cost function.  The skill
level could be used to determine how to interpolate.

        - Amit

--
Amit J Patel, Computer Science Department, Stanford University
       ``A language based on point and click is like a
         human language based on point and grunt.'' -- me

 
 
 

1. Combining shortest path with alpha beta. How?

Hi,

I've written a chinese checkers game.  It uses alpha-beta and quite
successfully.  It has as its goal to reach a better position on the
board which is considered to have its pieces advance to the
appropriate depth.

Now it searches 4-ply deep.  And say the highest Position value that
it can obtain is 7643 (for example).  If this same value can be
obtained at multiple nodes, one at depth 3, and another at depth 4,
how can I cause alpha-beta to choose the path that travels to this
node at depth 3 if it is not the last node of this value searched.

In other words how do I incorportate shortest path algorithm into
alpha beta.

Cheers.
Glenn.
--------------------------------------------------------------

Home Page:  http://home.clear.net.nz/pages/g.reed/index.htm
            Home Page of the freeware Chinese Checkers Game.
Postal:  109 Burns St,
         Cambridge
         New Zealand.
--------------------------------------------------------------

2. An Amigan does it *again*

3. OO and shortest path...

4. MUD client for OS/2?

5. Shortest Path Ideas

6. ALife V : Longest Conference Advertisement

7. Point to point shortest path

8. Microsoft Update

9. Shortest Path Algorithm

10. Augmenting Dijkstra all-shortest-paths

11. Shortest Paths, Dijkstra Variation

12. Shortest Path :)

13. kth shortest path