Please enable JavaScript.
Coggle requires JavaScript to display documents.
Adversarial search - Coggle Diagram
Adversarial search
Types of games
Non-deterministic games: These have different unpredictable events as a factor of luck/chance. Example: Poker
Deterministic games: Games which follows a pattern and a set of rules in a very strict manner. Example: Chess
-
Imperfect Information: The game agents does not have the wholed etails and they do not have knowledge on what is going. Example: Tic Tac Toe
Min-Max Algorithm: This is a type of backtracking algorithm which is used to make the decisions and the game theory to find the player's optimal move, thinking that your opponent also plays optimally. Example: Chess and Tic Tac Toe
-
-
-
This performs DFS for the game-tree, the Min-Max algorithm is O(bm) where b stands for the branching factor of the game tree and m for the maximum depth of the tree.
Alpha-beta pruning: This is a search algorithm which seeks the reduction of the number of the nodes that are calculated by the minimax algorithm in its search tree.
Alpha: this is considered to be the highest-value choice that can be found so far. the initial value of alpha is the infinity symbol.
-
Logic
This will pass only alpha, child notes are beta values
-
-
the values of the nodes will be passed to the upper nodes other than passing to alpha and beta when backtracking is done
-
Game Theory: This is a theoretical framework for conceiving the social situations among the players who are competing.
Nash Equilibrium: This is an important concept. Meant by the a stable state found in a game where no player can have an advantage by unilaterally changing the strategy.
The Prisoner's Dilemma: This is mostly known in the game theory. For instance when criminals are arrested the prosecutors have no solid evidence to prove them. however to have a confession they remove the solitary cell and question them in a separate chamber/room
Zero Sum Games: This is a situation in the theory of the game in which one person gain is equal to another person loss. Therefore the benefit is zero. Examples: Chess, Go, Checkers.
Adversarial search: This is a search where the problem is examined which are arisen then try to plan before the world while other agents plan against us.
Stochastic Games: Markov decision process (MDP) to case where there are multiple players in a common environment. These types of agents performs a group action which defines both the reward obtained by the agents and the new state of the environment.
And-Or Search Tree: Specifies only the search space to solve a problem. Different search strategies can be used.