Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Introduction to Artificial Intelligence

  1. #1

    3boxes Introduction to Artificial Intelligence

    Current Status:

    Update: April 25, 2011
    Finished "DFS + BFS introduction". Will be writing their implementation and usage next.

    Update: April 22, 2011
    Writing "AI As Search". I will adding actual implication of the queue soon as it requires heap implication which can be tricky. I am trying to find a faster way to do the array since AS3's Array object contain many advanced features such as splicing. However, I do not know the bench mark as any AI requires EVERY bit of power you need!

    Update: Jan. 11, 2011
    Hey guys, sorry for all the delay! I actually got a new computer over the holiday simply because I got an i7 960 for $99!!!!! Awesome deal Anyways, I am back! I will definitely continue writing more AI guide and hopefully I won't confuse whole bunch of you.

    History:
    • Jan. 11, 2011 - Creates history; added section 2.1.5, 2.2


    Introduction to Artificial Intelligence

    Hello guys, there seem to be a really old AI guide (LINK) that hasn't been updated in a long time! Therefore, I have decided to write a guide that will give you guys a board sense of what the field of Artificial Intelligence is.

    What to expect
    • AS3 implementation and explanation of Advanced Data Structures (ArrayList, LinearLinkedList, CircularLinkedList, DoubleLinkedList CicularDoubleLinkedList, Stack, Queue)
    • Fundamental concepts and theory about AI
    • Pseudo codes (might include AS3 version)
    • Complexity analysis
    • Basic Applications


    What NOT to expect
    • Tutorial on how to apply these knowledge to SPECIFIC game


    Topics Covered

    Ch. 1 What is AI?
    Ch. 2 Search
    Ch. 3 Constraints and Features
    Ch. 4 Logical Inference
    Ch. 5 Uncertainty
    Ch. 6 Planning
    Ch. 7 Learning



    Chapter 1 - What is AI?

    1.1 Introduction
    Obviously AI stands for Artificial Intelligence, and it has been around for a little short of 60 years. While it roots deep in the history of mankind, it is not until the recent 60 years does it start to shine. Many of its research has been widely applied to many and I emphasize many, daily technologies including:
    • Facial Recognition
    • Voice Recognition
    • Language Recognition (recognizing hand writings and translate into digital forms)
    • Smart Websites
    • Diagnostic Agents
    • Path Finding (shortest path, or least-cost path ect.)

    And much more that are not listed here. The reason I do not wish to list more is because they will not make sense until you have learned and understood some of the fundamental concepts in AI.

    So what is AI? AI or Artificial Intelligence is the field that studies the synthesis and analysis of computational agents that act intelligently. Naturally we can then ask, what can be defined as intelligent? However, if we go on with this approach, we will end up arguing philosophically; and we all know philosophical arguments take centuries if not forever to end. So, let us just say, an agent acts intelligently when:
    • What it does is appropriate for its circumstances and its goals
    • It is flexible to changing environment and changing goals
    • It learns from experience
    • It makes appropriate choices given its computational limit
      • The agent does not have infinite memory
      • The agent does not have infinite time to react


    Notice that humans fit under that category as well as artificial agents. However, this does not imply humans are the best representation of intelligence, and therefore AI should not use human intelligence as the end goal. Instead, the scientific goal is to:
    • Understand how intelligent behaviors are possible for both natural and artificial agents
    • Hypothesize on what it takes to construct intelligent agents
    • Construct computational systems that can perform tasks that require intelligence

    1.2 Short History
    coming soon ...

    1.3 Reasoning and Acting
    There are two board strategies to building an intelligent agent:
    1.
    • Simplify environment
    • Construct complex reasoning systems
    • Able to optimize solutions
    • Able to prove properties
    • Can "wonder" in the simplified world
    • Helpless otherwise

    2.
    • Adaptive learning given simple reasoning system
    • Inspired by insects - able to survive complex environment yet with limited reasoning abilities
    • Realistic

    These can be decomposed into the following categories:

    Modularity
    • Can they system be decomposed to interacting modular piece?
    • Is the system hierarchical? (modular organization)
    • Is the system flat? (No organizational structural)

    Representation Scheme
    • How is the world described?
    • Does it use states or features to represent the world?
    • Does it use propositions (logical) to represent the world?

    Planning horizon
    • How far ahead does the agent look into? (In a Chess game, how many steps does the agent take into consideration?)
    • Does the agent only look into a finite future? (Say always 5 moves ahead)
    • Does the agent look indefinitely ahead? (Planning until a specific goal)
    • Does the agent look ahead infinitely? (Looks ahead forever)

    Uncertainty
    • Does the agent observe the world fully or partially?
    • Are the effects by an agent's behavior certain or uncertain? (ie If I move here, I will have 50% (uncertain) chance of winning or 100% (certain))

    Preference
    • How does the agent react facing a trade-off problem? Does it prefer one side or the other?

    Number of agents
    • Does agents reason in a group or alone?
    • Can they share information back and forth?

    Learning
    • Is knowledge given?
    • Is knowledge learned?

    Computational limits
    • Does agent consider a simplified solution (may not be 100% correct) given limits of its RAM, and processing speed?
    • Should the agent ignore its computational limit?


    While the above list is a good guide to how to prepare the construction of an agent, it is not very specific. So let's break them down. The problems in AI can be divided into 2D graph:

    As you can see, Search takes up 50% of the topics! Therefore, we will begin with some representation techniques and use these techniques to learn how to make an artificial agent by Search. I am sure you will be surprised how much Search can do.
    Last edited by ChaoSXDemon; April 25th, 2011 at 08:49 PM.

  2. #2
    Chapter 2 - Search

    Before we jump into Search, I would like to point out the general direction I am taking you guys.

    Topics Covered:
    • Advanced Data Structure
    • Graphs
    • AI As Search
      • Depth First Search
      • Breadth First Search
      • Iterative Deepening Search
      • Heuristic Functions
      • Best First Search
      • Cost Functions
      • Least Cost First Search
      • A* Search
      • Branch and Bound Search
      • Iterative Deepening Search Star(*)



    2.1 Advanced Data Structures

    For readers who are familiarly with basic arrays, please skip ahead to 2.1.2 and later. Before we go right into search strategies, we need to understand the fundamental data structure, the array. Additionally, we need to add features to this structure so that we can ask and address the following questions:
    • How fast does it take to add an item?
    • How fast does it take to remove or retrieve and item?
    • How fast does it take to sort the item?
    • How much space does the entire structure take up?

    An array is simply a list of objects. They can have finite or infinite in length. In ActionScript 3 (AS3), only finite length ones are allowed, although we can abstract length away to make it to appear to have infinite length. An array can be interpreted as the following picture:



    Perhaps this is the first time you see that an array has a "next" pointer, but this is how arrays are like inside memory. To avoid confusion and all the bad memories about the word "pointer", lets just take it as what it literally mean; it points to a location in memory that has one of the boxes shown above which contains an "Item" and a "next". Notice the last box has a "null" instead of a "next". What this mean is that is has nothing to point to, therefore, it is the end of the array. While this structure is abstracted away from the user, understand this will help us construct better and more advanced structures that specialize in either and/or quick retrieval, quick insertion, quick sorting, or spatially efficient. Since AS3 does not allow for pointer manipulation, I will not go over this painful topics as I am sure it is for many people. But identifying the fact that arrays use pointers will help us better understand the reading ahead.

    2.1.1 Basic Array

    2.1.1.1 Array Creation and Assignment

    In AS3, the array is constructed like so:

    PHP Code:
    //empty array with no length = 0
    private var myarray1:Array = new Array();
    //empty array with length = 5
    private var myarray2:Array = new Array(5);
    //array with numbers {1,2,3,4,5}
    private var myarray3:Array = [1,2,3,4,5];
    //array with string {A, B, C, D, E}
    private var myarray4:Array = ["A""B""C""D""E"]; 
    While AS3 default library provide Array more like an ArrayList (we will explain what this is in later section) object, we will simply treat this as a basic array. Therefore, we will not use any method provided by the default library because using them imply that the array is an object as to a primitive type. If you do not know the difference between a primitive type and an object, do not panic. We will eventually use this basic array and develop it into an object. I shall explain when we are there. Now having said that we will be treating array in this section as primitive type, there is only one way to access the items inside an array - the index.

    All array index begin at 0. Therefore, the first item is actually 0th item, the second is actually the 1st, and the third is actually 2nd and so on. The items can be retrieved like so:

    PHP Code:
    private var firstInt:int myarray3[0];
    private var 
    lastInt:int myarray3[4];
    private var 
    firstStr:String myarray4[0];
    private var 
    lastStr:String myarray4[4]; 
    A valid question to ask now is "how would you know the index of an item?". The answer is simply we either know because we put the item that we want at that index, or we don't and need to find it. To put an item at an index can be done like so:

    PHP Code:
    private var myarray5:Array = new Array(10);
    myarray5[0] = "A";
    myarray5[1] = "B";
    myarray5[2] = "C";
    myarray5[3] = "D";
    myarray5[4] = "E";
    myarray5[5] = "F";
    myarray5[6] = "G";
    myarray5[7] = "H";
    myarray5[8] = "I";
    myarray5[9] = "J"
    You do not have to do this in sequential order, which means you can skip ahead and assign the 5th index first, then 3rd, then 0th, and so on. However, usually programmers do not do this unless they assign some kind of meaning to the index. For example, the 0th index always stores H.P. of the player, and the 1st index always stores M.P. of the player and so on.

    2.1.1.2 Finding an item in an basic array

    If, however, we do not know the where the items, and we want to retrieve it, we will have to find the item's index first. The idea can be simple: look through the entire array, and check for each one whether it is the item we are looking for. If it is, we are done! If not, some how tell the program the item does not exist. The first question that comes up should be "how are we suppose to know the length of the array?". Well luckily, AS3 includes a variable named "length" inside every array we create that knows how long the array is. However, we do need to be careful that length starts at 1 while index starts at 0. Having said that, a length 5 array will have the last index to only 4, a length 20 array will have the last index to only 19. Other words, the last index is always one short of the length. So a function that takes in an array, and returns an item can be written like so:

    PHP Code:
    public function getItem(array:Array, item:int):int{
    //you can also simply use i<array.length
    //as to array.length - 1
    //but  make sure to change your <= to <
         
    for(var i:int 0<= array.length-1i++){
              if(array[
    i] == item) return array[i];
         }
         return -
    1;

    While the above method works, it is not very good. What if -1 happens to be an item in my array? A better approach is to return the index instead of the item, since we know for sure, index is greater than or equal to 0. Other words, index is always positive.

    PHP Code:
    public function getIndex(array:Array, item:int):int{
        for(var 
    i:int 0< array.lengthi++){
            if(array[
    i] == item) return i;
        }
        return -
    1;

    This allows us to check that if we get a -1, it means there is no such item in the array. We can then either throw some exceptions, or print some error messages. However, what if we want to work with something other than integers? The correct answer should be Generic Programming. But AS3 does not have generic declaration for arrays. (Correct me if I am wrong about this. I have only manage to use generic typing with the Vector class). Therefore, we have to go back to casting and treat everything as objects. This is take heavily use of the "as" operator.

    PHP Code:
    public function getItem(array:Array, item:Object):Object{
        for(var 
    i:int 0i<array.lengthi++){
            if(array[
    i] === item) return array[i];
        }
        return 
    null;

    We can use the above method like so:

    PHP Code:
    var FirstEnemey:Enemy = (getItem(enemyListboss1) as Enemy); 
    2.1.1.3 The "==" and "===" operator

    This is where AS3 is different from imperative programming language like C++/C or Java. AS3's "==" operator does auto type conversions and they also compare the contents of the object. Other words, the follow statement returns true:

    PHP Code:
    var string1:String "OSCAR";
    var 
    string2:String "OSCAR";
    trace(string1 == string2); //this will be true
    var number_string:String "5"
    var real_number:Number 5;
    trace(number_string == real_number); //this will be true
    var right:Boolean true;
    var 
    right_int:int 1;
    trace(right == right_int); //this will be true
    var wrong:Boolean false;
    var 
    wrong_int:int 0;
    trace(wrong == wrong_int); //this will be true 
    However, the "==" operator does NOT convert strings into Boolean values. So a string with value "true" does NOT equal to a Boolean with value "true". If you guys do not like this, there is a "===" operator in AS3. The only difference between the "==" and "===" is that the ladder only convert number types (int, uint, and Number). So the following statement returns false:

    PHP Code:
    var number_string:String "5"
    var real_number:Number 5;
    trace(number_string === real_number); //this will be false
    var right:Boolean true;
    var 
    right_int:int 1;
    trace(right === right_int); //this will be false
    var wrong:Boolean false;
    var 
    whateverInt:int 45456;
    trace(wrong === whateverInt); //this will be false 
    2.1.1.4 Practices

    I am well aware the fact that these method are provided by the default library. However, understanding this from first principle allows us to have better insights for more advanced and complex forms of data structure. All the above, is basically all you need to know about the basic array. As practice exercise see if you can implement the following:

    • A getMid(array:Array):Object method that returns the item in the middle of the array. For example, if the array has length = 6, you should return the 3rd item. If the array has length = 5, you should return the 2nd item and so on.
    • A resize(array:Array):Array method that adds 10 extra space to the end of the array and returns the newly created array
    • A resize(array:Array, n:int):Array method that adds n extra space to the end of the array and returns the newly created array
    • An append(array1:Array, array2:Array):Array method that combines two arrays and returns it as one

    Please do not use the methods provided by the default library. Additionally, restrict yourself to only use the "[]" operator.

    Solutions will be posted upon request

    2.1.1.5 Conclusion

    Now that you have a fairly good idea about what a basic array can do, we will talk about its advantages and disadvantages. Keep in mind that the basic array is a primitive object, and therefore, the only operator you can use is the "[]" and perhaps the ".length" property. Therefore, one obvious disadvantage is that once an array is full, you will need to create a bigger one and copy all the value from the old on to the new one. This can cause undesirable increase in computation time. Additionally, upon removing an item that is not at the end, we need to shift all the element after the removed item up 1 slot. This again, can cause increase in computation time. The reverse is also true that adding an item in the middle will need to shift many items; not to mention the re-size possibility if the array is full.

    It can indeed be annoying to constantly check these properties like: is the array full? Do I need to shift things up or down? However, the next section introduces the ArrayList object which takes care of re-sizing, and adding/removing in the middle automatically.

    2.1.2 The ArrayList Object

    I will assume that you guys all know the different between primitive types and objects. It is not really important that you know since AS3 is not really a programming language but rather a script. However, it will be easier if you do know the difference.

    An ArrayList object is the object wrap around a primitive array. The reason that we use ArrayList objects rather than primitive arrays is that ArrayList encapsulates the resize and adjustment operators for a primitive array when it is full or an item is inserted in the middle respectively. This way, we do not have to worry about the limited size of an array, and all the adjustments necessary for non-beginning-non-tail insertions. However, understand how these are implemented, will help us understand how LinkedLists (and all their variables) are implemented. Mostly important, furthermore, is how we can use LinkedList objects to implement Stack and Queue data structures which is vital to Search in AI.

    2.1.2.1 Resizing

    When an array is full, we cannot simply expand our original array. However, we can allocate a bigger array and copy all the value over. You may say "how come I never had to do that in AS3 before?". Well it is because AS3 actually does not have a primitive array. the "Array" object in AS3 is already an ArrayList as it automatically resizes. However, it is good practice to understand how this is achieved.

    As described above, to resize, we simply need to make a new bigger array, and copy everything over.
    PHP Code:
    public function resize(list:Array):Array{
        var 
    bigger_array:Array = new Array(list.length 10);
        for(var 
    i:int 0< list.lengthi++){
            
    bigger_array[i] = list[i];
        }
        return 
    bigger_array;

    Noticed that I created a new array with only 10 more slots than before. This number can be changed to special needs. You may choose to create 2 times the empty slot every time an array is resized. However, it quickly wastes many memory slots.

    2.1.2.2 Removing

    To remove an item, we cannot simply set that item's slot to null or some default "empty" value. We need to make sure it does not exist inside the array. One way to do it is to copy everything up to that item but excluding that item, then skip over that item and continue copy over the rest of the list to a new list. However, that involves unnecessary allocation and copying. A smarter way is to look at the problem in a different perspective. If we want an item to not exist within a list, we can simply move that item to the end of the list, then subtract 1 from the length of the list. This way, when we loop through a list from 0 to length-1, we will not "see" that item. To avoid confusion, let's look at the following pictures:



    Notice that we always loop from 0 to length-1 to go through the entire array. Decreasing the length by 1, we loop from 0 to length-1-1, which is from "A" to "D", without the last item.

    So say we want to remove "B". Instead of making a new array and move everything over except "B", we can "slide" B down to the last, and make length one less. This way, we have "removed" "B". Instead of really sliding, we can just assign each slot the next slot's value like so:



    Finally, making length = length - 1, we have "removed" "B" from the list.

    This does bring up a very good question: can we really control list.length variable? For a primitive array the answer is no we cannot. But we are building an object around a primitive array! This means yes we can control list.length.

    2.1.2.3 Adding

    While removing is simply "sliding" everything up, adding will simply be "sliding" everything down, hence creating an empty slot for our new element. However, a basic add function will always add items at the end. This is easy; all we need to do, is find the last element's index, add one to it, then simply insert the new item. We do, however, need to take care of resizing if the array is full.

    2.1.2.4 The ArrayList Object

    At this point, we really need to build an object around the "primitive" array, so that we can change length to what ever we want if we desire. However, before we go right in, I want to create an Interface called List and have all my various lists (ArrayList, LinkedLists ... ect.) implement that Interface.

    PHP Code:
    package datastructure{
        
        public interface List{
            
            function 
    contains(item:Object):Boolean;
            
            function 
    add(item:Object):Boolean;
            
            function 
    insertAt(item:Objectindex:int):Boolean;
            
            function 
    remove(item:Object):Boolean;
            
            function 
    removeAt(index:int):Boolean;
            
            function 
    get(index:int):Object;
            
            function 
    getIndex(item:Object):int;
            
            function 
    length():int;
            
            function 
    iterator():Iterator;
            
        }
        

    If you do not know what an Interface is, please google around and find out.

    The following is the complete implementation of ArrayList object. As mentioned, it takes care of resize and insertion automatically. Perhaps the most complicated method is the "insertAt" method. I will try to add more comment to the code upon request. While this strictly not part of AI, it is good to understand this so that we can understand and implement "LinkedList" objects a lot easier.

    PHP Code:
    package datastructure{
        
        public class 
    ArrayList implements List{
            
            private var list:Array;
            private var 
    size:int 0;
            private var 
    maxSize:int 0;
            
            public function 
    ArrayList(_size:int 10){
                list = new Array(
    _size);
                
    maxSize _size;
            }
            
            public function 
    contains(item:Object):Boolean{
                return (
    getIndex(item) != -1);
            }
            
            public function 
    add(item:Object):Boolean{
                if(
    size == maxSizeresize();
                list[
    size] = item;
                
    size++;
                return 
    true;
            }
            
            public function 
    insertAt(item:Objectindex:int):Boolean{
                if(
    index || index size) return false;
                if(
    index == size) return add(item);
                if(
    size == maxSizeresize();
                var 
    temp:Object = list[index];
                var 
    lastItem:Object = list[size-1];
                for(var 
    i:int indexsize-1i++){
                    var 
    swapTemp:Object = list[i+1];
                    list[
    i+1] = temp;
                    
    temp swapTemp;
                }
                list[
    size] = lastItem;
                list[
    index] = item;
                
    size++;
                return 
    true;
            }
            
            public function 
    remove(item:Object):Boolean{
                for(var 
    i:int 0i<sizei++){
                    if(list[
    i] === item){
                        for(var 
    j:int ij<size-1j++){
                            list[
    j] = list[j+1];
                        }
                        
    size--;
                        return 
    true;
                    }
                }
                return 
    false;
            }
            
            public function 
    removeAt(index:int):Boolean{
                if(
    index || index >= size) return false;
                if(
    index == size 1){
                    
    size--;
                    return 
    true;
                }
                for(var 
    i:int indexi<size-1i++){
                    list[
    i] = list[i+1];
                }
                
    size--;
                return 
    true;
            }
            
            public function 
    get(index:int):Object{
                if(
    index >=&& index size) return list[index];
                return 
    null;
            }
            
            public function 
    getIndex(item:Object):int{
                if(
    size == 0) return -1;
                for(var 
    i:int 0sizei++){
                    if(list[
    i] === item) return i;
                }
                return -
    1;
            }
            
            public function 
    length():int{
                return 
    size;
            }
            
            public function 
    iterator():Iterator{
                return new 
    ArrayListIterator(this);
            }
            
            private function 
    resize():void{
                
    maxSize += 10;
                var 
    newList:Array = new Array(maxSize);
                for(var 
    i:int 0sizei++){
                    
    newList[i] = list[i];
                }
                list = 
    newList;
            }
            
        }
        
    }

    import datastructure.ArrayList;
    import datastructure.Iterator;

    final class 
    ArrayListIterator implements Iterator{
        
        private var 
    arraylist:ArrayList;
        private var 
    currentIndex:int 0;
        
        public function 
    ArrayListIterator(_list:ArrayList){
            
    arraylist _list;
        }
        
        public function 
    hasNext():Boolean{
            return (
    currentIndex arraylist.length());
        }
        
        public function 
    next():Object{
            return 
    arraylist.get(currentIndex++);
        }
        

    2.1.3 The LinkedList Objects

    LinkedList is a data-structure that exhibits fast insertion, and fast removal (despite the time it takes to find the item). The reason we need this data-structure is because what Search Algorithm use a lot is the Stack and Queue data-structure. And I would like to implement the Stack and Queue with Double-Linked-List (DLinkedList). I am not saying this is the absolute best way to write Stacks and Queue. You are more than welcome to try any crazy probabilistic algorithms and data-structures to improve run-time efficiency.

    2.1.3.1 The Node and Linear Linked List

    The idea of Linked-List is simply, instead of having a row of data that only gets identified by index, why don't we try using an object that contains the item, and also a variable that "shows" us where the next data is? This way, instead of sliding up and down, we can simply change that variable, (ie what it "shows" us), instead of resizing, and sliding up and down.



    Before your brain goes DING! That looks like an array! I must stop you. It is NOT an array nor an ArrayList. This is a data-structure which we can freely alter where the arrows point! Compared to array and ArrayList, the arrows cannot be changed.

    As you can quickly see, removing an object, is simply "dropping" it by taking the arrow ahead, and assign it to point to the object behind.



    This is exactly why adding and removing is fast! All you need to do is change the arrow! No more sliding around. Also, you might not notice right away, this allow us to have exactly the space needed. If there is an extra object, we just make a new variable, and point a arrow at it. This means, no more resizing as well!

    Before I show you guys the code for this wonderful data-structure, we must first understand what is the Node Object. If you look at the two pictures above, a Node is simply a rectangle with an item (in our example, a number), and an arrow that points to something (the box with cross in the end means null). So the first picture has three nodes, and the second one has only two (since we just "dropped" one).

    Nodes can generally be implemented like so:

    PHP Code:
    final class Node{

        private var 
    item:Object null;
        private var 
    next:Node null;
        
        public function 
    Node(_item:Object){
            
    item _item;
        }

        public function 
    setNext(_next:Node):void{
            
    next _next;
        }

        public function 
    next():Node{
            return 
    next;
        }

        public function 
    item():Object{
            return 
    item;
        }

        public function 
    setItem(_item:Object):void{
            
    item _item;
        }


    2.1.3.2 Double-Linked-List

    Notice the above structure allow easily allow us to find the next Node, which is where the arrow point to. But what if we also need to know the node before? Well take a look at this:



    This is a Doubly-Linked-List. We will be using this to implement Stack and Queue which is vital to all Search Algorithms. If anyone is interested, I can post the implementation of Doubly-Linked-List here; it will also implement the List interface and also the Iterator interface. (Let me know by post down below)

    2.1.4 Stack

    Stack is a Last-In-First-Out (LIFO) data-structure. It implies that we do not have the freedom to insert or remove at the middle of the list. The only methods to add and remove are:

    PHP Code:
    public function push(item:Object):Boolean{
        return list.
    add(item);
    }

    public function 
    pop():Object{
        var 
    temp:Object = list.get(list.length() - 1);
        if(list.
    removeAt(list.length() - 1)) return temp;
        return 
    null;

    If the pop() method returns null, that means the stack is empty. Both of the above method are constant time complexity, meaning no matter the size of the stack, adding and removing only takes 1 operation. Visually, this looks like this:



    We always operate at the tail of the list; both adding and removing starts from the back. So push() will append one item to the back while pop() will take one item out (remove from list). This structure is used in:

    • Depth First Search (DFS)
    • Iterative Deepening Search (IDS)
    • Branch and Bound Search (B&BS)


    2.1.5 Queue

    Note: This entire section (and all of the following sections) and the previous (Stacks) one will not show the AS3 implementation until I have finish my implementation of heap.

    Queue is a First-In-First-Out (FIFO) data-structure. This is very easy to remember - when you line up for something (queuing), who ever is in front of you (arrived earlier than you) will be served before you. So think of this as a lineup for bus.

    more coming soon...

    2.2 Graphs

    WOW! That was a long first section of Chapter 2. There is, however, one more chapter of some what less interesting concept that is required, before we actually jump into AI. Before you skip over this section, you need to make sure you understand Graph Theory. Or else what follows will be more difficult than it needs to be.

    The reason we need to understand Graphs is because it provide a nice pictorial representation of states. A state for now, will loosely define as specific status of a world. A world can be interpreted as the problem we are trying to solve. For example, lets assume we are making an AI for a Chess game. The world will simply be the Chess game. A state, therefore, is a specific setup for the game (the world) - all the position of the pieces. And yes, the state will change if anyone of the piece change its position (ie anyone makes a move). Let's look at the picture below from Wikipedia:

    Each circle here is a world, and the line connecting each world is possible change that lead to another world. Formally, we want to say:

    • The entire picture is called a Graph.
    • Each circle is called a Node, representing a world.
    • Each line is called an Arc from x to y written: arc<x, y>, which connects two and only two worlds.
    • Sometimes a graph will have cycles (3-4-5-2 in our example)
    • Usually in AI, going back and forth between the same worlds does not make sense; in fact, it usually indicate a faulty algorithm!
    • Each arc can be interpreted as a "choice" when applicable
    • In AI, graphs will always have a clear starting point called: Start Node
    • In AI, graphs will have at least one goal (ending point) called: Goal Node

    So given the above description, the process of solving something can be represented by some starting node, and a pathway to the goal node. For example, a Chess game will have a starting node with all the pieces in their starting position and the goal node is a world where the enemy's king is removed from play by one of your piece. Perhaps now, it is clear why Graph Theory is required to proceed - one way to solve a problem is to begin at the starting node and generate all possible pathways to the goal node and see which pathway is correct, or most optimal in terms of length or cost, if there exists any.

    2.3 AI as Search

    AI as search can actually solve MANY problems. It comes from a simple idea: if we do not know the answer, search it until you find it! On the surface this may seem like a brute force method that would probably take 100 years. I am not joking about the 100 years. I will give you an example:


    Sudoku is a board game that can be played by filling in numbers from 1 to 9. The board is divided into 9 chunks with each a 3X3 boxes arranged in a 3X3 fashion. Each box must be filled with numbers from 1 - 9 without repeating. Additionally, the numbers can not be reused vertically, horizontally, and in the local 3X3 chunk. Here's am image:



    It can be extended beyond 3X3 chunks of 3X3 blocks using more than 9 numbers. Here's an example:



    Since the objective of the game is to fill in numbers without violating the rules, a very simple "AI" can be randomly guessing a number say from 1-9 for the standard Sudoku board and then check if any of them violates the rules. If any rules are violated, repeat! On a MacBook Pro 13" with Intel Core 2 Duo processor running @ 2.26Ghz, this would literally take roughly 100 years of constant computation to find a correct solution. Of course if you only leave 1 empty space for the computer to guess, then it would only take maybe 1 minute. But you get my point

    Sudoku can actually be solved efficiently by Constraint Satisfaction. I wrote one in Java that solved one of the hard Sudoku in under 5 seconds! We shall return to this in the next Chapter.
    While searching can be a type of brute force but some can actually be successful! The best example is the "Deep Blue". Google it and you will know what it is! However, for AS3, we do not have the resources to brute force search. However, we can "smartly" search many things by using the following techniques:
    • Depth First Search
    • Breadth First Search
    • Iterative Deepening Search
    • Best First Search
    • Cost Functions
    • Least Cost First Search
    • A* Search
    • Branch and Bound Search
    • Iterative Deepening Search Star(*)

    Before applying those techniques, you must first convert your problem into a search-able problem. In the case of Sudoku, not only is it a Constraint Satisfaction, but also Search problem. The combination is known as Constraint Satisfaction and Domain Splitting. The "conversion" is simply by treating each Sudoku board as an individual object and put it inside a Node (also called vertex in Math, but we will call it a Node here) on a Graph. Each Arc from a Node to another is simply a SINGLE STEP transition of the board. What I mean by single step is that only 1 number (including blanks) is changed (or filled in the case of blanks). This single step thing is very common in AI Search using Graphs.

    As a result, many AI as Search problems distinguishes a Start Node, one or many Goal Node(s), and Arcs from one (and only one) Node to another. Under such context, search techniques are simply ways to navigate between the Start Node and the Goal Node(s). We shall begin with the simplest technique, Breath and Depth first search. While they are simple, they are fundamental and important. Keep in mind that Nodes are sometimes refereed as States or Worlds depending on the context. In our case, we will always use Nodes since it is what it will be inside a problem. States and Worlds are put inside this Node object while we search

    2.3.1 Depth & Breadth First Search

    Here's an example of what a real life AI Graph would look like:

    The above is a map of Germany. Each Node is simply a location, the Arc costs are distance between each location, and there is also a cycle - meaning we can go around and around and never having to stop!

    Given that graph, a typical AI question would be: "What's the shortest distance from A to B?"; "What is the shortest path (Arc) if one were to go to every location and back to the beginning?";

    Immdiately we think of ways to "navigate" through that "map" by means of looking at each path (Arc) (Don't tell me you did not think of that when you saw the question "how to go from point A to B"). We first set a Start Node, say Frankfurt. We then need a Goal Node, say Kassel. Depth First Search (DFS) would simply try one path (usually the left most, but this is a choice made by the programmer), and go ALL THE WAY until you find your target. If you reached a dead end, simply try the last Arc you split. Breadth First Search (BFS) on the other hand, will try each possible path one at a time. Let's look at them closer:


    Keep in mind that DFS has the "dump" character of always picking one way. If we pick left, it will ALWAYS go left until it is impossible. The following example should help you understand.

    Depth First Search picking the left Arc would be:
    • Frankfurt - START
    • Mannheim - ONLY ONE CHOICE TO CONTINUE
    • Karlsuhe - ""
    • Augsburg - ""
    • Munchen - THE MIDDLE PATH IS MORE "LEFT" THAN THE RIGHT, PICK THAT ONE
    • Nurnber
    • Wurzburg
    • Erfurt - DEAD END! GO BACK THE LAST TIME WE SPLIT, WHICH IS Wurzburg
    • Wurzburg - BACK TRACK
    • Frankfurt - BACK TO BEGINNING
    • Continue like above FOREVER!!!
    • Computer explodes due to mindless loop



    Depth First Search picking the right Arc would be:
    • Frankfurt - START
    • Kassel - GOAL FOUND



    Why isn't there a Middle choice example? Because the middle is not well defined. Each Node may have more than one Arc to another and it varies from Node to Node. The definition of middle, therefore, will not be the same for each Arc. For example, a Node to the next has 3 Arcs. The middle is obviously the 2nd Arc. However, that next Node has say 4 Arcs. The middle may not be so clear since we now have two Arcs that sits in the middle.

    This is not impossible to wirte an algorithm for. However, it is unnecessarily complex.

    Side Track

    Notice the HUGE difference between picking left and right. Knowing which way to pick is often up to God in Computer Science. If God does not exist, we either pick one just because, or we leave it up to the Random Number Generator. Such decisions may affect the outcome greatly as shown above. This choice character of an algorithm is what is known as Deterministic Algorithms - it always stick to one choice in a predictable manner. The irony of the problem is that if we were to find out which choice is the best choice, we would of already solved the problem or solved enough of the problem that it is very easy to find the answer. Most of the cast, finding this best choice is NP-Complete (a set of VERY VERY VERY VERY hard problems to solve for computers and sometimes even for humans!), but verifying the answer(s) may not be in NP-Complete. In English, it means these problems requires a "smart" choice at every junction, not some silly rule that says "ALWAYS CHOOSE ______" (fill in the blank). Knowing which choice to make, often means you know the answer

    End of Side Track
    From the above example, we may conclude the following:
    • DFS Cannot deal with cycles. If it gets "trapped" inside a loop, it stays forever!
    • With A LOT of luck, it can solve problems quickly. This implies that it is not very efficient.
    • It is VERY simple! Make a choice, then always stick to it till you find the answer or never.
    • This last point may not be intuitive, but it is true. DFS saves A LOT of space in terms of memory during the search. But we will get to the details when we talk about the algorithm for DFS.


    Formally for DFS: (Will be in more detail when in Algorithm section)
    • Completeness - No, DFS does not halt if Goal Node is not in a cycle while the search is "trapped" inside one.
    • Optimality - No, DFS does not always find the shortest or best solution
    • Run Time Complexity - O(b^m) where b = Branching Factor - the largest # of Arcs leaving a single Node. m = height of the graph - the longest sequence of Nodes in terms of Arcs
    • Space Complexity - O(bm) where b and m are same as defined above


    On the other hand, we have Breadth First Search (BFS). This method provides a very nice property - it always returns an answer if there is one, and the answer is always optimal in terms of length or cost if the Arcs in the Graph represent length or cost respectively. While the nice property may lead people to think that BFS is complex, it is not the case. BFS works by keeping a list of Nodes to search next. For example, at the very beginning, there is only one item in the list - the starting Node. As the search progress, the list expands. We call this list The Wave-Front or Frontier. Here's a picture to demonstrate:

    Additionally, BFS goes in ALL possible direction. Unlike DFS, which goes very "deep" before going "wide", BFS goes "wide" then "deep". Therefore, if there is an answer somewhere that is very close to the start, it will ALWAYS be found first than the other answers far away (deeper). Since BFS expands in all directions, it is never caught in any cycles. There is one exception: if the graph has cycles in ALL possible directions AND IT DOES NOT HAVE AN ANSWER ANYWHERE.

    Formally for BFS: (Will be in more detail when in Algorithm section)
    • Completeness - Yes, if there is an answer, BFS always finds it even if all directions have cycles.
    • Optimality - Yes, it finds the optimal solution given that the Arcs are length or cost related
    • Run Time Complexity - O(b^m) where b = Branching Factor - the largest # of Arcs leaving a single Node. m = height of the graph - the longest sequence of Nodes in terms of Arcs
    • Space Complexity - O(b^m) where b and m are same as defined above


    Right away, we see that BFS gained the advantage of Completeness and Optimality at the cost of increased Space Complexity. Depending on the situation, DFS and BFS has their own uses.

    2.3.2 Depth & Breadth First Search Implementation and Usage
    ...Coming Soon


    Constraints and Features
    coming soon...
    Last edited by ChaoSXDemon; April 25th, 2011 at 08:48 PM. Reason: Update 04/22/11

  3. #3
    Logical Inference
    coming soon...
    Uncertainty
    coming soon ...
    Last edited by ChaoSXDemon; December 13th, 2010 at 12:59 AM.

  4. #4
    Planning
    coming soon...
    Learning
    coming soon...
    Last edited by ChaoSXDemon; December 13th, 2010 at 01:00 AM.

  5. #5
    24
    posts
    Registered User
    Well, I am. Actually, I've already given up on some game ideas because they'd require programming an AI and I had no idea where to begin, and couldn't find any "AI for Dummies" links on Google. (But maybe I'm stupid and can't search, that's also a possibility.)
    So, your fangirl count went up by one, aren't you happy?

    (There's no need to write so big, though.)

  6. #6
    Quote Originally Posted by ChaoSXDemon View Post
    Anyone interested in this? Because this actually takes a lot of effort to write, and if no one cares, then I suppose I'll just keep the knowledge for myself

    I'm interested too!

  7. #7
    I've bookmarked this actually, I'm interested in seeing other peoples implementation of any kind of AI, I'm looking forward to some code (That may sound wrong, but take it as you will).

    Keep at it! Please

  8. #8
    973
    posts
    Registered User
    I am very interested! I didnt respond earlier because i didn't want to spam up your post with comments. But now i see you have reserved slots to update. So please continue!

  9. #9
    look s very interesting

  10. #10
    Awesome Will continue to update

    Also, if there is any comments about the guide, please do post them up. It would be great if someone has feedback on the whether if the guide is too detailed, or lacking detail; some explanation are unclear ect.
    Last edited by ChaoSXDemon; December 20th, 2010 at 01:45 AM.

  11. #11
    (There's no need to write so big, though.)
    What do you mean write so big?

  12. #12
    24
    posts
    Registered User
    What do you mean write so big?
    That you're using a font size bigger than the default one starting in section 2.1 and onwards. There's no need to do that.

  13. #13
    Any feedback is welcome! Let me know if any section is too long or too short or unclear. Also if you guys want me to put up more code or any examples you want me to do! So far, I plan to do Sudoku solver as an example for Constraints and Features; maybe even the game in Flash!

  14. #14
    that's cool i wanted read next

  15. #15
    I still have this bookmarked hoping for an update sooner or later, are you still alive and kicking ChaoS?

Page 1 of 2 12 LastLast

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Home About kirupa.com Meet the Moderators Advertise

 Link to Us

 Credits

Copyright 1999 - 2012