Archived

This topic is now archived and is closed to further replies.

Woody FX

Tactical AI for Wargame

Recommended Posts

Woody FX    169
Hi I’ve trawling the forums for info on how to create an AI to handle a small war game. I've been searching the forum for almost the last 2 hours. The Art of War, anything about real war based strategies, any reports on Strategies used in Iraq or why Black Hawk Down was not successful are very entertaining etc but are not getting me any closer to my goal of creating a lightweight AI for a war game. I'll explain exactly the problem I’m trying to solve. Hex based battle game. 2 armies face each other. (about 20 units each) 12*18 hex board. Infantry, Cavalry, Archers and up to 3 leader units. (Pre gunpowder) The game will last for 10 turns. There are rivers, bridges, hills, forests and camps. The platform I’m working for is very limited. No Floating-point calculations. 33mhz cpu. 256kb(yeah kb) of Heap space. (the total game needs to be just under 52KB) If you think you can help me or can tell me what would be required to implement this kind of AI. Something i saw mentioned lots was influence mapping. Thanks for your advice. Gratefully Brian Edit Just read http://www.gamedev.net/reference/articles/article1085.asp [edited by - Woody FX on January 16, 2004 8:24:35 PM]

Share this post


Link to post
Share on other sites
Kylotan    10008
Before any really practical answers can be given, we need to know your game mechanics. AI is essentially the art of making decisions, so we need to know what choices are available. For example, how do you move? How is combat resolved? How do you win the game? We also need to be able to judge the quality of any given choice, which in turn means you need to be able to guess any random factors.

Once you have all that sorted, I expect that some basic sort of search algorithm is what you want. One that comes to mind is minimax with alpha-beta cutoff although from what I can gather, there are numerous variations, of varying suitability to your requirements.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
Woody FX    169
Ok do you want all the rules??

Ok I’ll give a bit more detail.

Combat is resolved using luck and an attack number for each unit.
Only 1 unit can attack another unit at a time. Units cant be stacked.

A unit can Move, Attack, Retreat, be in a state of disarray or panic(its flees the field).

Each unit has values.

Movement from 1-4 (how many spaces per turn.
Attack strength 0-5*
Defence Strength 1-3*
* special ability against some units.
There are zones of control.
Each unit has a flank. (3 hexs opposite of the way the unit faces.
No extra units can join the field during a battle.

When a unit gets attacked its state becomes one of the below
Melee ( best)
Disorganised (normal)
or Destroyed (you have lost the unit)

So if another of the attackers attack the Disorganised unit then they have an extra advantage attacking an already disorganised unit so there is a higher chance the defending unit will become destroyed.

That’s the short of it!

I have studied some AI when i was in college, i could never see how it(what we were doing at the time) would be relevant to games, was all the searches minimax, alpha-beta. With the exception of A* and some home-made stuff I’ve never yet tried anything else. So I’m biting the bullet now and getting in a bit deeper.

Thanks Guys.

Share this post


Link to post
Share on other sites
Kylotan    10008
How many units move at once? If you just pick a unit to move each time, a very simple algorithm would be to look at each unit, work out what the highest scoring move would be for each one, then pick that. However that alone doesn''t give you any ''lookahead'', which is where something like minimax comes in. On the other hand, if you have simultaneous movement where each side gets to move all their units, then you''re gonna have so many possibilities that you may have to look at something a little less precise.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
Woody FX    169
Each player gets to move all units one by one each turn.

So the Computer can move all 20 units during its turn the passes control of the board over to the other player who can move all of his 20 or so units.

Kylotan you are jumping ahead of me here. That’s like telling me that my car will need some screws, nuts and bolts.

I''m not so concerned about searching through all options but representing the problem, how the computer will decide what to move. How it will decide to attack the infantry or Cavalry.
To get on to a hill and wait or retreat so it can focus its attack with other units during the AI''s next turn.

What I was looking for is too discuss with someone about making AI for a board game and the specifics of it.

Searching through the options is something I have yet to consider. I take it you love and know AI, i dont have your level of knowledge yet so dont assume anything.

Brian

Share this post


Link to post
Share on other sites
Predictor    198
You might try a fuzzy logic solution. I am thinking of a system which accepts some basic assessments of the current game situation, and outputs broad strategic indicators, like:

if LEFT_FLANK is CRUMBLING then ADVANCE_LEFT_RESERVES

The fuzzy part wouldn''t need to be terribly precise, so your hardware constraint shouldn''t matter.

-Predictor
http://will.dwinnell.com

Share this post


Link to post
Share on other sites
Woody FX    169
Hi Predictor,

Again you are jumping too far ahead.

How would you go about defining the flanks? let alone detect
that the flank is crumbling.

Has anybody got experience implementing something simliar to this on a simlpe level.

Thanks
Brian

Share this post


Link to post
Share on other sites
Krippy2k    134
Well, you can probably get away with something like this:

Create a list of individual scenarios, then for each scenario you add either a positive or negative weight for each potential, relevent action, etc. You also want to add a high negative weight for any impossible action, such as moving to a spot that is occupied. Then choose the action with the highest weight at the end of the processing.

So a simple example...

I'm not sure how I'd go about representing hexes in here so i'll use squares, you should get the idea.

|----|----|----|
| EA | EC | EA |
|----|----|----|
| -- | ME | FC |
|----|----|----|
| FA | FA | FA |
|----|----|----|


The unit we are calculating the move for is 'ME'. EA is enemy archer, EC is enemy cavalry, FA is friendly archer, FC is friendly cavalry, and -- is an open space

Now lets say our potential actions are something like this: attack up, attack left, attack right, attack down, Move up, left, right, down, etc.

Now lets say we have some weights set like this for the current unit, which is an infantry:

//scenario = enemy archer upper left box
enemy_archer_up_left -> move_up +1
enemy_archer_up_left -> move_left +1
enemy_archer_up_left -> move_right -1
enemy_archer_up_left -> move_down -1

//scenario = enemy cavalry upper box
enemy_cavalry_up -> attack_up -1

enemy_cavalry_up -> move_up -100
enemy_cavalry_up -> move_down +1

//scenario = enemy archer upper right box
enemy_archer_up_right -> attack_up +1
enemy_archer_up_right -> attack_right +1

enemy_archer_up_right -> move_up +1
enemy_archer_up_right -> move_left -1
enemy_archer_up_right -> move_right +1

// scenarion friendly archer down/left
friendly_archer_down_left -> attack_up +1
friendly_archer_down_left -> attack_left +2
friendly_archer_down_left -> attack_down +2

friendly_archer_down_left -> move_up +1
friendly_archer_down_left -> move_left +2
friendly_archer_down_left -> move_right -1

// scenarion friendly archer down
friendly_archer_down -> attack_up +1
friendly_archer_down -> attack_left +2
friendly_archer_down -> attack_right +2
friendly_archer_down -> attack_down -100

friendly_archer_down -> move_up +1
friendly_archer_down -> move_left -1
friendly_archer_down -> move_right -1
friendly_archer_down -> move_down -100

// scenario friendly archer down/right
friendly_archer_down_right -> attack_up +1
friendly_archer_down_right -> attack_right +2
friendly_archer_down_right -> attack_down +2

friendly_archer_down_right -> move_up +1
friendly_archer_down_right -> move_left -1
friendly_archer_down_right -> move_right +1
friendly_archer_down_right -> move_down -1


// scenario friendly cavalry right
friendly_cavalry_right -> attack_up +1
friendly_cavalry_right -> attack_left +1
friendly_cavalry_right -> attack_right -100
friendly_cavalry_right -> attack_down +1

friendly_cavalry_right -> move_up +1
friendly_cavalry_right -> move_left -1
friendly_cavalry_right -> move_right -100
friendly_cavalry_right -> move_down -1

//scenario empty spot left
empty_spot_left -> attack_left -100
empty_spot_left -> move_left +2

----

Now we have this:

Attack up:
+4

Attack left:
-95

Attack Right:
-95

Attack Down:
-96

Move up:
-94

Move Left:
+1

Move right:
-101

Move down:
-102

---

Our highest point total is +4, so we attack up. This is a really simplistic example, but it's the general idea.

You can add weights depending on the stats of the units, i.e.:
if enemy_up has attack strength > 3 -> move_down +1
if enemy up has attack strength <= 1 -> attack_up +1
if enemy up has special ability against infantry -> attack_up -1
if enemy up has special ability against infantry -> move_down +2

You can also build higher level scenarios:
if down_left is open_space and down_right is open_space and down is open_space then flank_not_covered

if flank_not_covered move_up -1
if flank_covered -> attack_up +3
if flank_covered -> move_up +2
if flank_covered -> move down -100
etc.

if enemy_up_disorganized and enemy_sides_not_covered then enemy_up_vulnerable +1

if enemy_up_melee then enemy_up_vulnerable -1

attack_up += enemy_up_vulnerable
move_down -= enemy_up_vulnerable

if most_enemy_units in upper_right_of_map then fan_out_towards_upper_right +5

if more than half of units moved back last round then enemy retreating


if enemy_retreating then full_assault +2

if enemy_advancing_4_hexes_away and my_flank_not_covered then wait_for_reinforcements +2

etc

It's a real simple example, but just build up units of logic with weights associated with them for each relevent action. You don't have a lot of units or a lot of potential spaces or actions, so you should be able to build up a pretty robust set with your memory requirements as long as you don't get too redundant.

Peace

[edited by - krippy2k on January 17, 2004 9:25:46 AM]

Share this post


Link to post
Share on other sites
Kylotan    10008
quote:
Original post by Woody FX
Kylotan you are jumping ahead of me here. That’s like telling me that my car will need some screws, nuts and bolts.

I''m not so concerned about searching through all options but representing the problem, how the computer will decide what to move. How it will decide to attack the infantry or Cavalry.
To get on to a hill and wait or retreat so it can focus its attack with other units during the AI''s next turn.

It''s not jumping ahead at all. The rules of your game are the most important thing here. If you have no rule that gives you a bonus for being on a hill then there''s no reason why the AI should ever want to do that.

I am certainly no AI expert. In fact, almost every time I post something, Timkin comes along and tells me I''m wrong. All I''m saying is that representing the problem is gonna come down to your rule set, and not any sort of idea we can give you. Proof of this: in chess, if you put a pawn 1 square diagonally across from a queen, and it''s the pawn''s move, then the queen is in danger and that is probably a good move for the pawn. In Civilisation, if you have a militia unit (the equivalent of a pawn in the early game) diagonally across from a Armor unit (somewhat queen-like) and it''s the militia player''s move, then the Armor unit isn''t really in any significant danger. The positions are identical but what is ''intelligent'' depends entirely here upon the rules used for resolving combat.

I think what you''re asking for is a much higher-level view of the problem, which is reasonable enough but is also perhaps not what computer AI is best at. Humans are great at mentally summarising high-level information and then acting upon it. Computers are better at exhaustively searching all the low-level options. Therefore getting a computer to beat a great general in combat is a far easier task than getting a computer to think like one. When I talk about searching through the options, I am referring to the low level process that computer AI often uses that will commonly result in the high-level behaviour that you seek.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
Woody FX    169
Kylotan you have posted a few times trying to help me and i appreciate that. But i was looking for a discusion on a lower level.

Once i have everything defined i will need to search and sort through it. Then my AI lecture will be smiling as i read back through minimax & alpha beta like he lectured.

i have been researching for a while now and influence mapping is one of the things i have to get to grips with.

Thanks,
Brian

Share this post


Link to post
Share on other sites
Woody FX    169
Maybe your right Kylotan but I think I will be using it as I have not come across anything else that I can see solving my problems.

Will post back during the week once I get a start into it.

But I still think it will de the most difficult part of the game to get right. As I feel AI makes a game.

I''m confident I’ll get it, but I know I’ll be back here looking for peoples opinions again

Thanks

Share this post


Link to post
Share on other sites
Timkin    864
Just a couple of thoughts that may or may not help in your decision process. These are the sorts of high level things you need to determine before you design your AI, because they typically determine the AI tools/techniques used.

1) Do you want individual units to move and make decisions by themselves, move and act in concert with their surrounding characters/unit, or accept orders from the Commanding Officer of the army?

2) If you want to go with the CO approach (which is most likely), do you want a heirarchical approach to orders? I.e., the Army-CO says 'Archers attack the left flank' and the Archer-CO determines how to do this?

3) Alternatively, do you want an Army-CO that micromanages every decision on the battlefield (down to which units/troops move to which positions, which units/troops retreat, etc)?


On an agent level, you'll want to at least implement a state machine for each indivual troop so that you can manage their actions and state changes. Your AI is really just the mechanism by which you choose an action to achieve a desired state change for each unit.

Other thoughts:

Because their is an opposition player, a game tree approach suggests itself for evaluating moves. HOWEVER, I'd actually suggest that you don't do this, simply because of the computational resources required to expand a single layer of the tree: each side has 20 units and each unit has at least 3 actions (Move, Attack & Retreat). Thats a large set of combinations to consider. To get an estimate of the search space, multiply the number of units by the number of actions and raise the result to nth power, where n is the depth of the search you want to consider. Thats the size of the state space at depth n, given the current state.

Personally, I would use a combination of Influence Mapping (for analysis of the important tactical areas of the battleground) along with Utility Theory for an assessment of the value of action outcomes. The basic premise is to determine the tactically sensitive areas on the map and move appropriate forces in to maintain dominance in those areas, or an ability to interdict into those areas when needed.

There is, of course, another level at which to understand this problem, which Kylotan was discussing... and that is the relationships between units. The rules of the game and the functionality of units will generally dictate the sorts of relationships that can be formed. For example, Archers might be able to shoot at targets up to 3 hexes away. Therefore, Archers can attack a hex that a melee attacker may also be attacking. We might designate this as 'support fire', or 'supression'. Thus, we might write a functional notation representation of this relationship: suppress(archer_unit_1,enemy_pikeman_unit_7). Or, in terms of the relationship between friendly units, we might write supporting(archer_unit_1,swordman_unit_13). Thus, if we had a system for deriving actions for the battle, this might be one of the outputs of this system. The sorts of relationships that can be formed will dictate the gameplay and hence dictate the sort of AI that you need to play the game on behalf of the computer (which is what Kylotan was trying to get at, I believe). You need to write all of these things down. You need to decide exactly how units could work together within the scope of the game rules and then you should sit down and run through a battle (or ten) on paper. Write down all of the things that you think are relevant to the analysis of the battle scene. Write down all of the things that you think are relevant to the decision process of a player of this game. Once you have this information, then and only then are you in a position to choose the right AI representation and tool for this problem.

I hope this information has helped. I'm more than happy to discuss any aspect of this thread with you further, so don't hesitate to ask more questions or pass on more information!

Cheers,

Timkin

[edited by - Timkin on January 18, 2004 11:38:31 PM]

Share this post


Link to post
Share on other sites
Squirell    196
quote:
Original post by Predictor
You might try a fuzzy logic solution. I am thinking of a system which accepts some basic assessments of the current game situation, and outputs broad strategic indicators, like:

if LEFT_FLANK is CRUMBLING then ADVANCE_LEFT_RESERVES

The fuzzy part wouldn''t need to be terribly precise, so your hardware constraint shouldn''t matter.

-Predictor
http://will.dwinnell.com




I think thats a good idea, if you defined lets say 5 units as the left flank when they were deployed, and 3 as the reserves, then when lets say 3 units from the left flank are destroyed, you move up the 3 reserves. I have no expierence in AI but it that would make it pretty easy i think.

Share this post


Link to post
Share on other sites
Predictor    198
quote:
Predictor wrote:
You might try a fuzzy logic solution. I am thinking of a system which accepts some basic assessments of the current game situation, and outputs broad strategic indicators, like:

if LEFT_FLANK is CRUMBLING then ADVANCE_LEFT_RESERVES

The fuzzy part wouldn''t need to be terribly precise, so your hardware constraint shouldn''t matter.



quote:
Squirell responded:
I think thats a good idea, if you defined lets say 5 units as the left flank when they were deployed, and 3 as the reserves, then when lets say 3 units from the left flank are destroyed, you move up the 3 reserves. I have no expierence in AI but it that would make it pretty easy i think.



Given the hardware limitations, I thought a straightforward fuzzy logic rule base was a realistic and flexible option. Let''s review: "No Floating-point calculations. 33mhz cpu. 256kb(yeah kb) of Heap space. (the total game needs to be just under 52KB".


-Predictor
http://will.dwinnell.com




Share this post


Link to post
Share on other sites
Woody FX    169
On the Game Boy Advance there is a very highly regarded strategy game Called Advanced Wars.

I have never played it but it is supposed to be fantastic.

Does anybody know how the AI is done for that??

Though i think it is probably a whole lot more powerful than the platform i going for.

Thanks for all your input

Share this post


Link to post
Share on other sites
VVoltz    122
Hey Woody FX, I''m on the same trouble here, I''m doing almost an exact game; and this one is my last practice before I leave college (soot, my english is kinda poor here). I''m using squares in a 2d scenario, my battles are sopposed to be historical of the Independence war of my country (Bolivia), so I''m using only 3 types of units: Infantry (with rifles and knifes), Cavalry (with swords) and Cannons.

I already made the UML diagram of the final product, now I have to actually program the thing (only one battle, the most important one). I haven''t decided the tool for doung it and since my PC isn''t the state of the art right now (Celeron 500, 196 RAM) I''m probably using only VB and MatLab.

I plan to use a vectorial matrix (vectors within a matrix) for the scenario and my troops won''t have any ''panic'' meter.

I''m sorry if this whole reply text is useless right now, but I just wanna make you know. I''m doing some research right now, and be sure I will be posting some reply here but later on.

Anyway, why don''t we get in contact for future references?, you can write me to:

walt20977@yahoo.com

Share this post


Link to post
Share on other sites
RPGeezus    216
Hi Woody,

I don''t think anyone can give you 1 right answer to your question. Here is an idea though:

Consider your problem as such: Given n units, each with an offsenive and defensive score, what can you do within one turn to maximze these scores?

Different units must have different attack / defensive abilites against other units. Therefore their proximity to these units would be one influence. ie) knigths -vs- archers would be bad for knights, good for archers.

Topographical Position is another influence of this score. Being atop a hill would give you an advantage (depending on how you wrote your game).

So what you have to do is figure out how to position each piece so that you can maximize the total attack and or defence.

One way to do this would be to statically precompute a score for each type of unit at each point along your terrain. Then modify this map based on the positions of friendly and enemy units.. Consult with this to figure out where to make each move, for each piece. You would then modify this map by adjusting for the proximity of any adjacent units.

To make your AI more aggressive / passive, you would probably want to modify how important defence and offence are to your evaluation.

So this will give you a way to make short term decisions. To make long range strategic decisions you can do all kinds of things-- if it were me, I would sit down and figure out a few different strategies that you think will work, and have your program pick one of these randomly (or not).

It''s not exactly a perfect solution, but hopefully it will give you an idea or two. I can think of a number of ways to improve this.

Best regards,
Will

Share this post


Link to post
Share on other sites
Woody FX    169
Hey Will,

Yeah i''ve plan has begun to form in my mind about how to handle this!

I will maybe get units to work together and work out how to maximise the score for all units on each turn.

Working out the odds on each unit probably winning there battles and been safe in the next turn and try and keep a well positioned cover unit (or 2) at the end of each series of turns by the AI to join in the Attack on any of the player units that didnt perish during the earlier attacks of it will be kind of like chess ( except you can move all your pieces on each turn.

So maybe influcne mapping may not be needed.. though i would like to give it a try.

I mailed you about a certain Alliance a few days ago. Did you get a chance to take a look?

Share this post


Link to post
Share on other sites
miles vignol    122
what happens at the end of 10 turns? or are you just saying how long a typical combat might take?

how long do you figure a player might take to move his units? this sorta affects how long they might be willing to wait for the computer to make its move.

is retreating different than moving away from enemies?

are moves resolved at the same time or on alternating turns? that is does the computer get to move all of its units and have the results happen before the player gets to move? if the actual moves happened simultaneously, then you could possibly have the AI working while the player was formulating his moves.

for example, if they each have 10 units, the player issues his orders and hits "go". meanwhile, the computer is figuring out its orders. the orders are then resolved simultaneously. you''d have to sort out what happens when a unit attacks a unit that is no longer where it was or two units attempt to enter the same hex. it would be easy enough to consider attacking implied by movement -- that is, if you move into an area occupied by an enemy, you attack it.


simply scoring the current state of the game and iterating thu all possible state changes is one way to go, but given the number of units and the range of motion of each, it might be pretty painful. a unit that can travel 4 hexes would have 61 possible positions to check. throw in attack range and you''ve got another large number of possible moves (dunno if you have attack range). but let''s say there is no attack range. that means that you''d have a potential of say on average 20 possible moves for each unit (blocked terrain, occupied hexes, less mobile units). so figure you''d need to score 400 game states (20 potential moves * 20 units) to pick the best move. but that''s with no real looking ahead. you''d need to score 400^2 game states to pick the best move based on a predicted player move (how you predict the player move is a nice way to tune your game''s AI, but however it happens, it''ll likely be based on the same number of potential game states). 400^3 state scores would let the computer start to form overall strategies (two move combos) and 400^4 would give the computer the ability to react to the player doing the same. but of course, then you''re up to like 25 billion test moves.

i have absolutely no clue how fast your system is. a simple way to guage things would be to come up with a simple scoring system and see how many random moves you can score in however long you figure the computer should think about things. that would answer the question of whether the exhaustive method would work out for you. or perhaps, just how exhaustive you can be.

you could conceivably reduce the number of potential moves each unit makes by adding a random factor to the move tester. perhaps the AI limits the number of potential moves based on how much action is going on in a perticular area -- if there''s heavy fighting, those units are given more breadth to search for a good move. if there''s not much going on for a particular unit, then the number of potential moves is reduced and perhaps selected from the full set of potential moves at random.

just some thoughts...

Share this post


Link to post
Share on other sites
Squirell    196
quote:
Original post by Woody FX

The platform I’m working for is very limited.

No Floating-point calculations.
33mhz cpu.
256kb(yeah kb) of Heap space. (the total game needs to be just under 52KB)

[edited by - Woody FX on January 16, 2004 8:24:35 PM]


That means your ideas wont work because of the system requirments he has. And besides i think his game is the player moves, then the computer. NOT together

Share this post


Link to post
Share on other sites