Please enable JavaScript.
Coggle requires JavaScript to display documents.
Adversarial Search - Coggle Diagram
Adversarial Search
Alpha-Beta pruning
Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player combinatorial games
Alpha
The best (highest-value) choice we have found so far at any point along the path of Maximizer. The initial value of alpha is -∞.
Beta
The best (lowest-value) choice we have found so far at any point along the path of Minimizer. The initial value of beta is +∞.
Logic
:
The Max player will only update the value of alpha.
The Min player will only update the value of beta.
While backtracking the tree, the node values will be passed to upper nodes instead of values of alpha and beta.
Will only pass the alpha, beta values to the child nodes.
Web links
https://www.javatpoint.com/ai-adversarial-search
https://www.javatpoint.com/mini-max-algorithm-in-ai
https://www.investopedia.com/terms/g/gametheory.asp
https://www.almabetter.com/bytes/tutorials/artificial-intelligence/adversarial-search-in-artificial-intelligence
Types of games
:
Perfect information:
A game with the perfect information is that in which agents can look into the complete board. Agents have all the information about the game, and they can see each other moves also. Examples are Chess, Checkers, Go, etc.
Imperfect information:
If in a game agents do not have all information about the game and not aware with what's going on, such type of games are called the game with imperfect information, such as tic-tac-toe, Battleship, blind, Bridge, etc.
Deterministic games:
Deterministic games are those games which follow a strict pattern and set of rules for the games, and there is no randomness associated with them. Examples are chess, Checkers, Go, tic-tac-toe, etc.
Non-deterministic games:
Non-deterministic are those games which have various unpredictable events and has a factor of chance or luck. This factor of chance or luck is introduced by either dice or cards. These are random, and each action response is not fixed. Such games are also called as stochastic games.
Example: Backgammon, Monopoly, Poker, etc.
Zero-Sum Game
:
Zero-sum games are adversarial search which involves pure competition.
In Zero-sum game each agent's gain or loss of utility is exactly balanced by the losses or gains of utility of another agent.
One player of the game try to maximize one single value, while other player tries to minimize it.
Each move by one player in the game is called as ply.
Chess and tic-tac-toe are examples of a Zero-sum game.
Game tree
A game tree is a tree where nodes of the tree are the game states and Edges of the tree are the moves by players. Game tree involves initial state, actions function, and result Function.
Example: Tic-Tac-Toe game tree
Game Theory
Game theory is the study of how and why individuals and entities (called players) make decisions about their situations. It is a theoretical framework for conceiving social scenarios among competing players.
Nash equilibrium
Nash equilibrium is an outcome reached that, once achieved, means no player can increase payoff by changing decisions unilaterally.
prisoner's dilemma
The prisoner's dilemma is the most well-known example of game theory. Consider the example of two criminals arrested for a crime. Prosecutors have no hard evidence to convict them.
Min-Max Algorithm
Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-making and game theory. It provides an optimal move for the player assuming that opponent is also playing optimally.
:
Mini-Max algorithm uses recursion to search through the game-tree.
Min-Max algorithm is mostly used for game playing in AI. Such as Chess, Checkers, tic-tac-toe, go, and various tow-players game. This Algorithm computes the minimax decision for the current state.
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.
Both Players of the game are opponent of each other, where MAX will select the maximized value and MIN will select the minimized value.
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.
Stochastic Games
In game theory, a stochastic game (or Markov game), introduced by Lloyd Shapley in the early 1950s, is a repeated game with probabilistic transitions played by one or more players. The game is played in a sequence of stages.
Ex: Chess
And Or Search Tree
The structure of an AND/OR search tree is based on the underlying pseudo-tree T. The root of the AND/OR search tree is an OR node, labeled with the root of T.
What is Adversarial Search
Adversarial search in artificial intelligence is a problem-solving technique that focuses on making decisions in competitive or adversarial scenarios. It is employed to find optimal strategies when multiple agents, often referred to as players, have opposing or conflicting objectives.
