Decision based AI

[Mario F.]

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.

[Perspective]

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.

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

[Mario F.]

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.