HELP: Recognising stratigic dispositions.
Andrae Muys
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.
--
=====================================================================
a.m...@mailbox.uq.oz.au | <Insert favourate dislclaimer here>
Andrae Muys |
Prentice Centre | If you are reading this you can feel
University of Queensland. | safe in the knowledge you are
Australia | literate.<Lecture Theatre Graffiti>
Steve Woodcock
: I am currently trying to write a game that will provide a computer
: 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
==============================================================================
Steven Woodcock _
Senior Software Engineer, Gameware _____C .._.
Lockheed Martin Information Systems Group ____/ \___/
Phone: 407-826-6986 <____/\_---\_\ "Ferretman"
E-mail: wood...@gate.net (Home)
swoo...@oldcolo.com (Alternate Home)
wood...@escmail.orl.mmc.com (Work)
Disclaimer: My opinions in NO way reflect the opinions of the
Lockheed Martin Information Systems Group, although
(like Rush Limbaugh) they should. ;)
Motto:
"...Men will awake presently and be Men again, and colour and laughter and
splendid living will return to a grey civilization. But that will only come
true because a few Men will believe in it, and fight for it, and fight in its
name against everything that sneers and snarls at that ideal..."
-- Leslie Charteris
THE LAST HERO
Will Uther
wood...@escmail.orl.mmc.com (Steve Woodcock) wrote:
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 (ric...@cs.su.oz.au) 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 the 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 wi...@cs.su.oz.au
"Nothing is so smiple it Basser Dept. of Computer Science
can't be stuffed up" University of Sydney, Australia
Andrae Muys
: 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.
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
era which may be adapted for computer play.
b) The rigid formations and formal tactics of the era should make the
pattern recognsion easier.
c) The principles of combined arms are easy to grasp and formalise
heruisticly in this era.
d) Only a small number of troop types have to be provided to provide a
reasonable game.
The rules which I intend on implementing to date consist of three troop
INF: slow, strong, short range;
CAV: fast, strong, zero range;
ART: slow, weak, long range;
and three extra terrain types(other than clear)
WOODS: defence from melee and ranged attacks, slows movement;
ROUGH(HILLS): defence from melee, slows movement, aids attack;
ROAD: no defence, faster movement;
Of course the principles of pattern recognition and stratigic disposions
apply to any game in any era, and also to more abstract forms of the
wargame such as CHESS, GO, and CHECKERS. I am using these rules because
I beleive they provide the basic elements of wargames, and are necessary
and sufficient for the application of traditional military stratagy and
tactics. Therefore if I can produce a computer player which successfully
plays a sound stratigic game and which has a 'grasp' of tactics, it
should be able to be applied to any napolionic rule system with little
modification, and to other eras without too much difficulty.
Andrae.
Andrae Muys
: Andrae Muys (cca...@dingo.cc.uq.oz.au) wrote:
: : I am currently trying to write a game that will provide a computer
: : opponent in a computer wargame.
: 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.
Identifing the front first and then defining the rest w.r.t it would seem
to simplify the problem further. I hadn't thought of that, it looks like
a good idea. However one question to contimplate. Where are the fronts
in the following position. {X - YOURS, Y - THEIRS}
YY Now by any standards X is in a bad way. It has been
Y completely outflanked and his left flank is already
XXX YY overrun. Intuitivly his front is now perpendicular
XX XXX XX XY Y to Y's. I think we may need a concept such as
X X Y contact point, which in this case is Y's centre, and
Y X's left flank. Naturally in most battles there would
YYY be multiple contact points. Personally I would draw the
Y fronts as follows.
|
| What do you think?
--------C|
|
|
: 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'?)
This is why I am using a very basic set of game mechanics, and using a
different era(see other post). This way the only way troops can reach
your rear is to march there. Also there are very few battles in this era
with multiple fronts. Although allowance must be made for bent and
twisted fronts. The hinge being a very critical point in an extended line.
: 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).
In the rules I have in mind, most cases you will only have mass attacks
or at least dense fronts. One problem you do have if you try to model a
high echelon game such as the eastern front(WWII) what happened next.
The russian front fragmented and from one dense front you ended up with
hundreds of small localised fronts, the resulting loss of cohesion being
one of the greatest advantages of blitzcrieg. Because cohesion is so
much more important at a grand stratigic level(not that it isn't in
stratagies at a operational/tactical level) I feel that a search for a
front maybe counter productive. My gut feeling is that it would be
better to consider area controled by your forces, controlled by their
forces, and contested. With an emphisis on your forces maintaining
unbroken contact between spheres of influence. So the insertion of
forces 'behind the lines' would only alter the balance of control in the
local area. A domino effect would be possible where forces stratigicly
inserted would weaken a units control of an area weakening a unit relying
on it for its 'cohesive link' weaking its control of another area and so
on. However this is what happens in real life so if any thing it
suggests that it may be a good approach.
: More brainstorming as I come up with ideas..............
ditto.
: Steven
Andrae
Andrae Muys
: In article <3onpj8$l...@theopolis.orl.mmc.com>,
: wood...@escmail.orl.mmc.com (Steve Woodcock) wrote:
: > Andrae Muys (cca...@dingo.cc.uq.oz.au) wrote:
: > : I am currently trying to write a game that will provide a computer
: > : opponent in a computer wargame. I intend eventually to incorporate
<<<SNIP>>>
: > Glad to see I'm not the only one wrestling with this problem! ;)
: Seems like there's a couple of us....
<<<SNIP>>>
: 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
However Y is definately infulencing the connection between the X's. The
right X should be able to support the left, however it is possible that
the reverse is impossible. Of course terrain could modify this.
: Whereas, they would say the the Y is between these two X's:
: X X
: Y
Here I would consider Y to have interdicted the link, or the X's are
still neighbours but they have outflanked/maybe even overrun, 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.
An alternitive(I havn't played bolo so I don't know if it's appropriate)
would be to draw a circle radius Y's maximum EFFECTIVE range (you decide
what that is) and if it cuts a line drawn between the two X's the link is
cut.
: 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.
Andrae.
Steve Woodcock
: A friend here (ric...@cs.su.oz.au) 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 the 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 :-}
Hmmm...this does have some merit to it. I like the idea of the 'center'
being arrived at via this circle-method; it has an elegance to it that also
is somewhat intuitive.
The only potential problem I can see with this approach is that it will
tend towards great massive brute force engagements by migrating the bulk
of both forces towards a common 'center'. This is fine in the case of
two combatants (i.e., two Bolo tanks) but not so good for two armies.
I think we could solve the multiple front problem if we generalized the
problem to find SEVERAL 'localized centers', thus allowing for multiple axes
of advance along a somewhat more fluid 'front'. In the case of two armies,
you might get something like this:
x x x
y1 y2 y3 y4
x x x
In this case, each of the x-x pairs make INDEPENDENT determinations
of what lies 'between' them. Then, based on the relative combat strengths
and other factors, you could issue separate orders for each section of
the battlefield. This effectively sets up a variety of 'mini-centers'
(using our terminology from above) and more realistically (IMHO) emulates
realworld operations (i.e., lots of mini-objectives, the possibility for
overlapping objectives, etc.).
Opinions? Comments?
Steve Woodcock
one of the more interesting I've seen in this newsgroup. *This* is the kind
of brainstorming the Net was made for....
Andrae Muys (cca...@dingo.cc.uq.oz.au) wrote:
: Identifing the front first and then defining the rest w.r.t it would seem
: to simplify the problem further. I hadn't thought of that, it looks like
: a good idea. However one question to contimplate. Where are the fronts
: in the following position. {X - YOURS, Y - THEIRS}
: YY Now by any standards X is in a bad way. It has been
: Y completely outflanked and his left flank is already
: XXX YY overrun. Intuitivly his front is now perpendicular
: XX XXX XX XY Y to Y's. I think we may need a concept such as
: X X Y contact point, which in this case is Y's centre, and
: Y X's left flank. Naturally in most battles there would
: YYY be multiple contact points. Personally I would draw the
: Y fronts as follows.
: |
: | What do you think?
: --------C|
: |
: |
I would agree with your assessment of the situation and your breakdown
of the forces into a front. Obviously in this case, X either a.) needs
to rapidly execute a turn of his front or b.) is in the midst of a brilliant
plan that wil prove to be Y's undoing. (The challenge, of course, is to
get a computer AI to execute 'b' more often than 'a'.)
If we define a contact point, then does that give us a natural focus
towards which to direct our forces and our strategic 'thinking'? They would
seem to.
: : 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'?)
: This is why I am using a very basic set of game mechanics, and using a
: different era(see other post). This way the only way troops can reach
: your rear is to march there. Also there are very few battles in this era
: with multiple fronts. Although allowance must be made for bent and
: twisted fronts. The hinge being a very critical point in an extended line.
Okay; let's go with that simplification for now. It'll certainly make this
easier to think about, and we can always make the AI smarter in Rev 2.0! ;)
: In the rules I have in mind, most cases you will only have mass attacks
: or at least dense fronts. One problem you do have if you try to model a
: high echelon game such as the eastern front(WWII) what happened next.
: The russian front fragmented and from one dense front you ended up with
: hundreds of small localised fronts, the resulting loss of cohesion being
: one of the greatest advantages of blitzcrieg. Because cohesion is so
: much more important at a grand stratigic level(not that it isn't in
: stratagies at a operational/tactical level) I feel that a search for a
: front maybe counter productive. My gut feeling is that it would be
: better to consider area controled by your forces, controlled by their
: forces, and contested. With an emphisis on your forces maintaining
: unbroken contact between spheres of influence. So the insertion of
: forces 'behind the lines' would only alter the balance of control in the
: local area. A domino effect would be possible where forces stratigicly
: inserted would weaken a units control of an area weakening a unit relying
: on it for its 'cohesive link' weaking its control of another area and so
: on. However this is what happens in real life so if any thing it
: suggests that it may be a good approach.
Okay then, fronts are out. Spheres of influence are in. They do seem
to better reflect the 'domino effect', as you suggest.
If we use your previous suggestion for identifying centers, combined with
the above-mentioned contact points, then this may lead us towards a more
natural way of handling the above situation. Based on what we've discussed
so far, I would envision an AI's logic train going something like this:
Pass #1: Identify natural 'groups' of X-Y forces using the
'circle method' discussed earlier, perhaps taking into account
the possibilities of influence and interdiction as a previous
poster suggested.
Pass #2: Having identified these natural groupings, identify
contact points amongst the forces within each group. These
will serve as natural foci for our planning process.
Pass #3: Having identified natural groupings and focus points,
we now begin thinking about steps needed to link up our groups,
minimize the size of enemy-held areas, elimination of enemy units,
etc.
One thing we do want to avoid, of course, is TOO much reliance on
maintaining unbroken contact between spheres of influence. As you know,
in the Napoleanic era cavalry forces on the same side were often miles
apart and in some cases didn't even know of each other's existence! In this
case the AI would need to know to treat the two forces independently and
NOT make linking them a high priority.
Robert A. Uhl
Steve Woodcock <wood...@escmail.orl.mmc.com> wrote:
>
> Hmmm...this does have some merit to it. I like the idea of the 'center'
>being arrived at via this circle-method; it has an elegance to it that also
>is somewhat intuitive.
>
> The only potential problem I can see with this approach is that it will
>tend towards great massive brute force engagements by migrating the bulk
>of both forces towards a common 'center'. This is fine in the case of
>two combatants (i.e., two Bolo tanks) but not so good for two armies.
Actually, Bolo can be played by as many as 16 players, with as many
as 16 different sides. But most people play against bots only when
they cannot get any human competition, and so play against only one.
> I think we could solve the multiple front problem if we generalized the
>problem to find SEVERAL 'localized centers', thus allowing for multiple axes
>of advance along a somewhat more fluid 'front'. In the case of two armies,
>you might get something like this:
>
>
> x x x
>
> y1 y2 y3 y4
>
> x x x
>
> In this case, each of the x-x pairs make INDEPENDENT determinations
>of what lies 'between' them. Then, based on the relative combat strengths
>and other factors, you could issue separate orders for each section of
>the battlefield. This effectively sets up a variety of 'mini-centers'
>(using our terminology from above) and more realistically (IMHO) emulates
>realworld operations (i.e., lots of mini-objectives, the possibility for
>overlapping objectives, etc.).
Hmmm...
I assume that this assumes a single master strategist giving orders
to the units. I would think that the master should group neighboring
units as one, in order to save time when calculating the following:
calculate a center between every piece and every other. When his is
all done, choose the minimum amount of centers which take care of the
maximum amount of enemies. This should allow certain interesting
effects over varying terrain, if said terrain is taken into account as
it should be.
Otherwise, it sounds pretty good. If I ever get my set of Bolo
brains working, I'll turn 'em loose and see what happens.
--
Christos anesti ek nekron, thanato Christ is risen from the dead, trampling
thanaton patisas, kai tois en tois death by death, thus bestowing upon those
mnimasi, zoin charisamenos. in the tombs the gift of eternal life.
------------------------------------Robert Uhl---------------------------------
Robert A. Uhl
Steve Woodcock <wood...@escmail.orl.mmc.com> wrote:
>
>Andrae Muys (cca...@dingo.cc.uq.oz.au) wrote:
>
>: Identifing the front first and then defining the rest w.r.t it would seem
>: to simplify the problem further. I hadn't thought of that, it looks like
>: a good idea. However one question to contimplate. Where are the fronts
>: in the following position. {X - YOURS, Y - THEIRS}
>
>: YY Now by any standards X is in a bad way. It has been
>: Y completely outflanked and his left flank is already
>: XXX YY overrun. Intuitivly his front is now perpendicular
>: XX XXX XX XY Y to Y's. I think we may need a concept such as
>: X X Y contact point, which in this case is Y's centre, and
>: Y X's left flank. Naturally in most battles there would
>: YYY be multiple contact points. Personally I would draw the
>: Y fronts as follows.
>: |
>: | What do you think?
>: --------C|
>: |
>: |
>
>
>
> I would agree with your assessment of the situation and your breakdown
>of the forces into a front. Obviously in this case, X either a.) needs
>to rapidly execute a turn of his front or b.) is in the midst of a brilliant
>plan that wil prove to be Y's undoing. (The challenge, of course, is to
>get a computer AI to execute 'b' more often than 'a'.)
Heh. Actually, if X is driving through Y, in order to create two
fronts along which Y must fight, thereby forcing Y to regroup, then
'b' has been executed.
> If we define a contact point, then does that give us a natural focus
>towards which to direct our forces and our strategic 'thinking'? They would
>seem to.
Yes. The AI should attempt to create as many contatc points as
possible. Why? These points mean that he is actually fighting the
enemy and hopefully killing the same. That is why two parallel lines
are a good formation. With a good lookahead, though, the T formation
is also good, because it will enable many points of contact _over
time_, and hurt Y's ability to create them. Part of the battle is
controlling contact. In fact, if the AI can do this controlling, then
it is my belief that it will have an extremely good chance at winning.
> Okay then, fronts are out. Spheres of influence are in. They do seem
>to better reflect the 'domino effect', as you suggest.
The sphere of influence idea seems to work well with the points of
contact idea. Perhaps each unit has a sphere wherein it can contact
within a certain number fo moves (say 3), and its job is to contact
the fewest enemies at once but the most over time. IOW, it doesn't
want to be outnumbered but it wants to see action.
And two units have a greater sphere of influence, say 8 moves, than
just one. This would help reflect the greater power of two. Controlled
territory would be defined as that surrounded by my own units and
without enemy units, once again utilizing the SoIs. Contested would,
of course, be that which neither side controls. Perhaps a 'strength'
value would be attached to areas, indicating the number of units
controlling it, time for more to get there &c. Thiswould provide an
incentive for the AI to encircle enemy territory.
Andrae Muys
: : YY Now by any standards X is in a bad way. It has been
: : Y completely outflanked and his left flank is already
: : XXX YY overrun. Intuitivly his front is now perpendicular
: : XX XXX XX XY Y to Y's. I think we may need a concept such as
: : X X Y contact point, which in this case is Y's centre, and
: : Y X's left flank. Naturally in most battles there would
: : YYY be multiple contact points. Personally I would draw the
: : Y fronts as follows.
: : |
: : | What do you think?
: : --------C|
: : |
: : |
: I would agree with your assessment of the situation and your breakdown
: of the forces into a front. Obviously in this case, X either a.) needs
: to rapidly execute a turn of his front or b.) is in the midst of a brilliant
: plan that wil prove to be Y's undoing. (The challenge, of course, is to
: get a computer AI to execute 'b' more often than 'a'.)
Of course the ultimate AI wouldn't find itself in such a dangerous
position. A bit like the untimate General wouldn't. But if it does it
must extricate itself well. Just one more 'special' situation to test
the AI's abiltiy.
: If we define a contact point, then does that give us a natural focus
: towards which to direct our forces and our strategic 'thinking'? They would
: seem to.
Well this thread is useful. The idea of contact points should radically
prune any decision tree.(And sooner or later the AI will have to make a
choice) Of course at the stratigic/grand stratigic levels we may need a
modified definition of contact point but at the level I am interested in
Contact points appear to be a good way to look at things. In fact now
that I think about it, contact points are how **I** allocate **MY**
consideration. This approach however leads us to consider how to
recognise potential contact points and how to evaluate the relitive
benifits of creating/avoiding specific contact points. e.g. in the
example above X should avoid contact with Y until he has rotated his
front.(it looks like we may still need to consider fronts as well).
: : This is why I am using a very basic set of game mechanics, and using a
: : different era(see other post). This way the only way troops can reach
: : your rear is to march there. Also there are very few battles in this era
: : with multiple fronts. Although allowance must be made for bent and
: : twisted fronts. The hinge being a very critical point in an extended line.
: Okay; let's go with that simplification for now. It'll certainly make this
: easier to think about, and we can always make the AI smarter in Rev 2.0! ;)
My thoughts exactly.
<<<<SNIP>>>>
: : front maybe counter productive. My gut feeling is that it would be
: : better to consider area controled by your forces, controlled by their
: : forces, and contested. With an emphisis on your forces maintaining
: : unbroken contact between spheres of influence. So the insertion of
: : forces 'behind the lines' would only alter the balance of control in the
: : local area. A domino effect would be possible where forces stratigicly
: : inserted would weaken a units control of an area weakening a unit relying
: : on it for its 'cohesive link' weaking its control of another area and so
: : on. However this is what happens in real life so if any thing it
: : suggests that it may be a good approach.
: Okay then, fronts are out. Spheres of influence are in. They do seem
: to better reflect the 'domino effect', as you suggest.
However as discussed above at a lower level fronts again become
important. IMHO this is because tactical considerations require physical
cohesion, while stratigic(level) utilise logical cohesion. As you later
note cavalry detatchments regularlly operated independently of other
units. However (excluding irregulars) many/most operated in conjunction
with armies, their presence in a particular area, important to enemy
forces, deliberate and planned. Even though operating independently.
: If we use your previous suggestion for identifying centers, combined with
: the above-mentioned contact points, then this may lead us towards a more
: natural way of handling the above situation. Based on what we've discussed
: so far, I would envision an AI's logic train going something like this:
: Pass #1: Identify natural 'groups' of X-Y forces using the
: 'circle method' discussed earlier, perhaps taking into account
: the possibilities of influence and interdiction as a previous
: poster suggested.
: Pass #2: Having identified these natural groupings, identify
: contact points amongst the forces within each group. These
: will serve as natural foci for our planning process.
: Pass #3: Having identified natural groupings and focus points,
: we now begin thinking about steps needed to link up our groups,
: minimize the size of enemy-held areas, elimination of enemy units,
: etc.
This sounds like it should work reasonably well, however I have a feeling
there may be problems with the way it handles many sparse stratigic
situations. I'll think about it and we can discuss it futher when I have
clearified my concerns.
: One thing we do want to avoid, of course, is TOO much reliance on
: maintaining unbroken contact between spheres of influence. As you know,
: in the Napoleanic era cavalry forces on the same side were often miles
: apart and in some cases didn't even know of each other's existence! In this
: case the AI would need to know to treat the two forces independently and
: NOT make linking them a high priority.
One more thing about cavalry is that the other arms(INF/ART) can't
operate this way as it requires a level of speed.
One thing I am considering is cross posting some questions regarding real
life treatment of these concerns to rec.games.miniatures after they finish
their reorganisation.
Andrae.
Steve Woodcock
: Of course the ultimate AI wouldn't find itself in such a dangerous
: position. A bit like the untimate General wouldn't. But if it does it
: must extricate itself well. Just one more 'special' situation to test
: the AI's abiltiy.
War appears to be full of special cases, eh?
;)
: : If we define a contact point, then does that give us a natural focus
: : towards which to direct our forces and our strategic 'thinking'? They would
: : seem to.
: Well this thread is useful. The idea of contact points should radically
: prune any decision tree.(And sooner or later the AI will have to make a
: choice) Of course at the stratigic/grand stratigic levels we may need a
: modified definition of contact point but at the level I am interested in
: Contact points appear to be a good way to look at things. In fact now
: that I think about it, contact points are how **I** allocate **MY**
: consideration. This approach however leads us to consider how to
: recognise potential contact points and how to evaluate the relitive
: benifits of creating/avoiding specific contact points. e.g. in the
: example above X should avoid contact with Y until he has rotated his
: front.(it looks like we may still need to consider fronts as well).
Yes, I'd come to that conclusion as well. By identifying contact
points and making them the focus of (at least some) activity, we've
pruned our number of decisions fairly radically.
One concern I have with relying on them exclusively, however, is
that this makes the AI very reactive without some additional logic to
force it to 'seek' the enemy. Two obvious ways to handle this would be
a.) random movement of forces until contact with the enemy has been
achieved and b.) deliberate movement of forces to attain certain objectives
(which are, in effect, 'artificial' contact points, if you will).
It would be simple enough (I'm still talking Napoleonic-level for
simplicity's sake) to provide the AI with whatever its objectives are
for a given scenario; that's easy. The hard part is how to make it
approach those objectives in some fashion that makes sense rather than
to blindly throw its units down a road leading towards said objective
(perhaps the main failure of the AIs in Perfect General and Empire Deluxe,
to name two examples).
As I recall, Napoleonic-era tacticians were trained to recognize
'classic' battle formations (one such example being the 'T' you presented
earlier) and react accordingly. Pattern recognition is easy enough
to do on a computer via a variety of methods, ranging from simple table
lookup to full-blown neural nets.
: : If we use your previous suggestion for identifying centers, combined with
: : the above-mentioned contact points, then this may lead us towards a more
: : natural way of handling the above situation. Based on what we've discussed
: : so far, I would envision an AI's logic train going something like this:
: : Pass #1: Identify natural 'groups' of X-Y forces using the
: : 'circle method' discussed earlier, perhaps taking into account
: : the possibilities of influence and interdiction as a previous
: : poster suggested.
: : Pass #2: Having identified these natural groupings, identify
: : contact points amongst the forces within each group. These
: : will serve as natural foci for our planning process.
: : Pass #3: Having identified natural groupings and focus points,
: : we now begin thinking about steps needed to link up our groups,
: : minimize the size of enemy-held areas, elimination of enemy units,
: : etc.
: This sounds like it should work reasonably well, however I have a feeling
: there may be problems with the way it handles many sparse stratigic
: situations. I'll think about it and we can discuss it futher when I have
: clearified my concerns.
Agreed, it may. However, based on the above idea of using pattern
recognition to manuever our units in something resembling a smart fashion,
we can now elaborate on Pass #3:
Pass #3: Having identified natural groupings and focus points,
run a pattern-matching algorithm to identify most likely tactical
situations and reasonable responses. Randomly pick from the best
2 or 3 to avoid predicatability. For each turn a course of
action is in place, make some evaluation of its effectiveness
and/or success (i.e., has the pattern changed signficantly enough
to warrant a new course of action? have we attained the objective
in question? have we lost contact with the enemy?).
In the case of a sparse strategic situation, the AI defaults towards
trying to attain known and logical objectives (i.e., moving towards Paris).
Once contact is made, the situation naturally becomes less sparse, and
the AI begins to make moves based on sound engagement philosophies.
The AI will end up being a bit 'bookish', if you will, but certainly
ought to surprise you once in a while.
: However as discussed above at a lower level fronts again become
: important. IMHO this is because tactical considerations require physical
: cohesion, while stratigic(level) utilise logical cohesion.
<snip>
I'll buy that. That's a good definition, particularly for this
problem (Napoleonic-era combat), and better than many I've seen.
: [regarding comment that we post this to rec.games.miniatures]
Actually, I've already seen one thread on comp.ai recommeding THIS
thread as 'worthwhile'. ;)
Steven
Still Pondering in Orlando
==============================================================================
Steven Woodcock _
Senior Software Engineer, Gameware _____C .._.
Lockheed Martin Information Systems Group ____/ \___/
Phone: 407-826-6986 <____/\_---\_\ "Ferretman"
E-mail: wood...@gate.net
swoo...@oldcolo.com
wood...@escmail.orl.mmc.com
Daniele Terdina
(Andrae Muys) wrote:
> : 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'?)
> This is why I am using a very basic set of game mechanics, and using a
> different era(see other post). This way the only way troops can reach
> your rear is to march there. Also there are very few battles in this era
> with multiple fronts. Although allowance must be made for bent and
> twisted fronts. The hinge being a very critical point in an extended line.
I don't know if it can help, however, when I was thinking about how to
build a program for a computer opponent for Squad Leader (an Avalon Hill's
boardgame) I didn't consider directly recognizing the troops patterns. I
would build intermediate maps describing entities like density of fire,
distances in unit movement points (rether than linear distance),
probability of passing the zone without damage, etc. and base the
reasoning on this intermediate maps. It turns out that looking (as an
example) at the fire distribution makes it clearer if some allineated
troops makes a real front or not. Many sub tactical problems could be
solved by looking for the shortest path in some of these maps: from what
side should I attack that hill? find the longest path from your units to
the hill in the percentage of survival map, where the path lenght is the
product of the percentage of the zones passed!
Sure it is not so simple, because the enviroment is highly dinamic and
there are a lot of interdependancies, but it is a good starting point.
Please answer by e-mail
Daniele Terdina
sis...@ictp.trieste.it
Satrapa / Alexander Marc (ISE)
> Steve Woodcock (wood...@escmail.orl.mmc.com) wrote:
> : Andrae Muys (cca...@dingo.cc.uq.oz.au) wrote:
>
> : : YY Now by any standards X is in a bad way. It has been
> : : Y completely outflanked and his left flank is already
> : : XXX YY overrun. Intuitivly his front is now perpendicular
> : : XX XXX XX XY Y to Y's. I think we may need a concept such as
> : : X X Y contact point, which in this case is Y's centre, and
> : : Y X's left flank. Naturally in most battles there would
> : : YYY be multiple contact points. Personally I would draw the
> : : Y fronts as follows.
[snip]
> benifits of creating/avoiding specific contact points. e.g. in the
> example above X should avoid contact with Y until he has rotated his
> front.(it looks like we may still need to consider fronts as well).
Two options I can see here - either X moves its forces into Y's "front"
to create as much damage as possible (in a concentrated strike or
"blitzkreig" style attack) or X moves its "front" back, forcing Y to make
the next move (allowing X the advantage in defence).
Is X aggressive or defensive? Y's forces are rather spread out, so X can
"spear" through the front and attack from both sides (like an inverse of
the "pincer" movement).
Just a thought...
-Alex
Steve Woodcock
e-mail, but thought everybody here (hopefully) would be interested
as well.....
Daniele Terdina (sis...@ictp.trieste.it) wrote:
: I don't know if it can help, however, when I was thinking about how to
: build a program for a computer opponent for Squad Leader (an Avalon Hill's
: boardgame) I didn't consider directly recognizing the troops patterns. I
: would build intermediate maps describing entities like density of fire,
: distances in unit movement points (rether than linear distance),
: probability of passing the zone without damage, etc. and base the
: reasoning on this intermediate maps. It turns out that looking (as an
: example) at the fire distribution makes it clearer if some allineated
: troops makes a real front or not. Many sub tactical problems could be
: solved by looking for the shortest path in some of these maps: from what
: side should I attack that hill? find the longest path from your units to
: the hill in the percentage of survival map, where the path lenght is the
: product of the percentage of the zones passed!
: Sure it is not so simple, because the enviroment is highly dinamic and
: there are a lot of interdependancies, but it is a good starting point.
: Please answer by e-mail
: Daniele Terdina
: sis...@ictp.trieste.it
Hello Daniele:
*Very* interesting approach...I don't believe I've seen it presented
here before.
It wouldn't be too hard to generate a density map such as you
described and use it in conjunction with a route-finding algorithm to
manage unit movement. That certainly has the added advantage of having
units attempt to 'avoid' enemy fire (very much a realistic behavior!)
as well as still focusing on objectives. And your point concerning
whether a front is REALLY a front based on fire distribution is a good
one; we'd been assuming almost toe-to-toe contact, I think, in the above
thread, but the inclusion of any type of ranged weapon muddies that up.
Question: How would we build a fire distribution map if a given
unit has several different types of weaponry? An example of that might
be a machine-gun crew from Squad Leader; the individuals in the squad
all have fairly short-range sidearms and such, but they're all supporting
the longer-range MG. I guess the worse-case situation is the one you
have to assume, even though you have no idea that they'll shoot at you
(it's that "fog of war" thing again).
This could very well be an interesting solution to the sub-tactical,
ordering-units-to-shoot-at-something part of the problem.
Satrapa / Alexander Marc (ISE)
[bigsnip]
> 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
> 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.
One problem - any enemy who knows this strategy may use it against you
(and therefore both sides end up fighting over the center while the edge
of the board is unused), or may act like water and flow - so you get
through to their centre, but find that the edges of the board have
suddenly caved in on you. So their center is your center, but their
distribution is wider than yours... while you're attacking them over
here, they're stealing your bases/terrain over there.
Just a thought.
-Alex
Satrapa / Alexander Marc (ISE)
> Steve Woodcock (wood...@escmail.orl.mmc.com) wrote:
> one of the greatest advantages of blitzcrieg. Because cohesion is so
> much more important at a grand stratigic level(not that it isn't in
> stratagies at a operational/tactical level) I feel that a search for a
> front maybe counter productive. My gut feeling is that it would be
> better to consider area controled by your forces, controlled by their
> forces, and contested. With an emphisis on your forces maintaining
> unbroken contact between spheres of influence. So the insertion of
> forces 'behind the lines' would only alter the balance of control in the
> local area. A domino effect would be possible where forces stratigicly
> inserted would weaken a units control of an area weakening a unit relying
> on it for its 'cohesive link' weaking its control of another area and so
> on. However this is what happens in real life so if any thing it
> suggests that it may be a good approach.
In real life, I would imagine one of the main targets in any campaign to
be supply lines. For example, The Dambusters is a movie about some
special bombers with special bombs desiged to destroy dams, with the aim
of crippling Germany's iron/steel industry. General Custer was in trouble
because he was surrounded and cut off from supplies and reinforcements
(yes, my knowledge is very sketchy).
Another approach to defining a front is that it is where you want it to
be! Perhaps call your front where you are trying to hold back/push back
enemy forces. Incursions don't necessarily happen on a front - you may
quick-march or drop forces into enemy territory next to a vital supply
line, or sneak in sabateurs to destroy strategic bridges ("A Bridge Too
Far").
I heard someone claim once that war is about economic ruin rather than
outright carnage. Is there any way your AI can calculate the move that
will cause most damage to industry and support, rather than shoot the
most enemy? Of course, these strategies apply to wars, not battles...
Just a thought...
-Alex
Will Uther
<Pine.SOL.3.91.95051...@student.canberra.edu.au>,
In the type of combat I was thinking of, you each have only one active
piece that moves around the board moving the other 'static' pieces. If
Player A surrounds Player B, but Player B has supplies 'inside', then
player B has the
advantage. e.g.
1 2
3 4
Supplies
5 6
7 8
Assume that 1,2,7 and 8 are owned by A and effectively 'surround' B who
owns 3, 4, 5 and 6 (and some supplies that mean he never has to leave his
fort). B can attack 1. when A moves there to defend, B can break off and
attack 8. A has a long way to go to get to 8 (A has to go right around
whereas B can go through the centre) and so will probably lose that
piece. Being more spead-out than the opposition can be a big problem.
I agree that this is probably not the type of combat you were thinking
about. For an example of this type of combat look at the mac game Bolo.
\x/ill :-}
P.S. as a side note, Sun Tzu (sp?) in his 'Art of War' recommends against
sieges which is effectively the situation you have above.
Andrae Muys
: On 11 May 1995, Andrae Muys wrote:
<<<SNIP>>>
: > front maybe counter productive. My gut feeling is that it would be
: > forces, and contested. With an emphisis on your forces maintaining
: > unbroken contact between spheres of influence. So the insertion of
: In real life, I would imagine one of the main targets in any campaign to
: be supply lines. For example, The Dambusters is a movie about some
: special bombers with special bombs desiged to destroy dams, with the aim
: of crippling Germany's iron/steel industry. General Custer was in trouble
: because he was surrounded and cut off from supplies and reinforcements
: (yes, my knowledge is very sketchy).
Yes you are right one of the major considerations at a Stratigic level is
supply, how do I attack yours, how do I protect mine. One point
concerning General Custer however, his problem wasn't so much that his
supply lines were cut, more that he was surrounded with no avenue of
retreat. This is a position which is so inheriently poor that any AI
should automatically avoid it without any requirement for a 'special case'.
: Another approach to defining a front is that it is where you want it to
: be! Perhaps call your front where you are trying to hold back/push back
: enemy forces. Incursions don't necessarily happen on a front - you may
: quick-march or drop forces into enemy territory next to a vital supply
: line, or sneak in sabateurs to destroy strategic bridges ("A Bridge Too
: Far").
With the game mechanics we have been considering of late the AI won't
have to be concerned with most of these problems. I personally can't see
how defining a front 'where you want it to be' is useful although this is
probably more me not thinking it though properly than a problem with the
idea. What do you mean by it, and is it in anyway related to the concept
of critical point/contact point currently being discussed?
: I heard someone claim once that war is about economic ruin rather than
: outright carnage. Is there any way your AI can calculate the move that
: will cause most damage to industry and support, rather than shoot the
: most enemy? Of course, these strategies apply to wars, not battles...
Personally I prefer Sun Tzu's philosophy. Basically it holds that to win
without fighting is best, and the aim of war is to capture territory
without damaging it.
BTW: does anyone know if there is a e-text version of The Art of War
anywhere?
Andrae.
Andrae Muys
is awkward.
Satrapa / Alexander Marc (ISE) (u90...@student.canberra.edu.au) wrote:
: On 15 May 1995, Andrae Muys wrote:
: > Steve Woodcock (wood...@escmail.orl.mmc.com) wrote:
: > : Andrae Muys (cca...@dingo.cc.uq.oz.au) wrote:
: >
: > : : YY Now by any standards X is in a bad way. It has been
: > : : Y completely outflanked and his left flank is already
: > : : XXX YY overrun. Intuitivly his front is now perpendicular
: > : : XX XXX XX XY Y to Y's. I think we may need a concept such as
: > : : X X Y contact point, which in this case is Y's centre, and
: > : : Y X's left flank. Naturally in most battles there would
: > : : YYY be multiple contact points. Personally I would draw the
: > : : Y fronts as follows.
: [snip]
: > benifits of creating/avoiding specific contact points. e.g. in the
: > example above X should avoid contact with Y until he has rotated his
: > front.(it looks like we may still need to consider fronts as well).
: Two options I can see here - either X moves its forces into Y's "front"
: to create as much damage as possible (in a concentrated strike or
: "blitzkreig" style attack) or X moves its "front" back, forcing Y to make
: the next move (allowing X the advantage in defence).
IMO The first of your options is probably going to lead to disaster. X
is not only outflanked but overrun. From this postion any attack he
makes is going to be piecemeal, and forces commited to an attack
piecemeal are destroyed piecemeal to very little effect. IMHO the second
option is the only option avaliable to X, the question for X is how far
back to regroup, and what to do next. Some of his options as I see them
involve, pulling all units at the contact point back, all units not at
the contact point foward, form an offensive formation and try to break
Y's, by now dissordered, centre. Or maybe send forces to delay Y's flank,
utilise defence in depth at the contact point to buy time, and either
prepare an attack, prepare a defence, or use the manuvour to start a
rearguard action.
: Is X aggressive or defensive? Y's forces are rather spread out, so X can
: "spear" through the front and attack from both sides (like an inverse of
: the "pincer" movement).
Personally I would quite enjoy gaming Y against an X attacking from this
postion.
Steve Woodcock
: > I think we could solve the multiple front problem if we generalized the
: >of advance along a somewhat more fluid 'front'. In the case of two armies,
: >you might get something like this:
: >
: >
: > x x x
: >
: > y1 y2 y3 y4
: >
: > x x x
: >
: > In this case, each of the x-x pairs make INDEPENDENT determinations
: >of what lies 'between' them. Then, based on the relative combat strengths
: >and other factors, you could issue separate orders for each section of
: >the battlefield. This effectively sets up a variety of 'mini-centers'
: >(using our terminology from above) and more realistically (IMHO) emulates
: >realworld operations (i.e., lots of mini-objectives, the possibility for
: >overlapping objectives, etc.).
: Hmmm...
: I assume that this assumes a single master strategist giving orders
: to the units. I would think that the master should group neighboring
: units as one, in order to save time when calculating the following:
: calculate a center between every piece and every other. When his is
: all done, choose the minimum amount of centers which take care of the
: maximum amount of enemies. This should allow certain interesting
: effects over varying terrain, if said terrain is taken into account as
: it should be.
Robert:
Good point; some type of nearness type to lump together nearby units
for the foci calculations makes sense. It might or might not end up
saving time overall; the test to see if somebody is nearby is almost the
same test as determing grouping.
However, the idea of choosing the minimum number of centers to affect
the maximum number of enemies has a good feel to it. After all, that's
what I do when I play a game--try to annihilate his forces with the
minimum amount of force necessary, so I can use my 'extra' forces for
something else.
Steve Woodcock
: Heh. Actually, if X is driving through Y, in order to create two
: fronts along which Y must fight, thereby forcing Y to regroup, then
: 'b' has been executed.
Good point. Yet another example of how a human can spot an opportunity
in the face of the most daunting situations....
: > If we define a contact point, then does that give us a natural focus
: >towards which to direct our forces and our strategic 'thinking'? They would
: >seem to.
: Yes. The AI should attempt to create as many contatc points as
: possible. Why? These points mean that he is actually fighting the
: enemy and hopefully killing the same. That is why two parallel lines
: are a good formation. With a good lookahead, though, the T formation
: is also good, because it will enable many points of contact _over
: time_, and hurt Y's ability to create them. Part of the battle is
: controlling contact. In fact, if the AI can do this controlling, then
: it is my belief that it will have an extremely good chance at winning.
I'm not sure I agree that I would want the AI to maximize its number
of contacts with the enemy; I would agree that it should seek to control
them.
Maximization in itself will only lead to toe-to-toe WWI slugfests, and
basically leads to the AI playing a war of attrition. That's perhaps one
of the defining characteristics of most AIs today--if they don't cheat
somehow, then they tend to fight wars of attrition.
: The sphere of influence idea seems to work well with the points of
: contact idea. Perhaps each unit has a sphere wherein it can contact
: within a certain number fo moves (say 3), and its job is to contact
: the fewest enemies at once but the most over time. IOW, it doesn't
: want to be outnumbered but it wants to see action.
Yes indeed. That's sort of where we were headed, I believe.
I do like the idea of factoring time into the equation somehow; the AI
ought to be willing to have NO enemy contact for two turns if it's busy
moving forces around for MAJOR enemy contract (say, the Normandy invasion)
on the third turn. That does make sense intuitively. Perhaps we can tie
time-weighted values to multi-turn engagement decisions?
: And two units have a greater sphere of influence, say 8 moves, than
: just one. This would help reflect the greater power of two. Controlled
: territory would be defined as that surrounded by my own units and
: without enemy units, once again utilizing the SoIs. Contested would,
: of course, be that which neither side controls. Perhaps a 'strength'
: value would be attached to areas, indicating the number of units
: controlling it, time for more to get there &c. Thiswould provide an
: incentive for the AI to encircle enemy territory.
Agreed. This is very similar to the idea of using a 'fire distribution'
map that was presented by Daniele, actually, just a different method of
solving the same problem. We'll want to do SOMETHING like this in order
to properly consider the limiting effects of enemy weaponry and the
local terrain.
Steve Woodcock
: With the game mechanics we have been considering of late the AI won't
: how defining a front 'where you want it to be' is useful although this is
: probably more me not thinking it though properly than a problem with the
: idea. What do you mean by it, and is it in anyway related to the concept
: of critical point/contact point currently being discussed?
That's right; at the moment we're sort of focusing on a roughly
Napoleonic-era level of combat for the sake of simplicity. Paratroopers
will be added in AI v. 2.0. ;)
: : I heard someone claim once that war is about economic ruin rather than
: : outright carnage. Is there any way your AI can calculate the move that
: : will cause most damage to industry and support, rather than shoot the
: : most enemy? Of course, these strategies apply to wars, not battles...
: Personally I prefer Sun Tzu's philosophy. Basically it holds that to win
: without fighting is best, and the aim of war is to capture territory
: without damaging it.
If we hold to the concept of specifying various objectives (as discussed
way back at the start of this thread), then I would think moves designed
to inflict economic damage would flow naturally out of that. Oil wells,
ports, rail lines, etc. would all be natural objectives, and as the AI
considers its moves and attempts to seize objectives they would naturally
be overrrun.
: BTW: does anyone know if there is a e-text version of The Art of War
: anywhere?
Good question...I'd like to know myself.
Will Uther
wood...@escmail.orl.mmc.com (Steve Woodcock) wrote:
> Robert A. Uhl (ru...@phoebe.cair.du.edu) wrote:
> : Yes. The AI should attempt to create as many contatc points as
> : possible. Why? These points mean that he is actually fighting the
> : enemy and hopefully killing the same. That is why two parallel lines
> : are a good formation. With a good lookahead, though, the T formation
> : is also good, because it will enable many points of contact _over
> : time_, and hurt Y's ability to create them. Part of the battle is
> : controlling contact. In fact, if the AI can do this controlling, then
> : it is my belief that it will have an extremely good chance at winning.
>
> I'm not sure I agree that I would want the AI to maximize its number
> of contacts with the enemy; I would agree that it should seek to control
> them.
>
> Maximization in itself will only lead to toe-to-toe WWI slugfests, and
> basically leads to the AI playing a war of attrition. That's perhaps one
> of the defining characteristics of most AIs today--if they don't cheat
> somehow, then they tend to fight wars of attrition.
Very good point.
> : The sphere of influence idea seems to work well with the points of
> : contact idea. Perhaps each unit has a sphere wherein it can contact
> : within a certain number fo moves (say 3), and its job is to contact
> : the fewest enemies at once but the most over time. IOW, it doesn't
> : want to be outnumbered but it wants to see action.
This is where the determination of neighbours came in before. Assume the
following:
1
2 3
A
A is attacking and could normally reach 1, 2 or 3. However most humans
would rule out attacking 1 because 2 and 3 are 'in the way' - 1 is not a
neighbour of A.
This is assuming normal distances are used. If you penalise paths for
travelling close to an enemy then the shortest path A -> 1 may be around
the outside of 2 or 3 - making it 'out of range' anyway. You have to
search for shortest paths in this case though.
\x/ill :-}
.oO FactorY Oo.
>Personally I prefer Sun Tzu's philosophy. Basically it holds that to win
>without fighting is best, and the aim of war is to capture territory
>without damaging it.
>anywhere?
>
http://timpwrmac.clh.icnet.uk/Docs/suntzu/szcontents.html
for the Art of War (not the 1960's translation, an older one) , and
http://fermi.clas.virginia.edu/~gl8f/paradoxes.html
for George Silver's Paradoxes of defence, which is probably
in a similarr vein, but I have not got around to reading it yet.
Anybody who does any type of strategic or tactical stuff should
read at least the Art of War, very good stuff indeed.
--
______ _____________________________________ _______
(_ ___ / / / / / / |/ / /
(__ / ___/ / / / / / / /__
/ __// . / ___/__ __/ __ / . /____ /___)_
Steve Woodcock
Jason Kester (the guy whose post is contained below) asked me to post this
for him; he's having some problems actually getting his posts to take.
He went ahead and tried the most recent suggestion for generating a
force map and got some interesting results....
==============================================================================
From JKe...@sea.ms.ch2m.com Fri May 19 15:04:11 1995
Received: from ds9.ch2m.com (ds9.ch2m.com [130.77.4.78]) by tequesta.gate.net (8.6.9/8.6.9) with ESMTP id PAA88870 for <wood...@gate.net>; Fri, 19 May 1995 15:03:48 -0400
Received: from smtpgate.ch2m.com (smtpgate.ch2m.com [130.77.4.228]) by ds9.ch2m.com (8.6.4/8.6.4) with SMTP id NAA08839 for <wood...@gate.net>; Fri, 19 May 1995 13:11:43 -0600
Received: by smtpgate.ch2m.com with Microsoft Mail
id <2FBC...@smtpgate.ch2m.com>; Fri, 19 May 95 13:04:29 PDT
From: "Kester, Jason/SEA" <JKe...@sea.ms.ch2m.com>
To: Steve Woodcock <wood...@gate.net>
Subject: AI Stuff
Date: Fri, 19 May 95 13:06:00 PDT
Message-ID: <2FBC...@smtpgate.ch2m.com>
Encoding: 64 TEXT
X-Mailer: Microsoft Mail V3.0
Status: RO
Hey, I dont know what's wrong w/ my mailserver, but for some reason it wont
send my posts out to the rest of the world. Anyway, I have some comments on
that strategic position thread in comp.ai.games & since I've seen yer name
on a bunch of stuff there, I thot you might do me a favor & post this there.
If not, just send me a big ol' nasty message & I'll try this thru someone
else. Thanks!
Jason Kester - jke...@sea.ms.ch2m.com
>:
>: The algorithm boils down to:
>
>: 1) Assign each map location one of three values:
>: a) If it's empty, assign 0;
>: b) If it's occupied by a friendly unit, assign a positive value.
>: c) If it's occupied by an enemy unit, assign a negative value.
>
>: 2) Make a new copy of the map with each location receiving its old
>: value modified by the six hexes surrounding it:
>: a) Increase by one for each adjacent hex containing a positive
>: value.
>: b) Decrease by one for each adjacent hex containing a negative
>: value.
>
>: 3) Copy the new map back into the old map.
>
>: 4) Repeat steps 2) and 3) an arbitrary number of times.
>
Well, I refined this algorithm a little & tried it out. First of all, I
used a square matrix so my computer could handle it easier. My major
change, however, was in step two.
for each square:
a) get the value it had last time
b) add the values of the 8 surrounding squares together & scale (divide)
them by some
factor. I used 4 & it worked ok, but 2 or 8 would be good too.
c) add a&b to get new value.
Then Step 3 & 4 - I repeated twice to get a good dispersion.
Your original values dont need to be too high, since they get increased with
each iteration. A couple 10's next to eachother grow to 50 or so after two
iterations.
Finally, I had a third matrix defined which holds the defensive
modifications due to terrain. These can be positive or zero, and you just
add them on top at the end. I suppose you could multiply them instead, but
you get the idea.
I ran this on a 10X10 matrix w/ 3 or four units for + and -, then stuck it
into my surface mapper. Sure enough, your zero-level contour defines a
front. Your units have areas of influence that overlap & combine w/
eachother & you can see where thecenter of their force is with a relative
max (or min).
I guess the next step is to have your forces find a relative max in the
opponents side, and send a bigger force in there. The idea being that you
send a group with a force count higher than the enemy, and not just a bunch
of individual units that may add up to enough if they happen to get there at
the right time.
==============================================================================
That's Jason's post.
Very interesting results. I remain somewhat unconvinced that it's a
good thing for a very high value unit to 'swamp' a nearby low-value enemy
unit, but it didn't seem to make a difference here, so maybe I'm wrong.
Time to try a little experimental coding myself....
Steve Woodcock
: cca...@dingo.cc.uq.oz.au (Andrae Muys) writes:
: >Personally I prefer Sun Tzu's philosophy. Basically it holds that to win
: >without fighting is best, and the aim of war is to capture territory
: >without damaging it.
: >BTW: does anyone know if there is a e-text version of The Art of War
: >anywhere?
: >
: >Andrae.
: http://timpwrmac.clh.icnet.uk/Docs/suntzu/szcontents.html
: for the Art of War (not the 1960's translation, an older one) , and
: http://fermi.clas.virginia.edu/~gl8f/paradoxes.html
: for George Silver's Paradoxes of defence, which is probably
: in a similarr vein, but I have not got around to reading it yet.
: Anybody who does any type of strategic or tactical stuff should
: read at least the Art of War, very good stuff indeed.
Thank you very much!!! I knew they had to be out there somewhere...
==============================================================================
Steven Woodcock _
Senior Software Engineer, Gameware _____C .._.
Lockheed Martin Information Systems Group ____/ \___/
Phone: 407-826-6986 <____/\_---\_\ "Ferretman"
E-mail: wood...@gate.net
swoo...@oldcolo.com
wood...@escmail.orl.mmc.com
Eric Dybsand
cs58...@lux.latrobe.edu.au (.oO FactorY Oo.) writes:
>
>cca...@dingo.cc.uq.oz.au (Andrae Muys) writes:
>>Personally I prefer Sun Tzu's philosophy. Basically it holds that to
>>BTW: does anyone know if there is a e-text version of The Art of War
>>anywhere?
>>
>>Andrae.
>
>http://timpwrmac.clh.icnet.uk/Docs/suntzu/szcontents.html
> for the Art of War (not the 1960's translation, an older one) , and
>
>http://fermi.clas.virginia.edu/~gl8f/paradoxes.html
> for George Silver's Paradoxes of defence, which is probably
>in a similarr vein, but I have not got around to reading it yet.
Do you have another site for the Sun Tzu work? I just tried the one
above as was unable to find /Docs/suntzu/szcontents.html at that site.
Apparently, things have changed there.
Any other suggestion would be appreciated.
Regards,
Eric
Steve Woodcock
: The function must first seek to find nearby units. The first
: criteria for 'nearness' would simply be physical nearness. This would
: choose, say 10 or 20 units. These would be sorted by strength, then by
: friendly units in the rough direction of the enemy. The idea is that a
: unit doesn't know where its allies are headed, but if they are near an
: enemy, the odds are that it is a melee situation. After sorting these
: the second time, the AI would choose the 'nearest' unit. In close
: quarters, it would most likely choose the physically nearest one. But
: from a distance, it would tend towards otehr criteria, such as unit
: strength, friendlies in the area, &c.
Okay. Earlier in the thread a mechanism for 'grouping' enemy and
allied units was proposed that involved drawing circles based variously
on movement capabilities and/or firepower.
: The one problem is that such an AI might be too chaotic at first,
: sending units out willy-nilly. These first units would be likely to go
: one way, then the other. But soon, I believe that some order would
: arise. Units would have a tendency to conglomerate in an area and
: fight as one. This is just my own thought, though. It is quite
: possible that it would be entirely too chotic.
I wonder if some variant of this isn't what many games already do?
Most of them do tend to exhibit a nasty tendency to trickle units unit
a battle.
: >
: > 1
: >
: > 2 3
: >
: > A
: >
: Hmm. I would suggest that the AI measure the distances. For the sake
: of argument A->1 = 3, A->2 = 2, A->3 = 2.
: The AI takes its 5 closest neigbours, that is 1, 2, 3, null and
: null. Of the the closest is 2 (since it is numerically before 3, which
: is the same distance away). In real life, this would be adjusted with
: another function, perhaps measuring the relative strength of the unit
: in question. It opts to attack 2. After attacking two, it opts to
: attack 1. After one, it takes on 3. Of course, it may be too weak by
: then and therefor leaves the field or waits for reinforcements.
: Simplistic, and probably not the best method. In fatc, I know that
: it is rather bad, but it works, and that is what counts for the
: moment. Perhaps it would only be good for individual movement. In
: fact, I think thta it would mimic a single man rather well. The man
: takes on the closest, weakest enemy.
As you say, this solution is fast but sub-optimal. There's no provision
or mechanism for combining the firepower of several allied units against
a single enemy unit. That's a situation that occurs in both the strategic
arena and the tactical.
On a related subject, I wonder how one would best determine how many
units to allocate to the attack against a given enemy unit? I can think
of two approaches:
a.) The AI operates on a battle-to-battle basis, always strives to
achieve a certain ratio (3:1) or certain probability of kill (say, 90%)
and allocates units (depending on their proximity to the battle) to
achieve this;
b.) The AI works on a more 'big picture' basis, attempting to maximize
OVERALL probability of kill across several battles (i.e., willing to
take a 20% chance of success in one battle for three others at 90%).
Intellectually, option 'b' is more appealing, and more reflective of
how most gamers actually play. You balance your needs and are sometimes
willing to sacrifice one unit to save several others.
There's no need, nor is terribly desirable, for the AI to attempt to make
this tradeoff across the entire battlefield. I think we could tie this in
with the influence mapping suggested earlier to easily identify sub-areas
of the battlefield that the AI could make the tradeoffs in, perhaps by
using some type of edge detection across the values of the hexes?
Steven
==============================================================================
Steven Woodcock _
Senior Software Engineer, Gameware _____C .._.
Lockheed Martin Information Systems Group ____/ \___/
Phone: 407-826-6986 <____/\_---\_\ "Ferretman"
E-mail: wood...@gate.net
swoo...@oldcolo.com
wood...@escmail.orl.mmc.com
Robert A. Uhl
Will Uther <wi...@cs.su.oz.au> wrote:
>In article <3pd6nc$l...@theopolis.orl.mmc.com>,
>wood...@escmail.orl.mmc.com (Steve Woodcock) wrote:
>
>>
>> Maximization in itself will only lead to toe-to-toe WWI slugfests, and
>> basically leads to the AI playing a war of attrition. That's perhaps one
>> of the defining characteristics of most AIs today--if they don't cheat
>> somehow, then they tend to fight wars of attrition.
>
Well, to minimize the possibility of a WWI-type war, something needs
to be done to keep the AI from planning one (gee, that was
brilliant:-). There are two possibilities: allow it to do so, but give
ti the long-range planning skills necessary to make it realize that
such a war is undesirable, or keep it from planning such a war. I will
focus on preventing this.
First of all, the unit must attempt to maximize contact with weak
units _over time_. It must seek to minimize contact with any units,
esp. strong ones, at once. To do so, it can be given either planning
skills, or merely given a function which will do so. Once again, I
will concentrate on the simpler way and faster. Planning takes CPU
time, something which most 'puters lack. Planning would take the form
of a path finder which would decide the path for a unit which would
bring it in contact with units individually.
The function must first seek to find nearby units. The first
criteria for 'nearness' would simply be physical nearness. This would
choose, say 10 or 20 units. These would be sorted by strength, then by
friendly units in the rough direction of the enemy. The idea is that a
unit doesn't know where its allies are headed, but if they are near an
enemy, the odds are that it is a melee situation. After sorting these
the second time, the AI would choose the 'nearest' unit. In close
quarters, it would most likely choose the physically nearest one. But
from a distance, it would tend towards otehr criteria, such as unit
strength, friendlies in the area, &c.
The one problem is that such an AI might be too chaotic at first,
sending units out willy-nilly. These first units would be likely to go
one way, then the other. But soon, I believe that some order would
arise. Units would have a tendency to conglomerate in an area and
fight as one. This is just my own thought, though. It is quite
possible that it would be entirely too chotic.
Also, it must be made possible for them to retreat. With this, your
units willbe akin to men; they don't like to be hit on too much.
Perhaps they would be craven or berserk. That would be neat.
>> : The sphere of influence idea seems to work well with the points of
>> : contact idea. Perhaps each unit has a sphere wherein it can contact
>> : within a certain number fo moves (say 3), and its job is to contact
>> : the fewest enemies at once but the most over time. IOW, it doesn't
>> : want to be outnumbered but it wants to see action.
>
>This is where the determination of neighbours came in before. Assume the
>following:
>
> 1
>
> 2 3
>
> A
>
> A is attacking and could normally reach 1, 2 or 3. However most humans
>would rule out attacking 1 because 2 and 3 are 'in the way' - 1 is not a
>neighbour of A.
> This is assuming normal distances are used. If you penalise paths for
>travelling close to an enemy then the shortest path A -> 1 may be around
>the outside of 2 or 3 - making it 'out of range' anyway. You have to
>search for shortest paths in this case though.
Hmm. I would suggest that the AI measure the distances. For the sake
of argument A->1 = 3, A->2 = 2, A->3 = 2.
The AI takes its 5 closest neigbours, that is 1, 2, 3, null and
null. Of the the closest is 2 (since it is numerically before 3, which
is the same distance away). In real life, this would be adjusted with
another function, perhaps measuring the relative strength of the unit
in question. It opts to attack 2. After attacking two, it opts to
attack 1. After one, it takes on 3. Of course, it may be too weak by
then and therefor leaves the field or waits for reinforcements.
Simplistic, and probably not the best method. In fatc, I know that
it is rather bad, but it works, and that is what counts for the
moment. Perhaps it would only be good for individual movement. In
fact, I think thta it would mimic a single man rather well. The man
takes on the closest, weakest enemy.
--
.oO FactorY Oo.
: In <1995May19.1...@lugb.latrobe.edu.au>: >
: >http://timpwrmac.clh.icnet.uk/Docs/suntzu/szcontents.html
: > for the Art of War (not the 1960's translation, an older one) , and
: >
: >http://fermi.clas.virginia.edu/~gl8f/paradoxes.html
: > for George Silver's Paradoxes of defence, which is probably
: >in a similarr vein, but I have not got around to reading it yet.
: Do you have another site for the Sun Tzu work? I just tried the one
: above as was unable to find /Docs/suntzu/szcontents.html at that site.
: Apparently, things have changed there.
: Any other suggestion would be appreciated.
Anybody who has a problem with this site could contact
m_coc...@icrf.icnet.uk, who converted the documents to
html format, and he is not reachable one could try Bob Sutton,
who wrote the preface,
( al...@cleaveland.freenet.edu or bo...@gnu.ai.mit.edu )
^^^^
Hmm is gnu going to do something with ai's, or does Bob have a
strange machine name..?
--
______ _____________________________________ _______
(_ ___ / / / / / / |/ / /
(__ / ___/ / / / / / / /__
/ __// . / ___/__ __/ __ / . /____ /___)_
/__/ /__/__/_____/ /__/ /______/__/__|______/______)
Will Uther
It seems that this thread is heading towards a 'spreading activation'
type algorithm (see the 'influence mapping' thread for my comments on how
to do/use that type of algorithm). I don't think that a real-time game
played of a large map has the computational power to implement that type
of algorithm.
A better type (computationally feasable) of algorithm would just
consider the pieces on the board, rather than each square. As whoever
started this thread said, the reason for looking for 'fronts' and other
high level entities was to speed up search. Finding these entities by
considering ever square on the board is self-defeating.
Anyway, as I said in my post to the 'influence mapping' thread, a front is
not just a line of equal influence/distance. It is a small section of
that line closest to the two opposing sides.
An algorithm for defining a front mathematically is to place a 'kernal
function' around each piece. Say each piece has a function
Strength/sqrt((x-X)^2+(y-Y)^2) == Strength/dist. Your pieces have +ve
strength, theirs have -ve strength. Where the sum of kernals is 0 is a
point of equal strength. Where the sum of kernals is 0 and there is a
large derivative is a front. This still leaves the problem of solving
that lot and doesn't take terrain into account.
Anyone else got any ideas? BTW, this was why I originally came up with
the concept of centres, and defining area in the circle which they sit on
as the 'front'. It doesn't use spreading activation and can be partially
modified for terrain.
Steve Woodcock
: Hi,
: It seems that this thread is heading towards a 'spreading activation'
: type algorithm (see the 'influence mapping' thread for my comments on how
: to do/use that type of algorithm). I don't think that a real-time game
: played of a large map has the computational power to implement that type
: of algorithm.
:
: A better type (computationally feasable) of algorithm would just
: consider the pieces on the board, rather than each square. As whoever
: started this thread said, the reason for looking for 'fronts' and other
: high level entities was to speed up search. Finding these entities by
: considering ever square on the board is self-defeating.
As I understand it, the influence mapping centers on the units themselves,
propogating their influence out across the map. While I question whether or
not it is practical or feasible to do this for evrey unit and every hex,
the approach is otherwise very similar to what you suggest.
: Anyway, as I said in my post to the 'influence mapping' thread, a front is
: not just a line of equal influence/distance. It is a small section of
: that line closest to the two opposing sides.
I don't think I would agree. A front isn't a line of equal influence,
nor is it a section of that line closest to the two opposing sides. It
is where there are opposing forces, of whatever strength, in close enough
proximity to affect each other.
: An algorithm for defining a front mathematically is to place a 'kernal
: function' around each piece. Say each piece has a function
: Strength/sqrt((x-X)^2+(y-Y)^2) == Strength/dist. Your pieces have +ve
: strength, theirs have -ve strength. Where the sum of kernals is 0 is a
: point of equal strength. Where the sum of kernals is 0 and there is a
: large derivative is a front. This still leaves the problem of solving
: that lot and doesn't take terrain into account.
I see this as a variant on influence mapping....you've got the unit's
strength, propogated over a distance.
: Anyone else got any ideas? BTW, this was why I originally came up with
: the concept of centres, and defining area in the circle which they sit on
: as the 'front'. It doesn't use spreading activation and can be partially
: modified for terrain.
Actually I'm still more in favor of defining centers and circles
rather than using influence mapping, if only because it's computationally
less intensive. On the other hand, the idea of influence mapping is
rather unique, and does better propogate the value of combined arms
than center definition.
Steven
==============================================================================
Steven Woodcock _
Senior Software Engineer, Gameware _____C .._.
Lockheed Martin Information Systems Group ____/ \___/
Phone: 407-826-6986 <____/\_---\_\ "Ferretman"
E-mail: wood...@gate.net
swoo...@oldcolo.com
wood...@escmail.orl.mmc.com
Daniel Boese
Is there any way to combine all of the previously mentioned approaches,
with limits on each? They've all got advantages, and are more useful in
certain situations than others (ie, influence mapping seems like it would
be excellent if you had a several forces on each side, some surrounding
each other). But is there any way for the AI to recognize which method to
use in a particular situation? Or would it do a "quickie" run of each,
and compare?
Then again, I'm not entirely sure I have any idea what I'm talking
about... :)
--
--
Daniel Boese aka Flying Fox
dbo...@freenet.niagara.com
Will Uther
cs58...@lux.latrobe.edu.au (.oO FactorY Oo.) wrote:
> Eric Dybsand (ed...@ix.netcom.com) wrote:
> : In <1995May19.1...@lugb.latrobe.edu.au>
> : cs58...@lux.latrobe.edu.au (.oO FactorY Oo.) writes:
> : >
> : >http://timpwrmac.clh.icnet.uk/Docs/suntzu/szcontents.html
> : > for the Art of War (not the 1960's translation, an older one) , and
> : >
> : >http://fermi.clas.virginia.edu/~gl8f/paradoxes.html
> : > for George Silver's Paradoxes of defence, which is probably
> : >in a similarr vein, but I have not got around to reading it yet.
>
> : Do you have another site for the Sun Tzu work? I just tried the one
> : above as was unable to find /Docs/suntzu/szcontents.html at that site.
> : Apparently, things have changed there.
>
> : Any other suggestion would be appreciated.
I found these two:
http://atlantis.austin.apple.com/html/gan2/TAW/STAW.html
and
http://deepthought.armory.com/~peterr/suntzu/szfront.html
Andrew Edward White
Does it make any difference to the AI if the game being played
is Real-Time as opposed to turn-based? In a real-time game, the
game state can change dynamically even as the analysis is being
performed. Is this significant, or is it simply a matter of
having a fast enough algorithm/processor that the dynamic
situation can be treated as static?
(I am assuming that individual units can be given simple commands
(eg 'Shoot that' or 'Move there') that they can carry out without
continual strategic direction.)
Steve Hodsdon
In article <3pd743$l...@theopolis.orl.mmc.com> wood...@escmail.orl.mmc.com writes:
>
> Andrae Muys (cca...@dingo.cc.uq.oz.au) wrote:
>
> : BTW: does anyone know if there is a e-text version of The Art of War
> : anywhere?
>
> Good question...I'd like to know myself.
>
I don't know of one. I do have the Shambhala editions of _The Art
of War_ and _Mastering The Art of War_. I'd like to use Sun Tzu's
philosophy in a wargame although I doubt that there would be much
interest in the game. Can you imagine it? Winning battles without
fighting? How boring! :)
Another book that you folks may find interesting is _The Art of
Maneuver_ by Robert Leonhard. (Subtitled "Maneuver-Warfare Theory and
AirLand Battle"). ISBN 0-89141-532-7, Presidio Press, 1991. I just
picked this one up a few days ago so I'm not going to post an in-depth
review. However, from what I've read so far, the "Maneuver-Warfare
Theory" section falls in with what I've read in this thread.
For example, in chess, what is the center of gravity? At first you
may think that it's the queen. After all, it's the strongest piece.
Lose the queen and you suffer a terrible reduction in your "warfighting
capabilities." But this isn't true. Think about it some more. The
enemy's center of gravity is not his source of strength, it's his
*critical vulnerability*. Therefore, in chess, the COG is the king.
Neutralize this piece and the war is over.
Steve
--
Whoops, Gotta run. | shod...@netis.mv.com
The cat's caught in the printer! |
Satrapa / Alexander Marc (ISE)
[bits cut out]
> ... This is a position which is so inheriently poor that any AI
The main problem here is - how does your AI recognise that it is entering
an "inherently poor" position? Traps don't usually lend themselves to
detection!
One trap I rather like was set in Anne Macaffrey's "The Ship Who
Searched" (or was it "PartnerShip"). (Both books were co-authored by
Anne). One particularly smart bloke took over manufacture of chips for
electronic devices, and released a new "hyperchip" which was so much more
advanced. Of course, everyone wanted this new advanced chip, so everyone
installed it. The trap was that the hyperchip was programmed to respond
to a particular signal, so when this bloke wanted to, he signalled all
the chips to fail, and almost managed to "take over the universe".
Another trap this same bloke laid was in a game he played with some
friends earlier in the story (I think as a hint to the reader about what
to expect later). In this game, players select different characters with
different skills - eg: A mage who can cast spells, a warrior who can kill
people, etc. This bloke had a really wimpy mage character, who spent most
of his time avoiding other players and casting a magical net. While the
other players were busy hack-and-slashing with each other, his net grew
bigger and stronger then "snap!" he closed the net, killed the other
players and won the game.
> : Another approach to defining a front is that it is where you want it to
> : be!...
[snip]
> ... What do you mean by it, and is it in anyway related to the concept
> of critical point/contact point currently being discussed?
What I meant was - draw a line in the sand and say "Any enemy crossing
this line are fair game". As (if) you manage to eliminate enemy crossing
the line, move the line further into enemy territory. This is, of course,
assuming that the war is about gaining territory.
[snip]
> Personally I prefer Sun Tzu's philosophy. ...
> ... the aim of war is to capture territory without damaging it.
[snip]
But then you have wars like in what was Yugoslavia, where the aim is not
to capture territory, but to "wipe out the infidel!" ie: A war of attrition.
In Bolo, the aim of the war is to make the enemy capitulate - whether by
capturing all supply bases (or rendering them unusable) or denying access
to territory.
In a naval battle, the main aim is to sink the other ship. The secondary
aim is not to be sunk. Sometimes one must realise that "he who fights and
runs away, lives to fight another day".
This is getting off topic, I think, but I'll be willing to discuss
different scenarios/strategies with whoever has the patience!
-Alex
Marc Carrier
I have been paying close attention to this thread and the Influence Mapping
one and their are two observation I have made:
1) First, the influence mapping algorithm proposed (not the priority queue but
the previous one) seemed very effective but is computationally intensive. However, I expect it would not have to be computed on every game turn and that
instead, modifications could be made to an already computed influence map to
obtain a sufficiently good approximation. (eg. When your troops move, you increase your influence in one hex and decrease it in the other, but your influence in the area, ie. adjacent hexes, remains approximately unchanged.) Only when units are destroyed or after a number of game turns would you have to go through the big expense of applying the influence mapping algorithm to get an accurate map.
2) The search for a fronts is extremelly important in planning your strategy but only looking for the front only gives you half the picture. Let me expand:
When I play war games, my first priority is to defend at fronts so my troops are not overunned. Maintaining sufficient power fire to DEFEND at the front is my number one priority (excluding exceptions here and there). Forget about an offensive for the moment. That comes later.
My second priority is finding, creating and assaulting "targets of opportunity". These are enemy units or objectives which are not well defended and usually isolated. Unfortunately, the influence mapping algorithm would show the hexes where these targets of opportunity are as under my control if they were surrounded by my troops. This enemy unit may be far from the front but is an unit that every one would attack immediately (excluding exceptions here and there.)
My last objective, once the destruction of all targets of opportunities has been
addressed, is to ATTACK on the fronts where I have superiority.
My beef about all this is that the current discussion does not include and detect these targets of opportunity. I think what need to be done is to compute two influence maps:
a) One map computed the standard way which defines fronts and zones of control.
b) One map computed the standard way except that the influence of opposing forces does not affect the value of a hexes occupied by a friendly unit. Hence, a hex occupied by a friendly is always positive, a hex occupied by a foe is always negative.
Map b) would show target of opportunity since one or a few hexes would have negative values while being surrounded by large positive values (Large derivatives would identify these areas) and the map a) would show that you have a large influence on that enemy occupied hex and hence, could destroy it easily.
Map b) would also identify which of your units are about to be destroyed because they are greatly out numbered (the opposite situation) and some strategic decision would have to be made about sacrificing , regrouping or reinforcing the unit.
Map b) would also indicate where on the front, identified with map a), you should strike since it would identify where the enemy is the weakest and you the strongest. ie. map a) identifies fronts as hexes where the influence value is zero but the derivative is large. Map b) values at the front hexes will indicate which side is on the defensive or offensive along each portion of the front. This is crucial to 1) DEFEND along the front, and 2) start an offensive where the enemy is the weakest on the front.
Andrae Muys
<<<SNIP>>>
: Well, I refined this algorithm a little & tried it out. First of all, I
: change, however, was in step two.
: I guess the next step is to have your forces find a relative max in the
: send a group with a force count higher than the enemy, and not just a bunch
: of individual units that may add up to enough if they happen to get there at
: the right time.
: ==============================================================================
: That's Jason's post.
: Very interesting results. I remain somewhat unconvinced that it's a
: good thing for a very high value unit to 'swamp' a nearby low-value enemy
: unit, but it didn't seem to make a difference here, so maybe I'm wrong.
: Time to try a little experimental coding myself....
I'm not so sure. This mapping idea is derived from an attempt to
represent the 'overall picture'. Each unit makes its own contribution to
the o.p but a small or weak unit can simply be insufficient to affect the
overall balance of power. Its presence has 'reduced' the control of the
square by the enemy BUT it is still definately in enemy territory. Still
one small unit in enemy territorry can do a lot of damage. I suggest
that this technique(which is very promising) must be used in conjunction
with others if the AI is to make good decisions, and that if needs
something with a 'higher resolution' when considering how to alter the
o.p. in its favour.
Andrae Muys
: : for George Silver's Paradoxes of defence, which is probably
: : in a similarr vein, but I have not got around to reading it yet.
Thanks for the sun tzu URL, but the paradoxes is giving me problems. My
browser keeps reporting 'host unknown'. If anyone knows anything about
it could they mail me please.
T.I.A.
Andrae Muys
: Robert A. Uhl (ru...@phoebe.cair.du.edu) wrote:
: : The function must first seek to find nearby units. The first
: : criteria for 'nearness' would simply be physical nearness. This would
: : choose, say 10 or 20 units. These would be sorted by strength, then by
: : friendly units in the rough direction of the enemy. The idea is that a
: : unit doesn't know where its allies are headed, but if they are near an
: : enemy, the odds are that it is a melee situation. After sorting these
: : the second time, the AI would choose the 'nearest' unit. In close
: : quarters, it would most likely choose the physically nearest one. But
: : from a distance, it would tend towards otehr criteria, such as unit
: : strength, friendlies in the area, &c.
: Okay. Earlier in the thread a mechanism for 'grouping' enemy and
: allied units was proposed that involved drawing circles based variously
: on movement capabilities and/or firepower.
The problem I see with this is the lack of cohesion. Units acting
independently will inevitably be defeated by a cordinated
attack/defence. The standard 'pick a unit and gang up on it' must surely
take into account such things as artillery support(there is ART in even
the basic rules I proposed), fire support from nearby units, location of
any reserves, location of any CAV(they can move fast) postion relitive to
front/bulk of friendly forces, possiblity of being outflanked IF
SUCCESFUL. There are of course numerous other factors to be considered
however the biggest problem is that any human player WILL KNOW WHAT
NEIGHBOURING UNITS WILL DO. Therefore if a handful of units decide to
attack and a handfull of units decide to retreat, go left, go right,
stand still etc, they will face the cordinated efforts of the human
player IN DISORDER. So they will be defeated.
: : The one problem is that such an AI might be too chaotic at first,
: : sending units out willy-nilly. These first units would be likely to go
: : one way, then the other. But soon, I believe that some order would
: : arise. Units would have a tendency to conglomerate in an area and
: : fight as one. This is just my own thought, though. It is quite
: : possible that it would be entirely too chotic.
: I wonder if some variant of this isn't what many games already do?
: Most of them do tend to exhibit a nasty tendency to trickle units unit
: a battle.
Assuming that a steady state will be reached. Won't
1. A signifigant advance/retreat on one side send it back into oscilation.
2. The s.s be reached after first contact.
3. Still lead to an uncordinated attack.
Andrae Muys
points. I sat down and drew a number of postions and tried to find which
points were critical to the result of the battle.(BTW I found this very
useful and you might find so as well) One thing I noticed as that most
of them fell into one of two catogrys. The first is indicitive of a bent
line. The hinge is a critical point, if either side breaks the hinge
then both sections of the enemys line become outflanked. You have
effectivly broken their centre even if the hinge is on the flank. It
would seem to me that (as I remember someone mentioning) this kind of
critical point is basically a point on a front with a high derivitive.
This makes sense to me. This leads nicely to the flank, the end of a
line having an infinite derivitive.
The second is basically where one side signifigantly outnumbers the other
at a localised point in the line.(after being modified for terrain/troop
type etc). IMO The critical nature of this point, even if contact hasn't
been made yet, should be obvious.
This leads to now two classes of points deserving of futher
consideration. Contact points(you after all don't want excessive
causualties) even if it isn't stratigically important, and Contact
points(which maybe one type of 'potential' contact points) which may
already be contact points(in which case extreme care must be taken) or
may be dis/advantagous should they become contact points.
Comments please.
Andrae.
P.S. as I am entering exam' time I will be unable to post as often as I
would like however I will keep myself uptodate with reading this thread.
Satrapa / Alexander Marc (ISE)
On 15 May 1995, Steve Woodcock wrote:
> Pass #3: Having identified natural groupings and focus points,
> run a pattern-matching algorithm to identify most likely tactical
> situations and reasonable responses. Randomly pick from the best
> 2 or 3 to avoid predicatability. For each turn a course of
> action is in place, make some evaluation of its effectiveness
> and/or success (i.e., has the pattern changed signficantly enough
> to warrant a new course of action? have we attained the objective
> in question? have we lost contact with the enemy?).
>
>
> In the case of a sparse strategic situation, the AI defaults towards
> trying to attain known and logical objectives (i.e., moving towards Paris).
> Once contact is made, the situation naturally becomes less sparse, and
> the AI begins to make moves based on sound engagement philosophies.
Perhaps there are also methods of matching to a number of patterns, with
a number of different suggested tactical responses, and combining those
responses, with weightings based on which pattern is the "closest match"?
Then the AI would have an almost infinite variety of responses, none the
same.
Even better, once the AI has selected a response and committed to it, can
it learn from the effects (make another entry in its "Book Of War"), so
it can remember "Hmm... sending that cavalry against 50 riflemen was A
Bad Thing(tm)... I'd better not do that again".
Heck, howabout doing what some chess games do, and also monitor/analyse
the opponent's responses ("Wow! How'd he do that? I'd better remember
that next time").
I ramble again...
-Alex
Satrapa / Alexander Marc (ISE)
On Wed, 17 May 1995, Will Uther wrote:
> In the type of combat I was thinking of, you each have only one active
> piece that moves around the board moving the other 'static' pieces. If
> Player A surrounds Player B, but Player B has supplies 'inside', then
[snip]
> P.S. as a side note, Sun Tzu (sp?) in his 'Art of War' recommends against
> sieges which is effectively the situation you have above.
Yes, I'm familiar with Bolo (I play it a lot, but being on the wrong end
of a SLIP line means it's hard for me to find a decent game).
I agree with you that the person doing the surrounding has to do a lot of
travel to fix damaged pills, but also consider that if B (on the
"inside") gets killed, it will have to travel through A's defences to get
back to its own base. Denying access to territory is almost as good as
owning it (that's what land mines are for).
-Alex
----
for usual .sig junk, finger daed...@blitzen.canberra.edu.au.
Robert A. Uhl
Andrae Muys <cca...@dingo.cc.uq.oz.au> wrote:
>
>The problem I see with this is the lack of cohesion. Units acting
>independently will inevitably be defeated by a cordinated
>attack/defence. The standard 'pick a unit and gang up on it' must surely
>take into account such things as artillery support(there is ART in even
>the basic rules I proposed), fire support from nearby units, location of
>any reserves, location of any CAV(they can move fast) postion relitive to
>front/bulk of friendly forces, possiblity of being outflanked IF
>SUCCESFUL. There are of course numerous other factors to be considered
>however the biggest problem is that any human player WILL KNOW WHAT
>NEIGHBOURING UNITS WILL DO. Therefore if a handful of units decide to
>attack and a handfull of units decide to retreat, go left, go right,
>stand still etc, they will face the cordinated efforts of the human
>player IN DISORDER. So they will be defeated.
But my whole idea is that order will arise from disorder. Think
about melee: men don't move as a whole; they move individually. And
order arises (ground is gained or lost). In a battle, the individual
units have certain objectives, but since it is unknown what the enemy
will be doing, they move based on what they know. And yet, somehow,
order arises. You can tell that I like non-linear dynamics:-)
Recall the basic idea: a unit will head for the 'nearest' unit. This
unit may be physically bearest (i.e. one ten feet from me as opposed
to the main force 100 yds. away), the weakest current one, the area
where most friendlies are &c. This simulates movement in real life.
With the addition of a set of objectives, this could work _very_ well.
Also, a 'unit' could be battalion, platoon, squad or man.
>: I wonder if some variant of this isn't what many games already do?
>: Most of them do tend to exhibit a nasty tendency to trickle units unit
>: a battle.
But I am assuming that all, or nearly all, units are in action at
the beginning. Not like the Strategic Conquest type of games. A
trickle is easy to beat, a flood is not...
>Assuming that a steady state will be reached, won't
>1. A signifigant advance/retreat on one side send it back into oscilation.
>2. The s.s be reached after first contact.
>3. Still lead to an uncordinated attack.
Since this is battle, there is no 'steady state,' except that which
is unit coordination. A significant attack will send the units back
into retreat mode, until each is in a position to fight back. Since
the calculations involve nearby friendlies, units will tend to
congregate and form fronts and stands. I would really like for someone
to figure out a way to implement this. I would but am currently far
too busy.
The ss would be reached _for a unit_ at first contact, but after the
contact is eliminated, it is once again ready to fight. Remember:
maximize contact over time, minimize contact at once.
The idea is that the coordination wil arise out of chaos. It may
not, and I have some doubts of my own, but I think that it would be
interesting to find out.
Will Uther
The way I see it, part of getting high level features out of the board
is that they don't change as rapidly as low level features. You can have
a 'strategy' piece of code (the general) that runs on a slower loop
(because it takes longer) and in parallel with it you run local 'Captains'
that handle local conditions, modified in some way by the last computed
global strategy.
In my Bolo 'bot we've hard-coded the local reactions to get them fast
enough. What we need is good strategy to make them useful.
Steve Woodcock
: On 15 May 1995, Steve Woodcock wrote:
: > Pass #3: Having identified natural groupings and focus points,
: > run a pattern-matching algorithm to identify most likely tactical
: > situations and reasonable responses. Randomly pick from the best
: > 2 or 3 to avoid predicatability. For each turn a course of
: > action is in place, make some evaluation of its effectiveness
: > and/or success (i.e., has the pattern changed signficantly enough
: > to warrant a new course of action? have we attained the objective
: > in question? have we lost contact with the enemy?).
: >
: >
: > In the case of a sparse strategic situation, the AI defaults towards
: > trying to attain known and logical objectives (i.e., moving towards Paris).
: > Once contact is made, the situation naturally becomes less sparse, and
: > the AI begins to make moves based on sound engagement philosophies.
: Perhaps there are also methods of matching to a number of patterns, with
: a number of different suggested tactical responses, and combining those
: responses, with weightings based on which pattern is the "closest match"?
I'll buy that. Again, for Napoleonic-era combat this is nearly ideal,
as officers of the time were often rigidly trained as to various tactical
and strategic situations and the 'proper' response.
Of course, Napoleon came along and wrote a whole new rulesbook,
which is why he kicked major butt.....
: Then the AI would have an almost infinite variety of responses, none the
: same.
: Even better, once the AI has selected a response and committed to it, can
: it learn from the effects (make another entry in its "Book Of War"), so
: it can remember "Hmm... sending that cavalry against 50 riflemen was A
: Bad Thing(tm)... I'd better not do that again".
Absolutely! A strategic level AI is *worthless*, IMNSHO, if it
can't learn either during the course of the game or perhaps in some
'learning session' after the game (if online learning proves to be too
much of a hit on gameplay). That's my biggest gripe against strategic
level AIs today; they are incapable of learning anything.
: Heck, howabout doing what some chess games do, and also monitor/analyse
: the opponent's responses ("Wow! How'd he do that? I'd better remember
: that next time").
Even better, as this makes the AI a better opponent against the one human
player who (mostly) is the main person to play solo against the computer.
Steven
==============================================================================
Steven Woodcock _
Senior Software Engineer, Gameware _____C .._.
Lockheed Martin Information Systems Group ____/ \___/
Phone: 407-826-6986 <____/\_---\_\ "Ferretman"
E-mail: wood...@gate.net (Home)
swoo...@oldcolo.com (Alternate Home)
wood...@escmail.orl.mmc.com (Work)
Steve Woodcock
: In article <3posed$d...@mirv.unsw.edu.au>, Andrew Edward White <andreww> wrote:
: > Does it make any difference to the AI if the game being played
: > is Real-Time as opposed to turn-based? In a real-time game, the
: > game state can change dynamically even as the analysis is being
: > performed. Is this significant, or is it simply a matter of
: > having a fast enough algorithm/processor that the dynamic
: > situation can be treated as static?
: >
: > (I am assuming that individual units can be given simple commands
: > (eg 'Shoot that' or 'Move there') that they can carry out without
: > continual strategic direction.)
: The way I see it, part of getting high level features out of the board
: is that they don't change as rapidly as low level features. You can have
: a 'strategy' piece of code (the general) that runs on a slower loop
: (because it takes longer) and in parallel with it you run local 'Captains'
: that handle local conditions, modified in some way by the last computed
: global strategy.
As I understand it, the AI in 'Beyond Squad Leader' will do something
very much like this. They've broken the AI into a Planner and an
Executor. The Planner's job determines the overall goal for, say, a
company of men ("capture this farmhouse"). Each platoon in the company
has an agent who then begins coming up with ways to achieve this goal
(platoon A elects to move along a ridgeline; platoon B elects to walk
down an orchard, etc.). The Planner resolves any problems or duplication
of efforts and then 'posts' the orders for each platoon.
The Executor then takes these orders and makes begins to attempt to
carry them out, based on several factors (did the unit GET the order, will
the unit obey the order, etc.) and begins moving units towards achieving
the objective. The Executor decides on individual engagement strategies,
firepower laydown, etc., for each platoon.
Of course, doing this in DOS or Windows is tough; there aren't any
multi-threading capabilities in either OS. Win-95 will offer some level
of multi-threading, though, and of course OS/2 and Unix *excel* at this.
I don't think it really makes any difference whether the game is run
turn-based or real-time, other than the *minor* advantage that the AI
can probably take a bit more time to make up its mind in a turn-based
game.
Steven
did
Doug Bonar
> I don't think it really makes any difference whether the game is run
> turn-based or real-time, other than the *minor* advantage that the AI
> can probably take a bit more time to make up its mind in a turn-based
> game.
>
>
> Steven
Hmmmm. I think it will make a big difference. I think that
on most (all?) present personal computers any really significant AI
code will take enough processing power that having it moving at the
same time as the human player will degrade the responce to the
player's actions. Of course, you could try to put a governer onto
the AI's moves, but in many cases simultanious play is issue to be
tackled after we can do reasonable alternating play. Even neglecting
any kind of interface problems, there is the added complexity of
having to figure out what order to move units and when to move units
(do I keep this one waiting to see what 'he'll' do or move it now)?
Doug
Robert A. Uhl
Steve Woodcock <wood...@escmail.orl.mmc.com> wrote:
>Will Uther (wi...@cs.su.oz.au) wrote:
>
>: The way I see it, part of getting high level features out of the board
>: is that they don't change as rapidly as low level features. You can have
>: a 'strategy' piece of code (the general) that runs on a slower loop
>: (because it takes longer) and in parallel with it you run local 'Captains'
>: that handle local conditions, modified in some way by the last computed
>: global strategy.
>
> As I understand it, the AI in 'Beyond Squad Leader' will do something
>very much like this. They've broken the AI into a Planner and an
>Executor. The Planner's job determines the overall goal for, say, a
>company of men ("capture this farmhouse"). Each platoon in the company
>has an agent who then begins coming up with ways to achieve this goal
>(platoon A elects to move along a ridgeline; platoon B elects to walk
>down an orchard, etc.). The Planner resolves any problems or duplication
>of efforts and then 'posts' the orders for each platoon.
Hmmm... Interesting idea. I would take my movement algorithm
suggested earlier and modify it to do something like this. The unit's
movement would always be towards an objective (that hill, the castle,
Paris &c.), _except_ when it had an enemy or ront near enough to
effect it. This would be quite reflective of real life. It would also
have the added advantage of not being as computationally intensive as
some already posted ideas, and of not trickling units in.
Perhaps the AI would 'correct' units which are too battle-hungry,
although I personally lean towards a queue, i.e. goto hill<-destroy
enemy unit guarding hill<-get to front<-destroy enemy in my way.
This queue idea would also help in the elimination of small,
insignificant enemies deep in friendly territory. While a unit is on
the way to the front, it will destroy any enemies which it sees. Very
useful behavior, _and_ the unit will get back on track, as opposed to
my earlier ideas, in whihc the unit might then head someplace else
because it has a higher value now. OTOH, such 'free companies' could
be useful, if there were a certian number of them wandering the field
and they were highly trained, in other words, crack fighters with no
true objective, just targets of opportunity.
> Of course, doing this in DOS or Windows is tough; there aren't any
>multi-threading capabilities in either OS. Win-95 will offer some level
>of multi-threading, though, and of course OS/2 and Unix *excel* at this.
The Mac would be very good for this also. The Thread Manager is for
the implementation of pre-emptive threads within an app. Very useful
in ths sort of situation.
> I don't think it really makes any difference whether the game is run
>turn-based or real-time, other than the *minor* advantage that the AI
>can probably take a bit more time to make up its mind in a turn-based
>game.
Well, if the game is sorta turn-based (each player moves one unit
each turn), it wouldn't be realistic, but it would be good for the
computer side of things. That is animplementation issue, though. I
would suggest an intelligent turn system, not one as in Strategic
Conquest.
Doug Walker
wood...@escmail.orl.mmc.com (Steve Woodcock) wrote:
> Absolutely! A strategic level AI is *worthless*, IMNSHO, if it
> can't learn either during the course of the game or perhaps in some
> 'learning session' after the game (if online learning proves to be too
> much of a hit on gameplay). That's my biggest gripe against strategic
> level AIs today; they are incapable of learning anything.
>
Well, I've thrashed this around alot. I would certainly LOVE for the W@W
SAI to keep a nice learning database to have at it's disposal, but again,
for a commercial game, it would require an awful lot of diskspace before
it could get enough data to expect a reasonable improvement (ie, not
enough payoff).
> : Heck, howabout doing what some chess games do, and also monitor/analyse
> : the opponent's responses ("Wow! How'd he do that? I'd better remember
> : that next time").
>
> Even better, as this makes the AI a better opponent against the one human
> player who (mostly) is the main person to play solo against the computer.
>
I think scale is a major factor in the feasibility of these techniques.
Chess is NOT your usual wargame. You have a limited number of fixed
strength, and fixed movement pieces. You move one piece at a time. THis
allows for slowly evolving patterns. However, in a wargame, pieces can
have variable strength, variable movement, irregular maps (like Risk).
You move all your units each turn. THis allows higly fluid patterns to
evolve and change drastically every turn. THat means the amount of info
that is required to analyse the situation after gameplay (or even during)
gets quite large, very fast.
For simple, chess-like, games however, these learning techniques are quite
valid, although I think still probably pretty slow to learn as long as the
human doesnt perform the exact sequence of moves in consequiteive games.
Ie, I think it would be pretty hard for an AI to detect that a player uses
a particular strategy every third game.
--
Doug Walker
Atomic Games
dwa...@atomic.com
Doug Walker
wood...@escmail.orl.mmc.com (Steve Woodcock) wrote:
> Will Uther (wi...@cs.su.oz.au) wrote:
> : In article <3posed$d...@mirv.unsw.edu.au>, Andrew Edward White
<andreww> wrote:
>
> : > Does it make any difference to the AI if the game being played
> : > is Real-Time as opposed to turn-based? In a real-time game, the
> : > game state can change dynamically even as the analysis is being
> : > performed. Is this significant, or is it simply a matter of
> : > having a fast enough algorithm/processor that the dynamic
> : > situation can be treated as static?
> : >
> : > (I am assuming that individual units can be given simple commands
> : > (eg 'Shoot that' or 'Move there') that they can carry out without
> : > continual strategic direction.)
>
> : The way I see it, part of getting high level features out of the board
> : is that they don't change as rapidly as low level features. You can have
> : a 'strategy' piece of code (the general) that runs on a slower loop
> : (because it takes longer) and in parallel with it you run local 'Captains'
> : that handle local conditions, modified in some way by the last computed
> : global strategy.
>
> As I understand it, the AI in 'Beyond Squad Leader' will do something
> very much like this.
Yup, if there is interest the Article that Gary Riley wrote for a game
magazine that covers the BSL AI architecture is available via anonymous
ftp from atomic.com in /pub/articles/bsl.ai
If there is interest I can repost it here (maybe even get Gary to answer
some questions).
Graham Healey
>
>I have been paying close attention to this thread and the Influence Mapping
>one and their are two observation I have made:
>
>1) First, the influence mapping algorithm proposed (not the priority queue but
>the previous one) seemed very effective but is computationally intensive. However, I expect it would not have to be computed on every game turn and that
>instead, modifications could be made to an already computed influence map to
>obtain a sufficiently good approximation. (eg. When your troops move, you increase your influence in one hex and decrease it in the other, but your influence in the area, ie. adjacent hexes, remains approximately unchanged.) Only when units are destroyed or after a number of game turns would you have to go through the big expense of applying the influence mapping algorithm to get an accurate map.
>
>2) The search for a fronts is extremelly important in planning your strategy but only looking for the front only gives you half the picture. Let me expand:
>
>When I play war games, my first priority is to defend at fronts so my troops are not overunned. Maintaining sufficient power fire to DEFEND at the front is my number one priority (excluding exceptions here and there). Forget about an offensive for the moment. That comes later.
>
>My second priority is finding, creating and assaulting "targets of opportunity". These are enemy units or objectives which are not well defended and usually isolated. Unfortunately, the influence mapping algorithm would show the hexes where these targets of opportunity are as under my control if they were surrounded by my troops. This enemy unit may be far from the front but is an unit that every one would attack immediately (excluding exceptions here and there.)
>
>My last objective, once the destruction of all targets of opportunities has been
>addressed, is to ATTACK on the fronts where I have superiority.
>
I think you are overdoing the targets of opportunity (TOP's). Going for
TOP's is a classic mistake easily illustrated in Chess but equally
important in real war and in war- and strategy games. While you are
going for targets of opportunity a good player would be persueing a
strategy and winning the war/game.
Just my two cents.
Graham
Marc Carrier
In article <3q44ru$5...@hasle.oslonett.no>, gra...@oslonett.no (Graham Healey) writes:
|> In article <3ptn8e$o...@bmtlh10.bnr.ca>, Marc Carrier <mcar...@bnr.ca> wrote:
|> >
(SNIP...)
|> >My second priority is finding, creating and assaulting "targets of opportunity". These are enemy units or objectives which are not well defended and usually isolated. Unfortunately, the influence mapping algorithm would show the hexes where these targets|> of opportunity are as under my control if they were surrounded by my troops. This enemy unit may be far from the front but is an unit that every one would attack immediately (excluding exceptions here and there.)
|> >
(SNIP...)
|>
|> I think you are overdoing the targets of opportunity (TOP's). Going for
|> TOP's is a classic mistake easily illustrated in Chess but equally
|> important in real war and in war- and strategy games. While you are
|> going for targets of opportunity a good player would be persueing a
|> strategy and winning the war/game.
|>
|> Just my two cents.
|>
|> Graham
|>
|>
I disagree!
First, I agree I might have over emphasised the "creating" targets of
opportunity part of my statement. But when one exist, taking adventage of it
should be considered prior to carrying on your move towards your objectives. A
single enemy unit behind your lines or out on the flanks can cause major damages
later on if not addressed. Example: In Clash Of Steel, I win the game on the
eastern front by sending single tanks around and behind enemy line to cut
supplies, then I destroy the unsupplied units. Whether I play the AXIS or the
ALLIES, the strategy usually works since the COS AI is not very good at
recongnizing that enemy units are about to cut his supply routes (In fact, the
COS AI is not very good period).
In chess, unless you can see that you can check-mate your opponent in a number
of moves, your rarely pass the opportunity to capture one of his pieces if you
will not lose anything. What you have to be careful about is that doing so is
not a trap by your opponent to open up your defenses and that you will not end
up in a less desirable state.
The point about my previous post was that their is a distinction between being
on the defensive and offensive on a front. And maximizing contact points over
time is something you usually do only if you are on the offensive. So far, many
good algorithms have been proposed to identify fronts. Now I am turning my
attention to identifying the state of the troops on that front
(Offensive/Defensive). Further more, if troops are on the defensive, can they
stand or must they fall back and regroup? If they are on the offensive, can they
attack now or should they wait to group and concentrate fire power instead of
trickling into combat?
Marc
Steve Woodcock
: In article <3pvupd$m...@theopolis.orl.mmc.com>,
: Well, I've thrashed this around alot. I would certainly LOVE for the W@W
: SAI to keep a nice learning database to have at it's disposal, but again,
: for a commercial game, it would require an awful lot of diskspace before
: it could get enough data to expect a reasonable improvement (ie, not
: enough payoff).
That's probably why it hasn't been done yet. Most AIs play decently
well, at least against somebody new to the game; it's only when you actually
get good at the game that the AI's flaws begin to become apparent. The
database issue vs. diskspace is a good one, and one I actually hadn't considered
in the rareified atmosphere of 'Net speculation.
: I think scale is a major factor in the feasibility of these techniques.
: Chess is NOT your usual wargame. You have a limited number of fixed
: strength, and fixed movement pieces. You move one piece at a time. THis
: allows for slowly evolving patterns. However, in a wargame, pieces can
: have variable strength, variable movement, irregular maps (like Risk).
: You move all your units each turn. THis allows higly fluid patterns to
: evolve and change drastically every turn. THat means the amount of info
: that is required to analyse the situation after gameplay (or even during)
: gets quite large, very fast.
Good point, although we've been trying to address that in other parts
of this thread. Some of the techniques suggested (such as using genetic
algorithsmf for a galactic conquest game--I can pick on that one, since
I suggested it) sound great but may not work simply due to the relatively
sparse number of turns in such a game.
I think the biggest problem isn't so much deciding what to do on
a turn-to-turn basis, but actually INTEGRATING things into some kind of
overall plan. Secondary to that is for the AI to be able to somehow recognize
what exactly the Human player is up to. A good example of why this is so
hard can be found in the Third Reich game, which allegedly was going to use
neural networks to drive the computer AI but which has in fact been delayed
for nearly two years due to problems with said AI.
Steve
Doug Walker
wood...@escmail.orl.mmc.com (Steve Woodcock) wrote:
> Doug Walker (dwa...@atomic.com) wrote:
> : In article <3pvupd$m...@theopolis.orl.mmc.com>,
>
> : Well, I've thrashed this around alot. I would certainly LOVE for the W@W
> : SAI to keep a nice learning database to have at it's disposal, but again,
> : for a commercial game, it would require an awful lot of diskspace before
> : it could get enough data to expect a reasonable improvement (ie, not
> : enough payoff).
>
>
> That's probably why it hasn't been done yet. Most AIs play decently
> well, at least against somebody new to the game; it's only when you actually
> get good at the game that the AI's flaws begin to become apparent. The
> database issue vs. diskspace is a good one, and one I actually hadn't
considered
> in the rareified atmosphere of 'Net speculation.
Yeah, but that's A Good Thing (tm). I used to write embedded
micro-controller code for a robotics project at NASA, so sometimes I am a
little too sensitive to the speed/memory type of trade offs. I like the
discussions on techniques that may be too CPU or RAM intensive to be sued
in a commercial game, because in a few years, they will be ok, and if it
is a good enough technique there are usually ways to optimize it's
implementation, even if that results in sub-optimal performance.
>
> : I think scale is a major factor in the feasibility of these techniques.
> : Chess is NOT your usual wargame. You have a limited number of fixed
> : strength, and fixed movement pieces. You move one piece at a time. THis
> : allows for slowly evolving patterns. However, in a wargame, pieces can
> : have variable strength, variable movement, irregular maps (like Risk).
> : You move all your units each turn. THis allows higly fluid patterns to
> : evolve and change drastically every turn. THat means the amount of info
> : that is required to analyse the situation after gameplay (or even during)
> : gets quite large, very fast.
>
> Good point, although we've been trying to address that in other parts
> of this thread. Some of the techniques suggested (such as using genetic
> algorithsmf for a galactic conquest game--I can pick on that one, since
> I suggested it) sound great but may not work simply due to the relatively
> sparse number of turns in such a game.
>
> I think the biggest problem isn't so much deciding what to do on
> a turn-to-turn basis, but actually INTEGRATING things into some kind of
> overall plan. Secondary to that is for the AI to be able to somehow recognize
> what exactly the Human player is up to.
Yes, the current W@W SAI only remembers it's "postures" for each side.
This may increase to actuall orders in the next revision. All teh AI can
do to determine what the player is up to is run itself with the situation
reversed, and the W@W AI does this at a Strategic Level, ie what
objectives will the player go for, what areas of the front line may be
attacked, etc. I can't do a N turn look ahead because too much depends on
what the TAI does with the individual units for this turn.
Steve Hodsdon
>
>
> I have been paying close attention to this thread and the Influence Mapping
> one and their are two observation I have made:
>
> 1) First, the influence mapping algorithm proposed (not the priority queue but
> the previous one) seemed very effective but is computationally intensive.
Well, it would depend on the size of the map. (This was one of my
original fears. But I was dealing with an 8 bit cpu @ 1mhz...)
I have never tested the algorithm on any large arrays. I'll have to do
that and time it on the little sx in the corner.
> My beef about all this is that the current discussion does not include and
> detect these targets of opportunity. I think what need to be done is to
> compute two influence maps:
[snip]
That's what I thought as I was reading your article. :) This way, the
AI can look for weakly controlled areas if it wants to.
Great ideas!
Satrapa / Alexander Marc (ISE)
> Even better, as this makes the AI a better opponent against the one human
> player who (mostly) is the main person to play solo against the computer.
Of course, the catch here is for players like me... I'll read the books
and be a know-all, but I won't even hold my own against a dumb
computer.
Howabout we start a new thread "Ignoring Strategic Dispositions"... on
how to make computers *intentionally* dumber so a simple human can come
up to speed without totally embarrassing themselves and being discouraged
from the game (witness Spaceward Ho! with its "Dumb" opponents).
-Alex
Marc Carrier
In article <3qmg26$p...@dingo.cc.uq.oz.au>, cca...@dingo.cc.uq.oz.au (Andrae Muys) writes:
|> One question of my own is how you might represent time on an influence
|> map? I have a feeling that if we could somehow represent the map w.r.t
|> as a 2D-vector field we might be able to quantify the effects of 'attacking
|> now' vs 'attacking in strength'. I seem to remember someone mentioning
|> that they were using Electo-Magnetic Field theory to aid in producing a
|> good graph. As an electrical engineering student I know some theory
|> regarding vector fields however representing them on a computer is
|> something I don't know anything about. I was thinking though if you
|> considered the level of control the angle of the vector, say PI/2=Completely
|> under my control, and -PI/2=Completely under their control, you would be
|> left with the magnitude of the vector to represent some parameter w.r.t.
|> time. So if the resulting vector was in the 1st or 2nd quadrent I would
|> have some sort of advantage w.r.t time at the location, and a
|> disadvantage in the 3rd/4th quadrants. The dig' below might help.
|>
|> |
|> |
|> Enemy Control | My Control
|> My time adv | My time adv
|> |
|> |
|> ==============================
|> |
|> |
|> My Control | Enemy Control
|> Enemy time adv| Enemy time adv
|> |
|> |
|>
|> Now of course you could swap them and represent the time variable by the
|> angle but I was thinking that if you represent the strenth by an angle
|> then you can have no poles(points going to infinity) in the final
|> function. This should help with array bounds or the like. Still I have
|> no idea how you might form the time function(the strenth function should
|> require only a little modification to apply and I will take a shot at it
|> after exams).
|>
|> Well what do you think?
|> and please no posts telling me how computationally intensive its going to
|> be, I all ready know.
|>
|> Andrae.
This was somewhat the idea I had w.r.t. using two influence maps since there is more than just the soil you control that determines your posture. However, i had not considered time as a second dimentioned but it makes a lot more of sense and the simple matrix you presented with its four quadrant can simply summarized the four behaviors I mentioned earlier:
1) retreat and regroup
2) stand and defend
3) stand and group / prepare for attack
4) attack now (attack who is another question though.)
On the subject of how to represent a 2D-vector field on the computer, use a rectangular coordinate
system such as with imaginary numbers in the form a + ib, instead of angles and magnitudes. You can store it as two different maps (array) or as an array of records/structures with two fields. I am sure one of these two will be better in terms of computational efficiency than the other because of the indexing involved but I do not know which one off the top of my head.
Now, how do we represent time? One method that came to mind would be to use the normal influence mapping algorithm proposed and compared the results after n iterations and 2*n iterations
where n < number of iterations required for value to stabilize and converge. Basically, compute the map with the influence of the units propagated n times which shows your more immediate influence and compare it to the map with the strengh propagated 2*n times (for example) which is your influence in the more distant future. (In not too sure this thinking is correct but I will do some simulation this weekend to try it out.)
An Example: After n iterations , the influence map could show that the ground where a friendly unit is located is under enemy control (ie. lots of enemy units close by) however, after 2*n iterations, the
influence value might turn positive, indicating that a lot more friendly units are close enough to reinforce the position. (I want to simulate this to see if this can happen with the influence mapping
algorithm.)
One problem I see with this is that the group of friendly units that could reinforce the position will have its influence spread all around and many friendly units in enemy territory may count on that reinforcement when the 2*n map is considered. Unfortunately this method does not help to make the decision of where the reinforcement should go and the units in enemy territory that do not get the
reinforcement will die if they stand.
Marc
Andrae Muys
: In article <3q44ru$5...@hasle.oslonett.no>, gra...@oslonett.no (Graham Healey) writes:
: |> In article <3ptn8e$o...@bmtlh10.bnr.ca>, Marc Carrier <mcar...@bnr.ca> wrote:
: |> >
: (SNIP...)
: |> >My second priority is finding, creating and assaulting "targets of opportunity". These are enemy units or objectives which are not well defended and usually isolated. Unfortunately, the influence mapping algorithm would show the hexes where these ta
rgets|> of opportunity are as under my control if they were surrounded by my troops. This enemy unit may be far from the front but is an unit that every one would attack immediately (excluding exceptions here and there.)
: |> >
: (SNIP...)
: |>
: |> I think you are overdoing the targets of opportunity (TOP's). Going for
<<<<SNIP>>>>
: I disagree!
:
: First, I agree I might have over emphasised the "creating" targets of
: opportunity part of my statement. But when one exist, taking adventage of it
: should be considered prior to carrying on your move towards your objectives. A
: single enemy unit behind your lines or out on the flanks can cause major damages
: later on if not addressed. Example: In Clash Of Steel, I win the game on the
: eastern front by sending single tanks around and behind enemy line to cut
: supplies, then I destroy the unsupplied units. Whether I play the AXIS or the
: ALLIES, the strategy usually works since the COS AI is not very good at
: recongnizing that enemy units are about to cut his supply routes (In fact, the
: COS AI is not very good period).
OK now its my turn to disagree. In my games I have found that when I
allow myself to be distracted from the overall picture to try and take
some trivial advantage(eg some poor soul stuck behind my lines without
supply and/or support) I lose. IMHO one of the main reasons behind this
thread is the realisation that taking time out from the pursuit of your
stratigic objectives to claim a tactical victory is poor play. One
mustn't forget that strength is only one of many factors which decide a
battle, in fact one of the less important IMO. Time, morale, position,
cohesion, leadership, etc are IMHO more important than mere manpower.
This is shown time and time again, from Alexander the Great, to Hannabal,
to William the Conquerer(an example of cohesion), Pitt, Frederik the
Great, Napoleon, et al, WWI, Vietmam, Korea, Hundread Years War as
examples of the effects of neglecting those other factors. (I can
explain my reasoning behind each of the examples but will do so only by
email for brevity). Oh and Israel and WWII German occupation of france
as an example of time. In each case victory was ensured against
signifigant numerical odds by the recognition of the relitive
inimportance of overall strength. It is this realisation which is
proving hard to teach a computer.
: In chess, unless you can see that you can check-mate your opponent in a number
: of moves, your rarely pass the opportunity to capture one of his pieces if you
: will not lose anything. What you have to be careful about is that doing so is
: not a trap by your opponent to open up your defenses and that you will not end
: up in a less desirable state.
I would here remind you of the gambit. And the sacrifice. I have won
many games of chess simply because I had a three or four move lead in my
development, bought with a couple of pawns, which I used wisely. I
personally consider this a good analogy to taking the time, and effort,
to pick off an insignifigant force left behind the lines.\
: The point about my previous post was that their is a distinction between being
: on the defensive and offensive on a front. And maximizing contact points over
: time is something you usually do only if you are on the offensive. So far, many
: good algorithms have been proposed to identify fronts. Now I am turning my
: attention to identifying the state of the troops on that front
: (Offensive/Defensive). Further more, if troops are on the defensive, can they
: stand or must they fall back and regroup? If they are on the offensive, can they
: attack now or should they wait to group and concentrate fire power instead of
: trickling into combat?
Good questions.
Andrae.
--
Andrae Muys
: This was somewhat the idea I had w.r.t. using two influence maps since
:posture. However, i had not considered time as a second dimentioned but
:it makes a lot more of sense and the simple matrix you presented with
:its four quadrant can simply summarized the four behaviors I mentioned
:earlier
: 1) retreat and regroup
: 2) stand and defend
: 3) stand and group / prepare for attack
: 4) attack now (attack who is another question though.)
: On the subject of how to represent a 2D-vector field on the computer,
:use a rectangular coordinate system such as with imaginary numbers in
:the form a + ib, instead of angles and magnitudes. You can store it as
:two different maps (array) or as an array of records/structures with two
:fields. I am sure one of these two will be better in terms of comput
:ational efficiency than the other because of the indexing involved but I
:do not know which one off the top of my head.
Well the idea came from my electrical background. I am used to treating
time based variables as phasors, with the magnitude representing
amplitude and the angle representing phase. I just drew an analogy
between amplitude and weighted strength(strength modified by other
factors), and phase and the time consideration(after all, if you are 'in
phase' with the tempo of the battle you will be ready to attack when the
time comes). However phasors can be represented both as |A|exp(jw) and a
+ jb. So how you represent one is determined by what you will use it
for(mag/angle for mult', cart' for addition). I do however like the
idea of representing the influence value as a single number(although
complex) with describes both now and the future.
: Now, how do we represent time? One method that came to mind would be
:to use the normal influence mapping algorithm proposed and compared the
:results after n iterations and 2*n iterations
: where n < number of iterations required for value to stabilize and
:converge. Basically, compute the map with the influence of the units
:propagated n times which shows your more immediate influence and compare
it to the map with the strengh propagated 2*
:n times (for example) which is your influence in the more distant
:future. (In not too sure this thinking is correct but I will do some
:simulation this weekend to try it out.)
I like it although why you chose 2*n seems a little arbitary. I
definately like the idea of using the rate of influence spreading over
time to calculate the time cordinate.
: An Example: After n iterations , the influence map could show that the
:ground where a friendly unit is located is under enemy control (ie. lots
:of enemy units close by) however, after 2*n iterations, the
: influence value might turn positive, indicating that a lot more
:friendly units are close enough to reinforce the position. (I want to
:simulate this to see if this can happen with the influence mapping
: algorithm.)
I believe we have already discussed the possiblility of a weak unit
having only a mitigating effect on the influence of a near by strong
enemy unit. Anyway it isn't so much the sign as the derivitive of the
influence which should determine the time co-ord' as if we worry to much
about the strength when calculating it we will probably be double
accounting. The sign is after all already part of the other strength
co-ord'.
: One problem I see with this is that the group of friendly units that
:could reinforce the position will have its influence spread all around
:and many friendly units in enemy territory may count on that
:reinforcement when the 2*n map is considered. Unfort
:unately this method does not help to make the decision of where the
:reinforcement should go and the units in enemy territory that do not get
:the reinforcement will die if they stand.
My original post to this group was based partly on a possible solution to
this problem. What I proposed was to break the army into a number of
sections which would evaluate their own capacities to attack/defend/etc
and report reinforcements required/avaliable, etc to a higher order
grouping which would then evealuate its capabilities and report to yet a
higher group until you reached the overall command who would decide what
each of the sections directly under his command would do (abstractly) and
then leave them to worry about the details before(assuming
multi-threading) continuing its evaluations before the next reports. These
groups were to
be reevaluated every few turns allowing for the dynamics of battle. It
was a failue to find some way of recognising these 'natural' groupings of
men that prompted my original post. I feel that influence mapping will
provide any groupings with the abiltity to evaluate their postions but I
still lack the mecanism to find these groups.
Great ideas Marc,