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]

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]

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.

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]

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

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

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

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]

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]

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