Skip to Content

Writing AI, is very very hard :(

9 replies [Last post]
X3M
X3M's picture
Offline
Joined: 10/28/2013

Well, this also involves the divison by 0 thread. Or actually, the decision there lead to this.

Sure I am going to test the 3 different dice this afternoon. (Finally some time)

But that is just 1 type vs 1 type.

The AI is very simple in that simulation.
Highest health takes the fire.

That's right, the rule is: The defender decides who takes the fire. As long as there is sufficient cover for the other units to hide.

Since taking into account how much cover is needed. I have temporarily discarded this.

1v1 is very easy now.

But what if I have more then 1 type in my army?
Now the problems start. I did work on a concept. But somehow it isn't what I am looking for, because sometimes it didn't work properly.

***

If I have more then 1 type of units in my army. Certain stats have influence on player behavior. And so should the AI behave.

For example, other units always hide behind walls. Until enough walls are broken down.

I am sure that every one agrees; that walls always take fire first. Simply to do the facts that they are cheap and can't supply the army with fire power.

***

The 4 statistics that count are:
- costs; cheaper units takes hits first. But if they are of use, we try to keep them alive when they are damaged.
- health; more health takes hits first. Obviously, this changes during the game. And has to be calculated every time.
- armor; depending on this number, some units have better durability. The health number will be totally different when facing different opponents.
- damage; a combination of a number of shots, multiplied by a weapon type.

2 calculated statistics that I am sure of that matters:
- The total damage that the entire army can do. Against each armor type that matters at the moment.
- The individual damage that each unit can do. Against each armor type that matters at the moment. Especially now, the "that matters" part matters. Since during a game, a certain type might die completely. And that total damage is gone. It could mean that when certain opponents die, the damage becomes low enough, that this unit will now better serve as meat.

An extreme example would be an anti air unit. When all air dies. This unit is just fodder.
Maybe to expensive to be using as meat at first, but still just meat now.

1 extra logical rule that I discovered after my first attempts:
"Meatier" units might have higher chances of dying than other more expensive units or units that supply with more damage.
In that case, the other units take fire first.

***

The goal of the AI is: to survive as long as possible and keep the total damages intact as long as possible.

How would you handle this?

andymakespasta
Offline
Joined: 07/26/2015
If you can write a program

If you can write a program for it, then probably some sort of Greedy algorithm, where the goal is to minimize decrease of damage output each turn.

A close heuristic algorithm is simply damage divided by (HP+armor), lower units get killed earlier. Walls have 0 value, so are killed first. (HP+armor) should be adjusted depending on your rules, to be (HP*armor, HP + 1.5*armor, HP + 2*armor^0.5, etc.)

A better but more complicated algorithm is to have whoever take damage if they are sure of surviving. (ie, meat shields) In the case of "every unit can possibly die from the next attack", calculate the chance of a unit dying multiplied by its attack. Lowest value takes the hit.

gilamonster
Offline
Joined: 08/21/2015
Are you familiar with the

Are you familiar with the Lanchester Square laws and the Salvo combat model? If not, have a look at them (both are on wikipedia; the latter is probably slightly more applicable for a turn-based game because it is based on discrete salvoes). These should provide you a method to predict rates of attrition for military forces using ranged attacks, from which you could try to choose a generic strategy which will yield maximum duration of survival for the AI. Your situation does complicate the model somewhat because different units have different strengths and vulnerabilities, but it shouldn't be to difficult to factor this into the base model, although it will pose a challenge in choosing a truely effective generic AI strategy. Personally, I'd advice switching from Excel (which I think you mentioned that you've been using) to a scripting language like python or ruby for prototyping an AI, as this allows much better and less clumsy flow control (but that's just my opinion).

I once programmed a real-time strategy game with resource-gathering and a simple AI as a hobby project. I was surprised how effective even a crude AI using simple heuristics could be.If I wasn't careful and the map wasn't too complex it could sometimes beat me. The techniques which I usd are probably not relevant to you,(I can look up what I did if you're interested) but the point is that many people start off by trying to apply very crude tactics which they sometimes self-sabotage due to laziness or overconfidence, or panic, so even a crude AI which is not susceptible to these can be superior (at least until the human player learns and starts properly using the leetle grey cells). So an AI doesn't have to be highly sophisticated to pose a reasonable challenge to human players.

One final point: you mentioned AA defences as being useless once the opposing aircraft are gone. Actually, in real life, they were often very useful against ground units too (like the '88s the germans used to kill allied tanks in WWII, or the soviet 23mm AA cannons that were used on american infantry in Vietnam). Even modern SAMS are often adapted for use against small surface warships. Perhaps you could allow AA to be used against effectively land units with a lot of damage but with an accuracy penalty, if your game mechanics allow that.

Edit: Hmmm - I think Andymakespasta's advice is more to-the-point than my long ramble - go with what he said.

X3M
X3M's picture
Offline
Joined: 10/28/2013
All info is welcome

You both have supplied me with new thinking ways. Allow me to reply to each.

andymakespasta wrote:
If you can write a program for it, then probably some sort of Greedy algorithm, where the goal is to minimize decrease of damage output each turn.

A close heuristic algorithm is simply damage divided by (HP+armor), lower units get killed earlier. Walls have 0 value, so are killed first. (HP+armor) should be adjusted depending on your rules, to be (HP*armor, HP + 1.5*armor, HP + 2*armor^0.5, etc.)

Hah!
I was somewhere with durability divided by damage. Turning the way around is indeed more correct. So obvious. Thanks.

How I apply H and A is a bit weird in my game. But bottom line would mean that for each unit needs to be checked what kind of A is working.
In that regard, the factor I use for durability has a part H/A intergrated. Where it is called H/D by that time. D can be lower then A, but never higher. That is the funny math trick that I use to get RPS working with just numbers.

andymakespasta wrote:

A better but more complicated algorithm is to have whoever take damage if they are sure of surviving. (ie, meat shields) In the case of "every unit can possibly die from the next attack", calculate the chance of a unit dying multiplied by its attack. Lowest value takes the hit.

This makes sense too. I was already pondering about this one. It requires a sub simulation in how much damage is done. However, that is a no problem issue once it is applied.

Excellent suggestions.

***

gilamonster wrote:
Are you familiar with the Lanchester Square laws and the Salvo combat model? If not, have a look at them (both are on wikipedia; the latter is probably slightly more applicable for a turn-based game because it is based on discrete salvoes). These should provide you a method to predict rates of attrition for military forces using ranged attacks, from which you could try to choose a generic strategy which will yield maximum duration of survival for the AI. Your situation does complicate the model somewhat because different units have different strengths and vulnerabilities, but it shouldn't be to difficult to factor this into the base model, although it will pose a challenge in choosing a truely effective generic AI strategy. Personally, I'd advice switching from Excel (which I think you mentioned that you've been using) to a scripting language like python or ruby for prototyping an AI, as this allows much better and less clumsy flow control (but that's just my opinion).

I'll look into it. However, range is not an issue in the simulation right now. I might add it later on. But then it is simply doing damage until both parties are able to fight.
Excel is only used for calculations. The next step would be simulation, where randomness and a number of replays are added. In that case, I sure can't finish with Excel.

gilamonster wrote:

I once programmed a real-time strategy game with resource-gathering and a simple AI as a hobby project. I was surprised how effective even a crude AI using simple heuristics could be.If I wasn't careful and the map wasn't too complex it could sometimes beat me. The techniques which I usd are probably not relevant to you,(I can look up what I did if you're interested) but the point is that many people start off by trying to apply very crude tactics which they sometimes self-sabotage due to laziness or overconfidence, or panic, so even a crude AI which is not susceptible to these can be superior (at least until the human player learns and starts properly using the leetle grey cells). So an AI doesn't have to be highly sophisticated to pose a reasonable challenge to human players.

That is so cool that you made a RTS. Do you have something left for me to see? Because I am interested. Originally, the A=D mechanic that I thought of was meant for a RTS.

Well, I got some experience in programming AI with triggers for my UMS in Starcraft. I too got beaten when I was a bit to slow. In that case. A job well done. Unless you tried your very hard and lost miserably.
I asume you forced the AI to scout first?
Did you steer the production of the AI with what he had scouted? I did, the scout discovered for example my tanks. And he started production of anti tank material to a certain point. And sended this to attack where it scouted.
I could abuse this of course. (placing the right units, right there where the AI scouted) But others where astonished in the smartness of the AI.

gilamonster wrote:

One final point: you mentioned AA defences as being useless once the opposing aircraft are gone. Actually, in real life, they were often very useful against ground units too (like the '88s the germans used to kill allied tanks in WWII, or the soviet 23mm AA cannons that were used on american infantry in Vietnam). Even modern SAMS are often adapted for use against small surface warships. Perhaps you could allow AA to be used against effectively land units with a lot of damage but with an accuracy penalty, if your game mechanics allow that.

Edit: Hmmm - I think Andymakespasta's advice is more to-the-point than my long ramble - go with what he said.


Yeah, in the video gaming world. AA means Anti Air only. I discovered that board gamers actually know that AA has secondary effects against ground. Which is logical.
A tank with a simple could also shoot an aircraft if it is low enough to the ground.

My game allows weapons to hit both air and ground. And I have 2 types of these. Those which can shoot both air and ground at the same time. And those who have to choose what to shoot in 1 action. The latter has a +33% penalty cost. The first one has 100% penalty cost.

X3M
X3M's picture
Offline
Joined: 10/28/2013
Ok people. I finally got a

Ok people. I finally got a first simulation running with 1 vs 1 type. Instead of 10 plays. I now got 10000 plays. The results look weird, but promising.
As expected, having 11 or 12 units in the game makes a huge difference. But it also seems that vy that point the randomness falls away in the background. And the winner of a possible battle is almost 100 percent certain.

The simulation will be updated soon. Which then will provide me with an average left over of both armies.

gilamonster
Offline
Joined: 08/21/2015
Its great that you've got a

Its great that you've got a simulation running. If you're doing a large number of simulations (like the 10000 you mentioned) it makes sense that most of the results would be in favour of the stronger force - that means things are working correctly and the odds are showing because you have a statistically significant sample-size (unless there is no variation at all, in which case you should check for an error in your code).

Regarding the Salvo combat model and Lanchester's laws; I didn't explain well; these models just assume that every combatant can attack every enemy combatant (i.e not only those in very close proximity - hence ranged attacks as opposed to melee/hand-to-hand). I think you've got beyond the point where they'll be useful, though, except maybe for interest's sake.

I can send you the code for my game if you can PM me your email or something similar. I wanted to release it under GPL, but I never finished it, although it is playable as is. (and my code is embarrassingly badly structured) This version doesn't even have simple scouting (strange - I really thought I added this), but I know I never tried to get the AI to modify the force it was building based on reconnaissance info (what you did sounds quite impressive!) In general, though, more advanced units were progressively stronger rather than following a rock-paper-scissors model, so it wasn't all that important.

Your handling of AA sounds fine - I've actually played a a few turn-based computer strategy games that do something similar (although most don't allow both air and ground attacks simultaneously - that's a nice touch).

gilamonster
Offline
Joined: 08/21/2015
Its great that you've got a

Its great that you've got a simulation running. If you're doing a large number of simulations (like the 10000 you mentioned) it makes sense that most of the results would be in favour of the stronger force - that means things are working correctly and the odds are showing because you have a statistically significant sample-size (unless there is no variation at all, in which case you should check for an error in your code).

Regarding the Salvo combat model and Lanchester's laws; I didn't explain well; these models just assume that every combatant can attack every enemy combatant (i.e not only those in very close proximity - hence ranged attacks as opposed to melee/hand-to-hand). I think you've got beyond the point where they'll be useful, though, except maybe for interest's sake.

I can send you the code for my game if you can PM me your email or something similar. I wanted to release it under GPL, but I never finished it, although it is playable as is. (and my code is embarrassingly badly structured) This version doesn't even have simple scouting (strange - I really thought I added this), but I know I never tried to get the AI to modify the force it was building based on reconnaissance info (what you did sounds quite impressive!) In general, though, more advanced units were progressively stronger rather than following a rock-paper-scissors model, so it wasn't all that important.

Your handling of AA sounds fine - I've actually played a few turn-based computer strategy games that seem to do something similar (although most don't allow both air and ground attacks simultaneously - that's a nice touch).

X3M
X3M's picture
Offline
Joined: 10/28/2013
I have learned a lot by using simulations

1)))

Yeah, I got it running. But the answers are A/B/Remise.

It is very rare to see a balanced battle where A and B are roughly the same.

It doesn't tell me what remains of the winning army. Which gives information about how well the next fight might go.
We are going to update this, this evening. And it will give me better info too.

I need that info for several reasons:
- In RTS, while you loose, you already take action to the the right unit for the job. Your resources are your reserves and might become any thing. So a losing battle still provides "balance" by skilled players.
- It helps to know how much the enemy has remaining of his/her forces. You can spend just enough resources for this. Again, balance by skill.

Another update that is needed and still possible:
While the highest health is placed in front. There is a limit in how much protection there might be. Eventually, you can attack those units that take cover.
Range is an important factor in this.

This too might be updated this evening.

***

2)))

As said before.
It is still a 1 type versus 1 type fight. Meaning that the normal armies that contain about 2 to 3 types cannot be calculated. Just rifle infantry versus tanks doesn't mean any thing in this game. An army might contain rifle infantry as "meat shield". While just 1 grenadier as support might win you the day! Those fights are awesome to play. But still super hard to program.

I need an entire new chapter to the simulation. And until now, it seems impossible.

***

3)))

Regarding the Salvo combat model and Lanchester's laws.
I have read the wiki pages.

The following is some info that I would like to share.

Frankly, these are simple models to the ones that I know.
Game models are entirely different and more complicated. Where unit durability, weapon types and speed might be factors as well.

The models that you mention are based on real life situations. And there we have a simple, kill or be killed. Not a "we can get shot 20 times before we die".

Games are different:
I always knew of sniping units means that a big fast dying army has only 50% damage effect in the long run. While just 1 unit does 100% damage. And while dying, remains doing 100% damage (most games).

In fact for the dying units:
Td = 0,5*(N*N+N)*D
And for the big unit:
Td = H*D

Where N=1 units has effect Total Damage = 1. But 2 units have effect 3. etc. etc.
A big unit often is worth 2 units, and has damage and health set at "2" times more. You get 4.
Divide 3 by 4 and you have 75%.

We know from this that the unit that is twice as big, will have 25% remaining in health.

But my game has low health and more units. And this is shown to me now in an obvious way. If I add health (literally hit points) of the units that shoot to the formula. You get different numbers.

So lets assume that any unit might take cover after being reduced to the last health. During a fight, they still continue to shoot. The 2 formulas can be combined into one simple formula. Where constants have no need either.

Td = H*D*(N*N+N)

Calculating for both armies doesn't give the real battle results. But still does give a rough indication who will win. And only N=X against N=1 with X health gives a certain outcome.
Randomness and time effects are not taken in account.

If we compare 10 units with 1 health and 1 damage to 1 unit with 10 health and 10 damage. We get the following:

Td = 1*1*(10*10+10) = 110

Td = 10*10*(1*1+1) = 200

Simply said, the small units only have 55% effect.

It is an all know fact in the RTS community that this calculation shows: How hard it is to balance a game.
If you ever work on a game. You need to add (half assed) mechanics to work against this fact:

- More health for all (weak and strong), IF you allow units to take cover in any form.
- Units need to be able to take cover (increasing health and shifting to the left in the formula). This can be done by adding:
--- walls or structures that block the enemy (Warcraft 2)
--- obvious meat and support roles (Warcraft 2)
--- entering another unit and shoot out from that unit. (C&C3; the GDI APC)
- Every unit has a weak spot in the form of being sniped. Yes, every unit!!! Not just 1 type. Most might think of the sniper using 1 bullet at infantry. But remember, no need to have it done with just 1 shot. A super fast firing weapon is also of use. As long as the enemy is only able to return fire just "once". Warzone 2100 has bunker busters (anti bunkers), assault guns (anti cyborg, weak armor), Tank killers (... anti heavy armor) etc.
- Pick your weakest unit and recalculate the new costs for every other unit.
root of ( "Td current unit"/ "Td of the weakest unit").
In the last example, the unit with overall strength 10, is now worth 35% more.
13,5 N little ones now provide Td 98%.
- Units with lesser health are often cheaper. They should be healed faster too.

I do not have the recalculation, nor the unit that can contain other units.

***

4)))

PM will follow.

***

5)))

Thanks about the triggers. But that wasn't really programming. It was just asking the AI to place a location on it's scout unit. The scout unit was asked to move to a location in the players main base, no matter what. Then count the number of each unit that the player owns within the location that the scout carried. And eventually plan to make a counter after the player contained a bit to much of one certain unit.

To make things harder for the player. I also added random attacks that contained another unit specific.

For this, I used Starforge.

And it isn't impressive in the "use map settings" community.

***

6)))

The both AA and ground attack. I got that idea from the mammoth tank from C&C. In C&C 3, it shoots cannons and rockets at the "same" time. If you have good control. You can keep it shooting cannons at the ground. But those rockets will be ordered to air.
In C&C 1, you cannot use cannons and rockets at the same time. You have to choose.

X3M
X3M's picture
Offline
Joined: 10/28/2013
What kind of suggestion would

What kind of suggestion would you give?

If I say that simply having wins/losses doesn't help?

I know that having knowledge of the remaining forces is important.

The one and only question here is, what to use as results?
Should I sum them up and divided by the iterations?
This would mean that the loser would also give a positive result. Not only is the remaining average health needed. The number of units as well, since 3 almost dead units taking cover do more damage than 1 full health unit.

Always winning, while having just 3 health left on 2 units while you started with 4 units and 12 health in total. Is a common thing in my board game.
51% to 100% win is not a final answer. Because there are aftermath's too. I am now pointing towards the self balancing game by skill in planning.

X3M
X3M's picture
Offline
Joined: 10/28/2013
Simulator shows me many mistakes and a path to answers

The simulator got upgraded a lot last week. And I have to say that without it, the game would have had many flaws that would never have seen the day light.

Down here starts looking like a blog. Neat to read...IF...you are interested.

But for others, TLDR.
However, if you wish to help me. Number 4 is a problem at this point.

And here is a summary of results:

***

1
--- Interpreting results correctly by accidental comparisons ---

Not only do I have a total of wins/losses/draws. I also have the results of remaining health on average. That's right, on average, when a player wins. And a little counter how many units are above 0,5 health (less than 1 health, but alive by random) and above 0,1 health (hardly alive; already dead by random).

The problem here is that certain "certain" fights, are way to certain. A unit looses for 99% and has no health on average as well. Well, this is the die problem mentioned somewhere else. Division by 0 seems to be a good balancing factor for war games. The winning ratio sky rocketed for the losing side and remaining health got way more options, thus a higher average.

***

2
--- A better answer to the little man imbalance ---

At first, the simulator showed me imbalance between different units that are in "theory" balanced. infantry against tanks. Certain light support infantry against those same tanks. etc.
A very known problem to RTS designers as well.

As an answer to this, I sought anew balance rule instead of tweaking the units. This through a bonus rule instead of penalty. Of 50% chance on an additional hit per projectile that received this bonus. Turns out that a Win/loss ratio got rooted. Thus previously 4 wins for every loss, became 2 wins for every loss. Etc.

Not only that, but this rule also has given certain support units an extra edge towards their targets. While being outnumbered. This is a welcome change.
Infantry has become much more useful in a game like this. It is regretful that this mechanic is not possible in RTS.

***

3
--- Fatal mistake? ---

This same bonus rule has ripped the RPS system for the first 3 basic unit designs, to shreds. Where the ranges 0, 1 and 2 had a good looking RPS of 2>1>0>2.
Due to the bonus rule, it has become 2<1<0>2.

This is deadly to the game, since the basis got crippled.

Next upgrade is a correct way in range influence. Meaning that the longest range doesn't start with hitting and than shifts turns. Instead, it hits a correct number of times. Then the correct battle takes place.
This also means that the bonus will be applied more correctly. Perhaps the RPS failure will become less. But on paper, I already know this one has died.

***

4
--- Fatal mistake? Part 2; search for an answer ---

There is one thing that 0 range can't do in the game. And that is providing extra cover to these units. The injured are sitting ducks. And the real results would be that a higher range can wrack them in a faster rate. Simply said, 0 range might actually still be bad against a variety of higher ranges.

I still have to calculate this on paper.
But the simulator has a problem here. I don't know how to do this. By default, the simulation program pretends that all units can take cover once injured. However, 1 range allows for 1 cover line. 2 range provides 2 cover lines. Etc.

Perhaps an option to remove this cover entirely?

What about 1 range, providing cover to half of the units?

But I don't know how to make the simulator do a correct cover for more lines.

The decisions for cover have to be made after every little skirmish. And with 2 cover lines or more. It is a little judgement call for the player.

Bottom line, the front line has to be bigger then the next line. To provide this cover. If the front line is smaller, then the next line also will take hits. This often results in having the weakest unit that took cover, to get hit first.

Syndicate content


forum | by Dr. Radut