article1085.asp.htm

电脑游戏中的人工智能制作（含源代码）

<!--<TABLE>
	<TR>
		<TD>
			
		</TD>
		<TD>
			See Also:
		</TD>
	</TR>
	<TR>
		<TD COLSPAN=2>-->

<CENTER><SPAN CLASS="title">Recognizing Strategic Dispositions thread</SPAN>
<BR><SPAN CLASS="author">compiled by <A HREF="mailto:[e-mail]">Steve Woodcock</A></SPAN></CENTER>

<CENTER><TABLE><TR><TD>
<PRE><DIV STYLE="font-family: Courier New">
Hello Everybody:                                            7/15/95

   Here's the second summarization of the excellent "Recognizing
Strategic Dispositions" thread, a followup containing posts made since
my original summarization posted on 6/12/95.  As before, if I missed
any posts I apologize; let me know and I'll fix it in future summarizations
(if there's any demand for such).

   The posts are presented essentially as is, with some *minor* editing
on my part for formatting.  

    Here are the e-mail addresses for those contributors whom I have.
Again, my profound apologies if I missed anybody; PLEASE let me know
and I'll correct this forthwith:

      Uri Bruck             ([e-mail])
      Marc Carrier          ([e-mail])
      Richard Cooley        ([e-mail], [e-mail])
      Owen Coughlan         ([e-mail])
      Dennis W. Disney      ([e-mail])
      Graham Healey         ([e-mail])
      Neil Kirby            ([e-mail])
      Alexander Marc        ([e-mail])
      Andrae Muys           ([e-mail], [e-mail])
      .oO FactorY Oo.       ([e-mail])
      Christopher Spencer   ([e-mail])
      Viktor Szathmary      ([e-mail])       
      Daniele Terdina       ([e-mail])
      Robert A. Uhl         ([e-mail])
      Will Uther            ([e-mail])
      Steven Woodcock       ([e-mail], [e-mail])


    Hopefully this will spark a renewal of the original thread and prove to
be informative to all concerned.  I know that *I* have found this to be
this most illustrative and informative thread I've ever seen on the Net;
this is truly where this medium shines.

    Enjoy!


Steven


      Andrae Muys ([e-mail]) started off this 
thread on May 9, 1995....
==============================================================================
I am currently trying to write a game that will provide a computer 
opponent in a computer wargame.  I intend eventually to incorporate 
relitivly complex game mechanics such as can be found in commercial table 
top rules systems.  However the current project is nowhere near as 
extensive with *extremely* basic rules and mechanics.  However as each 
unit may still move once each turn, and a number of distances the 
branching factor puts the CHESS/GO thread to shame.  In fact a lower 
bound calculated from rules far simpler than I intend to use ended with a 
branching factor of 2.6^8.  A simple PLY search is therefore out of the 
question.  Brainstorming suggested that by abstracting the battlefield 
into three frontal sections and maybe a reserve leaves a basic set of 
rules with a branching factor of approx 16(much more manageable).  
However to implement this the AI needs to be able to recognise what 
constitues a flank/centre/rear/front etc...  From practical wargaming 
experience this is something that is normally arrived at by intuition.  
Surely it is a problem which has been faced before and I was wondering if 
there was any theory/code/code examples which I might use to build 
such an engine.
In the meantime I intend to start on the AI assuming that a way can be 
found to recognise such stratigic dispositions.

Thanks in Advance.

Andrae Muys.

==============================================================================

Andrae Muys ([e-mail]) wrote:
: I am currently trying to write a game that will provide a computer 
: opponent in a computer wargame.  I intend eventually to incorporate 
: relitivly complex game mechanics such as can be found in commercial table 
: top rules systems.  However the current project is nowhere near as 
: extensive with *extremely* basic rules and mechanics.  However as each 
: unit may still move once each turn, and a number of distances the 
: branching factor puts the CHESS/GO thread to shame.  In fact a lower 
: bound calculated from rules far simpler than I intend to use ended with a 
: branching factor of 2.6^8.  A simple PLY search is therefore out of the 
: question.  Brainstorming suggested that by abstracting the battlefield 
: into three frontal sections and maybe a reserve leaves a basic set of 
: rules with a branching factor of approx 16(much more manageable).  
: However to implement this the AI needs to be able to recognise what 
: constitues a flank/centre/rear/front etc...  From practical wargaming 
: experience this is something that is normally arrived at by intuition.  
: Surely it is a problem which has been faced before and I was wondering if 
: there was any theory/code/code examples which I might use to build 
: such an engine.
: In the meantime I intend to start on the AI assuming that a way can be 
: found to recognise such stratigic dispositions.

: Thanks in Advance.
: Andrae Muys.
Andrae:


   Glad to see I'm not the only one wrestling with this problem!  ;)

   Your approach to break things down into 'front', 'flank', and 
'rear' makes sense and seems like a reasonable simplification of the problem.
A first-order definition of each might be:

     front -- Where the mass of the enemy units are known to be.  The
              direction I want to attack.

     flank -- Any area in which there are fewer (1/3 ?) as many enemy
              units as the area designed as 'front'.  (Note this is
              purely arbitrary, based as much on prior experience as
              anything else.)  Perhaps also selected based on natural
              defensive terrain (i.e., oceans or mountains).

     rear  -- Any area in which no (known) enemy units are operating,
              or an area completely surrounded and controlled by me.

     
    These definitions work by identifying the front, then extrapolating
from that.  As enemy units move around, become detected, attack, etc.,
the 'size' of the front will likely grown and shrink, forcing similar changes
to the flanks (especially) and perhaps to the rear areas as well.

    One problem I can think of off the top of my head is how to handle
multiple front situations; there's at least some possibility of overlapping
definitions, meaning that some precedence order must be established.
Special exceptions will also have to be made for overflying enemy aircraft
and incursions by enemy units of various types.  (Example: If the enemy
drops some paratroopers into your 'rear' area, does it automatically become
a 'front'?)

    In extreme situations of mass attack, I could see virtually the entire
play area being designated as a 'front' (imagine the Eastern Front in
WWII), which of course makes your branching problem worse.  On the other
hand, attempts to continually minimize the size of the front will cut down
on the branching options, but might result in poor strategic and tactical
choices (i.e., the entire German army focuses on capturing Malta, rather than
overrunning Malta on its way to North Africa).

    More brainstorming as I come up with ideas..............

Steven

==============================================================================

In article <3onpj8$[e-mail]>,
[e-mail] (Steve Woodcock) wrote:

> Andrae Muys ([e-mail]) wrote:
> : I am currently trying to write a game that will provide a computer 
> : opponent in a computer wargame.  I intend eventually to incorporate 
> : relitivly complex game mechanics such as can be found in commercial table 
> : top rules systems.  However the current project is nowhere near as 
> : extensive with *extremely* basic rules and mechanics.  However as each 
> : unit may still move once each turn, and a number of distances the 
> : branching factor puts the CHESS/GO thread to shame.  In fact a lower 
> : bound calculated from rules far simpler than I intend to use ended with a 
> : branching factor of 2.6^8.  A simple PLY search is therefore out of the 
> : question.  Brainstorming suggested that by abstracting the battlefield 
> : into three frontal sections and maybe a reserve leaves a basic set of 
> : rules with a branching factor of approx 16(much more manageable).  
> : However to implement this the AI needs to be able to recognise what 
> : constitues a flank/centre/rear/front etc...  From practical wargaming 
> : experience this is something that is normally arrived at by intuition.  
> : Surely it is a problem which has been faced before and I was wondering if 
> : there was any theory/code/code examples which I might use to build 
> : such an engine.
> : In the meantime I intend to start on the AI assuming that a way can be 
> : found to recognise such stratigic dispositions.
> 
> : Thanks in Advance.
> : Andrae Muys.
> 
> Andrae:
> 
> 
>    Glad to see I'm not the only one wrestling with this problem!  ;)

Seems like there's a couple of us....

>    Your approach to break things down into 'front', 'flank', and 
> 'rear' makes sense and seems like a reasonable simplification of the problem.
> A first-order definition of each might be:

A friend here ([e-mail]) I was discussing it with actually came
up with a different solution.  (based on two tanks on a board moving
pieces about - the game Bolo
http://www.cs.su.oz.au/~will/bolo/brains.html)

you define your 'center', their 'center' and the board 'center'.  Anything
closer to your center than theirs is yours and can be taken.  If they take
it back then it takes you less time to re-take than it takes them - if
they bother to take it they lose more time than you.

  The idea is to 
     i) move your center towards the center of the board, then
    ii) move your center towards their center, always keeping it between
    their center and the center of the board.  This should push them off the
    board.

  the defintion of 'center' is tricky.  It's more a 'focus' than a
center.  At the moment we have a couple we're looking at:

   - The modal position of all your pieces.  (mean would be horrible if
you get split in two somehow)
   - The average position of your tank

There is also one other interesting piece of info we've come across.  It
involves finding neighbours.

Most people would say that the 'Y' in the following diagram is not between
the 'X's:

X          X


  Y

Whereas, they would say that the Y is between these two X's:

X          X
   Y

The definition we found for 'between' or 'blocking' and hence allows you
get neighbour (nothing is between) is as follows.
  i) draw a circle between the two items such that the items sit on either
end of a diameter of the circle.
  ii) If there is anything inside that circle it is between the two items
otherwise it's not.

We thought of defining front as that section 'between' the two centers. 
This doesn't really handle multiple fronts, but then the game only really
has two moving pieces which makes multiple fronts difficult anyway.

Looking forward to comments,

\x/ill      :-}

     William Uther                   [e-mail]

==============================================================================

Andrae Muys ([e-mail]) wrote:
: I am currently trying to write a game that will provide a computer 
: opponent in a computer wargame.  I intend eventually to incorporate 
: relitivly complex game mechanics such as can be found in commercial table 
: top rules systems.  However the current project is nowhere near as 
: extensive with *extremely* basic rules and mechanics.  
<<<SNIP>>>

I thought it might be appropriate if I quickly outlined the game 
mechanics I intend on using for an *extremely* basic game.
I have decided to create a napolionic era game.  The reason's for this are..
a) Personal knowledge, and posession of a number of rule systems for the