AI programming help wanted

This is a discussion on AI programming help wanted within the General AI Programming forums, part of the Cprogramming.com and AIHorizon.com's Artificial Intelligence Boards category; I've been looking around for ages trying to find help on how to plan and build an AI for a ...

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    129

    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

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    You want to search for Minimax and Alpha-beta tree.

  3. #3
    Registered User
    Join Date
    Jun 2003
    Posts
    129
    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

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >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.

  5. #5
    Registered User
    Join Date
    Jun 2003
    Posts
    129
    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

  6. #6
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #7
    Registered User
    Join Date
    Jun 2003
    Posts
    129
    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

  8. #8
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    So you add a section of code that makes the AI form an alliance.

    Code:
     
    if(this->Allied == FALSE) this->OfferRandomAlliance();
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  9. #9
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >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.

  10. #10
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  11. #11
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >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.

  12. #12
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  13. #13
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >No. Not always

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

  14. #14
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  15. #15
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21