Searching and Game Playing in AI PDF

IT2206 Searching and Game Playing in AI which node they expand first. The following are some of the uninformed search Rationale for Searching in AI strategies and techniques (Russell & Norvig...

IT2206 Searching and Game Playing in AI which node they expand first. The following are some of the uninformed search Rationale for Searching in AI strategies and techniques (Russell & Norvig, 2022): The process of searching in artificial intelligence (AI) may involve observable, Breadth-first Search – This search process checks all the nodes per deterministic, static, known environments where the solution is a sequence of level, starting at the left working towards the right side of the tree, before actions. In most cases, AI problems are initially handled through the process searching the tree one level deeper. This search algorithm can provide a of finding a good state without worrying about the path to get to the goal, solution with the minimum number of steps from the initial state. It is also covering both discrete and continuous states. In a nondeterministic a simple search that can be applied to any search problem. However, its environment, an agent will need conditional plans and carry out different complexity still depends on the number of nodes. The simple pseudocode actions depending on its observations (Russell & Norvig, 2022). below encompasses the algorithm for the breadth-first search. Searching in AI is defined as a sequence of steps that creates a path between the initial state and the goal state. Different algorithms may be utilized in order to perform searching. In an environment, search algorithms generally treat states and actions as atomic – without any internal structure. Terminologies in Searching The following are the common terminologies that can be encountered in searching strategies and techniques in artificial intelligence: Search algorithm – This takes a problem as an input and returns a solution or an indication of failure. Search tree – This is commonly used to illustrate paths between states, towards a particular goal. It may contain multiple paths to any given state, Figure 1. A search tree that encompass breadth-first search. Source: Artificial Intelligence Basics: A Self-Teaching Introduction, 2020 p. 29 but each node in the tree has a unique path back to the root. Root – In a search tree, this corresponds to the initial state of the problem. Step 1: Put the initial node on a list (START). Nodes – In a search tree, these correspond to the states within the state Step 2: If (START is empty) or (START = GOAL), space of the problem. then terminate the search. Edges – In a search tree, these correspond to the available actions Step 3: Remove the first node from START and call node A. Step 4: If (node A = GOAL), then terminate the search with success. relative to the problem. Step 5: Else, if node A has successors, generate all of them Search data structure – This is required to keep track of the search tree. at the end of the list (START). Each node in the tree may be represented by a data structure with four (4) Step 6: Go back to Step 2. usual components: node.STATE, node.PARENT, node.ACTION, and node.PATH-COST. Depth-first Search – It is one of the main search processes used in AI. The process starts at the root of the tree and down to the left branch until Note: Some of these terminologies can also be encountered in Theories of it gets to the bottom node. If the goal state is not reached, the process Computations with Automata. goes back up and tries the next branch. The process continues until the goal state is reached. This search algorithm goes deep into the tree as Search Strategies and Techniques fast as possible, but does not guarantee an optimal path. Time complexity Uninformed search involves algorithms that do not have any domain-specific and space complexity are the most important factors to consider in dealing knowledge. This search proceeds in a systematic way of exploring nodes in a with this specific algorithm. The following pseudocode encompasses the predetermined order. Algorithms in uninformed search may differ based on algorithm for the depth-first search. 03 Handout 1 *Property of STI  [email protected] Page 1 of 5  IT2206 Informed search, also known as heuristic search, involves domain-specific knowledge and allows access to additional information, such as pattern databases with solution costs, that improves the search process. This search encompasses the exploration of nodes that are most likely to be nearest to the goal state. Heuristic search utilizes heuristics as an evaluation function. Heuristics are approximates that are used like guides pointing in a general direction, but may miss certain paths. Techniques that involve heuristics are considered vulnerable since they are prone to combinatorial explosion. The following types of problems utilize heuristic searches (Gupta & Mangla, 2020): Figure 2. A search tree that encompass depth-first search. i. Problems for which no exact algorithms are known, but approximation Source: Artificial Intelligence Basics: A Self-Teaching Introduction, 2020 p. 27 can be applied. ii. Problems for which exact solutions are known, but the computations Step 1: Put the initial node on a list (START). cannot be practically produced. Step 2: If (START is empty) or (START = GOAL), then terminate the search. Step 3: Remove the first node from START and call node A. Below are some of the informed search strategies and techniques (Gupta & Step 4: If (node A = GOAL), then terminate the search with success. Step 5: Else, if node A has successors, generate all of them and add them Mangla, 2020). at the beginning of the list (START). Best-first Search - It is a general strategy used in searching. On each Step 6: Go back to Step 2. iteration of this search algorithm, the node with the minimum evaluation function value is selected. If the search has not yet reached a goal state, Iterative Deepening Search – This search process combines many the process expands and child nodes are generated. Each child node is advantages of the depth-first and breadth-first search. The memory added at the priority queue if it has not been reached before or is re-added required in this search is relatively moderate. It is optimal for problems if it is currently being reached through a path that has a lower cost than where all actions have the same cost. Each iteration generates a new level any of the previous paths. The simple pseudocode below encompasses or performs search per level, in the same way that breadth-first search is the algorithm for the best-first search. performed, but without storing all nodes in memory. Bidirectional Search – It encompasses a distinctive process that Step 1: Put the initial node on a list (START). simultaneously searches forward from the initial state and backwards from Step 2: If (START is empty) or (START = GOAL), then terminate the search. Step 3: Remove the first node from START. Call node A. the goal state(s), with the anticipation that the two (2) searches will meet. Step 4: If (node A = GOAL), then terminate the search with success. It technically replaces a single search tree with two smaller sub-trees and Step 5: Else, if node A has successors, generate all of them. Find out how far terminates when the two graphs meet. In most cases, this search each successor node is from the GOAL. Sort all the generated algorithm can reduce the cost of exploration. Note that there are different nodes by the remaining distance from the GOAL. variants of bidirectional search. Step 6: Name the new sorted list as START1. Uniform-cost Search – This search process can be considered as a Step 7: Replace START with START1. variant of the Dijkstra’s algorithm. The complexity of this search can be Step 8: Go back to Step 2. characterized through the cost of the optimal solution. The search process spreads out in waves of uniform path-cost. It considers all paths Hill Climbing Search– It is a search technique for finding the maximum systematically in terms of increasing cost, making it a comprehensive and or the minimum of an evaluation function. This is considered an cost-optimal search. On the other hand, this particular algorithm can also irrevocable scheme since it does not allow shifting back to previously be implemented as a best-first search with a path-cost as an evaluation suspended alternatives, even if it may have offered a better alternative function than the one at hand. This search only requires little memory, since 03 Handout 1 *Property of STI  [email protected] Page 2 of 5  IT2206 alternatives are not stored for future consideration. A solution is not the ability to learn. In general, successful gaming requires intelligence (Gupta guaranteed since the search process can be stuck on a plateau or even & Mangla, 2020). follow an infinite uncontrolled path, unless the heuristics are very informative. The simple pseudocode below encompasses the algorithm for Computers can be programmed to play games such as tic-tac-toe, checkers, hill climbing search. chess, and Go. The board configurations in playing these games can be easily represented through programming codes that does not require complex Step 1: Put the initial node on a list (START). formalisms (Gupta & Mangla, 2020). For AI researchers, the simple and Step 2: If (START is empty) or (START = GOAL), then terminate the search. deterministic nature – perfect information or fully observable – of these games Step 3: Remove the first node from the START. Call node A. is an advantage. The states of a game are easy to represent, and the agents Step 4: If (node A = GOAL), then terminate the search with success. Step 5: Else, if node A has successors, generate all of them. Find out how far are commonly bounded to a minimal number of actions whose effects are each successor node is from the GOAL and defined by fixed rules (Russell & Norvig, 2022). On the other hand, solving add them at the beginning of the START. complex AI problems and creating complex AI games require numerous Step 6: Go back to Step 2. techniques and heuristics. A* Search – This is the most common informed search technique that Below are the reasons why game playing serves an important role in AI uses the evaluation function: f(n) = g(n) + h(n), where g(n) is the path- development (Gupta & Mangla, 2020). cost from the initial state to a specific node n, h(n) is the estimated cost of i. Games visualize and manifest real-life situations in a constricted the shortest path from node n to the goal state, and f(n) is the estimated manner and permits simulations. cost of the best path that continues from node n to the goal (Russell & ii. Games provide a well-structured task where success and failure can Norvig, 2022). The algorithm used in A* search combines the features of be measured with the least amount of effort. a uniform-cost search and a pure heuristic search to efficiently compute iii. Extensive amount of domain-specific knowledge is infrequently for the optimal solution. needed because of the limited rules of games. Beam Search – This is a search technique that utilizes heuristics to trim the state space and turn it into a small number of nearly optimal Game theory is a branch of applied mathematics that encompasses a alternatives. This implements the breadth-first search in building the theoretical framework that abstracts social situations of multiple agents search tree. Successors are generated for each state at the current level, (competing players) in a well-defined environment. This can also be sorting those states in an increasing order based on their heuristic cost. considered as the science of strategy or the optimal decision-making of However, it only stores a predetermined number of best states at each independent and competing agents in a strategic environment. Some of the level, called the beam width, and only those states are expanded. basic terminologies that can be encountered in studying the game theory are Constraint Satisfaction – It is a search strategy that deals with as follows (Hayes, 2022): constraints that are the same as the ones that can be encountered in the Game – An environment that involves a set of circumstances that can real world. Constraints can either be temporal or tangible. Either way, produce a particular result dependent on the actions of two (2) or more dealing with constraints poses a varying degree of success. Extensive players. domain-specific and heuristic knowledge are needed in dealing with this Players – These are the strategic decision-makers within the game. kind of search strategy. Strategy – It is a complete plan of action of a player that considers the set of circumstances that may occur within the game. Rationale for Game Playing in AI Payoff – It is something quantifiable that a player can receive in arriving Game playing exhibits different aspects of intelligence, particularly the ability at a particular outcome. to plan at an immediate tactical level and/or for long-term strategic level and 03 Handout 1 *Property of STI  [email protected] Page 3 of 5  IT2206 Information Set – This encompasses the available information at a of the game and the arcs represent the possible moves by the players. Every particular point in a game, which is commonly utilized in games that has game begins with specific rules and a set of possible moves. Hence, sequential components. considering all the possible moves at each state leads to the game-tree Notion of Equilibrium – It is a point in a game where both players have development (Gupta & Mangla, 2020). made their decisions or moves and a particular outcome is reached. Games can be classified as either single-player (single-agent) or multi-player There are at least three (3) viewpoints that can be derived in an environment (multi-agent). For single-player games like the 8-puzzle and the Rubik’s with multiple agents, such as games. Below are the viewpoints (Russell & Cube, the common search strategies and techniques, such as the best-first Norvig, 2022). and A* search, are utilized in identifying clear paths. On the other hand, multi- 1. If the total number of agents is very large, then it is possible to consider player games like checkers and chess, where players try to outsmart their the agents as an aggregate – an economy. opponent(s) and obtain the maximum benefits, encompass different ways of 2. Considering the argumentative – adversarial agents as part of the evaluating the situations. environment, even if it makes the environment nondeterministic. 3. Explicitly model adversarial agents with a specific search strategy or The basic strategies for game playing are as follows (Gupta & Mangla, 2020; technique. Russell & Norvig, 2022): Minimax strategy – This is a well-known strategy for two (2) player Game Playing Components games, where one player is identified as a maximizer (MAX) and the other The following are the two (2) major components of a game playing program as a minimizer (MIN). The main objective of this strategy is for a player to (Gupta & Mangla, 2020): minimize loss and maximize benefit. Therefore, the move that leads to a A plausible move generator: If the number of permissible moves is too terminal state with maximum payoff, under the assumption that the high, then it is impossible to perform a full-width search to a depth opponent plays to minimize payoff, can be considered optimal. adequate enough to have a good game. A plausible move generator is considered an important search alternative in such domains. The process expands only the selected moves. It is not possible for all moves to be examined, since the given amount of time for a specific move is limited and the available computational power is also limited. However, further researches are being conducted aiming to enhance computational power using parallel processing architectures. A static evaluation function generator: This is the most important component of a game playing program. It is used to evaluate every move that is being made. A static evaluation function generator holds a crucial role since it utilizes heuristic knowledge for evaluating and it acts like a pointer towards a plausible move generator that will generate the future paths. This can also be considered as a limiting factor in a search algorithm. Thus, a good static evaluation function generator should be very fast. Game Playing Strategies Possible game states/conditions can be represented using a directed graph, Figure 3. A partial game tree for tic-tac-toe. commonly called a game tree. The nodes of a game tree represent the states Source: Artificial Intelligence: A Modern Approach (4th ed.), 2022 p. 194 03 Handout 1 *Property of STI  [email protected] Page 4 of 5  IT2206 The top node in indicates the initial state. The MAX moves first, placing an x mark on an empty square. The game tree shows alternating moves by MAX and MIN, until a TERMINAL state (true when the game is over and false otherwise) is reached, which can be assigned utilities or payoffs according to the rules of the game. The algorithm for the minimax strategy begins at the current position and implements the plausible move generator to generate a set of possible successor positions. A static evaluation function is then applied to those positions. Then, the best successor will be chosen and its value will be placed back up to the starting position to represent the evaluation. Alpha-beta pruning – This is a minimax strategy with alpha-beta cut-offs. A slight modification in the search procedure is necessary in order to handle both maximizer and minimizer. This strategy requires the maintenance of two (2) threshold values: o Alpha – It represents the lower bound value that a maximizing node may be assigned. Thus, representing the minimum score that the maximizer is assured of. o Beta – It represents the upper bound value that a minimizing node may be assigned. Thus, representing the maximum score that the minimizer is assured of. This strategy is strongly affected by the order in which game tree branches are explored. For the minimizing nodes, the score computed starts with positive ( + ) infinity and decreases with time. For maximizing nodes, the score computed starts with negative ( - ) infinity and increases with time. The number of nodes at a game tree is exponential in depth, and no algorithm can completely eliminate the exponential factor. However, it can sometimes be cut in half by computing the correct minimax without examining every state and pruning large parts of the game tree that does not affect the outcome. References: Gupta, N. & Mangla, R. (2020). Artificial intelligence basics: A self-teaching introduction. Mercury Learning and Information LLC Russell, S. & Norvig, P. (2022). Artificial intelligence: A modern approach (4th ed.). Pearson Education Limited Hayes, A. (2022, February 02). Game Theory in Investopedia.com. Retrieved on March 2, 2022 from https://www.investopedia.com/terms/g/gametheory.asp 03 Handout 1 *Property of STI  [email protected] Page 5 of 5