The purpose of this articile to explain to the user the importance and the essential features of the following algorithims. 1) MinMax Algorithm,2) Alpha-Beta Pruning Algorithm and 3) AC 3 Algorithm.
MENU 1) Steps for installing firestarter (fire wall) on Ubuntu 5.10 2) Shell Scripting with Linux/Unix 3) Shell Scripting with Linux/Unix ( Part 2) 7) Computer Security ( Bell LaPadula Model) 8) Critical Essay and Analysis Part 1. 9) Critical Essay and Analysis Part 2 11) Artificial Project 1 Uninformed and Informed Search Algorithms. 13) Explicit and Implicit DLL Linking 15) CS8803 AIA @ Georgia Institute of Technology 16) CS 8803 Week 3 Paper Critque
| MinMax Algorithm: The gist of the algorithm is that there is a utility function that assigns a pay off value to each leaf in the tree. 1) The value from the leaf flows upwards to the root(the state under consideration) according to some rules based on min and max criteria.
3) Note: Max is currently the player about to make the move. The state of the game at this point is represented as a root.
The figure above explains how the algorithm works: 1) The leaf nodes are assigned the values ( 3, 18, 5) (1,15,42) (56,-12,-5) 2) Min makes a move from ( Min-Max), and hence will choose that node which minimize Max's score. Hence from the option available of ( 3,18,5), MIN will choose 3. Similarly 1 from (1,15,42) and -12 from (56,-12,-5). 3) Max on the other hand will choose that option which will maximise his score. Therefore from the option of ( 3,1,-12) he will choose 3. Hence the root node is selected with 3.
Time and Space Complexity with MiniMax Algorithm: Time: All the nodes need to be generated before the AI agent can make a decision. Hence the Big O for time complexity is O(b^m) where b is the branching factor of the tree and m the depth of the tree. Space: Once the AI(max) agent makes the decision or knows which node to choose next, keeping other choices of Max at that level is not required. Hence the AI agent can get rid of them. Therefore the Big O notation for space is O(bm) where b is the branching factor and m is the depth of the tree. Links: Alpha Beta Pruning Algorithm: At its core, the Alpha Beta Pruning algorithm is very similar to the MiniMax algorithm except for some subtle intelligence reasoning. Consider the following tree structure: (max) B (min) C1 C2 C3 (max) D2 Note: for clarity sake, C1, C2, C3 are children of B. D2 is child of C2. This is how the algorithm works: 1) B is the max node. This means, B will take the maximum value of (C1,C2,C3) 2) D2 is child node of C2. C2 is min node and takes the minimum value of its children. 3) Consider that C1 has a value of 40 assigned to it. B gets 40. 4) Now if the child of C2 i.e. D2 has a value of 20. As D2 has a value of 20, the maximum value C2 can take is 20 and no value greater than that. If C2 has the following children (D2, D3, D4, D5) it doesn't matter what values D3, D4 and D5 have because C2 will take the min ( D2, D3, D4, D5) and what ever value C2 takes, it wont be greater than 20. Because it wont be greater than 20 and because it will be less than 40, B still has the value of 40 and the rest of the children of C2 can be safely ignored. In other words, we dont need to compute the values of all the grand children. We need to compute only until we find a value lower than the highest child value. The ordering of children is important for the maximum efficiency of the alpha-beta pruning algorithm. The working of the algorithm is nicely summarized in the following figure: (X in the figure means, no need to search that portion/children of the tree)
(Adobe Flash Player Required) The complete tutorial is available on this website: http://www.ndsu.nodak.edu/instruct/juell/vp/cs724s01/alpha/alpha.html Links for Alpha-Beta Pruning Algorithm: 1) Excellent information on Alpha-Beta Pruning 2) Nottingham University CS dept AC 3 Algorithm: The AC 3 algorithm is part of the CSP (Constraint Satisfaction Problem) family. Please do read up on CSP before reading on this section. The idea behind the AC 3 algorithm is to check for arc consistency between two variables under consideration. Lets consider the two variables as Xi and Xj. The algorithm traverses through all the nodes/elements of Xi, and for each node of Xi it checks if there exists atleast one element in Xj for which arc consistency is valid. If no such element is found in Xj, then that element of Xi is deleted. So far so good, but on deleting this element from Xi, we need to add all the arcs that exist between (Xk, Xi) where Xk are all the neigbours of Xi in the queue. Why? The reason to this is that by deleting the element from Xi, we might have created arcs inconsistency between (Xk, Xi). If yes, then those elements in turn need to be deleted from Xk. Pseudocode for the algorithm can be found here @ Wikipedia. |