AI programming help wanted

[DanFraser]

I've been looking around for ages trying to find help on how to plan and build an AI for a turn based strategy game. I keep finding loads of information on FPS/RTS/etc AI, more than I could ever want to know, but I can't find a single thing about turn based AI. It's driving me nuts. Does anyone know of any concrete sources for this information i'm after?

[Perspective]

You want to search for Minimax and Alpha-beta tree.

[DanFraser]

Thanks, looking that up now.

As I read through, is this type of AI suitable for an up to 11 AI player complex grid map turn based game?

[Perspective]

>up to 11 AI player complex grid map


no. It's for adversarial 1v1 turn based games. Its what's used in traditional game AI like chess, checkers, etc...

Sounds like you may want a decision tree for that type of thing. These types of games often have human designed AI, though you could probably train a tree by playing the game against itself.

[DanFraser]

Ah, this is starting to lead me in a good direction. It's always good to have someone not speak like they're writing a book :)

If you have any more suggestions or stuff, lemme know. Would telling you a little more about the game and it's constricts allow you to point me further?

[abachler]

For a turn based game, your ai should probably be pretty simple. Scripting it to just build an economy and make units and then attack will probably beat most players. You can hide any defficiencies by giving it an advanatge in materials or unit cost/quality. 85% of players cant tell the dfifference between smarter AI and AI with higher hitpoints/more resources.

[DanFraser]

I think it needs to be a bit more complicated than that though. The properties of each empire and it's governed systems is quite huge, and the actual game itself in real life demands that you make at least one alliance or die.

[abachler]

So you add a section of code that makes the AI form an alliance.



if(this->Allied == FALSE) this->OfferRandomAlliance();

[Perspective]

>if(this->Allied == FALSE) this->OfferRandomAlliance();

It would work but it's pretty simple.


I would break things down into basic actions, like attacking a unit in neutral territory, invading enemy territory, expanding your territory, etc... As well as the state of the game (I have an alliance, x territory, x units).

All of these can then be fed to a scoring function for a particular goal. If you have a goal to make an alliance, than attacking a unit in neutral territory carries negative weight for that goal. Invading an enemy carries even worse weight. However, they carry positive weight towards other goals such as winning the game. Not having an alliance also contributes negatively to winning the game. etc..

The AI then evaluates the effect of candidate actions on all of it's goals and chooses accordingly. Different AI strategies will value (or weight) goals differently. Tuning these weights (or learning them) is what makes a good AI.

[mike_g]

You may want to learn to use Dijkstras algorithm for path finding. A* is a faster, simpler, and more common pathfinding technique, but it doesent necessarily find the shortest path. Since turn based strategy games don't have to do pathfinding as frequently as real-time games dijkstras algo should be much better for what you need.

[Perspective]

>A* is a faster, simpler, and more common pathfinding technique, but it doesent necessarily find the shortest path


What? It most certainly does find the shortest path.

[mike_g]

No. Not always :p

It can find the most direct path from a to b with no obstructions, but it works on guessing the distance from the current location to its target. This causes problems when you have variable stuff like differing movement costs for terrain types. I have been there and done that with a turn based strategy game. From experience I found Dijkstras algo is the one to go for.

[Perspective]

>No. Not always

Than your implementation is wrong or your heuristic is over-estimating.

[mike_g]

There is nothing wrong with my implementation. A* heuristic improvements I have seen on net simply point to finding a more direct route. How would you implement varying terrain move costs in your A* heuristics? Use the average move cost per tile on the map?

The A* algorithm finishes once a path has been found; regardless of if its is the shortest path. As heuristics here basically means guessing you cant be guaranteed to have the shortest path.

Dijkstras algorithm is often referred to as 'the shortest path algorithm'. A* is not.

If theres anyone else here familiar with both algorithms they should agree with me.

[Perspective]

Just do a little googling, you can model all of your terrain stuff as part of the cost function. As long as your heuristic doesn't overestimate the cost at any point, the A* search will always find the shortest path.

http://en.wikipedia.org/wiki/A*_search_algorithm

In computer science, A* (pronounced "A star") is a best-first, tree search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).


The article even describes how Dijkstra's algorithm is a special case of A* for an always 0 heuristic.

Your A* implementation is broken :p

[mike_g]

Dijkstra's algorithm is a special case of A* for an always 0 heuristic.
That means that its not doing any 'guessing', which is exactly the problem with A*.

If you chuck a load of walls between the origin and destination it can screw up the heuristics resulting in an estimated distance that is much less than actual distance needed to reach the target.

The only way to truly be exact is to not use heuristics, although that is a lot slower.

also you have not explained how you would model the terrain cost into the heuristics.

[Wraithan]

I would break things down into basic actions, like attacking a unit in neutral territory, invading enemy territory, expanding your territory, etc... As well as the state of the game (I have an alliance, x territory, x units).

All of these can then be fed to a scoring function for a particular goal. If you have a goal to make an alliance, than attacking a unit in neutral territory carries negative weight for that goal. Invading an enemy carries even worse weight. However, they carry positive weight towards other goals such as winning the game. Not having an alliance also contributes negatively to winning the game. etc..

The AI then evaluates the effect of candidate actions on all of it's goals and chooses accordingly. Different AI strategies will value (or weight) goals differently. Tuning these weights (or learning them) is what makes a good AI.

Sounds like a good place to apply fuzzy logic if you ask me... Programming Game AI by Example maybe something you want to look into. While the examples may not fit exactly, a lot of the logic will be useful.

[abachler]

Programming Game AI by Example, ISBN 1-55622-078-2

good introductory-intermediate text on the subject, although the author is a bit stuck on writing everythign as a class and Im not real fond of singltons. Other than that he does a decent job of covering most aspects of AI as it applies to games.

[Perspective]

That means that its not doing any 'guessing', which is exactly the problem with A*.

If you chuck a load of walls between the origin and destination it can screw up the heuristics resulting in an estimated distance that is much less than actual distance needed to reach the target.


Ok, you've now made it clear that you don't understand A*. In order for A* to give you an optimal path, you're "guess" has to be equal to or less than the actual distance. If that is the case, A* is always optimal. period.


also you have not explained how you would model the terrain cost into the heuristics.

Build a graph with a node for each position. Edges are placed between nodes that you can walk to (allows you to model all of your walls and obstacles). A weight is placed on each edge representing the cost of traversing it (based on your terrain type or anything else you'd like). A* will, as long as your heuristic does not over-estimate any distances, always find a minimum cost path through the graph.

A simple heuristic that will work fine for your games is straight-line distance. Minimum cost path guaranteed.

I suggest you read this (http://en.wikipedia.org/wiki/A*_search_algorithm). It's a good description and there are some links to A* demos that can show you how it works.

Also, these slides (http://www.autonlab.org/tutorials/astar.html) from a CMU prof are pretty good. You'll notice slide 11 makes your claim, that A* is not optimal, but that is only because the heuristic overestimates costs. On slide 14 the main theorem of A* is stated "A* with an admissible heuristic guarantees an optimal path". Admissible means that the heuristic never over-estimates as I've mentioned a few times. The proof that A* always finds an optimal path starts on slide 21.

[Wraithan]

Just an observation, but this thread isn't discussing path finding and if you folks are going to continue discussing A* or Dijkstra's perhaps you should start your own thread.

[Perspective]

Just an observation, but this thread isn't discussing path finding and if you folks are going to continue discussing A* or Dijkstra's perhaps you should start your own thread.


3/10.

[abachler]

Just an observation, but this thread isn't discussing path finding and if you folks are going to continue discussing A* or Dijkstra's perhaps you should start your own thread.

ah, btut he thread is discussing the guys need for AI, and part of game AI is pathfinding algorithms.

[mike_g]

Wraithian: Yep, Pathfinding is AI

Perspective:
Ok I went through my A* code and there was no problem with the heuristics, but I discovered that my cost function was counting one less tile than had been traversed. So yeah you were right my implementation was broken and I'm an idiot. Thanks for pointing it out ;)

It seems understandable to me now that A* can find the shortest path as long as it does not over estimtate the heuristics, but from what I could see it appears you could still get problems using A* heuristics with terrain.

In the crude diagram below A is a current end node on a path, T is the target, and numbers indicate the squares move cost (A and T have a cost of 1). Assuming I understood you right and you would factor in all tiles along the line drawn by the heuristic, this would give a heuristic value of 9 when the actual cost is closer to 3.8.
1 1 1 1

A 5 5 T

1 5 1 1

Putting accuracy aside there is another reason why I would chose Dijkstras algo for a turn based strategy game. Since A* uses a heuristic to a target, it needs a target first. A common way to get the closest target is to use Pythagoras, which would be guessing the distance for this purpose. Using an algorithm that dosent use heuristics means that it can expand nodes outward up to the units move range and not only find the closest target, but build up a list of all reachable targets from which the AI can make decisions based on stuff like: distance, stength, proximity to allies etc.

[Perspective]

>Assuming I understood you right and you would factor in all tiles along the line drawn by the
> heuristic, this would give a heuristic value of 9 when the actual cost is closer to 3.8.

The heuristic can be independent of the tile costs, it just has to be some conservative estimate. If you use city block distance for example, you will estimate the cost (h) of A->right to T as 2, A->up to T as 4, and A->down to T as 4. Then, the actual cost of your next step is cost(A->move) + h(A).

Assuming it cost us 0 to get to A so far, the estimate for going right is (5+2) = 7, and for going up or down is (1 + 4) = 5. So the long path is ruled out immediately. In the next step we'll rule out the bottom path in the same way and A* will find the top, least-cost path.

[mike_g]

Sorry, I explained that example incorrectly. 'A' was meant to refer to a tile checked from an adjacent tile, not a position from which the surrounding tiles would be checked. Also I said there would be a heuristic of 9 when it should be 11 o_0.

Anyway since the heuristic for A would then be high that node may not be as high up on the list as it ought to be. Hope that makes sense.

[Perspective]

>Also I said there would be a heuristic of 9 when it should be 11 o_0.

If the heuristic from A to T returns anything higher than 5, than it is not an admissible heuristic. The city block heuristic from A to T would be 3.

[mike_g]

Yeah I guess that by using the base move cost for a tile you would never overestimate the heuristic, but the pathfinding would be a lot slower.