Introduction to AI, AI Techniques PDF

AI, AI problems & Techniques Prof M.Shashi Andhra University, Visakhapatnam Definition Field of Computer Science that emulates human intelligent behaviour AI is the study of how to make computers do things which, at the moment , people do better. But Modern AI...

AI, AI problems & Techniques Prof M.Shashi Andhra University, Visakhapatnam Definition Field of Computer Science that emulates human intelligent behaviour AI is the study of how to make computers do things which, at the moment , people do better. But Modern AI systems can do much beyond. Problems that couldn’t be solved by an individual are also solvable by AI systems AI problems or tasks- categorization Difficulty order Mundane tasks Difficulty order decreases for AI sys increases for humans Perception Vision, Speech Natural Language Understanding, Generation, Translation Common sense Reasoning General problem solving Robot Control Formal tasks Games Chess,Backgammon, Checkers-Go, etc. Mathematics Geometry, Logic, Integral calculus Expert tasks Engineering Design, Fault analysis, Manufacturing planning Scientific Analysis Medical Diagnosis Finacial Analysis Physical Symbol system Hypothesis A physical symbol system (PSS)consists of : A set of symbols / physical patterns that can occur as components of another entity called expression or symbol structure Such symbolic structures are composed of a number of instances of symbols related in some physical way At any instance of time the system contains a collection of such symbolic structures PSS also contains a collection of processes that operate on structures (expr) to produce other structures (exprs) for creation, modification, reproduction, and destruction. PSS is a machine that produces an evolving collection of symbol structures through time Such a system exists in a world of object wider than just those structures PSS hypothesis: A PSS has Necessary and sufficient means for general intelligent action. Role of Knowledge Knowledge is essential and indispensable for intelligent action Challenging properties of Knowledge: Voluminous Hard to characterize accurately Constantly changing Differs from data by being organized in a way that corresponds to the ways it will be used AI Technique AI technique is a method that exploit knowledge by representing it in such a way that: it captures generalization by grouping together similar situations It is interpretable easily by the knowledge providers Easily modifiable to correct errors and to reflect changes Can be used in many situations even with a possible uncertainty Helps to narrow down the range of possibilities to be considered  X X Tic-Tac-Toe problem O - - Solution 1 O Data structures for Representation: Board 9-ele Vector of ternary symbols with i-th ele indicates the symbol at tha position Contents of each location can be either a X, O or Blank Movetable: A large array of 19,683 (39 )elements each indicating the next best move for the board position corresponding to the index of the element. Algorithm: Find the number (n) corresponding to the present board position. Find the 9-ele vector (v) of the Movetable at the index =n Determine the board position in v that is different from the present board position and apply the move to make the present board position same as v. Analysis: Highly efficient, but requires lot of human effort to find the next best moves for each possible board positions It also requires lot of memory space Solution is not at all flexible for adopting it to other versions of the problem like 3-D or 5 x 5 matrix Tic-Tac-Toe problem - Solution 2  Tic-Tac-Toe problem - Solution 2-Algorithm contd… The algorithm has a built-in strategy for each move as given below: Uses odd numbered moves to play with X and even numbered moves for playing with O. Turn # Description of the move 1 X Go(1) fill upper left corner 2 O If Board is blank, Go(5), else Go(1) 3 X If Board is blank, Go(9), else Go(3) 4 O If Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2) (returns 5 or any non-corner cell, if it is blank) 5 X If Posswin(X) is not 0, then Go(Posswin(X)) to WIN, else if Posswin(O) is not 0, then Go(Posswin(O)) to BLOCK, else if Board is blank, then Go(7), else Go(3) to FORK 6 O If Posswin(O) is not 0, then Go(Posswin(O)) to WIN, else if Posswin(X) is not 0, then Go(Posswin(X)) to BLOCK, else Go(Make2) 7 X If Posswin(X) is not 0, then Go(Posswin(X)) to WIN, else If Posswin(O) is not 0, then Go(Posswin(O)) to BLOCK, else go anywhere that is blank 8 O If Posswin(O) is not 0, then Go(Posswin(O)) to WIN, else If Posswin(X) is not 0, then Go(Posswin(X)) to BLOCK, else go anywhere that is blank 9 X Same as Turn 7  Comparitive Analysis of the solutions 1 & 2 Solution1 Solution2 Once the solution is available in the Solution is easy to understand and Movetable, playing the game is very fast implement and efficient. It is efficient in terms of space Disadv: requirement. Lot of human effort is required to specify the best moves for each case Disadv: Prone to error while finding the best move Solution is not fast as it has to check for or while entering in Movetable multiple conditions (8 x2 multiplications Lot of memory space required in each call to Posswin( ) function) at Does not work for more general cases like, each step. if the game is extended to 3-D or 5 x5 grid. Total strategy is fixed in advance Totally new moves have to be found starting Can not generalize to 3-D or 5 x 5 grid from scratch. Movetable size become enormous.  8 3 4 Magic Square 1 5 9 6 7 2 All rows, columns and diagonals sum up to 15 in a 3 x 3 magic square Similarly the sum of numbers in all rows, columns and diagonals in a 5 x 5 magic square is 65. Tic-Tac-Toe Problem-Solution2 with Board Rep. as Magic Square Function Posswin( ) will be called repeatedly in solution 2. It can be implemented more efficiently by Representing the board as a magic square wherein the cells are numbered to get the same total (15) along rows, columns and diagonals. Keeping the list of cell numbers captured by each player separately Posswin( ) is implemented simply by finding the sum of all pairs of cells in a list and subtracting it from 15. If the difference is in between 1 to 9, and if corresponding cell is blank, then by capturing that cell leads to WIN for that player whose list is being examined. Since no list contains more than 4 cell numbers, Posswin( ) is very fast. The solution can be extended to 3-D or 5 x 5 grid also.  Tic-Tac-Toe problem - Solution 3- AI Technique Data structures: A 9-ele vector Board representation List of legal moves to change the Board and their preconditions of applicability Heuristic function that estimates the possibility of winning for Player_1 given a Board position Algorithm: (MiniMax strategy) Examine each plausible Board position reachable from the Cur_Board position (by applying a legal move), find the BEST among the reachable Board positions and assign the rating of that Board position to the Cur_Board. Continue recursively through multiple plies by altering the criteria for selecting the BEST between Max and Min in successive plies. Propagate the ratings towards the Cur_Board and mark the Best Legal Move at each ply. Make the Best Legal Move at the root node. Analysis: The strategy is easily understandable and goes in sync with human cognition. This solution requires much more time, and may not worth its complexity for playing Tic-tac-toe. But it is a general strategy and is successfully applied to many complex 2-player games like chess, Backgammon, etc., where the previously discussed algorithms fail as they try to enumerate the solution steps in advance. 2-ply search with MinMax algorithm Criteria for Success of AI-Turing Test