Writing AI for a board game

Wed, 05/31/2017 - 01:36

#1

ssm

Offline

Joined: 04/06/2017

Check out the Tradewars

Check out the Tradewars Launches Today thread. There is a link on page 2 for AI for boardgames.

Wed, 05/31/2017 - 05:14

#2

X3M

Offline

Joined: 10/28/2013

Ah yes, eventually, I am

Ah yes, eventually, I am directed here.

https://boardgamegeek.com/video/137566/outside-scope-bgg/rahdo-runs-thro...

The big differences between all the mentioned AI and the AI that I need are:
- My AI will be using any type of unit. There are thousands of possibilities.
- My AI needs to respond TO any type of unit. Again, thousands of possibilities.
- My problem is only in the defending part. The AI needs to take the best position.

Telling that the AI goes from A to B is not a problem at all. It is the mission.

Yet, telling the player that the AI places 3 units of type A in the front and 18 units of type B in the back is problematic. Again, to keep in mind, type A and B can stand for any of the thousands of design.
Although, I understand that it is impossible to tell the player each time, which to put in front or in the back. Unless a very simple rule can be used. Like for example, the AI uses a designed unit for A and for B and always puts A in front of B. Despite the fact that B sometimes might be better to be in the front.

To bad for me. It can't be the case with thousands of designs. So, in order to get AI working properly. I need to point my attention to some programming. There will only be AI in a programmed version of the board game.

I think, I am way over my head into this one. I had some trouble with the "simpler" rules too. Perhaps, it is better to not do this at all. And check for situational behaviour on paper.

Wed, 05/31/2017 - 11:57

#3

kilmor81

Offline

Joined: 04/20/2017

Scenarios

Try setting up scenarios instead for the AI.
That would limit the decisions and judgement that your AI has to take.

Many co-op games handles the AI in that way.

Wargame scenario for 1 player:-
- have players try to attack a bunker/fort. The defenses automatically attack the nearest
- Have the player defend against an attack, AI army keeps sending units along certain paths or areas of the map

Wed, 05/31/2017 - 12:22

#4

ssm

Offline

Joined: 04/06/2017

Similar to that ^

If you have a board game with that many different units & terrain, I'm guessing you know a lot about traditional tactics & strategy? That is what AI usually uses. It isn't always 'best', but against a player that isn't an expert, the AI will usually perform well & teach the player.

Wed, 05/31/2017 - 13:16

#5

larienna

Offline

Joined: 07/28/2008

Did you take a look at my

Did you take a look at my starcraft solitaire game:

https://www.boardgamegeek.com/filepage/75507/starcraft-invasions-solitai...

Not all games can be adaptable for solo play. Normally, the AI will not play the same game as the player. It will more likely siimply increase and push threats for the player to handle.

Wed, 05/31/2017 - 17:26

#6

X3M

Offline

Joined: 10/28/2013

kilmor81 wrote:Try setting up

kilmor81 wrote:

Try setting up scenarios instead for the AI.
That would limit the decisions and judgement that your AI has to take.

Many co-op games handles the AI in that way.

Wargame scenario for 1 player:-
- have players try to attack a bunker/fort. The defenses automatically attack the nearest
- Have the player defend against an attack, AI army keeps sending units along certain paths or areas of the map

Don't worry, I got those. But they are all based on having 1 unit type at a time. It is very easy to set up just 1 unit type. Healthy units in front. Injured in the back.
One of the scripts is:
- 3 Rifle infantry
- 1 Tank
- 9 Rifle infantry
- 2 Tanks
- etc.
Where the forces are positioned close to the barracks and factories. The AI constantly produces. Has a lot of defences at first too. But sends in these squads once ready. Once a squad is defeated, the next one starts moving. Players need to get closer and start taking out the barracks and factories, only to diminish the production. If the player doesn't act properly, the player might be overrun eventually.

It is also true that defences are static and can't switch position. In that case, I can tell the AI to put certain defences in front, and the rest in the back.

My problem is with 2 unit types in one spot, that can switch places.

ssm wrote:

If you have a board game with that many different units & terrain, I'm guessing you know a lot about traditional tactics & strategy? That is what AI usually uses. It isn't always 'best', but against a player that isn't an expert, the AI will usually perform well & teach the player.

You are right about that. The strategy is sometimes very deep. And contains several regions(or squads). It is sad to say, that I am actually trying to set up the strategy for only one mixed squad of 2 unit types.

In your view. You would say, how about putting the best "tanky" units in front? Always?
But one of the best properties of my game is: cannon FODDER. We actually have situations where infantry are the bait. And tanks need to be kept in the background. My game kinda rides on this fact.

With 3 tanks and 18 infantry, it is clearly that the tanks will be in the front. Especially when dealing with a squad of solely 36 infantry. Tanks are useless for damage here, but are the sponge of incoming bullets.
When having to deal with 6 tanks on the other hand, the situation reverts. The infantry can soak it up now. While the tanks need to remain in the background.

Suffice to say, writing the AI got problematic for me when I tried to have 3 tanks and 18 infantry, against 3 tanks and 18 infantry. Will the tanks be meat, or the infantry fodder?

larienna wrote:

Did you take a look at my starcraft solitaire game:

https://www.boardgamegeek.com/filepage/75507/starcraft-invasions-solitai...

Not all games can be adaptable for solo play. Normally, the AI will not play the same game as the player. It will more likely siimply increase and push threats for the player to handle.

I'll take a look for fresh idea's.

Wed, 05/31/2017 - 18:32

#7

FrankM

Offline

Joined: 01/27/2017

Start with simple heuristics

Just start with simple heuristics that recover a passable strategy.

For example: if a unit cannot do damage to the opponent, but another co-located unit can with a ranged attack, put the cannon-fodder in front.

Ideally, every decision step is also a stopping rule (no further decisions required to arrange the battle), but that probably can't happen with >2 friendly unit types in the same battle.

Wed, 05/31/2017 - 21:59

#8

ssm

Offline

Joined: 04/06/2017

"In your view. You would say,

"In your view. You would say, how about putting the best "tanky" units in front? Always?
But one of the best properties of my game is: cannon FODDER. We actually have situations where infantry are the bait. And tanks need to be kept in the background. My game kinda rides on this fact."
No, normally it would be mixed units. When I see infantry as bait, I think either-
The enemy will be hit from the side or from up high.
After the second time a player is baited, they become gun-shy.

"Suffice to say, writing the AI got problematic for me when I tried to have 3 tanks and 18 infantry, against 3 tanks and 18 infantry. Will the tanks be meat, or the infantry fodder?"
IDK. Don't the tanks have gunners on them? Or are they just using artillery?
Normally a tank would need to be somewhat contained to be overrun or easily defeated by regular infantry. In the open tanks often function to hold the enemy down while they are overrun by tanks or infantry.
I can't see how units would be hidden in a board game, unless one side is constantly deploying smoke or something, and with that idk why enemies would approach.

Thu, 06/01/2017 - 03:16

#9

X3M

Offline

Joined: 10/28/2013

The game is more or less

The game is more or less based on basic RTS games.
Of course, 1 infantry unit cannot give cover to a tank. But an army that costs the same or more, will draw attention. Just like in A&A. But my rps is different. And you need sufficient "cover".

When I say tanks. I am picturing the tanks from RTS games that only have a big cannon. I do however have variants with crushing, minigun, flamethrower, grenade launcher and rockets. But those are tanks that would fail against the normal ones.

Some examples:
Basic infantry; 1 damage, costs 1, 5 health.
Basic tank; 1 damage vs inf. 36 damage vs tanks, costs 6, 180 health.
Tank that has both weapons; 7 damage vs inf. 42 damage vs tanks, costs 9, 180 health.

Thu, 06/01/2017 - 03:22

#10

X3M

Offline

Joined: 10/28/2013

FrankM wrote:Just start with

FrankM wrote:

Just start with simple heuristics that recover a passable strategy.

For example: if a unit cannot do damage to the opponent, but another co-located unit can with a ranged attack, put the cannon-fodder in front.

Ideally, every decision step is also a stopping rule (no further decisions required to arrange the battle), but that probably can't happen with >2 friendly unit types in the same battle.

That is the general idea, yes.
But if both units can do the same damage. Then the same durability remains.
I am having trouble with that.

Thu, 06/01/2017 - 05:13

#11

The Professor

Offline

Joined: 10/25/2014

Remember, it's not a player...

X3M,

It might sound obvious, but remember that designing an AI is NOT designing another player, it's designing an intelligent "other" which will react not only in a fundamentally different way, but may simply have option unavailable to the player for ease of implementation and smoothness of design.

For my own AI, I completely abandoned the notion that the AI would have access to all of the decks accessible to a human player. While that might sound anathema to a deck-builder, I needed to remain cognizant of the fact that a human player actually had to do something on the AI's turn. Something I write about at length is finding that balance, as Morten Pedersen calls it, "between simple and simulation." Thus, in your game, don't try to emulate everything that the player may or may not do, but what's the essence of the game. If it's attacking, moving, and or engaging in combat, make sure that's in there, and throw away anything extraneous.

Cheers,
Joe

Thu, 06/01/2017 - 08:54

#12

larienna

Offline

Joined: 07/28/2008

Quote:It might sound obvious,

Quote:

It might sound obvious, but remember that designing an AI is NOT designing another player, it's designing an intelligent "other" which will react not only in a fundamentally different way,

I second this, like I said, unless you are making a digital implementation, the AI does not play the same game as the player.

In your case, you could have "event" cards that makes the AI trigger an attack with a preconfigured list of units.

And when you ding into ennemy territory, you could for example reveal a face down token that tells you which composition of unit was there.

Think of it as 2 entity (players) that needs to communicate with each other, but instead of giving a copy of the same entity, you create a new entity that only knows how to communicate with the player.

List what are the connections between both players, and determine how could those connections get filled wihout playing the actual game.

A quick example, in star wars rebellion, when you assign a character to a mission, the opposing player can oppose you by placing a character of his own. Here you have a connection, that If I play alone I need to fill up. A suggestion would be to make the success of the mission, not depend on the other player (you roll X dice and need X success). This way, there is no need to figure out a AI that will oppose the player's mission.

Here I changed the rules of the game to adapt it for an AI instead of finding and AI patch.

Thu, 06/01/2017 - 10:18

#13

X3M

Offline

Joined: 10/28/2013

larienna wrote: unless you

larienna wrote:

unless you are making a digital implementation, the AI does not play the same game as the player.

This is actually the case. A digital implementation.
The AI for the actual board was already finished long time ago. I am simply searching for ways to make the AI as good as possible.

I have not had time yet for your link.

Thu, 06/01/2017 - 13:48

#14

larienna

Offline

Joined: 07/28/2008

So you want a way to make a

So you want a way to make a AI for a digital game?

I am currently doing my self a lot of research in the subject considering I eventually want to make a modern hex grid war game. It seems turn based strategy games documentation is the hardest to find besides min-maxing algorithm which only works for simple open information games.

So far, it seems that I will need a multilayered AI. I designed a Floating Logic Circuit system which seems to be a combinations of Fuzzy logic and rule based logic. I'll have to put it into action eventually to see it's efficiency.

So far it was used to give for a ponderation to a list of units to determine: which unit plays first, which unit gets targeted first, which unit is most important to produce, etc.

I also learned recently about influence maps which could also be useful. But since I am not yet working on that game in particular yet, everything so far is very theoretical. I have actually no proof it could work.

Else, while Playing "Dai Senryaku", I realised that I played the game according to a specific pattern that I will try to reproduce for the AI.

For example, I always chose units which has the least units in target range and attack the units which can be the least targetted. This avoid for example wasting attacks by destroying a unit too soon.

Thu, 06/01/2017 - 15:28

#15

X3M

Offline

Joined: 10/28/2013

Warning ahead, tldr post imminent

larienna wrote:

So you want a way to make a AI for a digital game?

YES! :)

The programming is for my cousin. (since I am an idiot with computers)
I on the other hand, am mapping the rules out that the AI could follow. Most of them are from the paper version of the board game. But then the AI is simple. We are also going for a challenge AI in a sense.

larienna wrote:

I am currently doing my self a lot of research in the subject considering I eventually want to make a modern hex grid war game. It seems turn based strategy games documentation is the hardest to find besides min-maxing algorithm which only works for simple open information games.

So far, it seems that I will need a multilayered AI. I designed a Floating Logic Circuit system which seems to be a combinations of Fuzzy logic and rule based logic. I'll have to put it into action eventually to see it's efficiency.

So far it was used to give for a ponderation to a list of units to determine: which unit plays first, which unit gets targeted first, which unit is most important to produce, etc.

I also learned recently about influence maps which could also be useful. But since I am not yet working on that game in particular yet, everything so far is very theoretical. I have actually no proof it could work.

Else, while Playing "Dai Senryaku", I realised that I played the game according to a specific pattern that I will try to reproduce for the AI.

For example, I always chose units which has the least units in target range and attack the units which can be the least targetted. This avoid for example wasting attacks by destroying a unit too soon.

I understand the pain.
It is very different, depending on the rules and mechanics. This for each boardgame.

Sure I can ask for advice here. But examples are even better.

And it is that part, where the AI has to decide on "instinct".

Today, I had some brainstorming time myself. And I got some new idea's.

My old idea was determing a protection factor for each unit. With very (not working) complex math. I thought, I could apply a factor. And the highest factors need the most protection.

Well, that didn't work at all. Once damaged units went to the last line, healthy but weak units went in front combined with tanky units. Optimal damage distribution would inflict much, much more damage. This was actually bad and dumb.

Then I started this topic, when I was sure to be stuck.

The new idea's take an entire different approach. Perhaps they give you some idea's.

***

Basic AI protocol:
The AI will test a number of permutations. Putting each unit type in the formation. Event cards (that change things) are not included for various reasons.
There are only 3 positions possible for the forces.

With 1 type, a sub protocol might put damaged units in the second and last line. But with more types, it is the unit on itself entirely. Damaged units are "doomed".

With 2 types, the AI will test A/B then B/A. Damaged units might go to the last line from the second. But only for that type.

With 3 types, the AI will test ABC, ACB, BAC, BCA, CAB and CBA.

With 4 types, 24 permutations. etc.

I have 1 type done and tested.
This topic regards 2 types and my next step.

Each permutation will be tested by getting a goal score.
For this, it is calculated what remains of the force, after fighting you.
It will only be the absolute average result of victims. Of course with your units having fired most optimal on the AI.

Which goal score?

Firepower AI:
This AI will go for maintaining firepower. The main objective here is to inflict as much as possible damage on YOU, the player. So,... that you die as fast as possible.

The total remaining firepower is used as goal score.
Simply said, all damage is added up, that can be inflicted on you, regarding every target type. (Sorry, that is not simply said :[, I don't know how to put it)

There could be an advanced version of this. Where the AI also considers, how much units of a type your force has. And I think, this has to be multiplied by the initial score. Then divided by the total score. Thus giving a goal score, based on what you send as well.

This last one, was the one that I was initially looking for. This AI will be the best and most efficient in giving you a beating.

Durable AI:
The main goal would be; holding you somewhere, as long as possible.
This AI will look at how much health remains.

But this is "weird" in my game.
Due to my RPS, I need to use the armor value's as well. Dividing the health by armor, will show a net health. 5/1=5, 20/4=5, 45/9=5. That is how my armor works.

I can't even imagine if a designer has used armor as a substraction tool.

Greedy AI:
This AI is rather dumb. It will try to keep you from gaining XP initially. Simply by keeping more expensive units alive. This even could mean that an expensive concrete block will be protected by fodder infantry. While the players attacks with flamethrowers first.
The goal is to maintain what has been paid. As much as possible.

I don't think, this greedy AI will manage.

Retreating or dodging AI:
Depending on the first 2 (or 3 including greedy) AI's. The score's will also be tested, if the AI decides to run away.

Whether or not the AI shoots back during retreat. I don't know yet.

But I could apply a cautious score to this. If the retreat score manages to save more units by a certain factor. Thus more goal score. And this factor is 1.2 or whatever. Then the retreat is chosen instead.

To keep in mind for myself. Scores with retreating will have clean 6/5, 36/25, 216/125 etc. 6/5 to the power of...

***

That is all for now. I need to test this all. And make sure the first AI, regarding firepower. Is properly mapped out.

Thu, 06/01/2017 - 15:48

#16

larienna

Offline

Joined: 07/28/2008

You need at least 2 AI, one

You need at least 2 AI, one that do the strategic planning and one that mange individual units.

The stratgic planning could be done by defining strategic points and drawing the influence map to know the placed where you you are winning and losing. Then using a rule based AI you determine which city are worth defending attacking, etc.

This will give the general guidelines for the units in those area. If you are losing too much influecen in an are and the AI decides, ok it's tiem to retreat, and the unit AI will act according to the priority.

As for the unit AI it's basically:

- I am asked to retreat?, if no
- Which unit around me who I shall target? list units in priority order according to threath and least targettable.
- If there is no units, then which tactical point must I move to.

Another idea for scenario based AI like advance wars. You can during map design pre program the behavior of the unit by giving them priorities according to the design of the map. For example, each unit could have an instruction like:

- Defend target location
- Attack ennemy player
- Attack target location
etc.

The commands never get changed during the game. It's easier to implement as ou don't need a strategic AI but it requires scenario specific design.

Thu, 06/01/2017 - 17:07

#17

X3M

Offline

Joined: 10/28/2013

Now, I am just brainstorming again

Yeah, we certainly don't want roaming.

Although, I don't know how to individual unit management. Since, retreating units without protection. Are dead. So, some other units need to tag along. It would require splitting up a squad. There are special rules regarding this.
I think, that this is even more difficult then what I am attempting so far.

***

A leftover from our Starcraft(1) trigger design era is. To let the AI design a squad. With a purpose somewhere else on the map.

- Regarding which area's are important:
The AI moves to that area with units. The squad that is designed by the AI at first. Will have key units that are good for their purpose.

I used to count player units back then. And the AI would send several different squads when ready. The board game can be deeper in this. By using the mentioned protocols in the previous post. But then based on all "visible" units from the area that the AI is going to take.

Finally, if a player knows the locations for the triggers. And actually tries to abuse the AI behaviour. The AI will not act as mentioned above. But will consider the location first as a specific target to take out.

- Specific targets to take out:
Kinda like what you said.
An AI that will have once again, an important area. But now to snipe something important. This will be the case for protecting missions. But also resources etc.
These locations could move along with the targets.

The AI either sends in 1 unit at a time.
Or gathers enough units to perform a Snipe.
Or simply gathers an overwhelming force.

To reach important locations. The AI also needs to compare the distance to their HQ. Maybe even some path finding too. Just to keep save from the players units.

***

We got a lot of work to do.

Fri, 06/02/2017 - 09:02

#18

FrankM

Offline

Joined: 01/27/2017

Extensive-form games

Extensive-form games are useful if there are only a few possible plays for a given squad.

An example for arranging a battle:
1. Run down each feasible arrangement for the AI's units (A/B, B/A, wounded in front, wounded in back, etc.). Say there are X possibilities.
2. For each of those arrangements, run down each feasible arrangement for the player's units. The AI doesn't need to handle every possibility, just the ones you want it to be prepared for. The number of possibilities could vary for each of the X arrangements, but for now assume Y responses for each of the X arrangements.
3. Numerical score the outcome for each of the approximately X*Y plays. Pick the one that best matches the AI's motive for that encounter (most units surviving, most damage inflicted, etc.)

So long as X and Y are reasonable numbers, a computer program can zip through the possibilities in a flash. Now this gets too expensive in a game like chess where you look several moves ahead (X1 * Y1 * X2 * Y2 * X3 * Y3 * ... is a big number), but is quite serviceable for a tactical AI.

Edit: Forgot an important part of step 3, how to pick the player's expected response. Generally you'd score X by what happens when the player picks her best-scoring Y available in response to that particular X. But another criteria could be to pick the Y that does the most damage to the AI's goal (if the AI is trying to kill player units, pick the Y with the fewest casualties); this is called maximin strategy where you come up with the choice that has the least-bad worst-case scenario.

Fri, 06/02/2017 - 09:40

#19

jfeast

Offline

Joined: 05/18/2017

podcsts

There is a great podcast on BGDL that deals with making solo variants of multiplayer games (by Morten Pedersen). It may be helpful.

Tue, 06/06/2017 - 01:55

#20

X3M

Offline

Joined: 10/28/2013

Little Update

We went to programming the "super" AI's. My cousin adviced to actually consider every unit as a separate piece. Which would yield much more detailed results. So, it turns out that the "damage" AI is 3 times better then the durable AI. The "durable" AI will only win 1 or 2 rounds of blocking. And that is only 10% of the situations. But the "damage" AI kills you. And then you are stopped too...much more permanently.
The "greedy" AI is considered an idiot. 0% chance that it proves to be the best. But resembles some players in RTS that I know. So, no harm keeping them all 3. :D
The results are COOL! I can tell you that.

The "damage" AI will be used for most situations.
The "durable" AI will need to be tested on before hand. If it proves to be the better choice. Then it is this AI that will be put into work on that spot.
The "greedy" AI will be discarded for the real campaign.

During programming, I thought to had to work on one more issue, sacrifices. But it turns out, that this is done automatically by the programm that my cousin wrote. I am very happy about the results.

***

For the more basic stuff. I certainly want to read the material and listen to podcasts that you all provided. I am hoping to have some time for that, this week.

Who knows what more idea's I might get from them. Because for now, I am sometimes literly copying existing RTS missions (especially my favorites).

Fri, 06/09/2017 - 03:23

#21

X3M

Offline

Joined: 10/28/2013

Cheered to soon

Slowly but certain, we increased the number of units in the simulator. I suspected that it would get harder. But didn't payed attention to the set up. There are also duplicates that all are displayed on screen. This was already noted with only 2 units.

For 6 units, the ai checks 2.160 options. Less than a second to calculate.

I quit at 8 units, that checks 120.000 options. About 12 seconds. I already had doubts at 7 units that started to take almost 2 seconds.

For 12 units, the ai checks more then 1.000.000.000 options. I figured that this would take a day to calculate.
Not even going to calculate, what I need for 36 units.

The super ai is impossible regarding time, despite the simple behaviour. It is just a bit too much checking.

Suffice to say; "back to the drawing board".

Fri, 06/09/2017 - 11:49

#22

larienna

Offline

Joined: 07/28/2008

It depends on the algorithm

It depends on the algorithm you use. Min-maxing is very slow for large amount of moves. It also depends on the depth of the search (how many moves ahead)

This is why in games like GO, monte carlo search tree are used.

Fri, 06/09/2017 - 13:15

#23

X3M

Offline

Joined: 10/28/2013

https://en.wikipedia.org/wiki

https://en.wikipedia.org/wiki/Monte_Carlo_tree_search

Well, that makes a lot of sense. Having the game randomly search for the best options obviously beats trying everything out.

Perhaps putting in a check that the cover lines are randomized correctly will help. Front >= Middle >= Back.

I also need to think of something that allows the secondary AI to distribute damage more correctly. At first, we did highest damage first. And the set was an optimal one with 2 types. Often a high damage and a 1.

Not going into details of why and how. But coding will not help me here. Since there is "instinct" like having 2 times 4 damage dealing with a 9 armored guy that has only 8 health left. And saving the 9 damage for the next 9 armored guy.

This too would be better with a simulator. But I guess only about 150 x 150 attempts would take like 2 to 3 seconds. That is enough for a game. Mistakes happen, why not letting the AI make them from time to time. After all, the player is the secondary AI, who might do something entirely different then expected.

For the simulator, we could increase this as much as to 500 x 500. That would be around 25 seconds. 10 times as much time, but the result would be only 3 times more accurate. I don't know if that is of use to me. But perhaps the coding will be simple with monte carlo. Thus the time would be less per simulation.

I don't know, when the next time is on working on this AI. But I am hyped, since I am learning new ways to deal with things.

Mon, 06/12/2017 - 15:07

#24

X3M

Offline

Joined: 10/28/2013

PS. It is only 1 move ahead.

***

Some systems are complexer then the simulation. According to my cousin, this could be as high as 99,99%. That the most optimal situation isn't seen at all. Or let's just say that the AI would be rather dumb in those cases.

My cousin suggests discarding the simulation for the AI. And simply go back to a formula that determines how hard an unit is going to get hit. And how hard this hits on the outcome of the next round.

I have a rought idea of how this is supposed to be done. Since I already did that before I tried simulations.
So back to the drawing board.

User login

Navigation

Nov 23 2024

Nov 21 2024

Nov 20 2024

Nov 18 2024

Nov 17 2024

Nov 15 2024

Nov 13 2024

Nov 10 2024

Nov 7 2024

Nov 5 2024

Nov 1 2024

Oct 31 2024

Oct 29 2024

Oct 28 2024

Oct 25 2024

Oct 21 2024

Oct 17 2024

Oct 15 2024

Oct 14 2024

Oct 11 2024

Oct 9 2024