Please enable JavaScript.

Coggle requires JavaScript to display documents.

Adversarial search, image, image, image - Coggle Diagram

- - - - The optimal strategy can be found from the minimax value of each node, which we express as MINIMAX, given a game tree (n). Assuming that both players play optimally from there through the finish of the game, the utility (for MAX) of being in the corresponding state is the node’s minimax value.
- - - - Chess and Checkers:
        
        Minimax Algorithm: The basic adversarial search algorithm, where the AI evaluates possible moves and their consequences several moves ahead, assuming optimal play from the opponent. Minimax helps determine the best move by minimizing the possible loss for a worst-case scenario.
        
        Alpha-Beta Pruning: This is used to cut off branches in the minimax tree as soon as it determines that they cannot possibly influence the final decision, which significantly improves the efficiency of the search
    - - Multiplayer Online Battle Arenas (MOBAs, e.g., League of Legends, DOTA):
        
        Multi-Agent Coordination: Adversarial search in MOBAs involves not only predicting and countering individual player actions but also coordinating strategies among multiple AI agents or between AI and human players.
    - - Challenges:
      - Computational Limits: The complexity of the search increases exponentially with the number of possible moves (branching factor) and the depth of the search necessary to predict future states.
      - Adapting to Human Play: Humans might not always play optimally; thus, AI systems need to adapt to unpredictable strategies and mistakes made by human players.
      - Balancing Exploration and Exploitation: In unknown game spaces or new variations of games, AI must balance between exploring new strategies and exploiting known successful strategies.
    - - Consider all the legal moves you can make.
      - Each move leads to a new board configuration.
      - Evaluate each resulting position & determine which is best.
      - Make that move.
      - Wait for your opponent to move & repeat.
  - - - Monte Carlo Tree Search (MCTS): This has been a breakthrough in playing the game of Go at a high level, notably with Google's AlphaGo. MCTS explores the most promising moves, expanding the search tree based on random sampling of the game space. It has proven effective in handling the extremely large branching factor of Go compared to chess.
  - - - Heuristic Search Techniques: Due to the complexity and the need for real-time decision-making, these games often use simpler, heuristic-driven search methods that can operate under tight time constraints. These heuristics are informed by typical game states and common strategies.
      - Scripted Strategies and Tactical AI: Predefined scripts are used to handle frequent situations, combined with dynamic adversarial search to adapt to the strategies of human players.
  - - - Imperfect Information Handling: Adversarial search in games like poker involves dealing with hidden information and bluffing. Algorithms are designed to handle uncertainty and to make probabilistic considerations about unseen cards and opponents' strategies.
      - Counterfactual Regret Minimization: A technique used in poker to improve the decision-making process by minimizing regret about decisions made in the past, based on the difference between the actual outcome and the best possible outcome that could have been achieved.
  - - - Negotiation and Trade: Advanced adversarial search strategies in such games simulate and strategize not just move efficiency but also player interactions, trade negotiations, and probabilistic outcomes based on dice rolls or card draws.
- - - - ,
        
        From the initial state, MAX has 9 possible moves as he starts first. MAX place x and MIN place o, and both player plays alternatively until we reach a leaf node where one player has three in a row or all squares are filled.
        
        Both players will compute each node, minimax, the minimax value which is the best achievable utility against an optimal adversary.
        
        Suppose both the players are well aware of the tic-tac-toe and playing the best play. Each player is doing his best to prevent another one from winning. MIN is acting against Max in the game.
        
        So in the game tree, we have a layer of Max, a layer of MIN, and each layer is called as Ply. Max place x, then MIN puts o to prevent Max from winning, and this game continues until the terminal node.
        
        In this either MIN wins, MAX wins, or it's a draw. This game-tree is the whole search space of possibilities that MIN and MAX are playing tic-tac-toe and taking turns alternately.
  - - - Utility function– Numeric value for a terminal state representing its utility for a given player.
      - Eg: In tic tac toe, the outcome is win, loss or draw with values +1, -1 or 0
- - - - Recursive Function:
        
        The alpha-beta pruning is typically implemented as a recursive function that explores the game tree depth-first, updating α and β values.
  - - - The MAX player seeks to maximize the score. At each MAX node, the algorithm updates the α value.
      - If α becomes greater than or equal to β, prune the remaining branches (beta cut-off).
    - - The MIN player seeks to minimize the score. At each MIN node, the algorithm updates the β value.
      - If β becomes less than or equal to α, prune the remaining branches (alpha cut-off).
- - - - Multiple Interacting Agents: Each agent may represent different stakeholders with varying, and possibly competing, goals.
      - Partial Observability: Unlike simpler adversarial games like chess, agents often have incomplete information about the state of the environment and the intentions or capabilities of other agents.
      - Communication Constraints: Agents might be limited in how and when they can communicate, which influences their strategies and decision-making processes.
      - Diverse Strategies: Agents can employ a range of strategies, from cooperative to competitive, depending on their goals and the goals of other agents in the environment.
    - - ,
        
        Nash Equilibrium: This is a concept from game theory where no agent can benefit by changing their strategy while other agents keep theirs unchanged. Finding a Nash Equilibrium in a multi-agent setting helps in predicting the actions of rational agents.
        
        Maximin Strategy: Extending the minimax approach to more than two players, agents try to maximize their minimum possible payoff, anticipating the worst-case scenario given the strategies of other agents.
        
        Mechanism Design: Often used in economic theory and multi-agent systems to achieve desired outcomes by designing rules and protocols that incentivize agents to behave in certain ways.
        
        Multi-Agent Coordination and Negotiation: Techniques are developed to enable agents to coordinate with each other to achieve collective goals or to negotiate outcomes beneficial to all parties involved.
    - - Minimax for Multiple Players: This is an extension of the traditional minimax used for games like chess but adjusted for multiple players, which is computationally more intensive.
      - Alpha-Beta Pruning: Can still be used to reduce the search space, but the efficiency gains are less predictable with more agents.
      - Monte Carlo Tree Search (MCTS): Popular in complex game environments like Go, MCTS can be adapted for multi-agent systems to handle larger decision spaces with randomness and probabilistic outcomes.
      - Reinforcement Learning: Agents can learn optimal strategies through trial and error interactions within the environment, adjusting their actions based on rewards and punishments.
    - - Scalability: As the number of agents increases, the complexity of the search and coordination escalates dramatically.
      - Strategy Complexity: Developing optimal strategies that consider the potential actions of multiple other agents is significantly harder than in two-player games.
      - Computational Overhead: The need to simulate or calculate outcomes for numerous possible actions by multiple agents can lead to high computational costs.
    - - .
        
        Autonomous Vehicles: Negotiating movement and routes in an environment with other autonomous vehicles and human drivers.
        
        Robotics: Multiple robots working together in industrial or exploration tasks must plan actions that consider the potential interference or collaboration of other robots.
        
        Economic Models: Adversarial search can help simulate and predict outcomes in competitive markets or auctions where multiple entities compete.
    - - 2 agents whose actions alternate.
      - Utility values for each agent are the opposite of the other which creates adversarial situations.
      - Fully observable environments.
- - - - MAX Level: The MAX player chooses the move that leads to the maximum score from the available options.
      - MIN Level: The MIN player chooses the move that leads to the minimum score from the available options.