Thematic Solitaires for the Spare Time Challenged

A blog about solitaire games and how to design them. I'm your host, Morten, co-designer of solo modes for games such as Scythe, Gaia Project and Viticulture.
 Thumb up

Degenerate behavior of board game bots and agents

Morten Monrad Pedersen
flag msg tools
Microbadge: Fan of Stonemaier GamesMicrobadge: 1 Player Guild - Together We Game AloneMicrobadge: 'When playing a game, the goal is to win, but it is the goal that is important, not the winning' - Dr. Reiner KniziaMicrobadge: Level 17 BGG posterMicrobadge: Automa Factory fan
When designing bots (artificial opponents) for board games I put a lot of emphasis on making them as simple as possible to make it faster for the player to learn the rules and to run the bots. This simplicity carries risks, though, one of which I’ll talk about today.

Before we get to that, I’ll quickly note that even though I’m writing this as an off-shoot from an upcoming double post about Automas, I’ll go beyond just talking about bots that replace human players in a game and include in-game agents that are at least partially handled by the game itself.

Degenerate behavior

With that aside let’s get on to the topic for today, which is the risk of degenerate and exploitable behavior of board game bots and agents, when making bots and agents that follow as few and as simple rules as possible.

In order to be simple each rule has to handle a lot of different situations and that’s hard to pull off without a few weird edge cases cropping up. Such edge cases can either lead to two kinds of problems:

1) Degenerate behavior.
2) Exploitable behavior.

Degenerate behavior: Enforcing action sequences

Often the goal of Euro games is to score victory points and so it’s worth talking about some traps that you should avoid when adding a bot to such a game.

Most humans are smarter than a stack of cardboard and therefore board game bots must cheat to present a challenge to the human, but you want to hide that as much as possible. Therefore, you can easily be tempted to make the bot score VP in the same way as a human player does and thus require it to do the same actions in the same order as a human would in order to score VP. E.g. in Viticulture you plant vines, harvest grapes, turn the grapes into wine, and sell the wine and you could require your bot to go through the same steps.

As another example we can take Charterstone, where players must gather resources before being able to build a structure. When making the Automa (bot) for that game, we chose not to force it to follow that sequence of actions. We did this both to streamline it and to avoid the problems that I’ll discuss now.

If you want to force the action sequence on your bot you can approach the task in (at least) two ways:

1) Have the bot randomly do actions corresponding to the steps in the process.
2) Make an on-rails system that helps the bot through the sequence.

Option 1) has the problem that it can lead to degenerate behavior, which is illustrated by the bot in Tiny Epic Galaxies. In TEG you roll dice that determines which actions the bot takes. This means that it can start by trying to colonize planets multiple times before it has any colonization ships and then constructs the ship leading to no VP being scored, while it would have scored a ton of VP had it performed the actions in the opposite order. That is degenerate behavior, which can make the game very swingy.

This problem can be acceptable in a quick and simple game like TEG, but for games with longer playtimes, though, such behavior will likely be a showstopper.

Board Game: Tiny Epic Galaxies

The fickle action selection dice of Tiny Epic Galaxies.

Option 2) has the problem that your on-rails system can end up either being so simple and predictable that the human player can exploit it, so complex that it places a large burden on the player running the bot, or decouples the mechanic so much from the game that it doesn’t achieve the goal of simulating a human player.

My solution is to simply cut out this kind of behavior from the bot to make it simple while avoiding degenerate and exploitable behavior. In my next blog post, though, we’ll see that my team and I broke this rule when we made our Automa for Gaia Project, but we did that for a good reason.

The problem with the degenerate behavior in TEG that I mentioned above is an example of how, degenerate behavior caused by forcing an action sequence on the bot, can be fixed by putting the bot on rails. This can be done in TEG by simply rerolling action dice that picks a colonization action, when the bot doesn’t have a colonization ship or even simpler treat the colonization as construction colonization ship actions.

This is a simple fix and (AFAIR) the player can’t exploit it. It’s not all degenerate behavior that can be fixed this easily, though, and you’ll often be faced with choosing between a complex system or a simple system that causes degenerate or exploitable behavior.

Degenerate behavior: Scoring intermittently

In many games scoring happens when achieving subgoals. Building a structure in Charterstone gives you VP, but as mentioned above you must gather resources before you can build and this often won’t give you any VP. Thus, your scoring might go something like this: 0, 0, 0, 5.

Doing it in the same way for the Automa can have some downsides since the Automa takes actions randomly, so if the Automa because of randomness gets more of the zeros than of the fives it will significantly hurt its scoring and vice-versa. Thus, the scoring can be too swingy, and the winner of the game will be decided by this randomness, not by how well you play, which will make the game boring.

Our solution for this in the Automa for Charterstone was to spread out its scoring so that it might go like this: 1, 1, 2, 1. With a system like this randomness in which scores are activated will add the kind of limited variation in a bot’s scoring, but no more than that.

From gallery of mortenmdk

A simplified scoring graph for Charterstone.

In Charterstone we would have had the problem to a much larger extent than normal. In our other games there’s only one Automa and it has one deck of action selection cards, so variation in which cards it gets and by extension how many VP it scores is bounded. In Charterstone, on the other hand, you can have up to 5 Automas sharing the same deck of cards (there has even been one player who went through the entire campaign with all 6 players being Automas).

The shared deck would have caused huge swings if scoring was like that of a human because we could have one Automa get most of the 0 VP cards and another get most of the 4+ VP cards, which would make a mockery of the balance in the game.

Behavior that only looks degenerate

The downside of the constant scoring of the Charterstone Automa is that it gives the game a stronger sense of urgency than when playing against a human, because scoring all the time make it seem to score faster than human opponent, while in reality it isn’t. It simply scores the same number of VP following a smooth linear curve, while your scoring curve looks like a stair.

This is an example of bot behavior that seems degenerate, but actually isn’t.

Another example is Scythe, where there are two kinds of combat units: 4 mechs and 1 character per player. There’s also a central space on the board called the Factory. If you control the Factory at the end of the game you get a nice VP bonus and if during the course of the game your character goes to the Factory, you gain a Factory card that gives you access to 2 special actions.

You can have any number of combat units per space on the board including the Factory, but the Automa can only have one per space because that rule allowed us some rule simplifications and avoided a severe case of degenerate behavior.

An effect of this is that if the Automa places a mech on the Factory the Automa’s character can’t go there and the mech will likely stay there unless the human player attacks that mech and wins.

We decided it was not worth additional rules to handle this, since it makes little actual difference in the game, because the Automa doesn’t use Factory cards and so taking one only has the effect of removing one Factory card for the player to choose between if he later takes over the Factory.

Also, the result of this seemingly stupid behavior is not much out of line with a human player’s behavior, since sometimes the human player will decide that there are things that are more important for the character to do (e.g. go for encounters which only it can do) and sometimes it’s preferable to move a mech to the Factory, because it can carry workers and drop them off along the wat, which the character can’t.

So, from a point of view of mimicking the effects of a human player’s behavior the rule is fine, but the fact that the character simply cannot go to the Factory, when it has a mech there, seems[/b] really weird.

Our Automas play differently than a human player all the time, but this instance stands out to the human player, because it’s not only looks [i]different
(which the human player quickly gets used to), it looks silly. So, for psychological reasons, this simplified rule seems wrong even though it really isn’t.

Degenerate behavior: Pathfinding

A classic example of degenerate behavior is bad computer controlled pathfinding in real-time video games (e.g. StarCraft).

Pathfinding in a complex environment is a solved problem in theoretical computer science where infinite processing power is assumed, but in the real world you surprisingly don’t have that available, so back in the day where the processing powers of computers were 3 orders of magnitude lower than current computers it was really hard to do good pathfinding in a short amount of time. I remember facing this problem when working a hobby-level game for the 8 MHz Amiga 500.

If you’ve played real-time strategy games I’m guessing you’ve thrown curses at the screen, when your units with naïve tenacity tried to walk through a wall to get to their destination.

With today’s computers that’s much less of an issue, but it can probably still rear its ugly head if lots of units need to be pathfinded at the same time – or if the developers were lazy .

External image

I went on a quest to find an image of failed pathfinding, but it felt like I was walking into a wall, so I gave up. Instead I’ve just put in a random image of Warcraft 3.

Degenerate behavior: Kiting

Another video game example of degenerate behavior is kiting – a technique that works in games like World of Warcraft. When kiting you move towards a monster in a group just close enough to come within the distance where the monster triggers and runs towards you, but outside the same distance for the other monsters in the group.

After that you run backwards while “kiting” the monster along with you. You can then either kill it off at a distance while running (if you can do ranged combat) or attack it once you’re far enough away from the group that you don’t risk having to deal with the rest of them. On a more nefarious note you can pull powerful monsters into an area where there are many low level players or into the hometown of the opposing faction so that the monster kills off the NPCs there.

External image

World of Warcraft

For the first two uses of kiting it’s an obviously unrealistic behavior that allows you to kill a group of monsters one by one, when you wouldn’t have had any chance in taking them all on at once. This degenerate behavior rubs your face in the fact that you’re playing a computer game instead of questing in a fantastical world. My guess is that there are the several performance related reasons for the algorithms to allow kiting:

1) If you can take on a group at once and win it means that the servers need to handle a full group of agents at once per player instead of just one at a time, so by allowing the player to kite one powerful enemy instead of for example a group of 5 lesser enemies means a factor 5 performance gain.

2) It avoids one player sucking up all the enemies in an area, without having to make the world large enough to have at least a group per player that might be in the area with sufficient distance between them.

3) It limits the agent activation checks to be a simple distance check between each enemy and each player in the area instead of also having to check of distance between non-activated enemies and activated enemies to see whether the non-activated ones are alerted by the activated ones.

Given that there are tens of thousands of player and computer agents in each world, this significantly cuts down on the required number of checks the servers must do (or communicate about in case the check is done of the player’s computer).

You might ask why I spend so many words on video games on at game about board games. The reason is simply that I think that most of you will be familiar with these kinds of computer games and having to simplify the work in running the environment of a game is qualitatively the same whether the “CPU” doing it is an actual CPU or a human brain.

In my next post I’ll give an example of how kiting was used at a point during playtest of Scythe Automa to exploit the simplicity of the Automa’s simple movement system

Next up

Having spent 2300 words on degenerate behavior caused by simplicity in bots and agents I’ll move on to a related problem: Exploitable behavior of board game bots and agents. But that will be a topic for another day.

UPDATE: That "another day" arrived a week ago, so here's the link: Exploitable behavior of board game bots and agents
Twitter Facebook
Subscribe sub options Sat Mar 24, 2018 1:20 pm
Post Rolls
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}