next »

[Soulliard]

I'm about ready to start adding AI to my game, and I want to make sure I'm on the right track.

During a turn, each unit may take several actions (generally one movement action, one normal action, and possibly one fast action). Actions can consist of movement, attacks, support abilities, summons, and more. Actions may be taken in any order. One unit may take an action, and then another unit may take an action, and then the first unit may take another action. Many actions involve a targetted tile.

Here's how I'm currently planning for the AI to work. Planned actions are stored in a directed acyclic graph, to account for actions that must come before others (ie moving into position before attacking).

Repeat until no available actions remain:

Code:

  Find all possible locations that units can move to this turn
  Go through all available actions (for all units) that can be used from any of these possible locations, and rate each action, taking into account the terrain the unit ends on
  Find the best rated action, and add it to the graph
  If any movement was necessary for that action, add those actions to the graph as well, with edges showing that they are prerequisites of the action
  If the action affects any actions already in the graph, add edges between them (for example, an attack which reduces enemy defense should come before other attacks against that enemy)
  Repeat the process, taking into account the effects of moves that are already planned

After all planning is done, the actions are executed in order.

Does this sound like a good approach?

[Danmark]

The way you're planning to do move ordering sounds needlessly complex. Can't you just add all the moves to a list, then sort it?

I'd store moves as the thing to do, and the position to do it from, so that move actions can be sorted among other actions.

[Fallsburg]

Also, a thing to make note of, an AI doesn't need to play optimally to be compelling. Or rather, you might want varying levels of optimality. And playing optimally might not be fun.  So, consider that.

As for you proposed AI, it sounds ok, but you kind of gloss over the biggest point with this line:
"Find the best rated action"

How do you determine the best rated action?  That's the real question.  Particularly when you have multiple units.  What if the best option for a unit is to attack, but the best option for the group as a whole is for one to heal and the other to attack?

Going to a "simpler" game, chess, it's hard enough to figure out the "best" move at any point and that's for a game that only allows movement of one piece a turn.

[Danmark]

Fallsburg is right. You're not focusing on the fundamental issues.

What I'd do is have your AI come up with a list of plausible moves for each unit. The more the merrier, but it depends on your technical constraints. Then, for each possible combination of moves across units, evaluate the effectiveness of that turn if it were to play out.

Thus the AI is coordinating its units, not just letting each one do what it thinks is best. Yet this raises a new question: how do you evaluate the effectiveness of a turn?, without even resolving the last one: how do you rate actions? So let's get down to business. First, I'm going to misuse words for clarity, and call the former question 'strategy', and the latter question 'tactics'.

You need a bunch of heuristics. Warfare is about killing without dying. Killing good, dying bad. Let's consider killing. Part of the goodness of a tactical move is inflicting damage. So make a function mapping injuring to utility. Start with a linear one, i.e., simply the amount of hitpoints damaged. Not ideal, but it's a start. Now, I'm assuming units can be healed, so it's not enough to just injure an enemy: we want to kill them dead. This is a strategic matter. Make a utility function for killing (depends on the unit killed).

Now, dying. Generally to be avoided. At the end of our tactical move, we prefer not to be standing where we face imminent death. So consider all the fuck-uppage the next player's units can possibly dish out, and bake it into a risk field/map (you only need to do this once per turn). Make a utility function for risk (gives negative values, and probably depends on current damage). Strategically, the AI wants to minimize average risk across his units, so make a function for average risk->utility (negative again). Even better if you ignore a killed enemy's contribution to the risk field when evaluating a turn where he dies.

Post's getting awfully long, so I'll pinch it off, so to speak, here. AI is the hardest aspect of game implementation. You've much tinkering in your future.

[Soulliard]

The way you're planning to do move ordering sounds needlessly complex. Can't you just add all the moves to a list, then sort it? I'd store moves as the thing to do, and the position to do it from, so that move actions can be sorted among other actions.

I don't see how it's all that complicated. Unless I misunderstand you, the only real difference between my plan and what you suggest is that the sorting occurs immediately, instead of it coming later. Under my plan, move actions are stored like any other actions in the graph.

Also, a thing to make note of, an AI doesn't need to play optimally to be compelling. Or rather, you might want varying levels of optimality. And playing optimally might not be fun.  So, consider that.

I'm considering adding different AI profiles, but I want to get something working first before I worry about things like that.

As for you proposed AI, it sounds ok, but you kind of gloss over the biggest point with this line:
"Find the best rated action"

How do you determine the best rated action?  That's the real question.  Particularly when you have multiple units. 

I glossed over it because I expect it to be fairly complex. As a relatively simple example, let's consider how it might handle a damaging attack. You would consider the possible targets, and analyze the threat each one presents (this calculation would only need to be performed once for all attacks). Then, consider the percentage of each target's health that would be eliminated by the attack, and whether or not the attack would outright kill the target. Finally, consider the tile that the attacker will end its turn on (whether it ends in range of enemies, for example... I plan on making a threat map).

Since that's just one simple type of attack, the actual analysis will probably be a bit more complex. This will require some experimentation.

What if the best option for a unit is to attack, but the best option for the group as a whole is for one to heal and the other to attack?

I'm not sure what you mean by this question. Healing will be rated in a manner similar to other actions.

What I'd do is have your AI come up with a list of plausible moves for each unit. The more the merrier, but it depends on your technical constraints. Then, for each possible combination of moves across units, evaluate the effectiveness of that turn if it were to play out.

I like this idea, but it's still missing some details. For example:
How does it determine which moves are plausible?
How does it ensure that a combination of moves is valid?
Is movement taken into account when finding plausible moves? How so?

Thus the AI is coordinating its units, not just letting each one do what it thinks is best.

I'm not sure that my proposed AI would be unable to coordinate, though, since units would know what some of the other units were planning to do. For example, if Unit A was already planning to attack Enemy B, Unit C would rate lowering Enemy B's defenses more highly.

Post's getting awfully long, so I'll pinch it off, so to speak, here. AI is the hardest aspect of game implementation. You've much tinkering in your future.

Yes, I expect it to be the most difficult part of the project.

[Dacke]

What I'd do is have your AI come up with a list of plausible moves for each unit. The more the merrier, but it depends on your technical constraints. Then, for each possible combination of moves across units, evaluate the effectiveness of that turn if it were to play out.

If you use this approach, there is no real reason to stop that early. For each set of moves you try for your team you can test different enemy responses using the same method. And for each response you can test your re-response. And so on, back and forth, until you run out of AI time. At which point you evaluate the different game-states you have arrived at (using some heuristic), going with the move that has the best outcome (assuming the opponent makes the best counter-moves).

This is a very powerful approach if used correctly, as it can result in a very powerful AI that can't be easily tricked. It acts on actual results, rather than a poor approximation of strategies used by humans. The drawback being that the search branches extremely quickly. But this can be remedied by aggressive use of Alpha-beta pruning* using heuristic improvements to avoid search paths that appear to be bad.

edit: *there is no such thing as "aggressive alpha-beta pruning". Actual alpha-beta pruning, even with heuristic improvements, will still yield optimal results. But since you don't need optimal results you can probably use a modified version of the algorithm to prune things more aggressively at the cost of optimality.

[Danmark]

You probably wanna read this excellent series of articles on TBS AI for some ideas.

Unless I misunderstand you, the only real difference between my plan and what you suggest is that the sorting occurs immediately, instead of it coming later.

Right, it is just a different way of doing the same thing. It requires less & more maintainable code. Also, if you try out multiple different full turns, this way is more efficient.

How does it determine which moves are plausible?
...
Is movement taken into account when finding plausible moves? How so?

I tried to explain this throughout the post (with my misuse of 'tactics'). Plausible moves are determined per unit by considering where he can move, how/who he can attack, the risk at the position he ends his turn on, etc.

How does it ensure that a combination of moves is valid?

You would have to test for it. Perhaps it'd suffice to stop considering a combo as soon as invalidity (can it come any way other than a position conflict?) is detected.

I'm not sure that my proposed AI would be unable to coordinate, though, since units would know what some of the other units were planning to do. For example, if Unit A was already planning to attack Enemy B, Unit C would rate lowering Enemy B's defenses more highly.

Good point. However, it's a bastardized form of coordination, with massive dependence on the order units are considered. An improvement would be to, after choosing moves in the normal way for all units, go back and consider all units again, and check for more optimal moves in light of other units' currently selected moves. Do this repeatedly. You could optimize this by storing all possible moves per unit sorted by local utility (independent of what his allies do). Intuitively, this should converge on a bunch of 'good' configurations after enough iterations.

I don't recommend doing anything like this. There's still no centralization of command, but a bunch of units doing what they think is best for the team. Inappropriate for a game where units have no autonomy in the mechanics.

If you use this approach, there is no real reason to stop that early...

Good point. I'll just note that you'd have to pick the best-looking turns and only consider those as branches, because otherwise, the branching factor is still far too high (~16000), no matter how you optimize the search.

A cheap trick you can employ here is to consider fewer branches deeper into the tree. You might pick the 8 best moves for the AI's initial move, the 4 best moves for the player's response, the 2 best moves for your response & the player's next response. This should keep the total nodes considered low, and is consonant with humans' increasingly vague sense of a more distant future.

Note also that because it's a tactical game, there's no point in a very deep search.

[Dacke]

Agreed
(I had that thought, but lost it while writing. I tried to say something like that in my edit.)

[Soulliard]

If you use this approach, there is no real reason to stop that early. For each set of moves you try for your team you can test different enemy responses using the same method. And for each response you can test your re-response.

That makes sense.

You probably wanna read this excellent series of articles on TBS AI for some ideas.

I've been reading it religiously for a few months now. I agree, it's a great asset.

Right, it is just a different way of doing the same thing. It requires less & more maintainable code. Also, if you try out multiple different full turns, this way is more efficient.

I don't know that the code would be any easier. Since the order of movement often matters, the sorting algorithm would need to be pretty complex.

I tried to explain this throughout the post (with my misuse of 'tactics'). Plausible moves are determined per unit by considering where he can move, how/who he can attack, the risk at the position he ends his turn on, etc.

Okay, I thought you meant that as more of a general suggestion. It sounds similar to how I was planning to rate attacks.

Good point. However, it's a bastardized form of coordination, with massive dependence on the order units are considered.

Yeah, that's why I was planning on starting with the highest-rated attack.

An improvement would be to, after choosing moves in the normal way for all units, go back and consider all units again, and check for more optimal moves in light of other units' currently selected moves. Do this repeatedly. You could optimize this by storing all possible moves per unit sorted by local utility (independent of what his allies do). Intuitively, this should converge on a bunch of 'good' configurations after enough iterations.

Yeah, I suppose that's possible. I'm not sure how big a difference it would make.

[Danmark]

I don't know that the code would be any easier. Since the order of movement often matters, the sorting algorithm would need to be pretty complex.

But this complexity would be reflected in the way you gather actions once your graph is finished.

Yeah, that's why I was planning on starting with the highest-rated attack.
Yeah, I suppose that's possible. I'm not sure how big a difference it would make.

Peeking ahead and considering only the best action to do next is inadequate. Later actions are constrained by somewhat arbitrary & final decisions on the preceding best actions. The AI isn't properly considering the possibilities. Unless, that is, your rating algo was so complex and monolithic that it considered the future itself, which is woefully impractical.

Let me explain. If you had a machine that could efficiently process an arbitrary branching factor all the way to all possible endgames, optimal AI for any game would be trivial. A desktop PC only accommodates a meager number of branches, so deliberative game AI focuses on cutting down on the branches the AI must consider & thus avoiding a combinatorial explosion. You need to do it early, aggressively, and at every point in the AI. In fact, this is no mere side concern; it's literally all the AI algorithm does (short of achieving human-like behavior, a compatible goal).

The only useful thing achieved by your graph idea is forcing any sequence of actions for all units into the best order. However you do it, this is essential, effectively cutting down on the branching factor by 4 orders of magnitude.
Considering only good looking moves per unit cuts by 2 orders.
Only processing good looking full turns cuts by 4 orders per turn branch.

Of course I don't recommend doing all this at once. Just keep in mind the overarching goal.

[Soulliard]

But this complexity would be reflected in the way you gather actions once your graph is finished.

It can be accomplished in a fairly straightforward manner with topological sorting.

My current plan is to use my initial algorithm as a way to find moves with the greatest potential. It takes any move with a score above a certain threshold as a move to consider. Then it considers branching possibilities in the manner folks have described.

[ASnogarD]

I dont know if this is of ANY value at all but I may as well let you decide...

One of the games I am planning to do in the future will require some complex AI to really suprise the player, and while considering how to go about it I came up with a theoretical system to add some reasonable randomness... a probability index.

The idea is simple enough, add traits to your AI characters that can effect how they will act in a given situation and use the traits with a random number generator.

Say for example a enemy encountering the player , has a bravery stat of 60 / 100... the probability index will work like this:

decide = rnd number 1 - 100 // run from player.
add 60 to rnd number
decide = 60 - 100 // run from player

This is just a basic example, a properly fleshed out index would include numerous factors, like the armor the player has on, the weapons, the level difference... the idea is to eliminate predictability, I mean in the example , the stat could be 90 / 100 but the AI can still just run off despite the probability being unlikely.
Imagine a players reaction to seeing an tough enemy guarding a door, moving to battle the guard for the loot... and the guard lets of a howl of terror and legs it, player will be W T F ?!?

There was a saying, take 20 humans put them in a dangerous situation and you will get 20 reactions 

[Dacke]

This is going to be a completely off-topic response to ASnogarD:
Your idea would work fine for a RPG-AI, but it's not really applicable for a tactical AI that should try to emulate a human opponent.

Your idea would probably be nice to combine with a Markov chain, though. Which is a simple way of describing something that shifts between different states. For example:

• If you are guarding, there is a 95% chance that you will keep guarding and a 5% chance that you will fall asleep.
• If you are sleeping, there is a 60% chance that you will keep sleeping and a 40% chance that you will wake up and start guarding again

Can be written as a Markov model:

	Will guard	Will sleep
Is guarding	95%	5%
Is sleeping	40%	60%

I think this could (possibly) help you formalize your idea, making it easier to write down and program. But in your case, you wouldn't have fixed percentages but rather calculate them on-the-fly based on a number of factors.

If you are interested in this approach, feel free to PM me or start a new thread about it