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

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