AI programming help wanted

DanFraser · 12-12-2007, 09:19 AM

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 · 12-12-2007, 09:34 AM

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

DanFraser · 12-12-2007, 09:50 AM

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 · 12-12-2007, 10:43 AM

>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 · 12-12-2007, 11:35 AM

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 · 12-13-2007, 07:45 AM

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 · 12-13-2007, 08:35 AM

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 · 12-13-2007, 12:40 PM

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

Code:

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

Perspective · 12-13-2007, 01:11 PM

>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 · 12-13-2007, 08:18 PM

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 · 12-13-2007, 08:46 PM

>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 · 12-14-2007, 08:00 AM

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 · 12-14-2007, 09:36 AM

>No. Not always

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

mike_g · 12-14-2007, 10:47 AM

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 · 12-14-2007, 01:21 PM

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

Quote:

Originally Posted by wikipedia

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

12-12-2007, 09:19 AM	#1
DanFraser Registered User Join Date: Jun 2003 Posts: 90	AI programming help wanted 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? __________________ He who asks is a fool for five minutes, but he who does not ask remains a fool forever. The fool wonders, the wise man asks. - Benjamin Disraeli There are no foolish questions and no man becomes a fool until he has stopped asking questions. Charles Steinmetz
DanFraser is offline

12-12-2007, 09:34 AM	#2
Perspective Crazy Fool Join Date: Jan 2003 Location: Canada Posts: 2,588	You want to search for Minimax and Alpha-beta tree. __________________ jeff.bagu.org - Terrain rendering and other random stuff
Perspective is offline

12-12-2007, 09:50 AM	#3
DanFraser Registered User Join Date: Jun 2003 Posts: 90	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? __________________ He who asks is a fool for five minutes, but he who does not ask remains a fool forever. The fool wonders, the wise man asks. - Benjamin Disraeli There are no foolish questions and no man becomes a fool until he has stopped asking questions. Charles Steinmetz
DanFraser is offline

12-12-2007, 10:43 AM	#4
Perspective Crazy Fool Join Date: Jan 2003 Location: Canada Posts: 2,588	>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. __________________ jeff.bagu.org - Terrain rendering and other random stuff
Perspective is offline

12-12-2007, 11:35 AM	#5
DanFraser Registered User Join Date: Jun 2003 Posts: 90	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? __________________ He who asks is a fool for five minutes, but he who does not ask remains a fool forever. The fool wonders, the wise man asks. - Benjamin Disraeli There are no foolish questions and no man becomes a fool until he has stopped asking questions. Charles Steinmetz
DanFraser is offline

12-13-2007, 07:45 AM	#6
abachler Rampaging 35 Stone Welsh Join Date: Apr 2007 Posts: 2,927	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. __________________ He is free, you say. Ah! That is his misfortune… These men… [have] the most terrible, the most imperious of masters, that is, need. … They must therefore find someone to hire them, or die of hunger. Is that to be free? - Simon Linguet
abachler is offline

12-13-2007, 08:35 AM	#7
DanFraser Registered User Join Date: Jun 2003 Posts: 90	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. __________________ He who asks is a fool for five minutes, but he who does not ask remains a fool forever. The fool wonders, the wise man asks. - Benjamin Disraeli There are no foolish questions and no man becomes a fool until he has stopped asking questions. Charles Steinmetz
DanFraser is offline

12-13-2007, 12:40 PM	#8
abachler Rampaging 35 Stone Welsh Join Date: Apr 2007 Posts: 2,927	So you add a section of code that makes the AI form an alliance. Code: if(this->Allied == FALSE) this->OfferRandomAlliance(); __________________ He is free, you say. Ah! That is his misfortune… These men… [have] the most terrible, the most imperious of masters, that is, need. … They must therefore find someone to hire them, or die of hunger. Is that to be free? - Simon Linguet
abachler is offline

12-13-2007, 01:11 PM	#9
Perspective Crazy Fool Join Date: Jan 2003 Location: Canada Posts: 2,588	>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. __________________ jeff.bagu.org - Terrain rendering and other random stuff
Perspective is offline

12-13-2007, 08:18 PM	#10
mike_g Wheres the lesbians? Join Date: Oct 2006 Location: UK Posts: 1,219	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. Last edited by mike_g; 12-13-2007 at 08:26 PM.
mike_g is offline

12-13-2007, 08:46 PM	#11
Perspective Crazy Fool Join Date: Jan 2003 Location: Canada Posts: 2,588	>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. __________________ jeff.bagu.org - Terrain rendering and other random stuff
Perspective is offline

12-14-2007, 08:00 AM	#12
mike_g Wheres the lesbians? Join Date: Oct 2006 Location: UK Posts: 1,219	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.
mike_g is offline

12-14-2007, 09:36 AM	#13
Perspective Crazy Fool Join Date: Jan 2003 Location: Canada Posts: 2,588	>No. Not always Than your implementation is wrong or your heuristic is over-estimating. __________________ jeff.bagu.org - Terrain rendering and other random stuff
Perspective is offline

12-14-2007, 10:47 AM	#14
mike_g Wheres the lesbians? Join Date: Oct 2006 Location: UK Posts: 1,219	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.
mike_g is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Simple space combat AI	Bubba	Game Programming	5	01-06-2009 12:54 AM
chess ai contest	Raven Arkadon	Contests Board	7	07-09-2005 06:38 AM
AI Contest Proposal	MadCow257	Contests Board	4	03-13-2005 03:27 PM
Game Design Topic #1 - AI Behavior	TechWins	Game Programming	13	10-11-2002 10:35 AM
Technique of all board-like games?	Nutshell	Game Programming	28	04-24-2002 08:19 AM