Scribd Logo
Upload

Welcome to Scribd!

  • 32 views

    Mini-Max Algorithm in Artificial Intelligence

    Uploaded by

    CED18I054 V S PRAVEEN
    The mini-max algorithm is a recursive algorithm used in decision making and game theory. It uses a depth-first search to explore the game tree, with one player trying to maximize score and the other minimize it. The algorithm recursively traverses the tree to the terminal nodes, then backtracks to assign values at earlier nodes based on the terminal values. It runs in O(bm) time and space, where b is the branching factor and m is the maximum depth, and finds an optimal solution if both players play optimally. However, it does not scale well to complex games with large branching factors like chess due to its exponential time complexity.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Mini-Max Algorithm in Artificial Intelligence

    Uploaded by

    CED18I054 V S PRAVEEN
    32 views11 pages
    The mini-max algorithm is a recursive algorithm used in decision making and game theory. It uses a depth-first search to explore the game tree, with one player trying to maximize score and the other minimize it. The algorithm recursively traverses the tree to the terminal nodes, then backtracks to assign values at earlier nodes based on the terminal values. It runs in O(bm) time and space, where b is the branching factor and m is the maximum depth, and finds an optimal solution if both players play optimally. However, it does not scale well to complex games with large branching factors like chess due to its exponential time complexity.

    Original Description:

    slides

    Original Title

    minmaxslides-191116183058

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The mini-max algorithm is a recursive algorithm used in decision making and game theory. It uses a depth-first search to explore the game tree, with one player trying to maximize score and the other minimize it. The algorithm recursively traverses the tree to the terminal nodes, then backtracks to assign values at earlier nodes based on the terminal values. It runs in O(bm) time and space, where b is the branching factor and m is the maximum depth, and finds an optimal solution if both players play optimally. However, it does not scale well to complex games with large branching factors like chess due to its exponential time complexity.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    32 views11 pages

    Mini-Max Algorithm in Artificial Intelligence

    Uploaded by

    CED18I054 V S PRAVEEN
    The mini-max algorithm is a recursive algorithm used in decision making and game theory. It uses a depth-first search to explore the game tree, with one player trying to maximize score and the other minimize it. The algorithm recursively traverses the tree to the terminal nodes, then backtracks to assign values at earlier nodes based on the terminal values. It runs in O(bm) time and space, where b is the branching factor and m is the maximum depth, and finds an optimal solution if both players play optimally. However, it does not scale well to complex games with large branching factors like chess due to its exponential time complexity.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 11

    Mini-Max Algorithm in

    Artificial Intelligence
     Mini-max algorithm is a recursive or backtracking algorithm which
    is used in decision-making and game theory.
     Mini-Max algorithm uses recursion to search through the game-
    tree.
     In this algorithm two players play the game, one is called MAX
    and other is called MIN.
     Both the players fight it as the opponent player gets the minimum benefit while they get
    the maximum benefit.
     The minimax algorithm performs a depth-first search algorithm for the exploration of the
    complete game tree.
     The minimax algorithm proceeds all the way down to the terminal node of the tree, then
    backtrack the tree as the recursion.
    Working
     An example of game-tree which is representing the two-player game.
     In this example, there are two players one is called Maximizer and other is
    called Minimizer.
     Maximizer will try to get the Maximum possible score, and Minimizer will
    try to get the minimum possible score.
     This algorithm applies DFS, so in this game-tree, we have to go all the way through the
    leaves to reach the terminal nodes.
     At the terminal node, the terminal values are given so we will compare those value and
    backtrack the tree until the initial state occurs.
    Properties
     Complete- Min-Max algorithm is Complete. It will definitely find a
    solution (if exist), in the finite search tree.
     Optimal- Min-Max algorithm is optimal if both opponents are playing
    optimally.
     Time complexity- As it performs DFS for the game-tree, so the time
    complexity of Min-Max algorithm is O(bm), where b is branching factor of
    the game-tree, and m is the maximum depth of the tree.
     Space Complexity- Space complexity of Mini-max algorithm is also similar
    to DFS which is O(bm).
    Limitation
     The main drawback of the minimax algorithm is that it gets really slow for
    complex games such as Chess, go, etc. This type of games has a huge
    branching factor, and the player has lots of choices to decide. This
    limitation of the minimax algorithm can be improved from alpha-beta
    pruning.

    You might also like