Decision based AI

This is a discussion on Decision based AI within the Game Programming forums, part of the General Programming Boards category; I'm thinking implementing for some parts of my game an AI based on decisions. I need your help to achieve ...

  1. #1
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,532

    Decision based AI

    I'm thinking implementing for some parts of my game an AI based on decisions. I need your help to achieve it.

    First, I'm not even sure this is the name I should be using. But basically I'm thinking of implementing a matrix that will define conditions for an action to be taken. Each element in a row determines a condition. The whole row determines the needed state for an action to be taken. A small example:

    Matrix legend (row): Rainy, Night, Winter, Full Moon, Action

    0,1,1,0,load_vampire_into_room
    0,1,0,1,statemachine(choose monster from other data)
    ...

    This type of AI is meant to be a simple one. One of the places where it will be used is with CRoom objects as exemplified above. The second row shows an example of me wanting to eventually implement it also in conjunction with a state machine.

    Now... I have two problems with this.

    First, do you think this makes a good framework for an AI?

    Second, the matrix rows can grow considerably (vertically). However, the actions will be finite. There's only a bunch of actions that I want to put through this AI (some monster placement, some doors being closed or opened, some lights on or off).

    What I can see in this is an excellent opportunity to turn this matrix into a tree and speedup considerably the lookup phase. However, I've been working around an algorithm to do it, but simply can't find one. Mentally, I can envision the tree and I can envision the matrix... so this can only mean it is possible to express programatically the conversion. I just can't see how.
    Last edited by Mario F.; 11-28-2006 at 05:09 PM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    You want a decision tree, nodes are your states, left & right are your "yes" or "no" decisions, and leaves are the actions. How you design the tree is the question. In a typical decision tree situation you would train the tree with training data, but that doesn't seem toa apply here.

    Code:
                   Rainy?
                    /  \
               yes /    \ no
                  /      \ 
               Night?    Winter?
                /    \      / \ 
               /      ... ...  Night?
            Moon?               /   \
             /  \           Action   \
            /   Action                Moon?
       Winter?                       /     \
        /   \                   action    action
    action action

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,532
    Yes. Building the decision tree from a matrix stored externally seems to me the natural way to go. The game data is stored with SQLite. I would have right there the perfect medium. But building the tree from a matrix seems not an easy task.

    However, you gave me an hint. I wasn't aware this was an actual tried and tested design. So I searched google for your keyword "decision tree". Wiki was not helpful this time. But this was, after I added AI to the query: http://ai-depot.com/Tutorial/DecisionTrees.html

    It's called Recursive Partitioning and it seems to be exactly what I want. Will give it a better look.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

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. Text Based RPG & AI?
    By TylerMoyer in forum General AI Programming
    Replies: 4
    Last Post: 10-12-2007, 07:40 AM
  3. decision based on answer
    By niceguy664 in forum Windows Programming
    Replies: 4
    Last Post: 06-26-2006, 08:20 AM
  4. chess ai contest
    By Raven Arkadon in forum Contests Board
    Replies: 7
    Last Post: 07-09-2005, 07:38 AM
  5. Game Design Topic #1 - AI Behavior
    By TechWins in forum Game Programming
    Replies: 13
    Last Post: 10-11-2002, 11:35 AM

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