HomeChapter 5: Game Playing
+3
Honey Lynne Accion
aqua_pepper214
blacksnake
7 posters
Page 1 of 1
Chapter 5: Game Playing
blacksnake Wed Feb 23, 2011 11:02 am
Chapter 5
1. Enumerate and explain the different defines of a game.
2. Explain minimax algorithim.
3. Explain alpha-beta algorithm.
1. Enumerate and explain the different defines of a game.
2. Explain minimax algorithim.
3. Explain alpha-beta algorithm.
blacksnake- Posts : 18
Join date : 2010-11-20
Age : 35
Location : Davao -
Minimax ang Alpha-beta Algorithm
aqua_pepper214 Fri Feb 25, 2011 3:13 am
2.) Minimax algorithim is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss while maximizing the potential gain. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty. A minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game.
3.) Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated by the minimax algorithm in its search tree. Alpha-Beta is a well known optimized algorithm used to compute the values of classical combinatorial games, like chess and checkers The known proofs of correctness of Alpha-Beta do rely on very specific properties of the values used in the classical context (integers or reals), and on the finiteness of the game tree.
References:
http://en.wikipedia.org/wiki/Minimax
http://ezinearticles.com/?The-Minimax-Algorithm&id=5125760
http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/2003-04/intelligent-search/minimax.html
http://en.wikipedia.org/wiki/Alpha-beta_pruning
http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
http://www.springerlink.com/content/f9t5vf5hdtax8eh6/
Minimax Algorithm aims to find the best solution or the best move for the computer if it plays against a user. The theory behind minimax is that the algorithm's opponent will be trying to minimize whatever value the algorithm is trying to maximize (hence, "minimax"). Thus, the computer should make the move which leaves its opponent capable of doing the least damage. Minimax is still useful when employed with heuristics which approximate possible outcomes from a certain point.
3.) Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated by the minimax algorithm in its search tree. Alpha-Beta is a well known optimized algorithm used to compute the values of classical combinatorial games, like chess and checkers The known proofs of correctness of Alpha-Beta do rely on very specific properties of the values used in the classical context (integers or reals), and on the finiteness of the game tree.
References:
http://en.wikipedia.org/wiki/Minimax
http://ezinearticles.com/?The-Minimax-Algorithm&id=5125760
http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/2003-04/intelligent-search/minimax.html
http://en.wikipedia.org/wiki/Alpha-beta_pruning
http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
http://www.springerlink.com/content/f9t5vf5hdtax8eh6/
Minimax Algorithm aims to find the best solution or the best move for the computer if it plays against a user. The theory behind minimax is that the algorithm's opponent will be trying to minimize whatever value the algorithm is trying to maximize (hence, "minimax"). Thus, the computer should make the move which leaves its opponent capable of doing the least damage. Minimax is still useful when employed with heuristics which approximate possible outcomes from a certain point.
aqua_pepper214- Posts : 7
Join date : 2011-01-24
Age : 36
Location : Davao City
Re: Chapter 5: Game Playing
Honey Lynne Accion Mon Feb 28, 2011 3:47 pm
1. The different defines of a game are the following, namely:
(1) The initial state
(2) A set of operators
(3) A terminal test
(4) A utility function or also known as a payoff function
such example,
> Two players: A and B
> A moves first and they take turns until the game is over. Winner
gets award, loser gets penalty.
> Games as search:
> Initial state: e.g. board configuration of chess
> Successor function: list of (move,state) pairs specifying
legal moves.
> Terminal Test: Is the game finished?
> Utility function: Gives numerical value of terminal states.
E.g. win (+1), lose (-1) and draw (0) in
tic-tac-toe.
> A uses search tree to determine the next move.
http://www.slideshare.net/lordmwesh/game-playing-in-artificial-intelligence
Russel, S J. and Norvig, N,"Artificial Intelligence A Modern Approach".
2. Explain minimax algorithim.
Minimax algorithm or often called minmax is a decision rule being use in different aspect of theories. In game theory, minimax is used in zero-sum games to denote minimizing the opponent's maximum pay-off. This is identical to minimizing one's own maximum loss and to maximizing one's own minimum gain.
http://en.wikipedia.org/wiki/Minimax
3. Explain alpha-beta algorithm.
Alpha-beta algorithm works along with the minimax algorithm since the latter is responsible of the evaluation as the former seeks to reduce the number of nodes in search tree. The process stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move.
http://en.wikipedia.org/wiki/Alpha-beta_pruning
Last edited by Honey Lynne Accion on Fri Mar 18, 2011 3:26 pm; edited 2 times in total
Honey Lynne Accion- Posts : 8
Join date : 2010-11-30
Re: Chapter 5: Game Playing
blacksnake Thu Mar 03, 2011 8:42 pm
Games as Search Problems
This is the areas of endeavor in artificial intelligence. It is because it requires decision in order to achieve a goal. However, opponents are design to find the possible moves through searching in order to thwart them. One of the examples are chess and even role-playing games in which it requires search problems to achieve the goal.
Games as Decision Problems
Most games today especially on fight-based games in which the user requires strategy to thwart opponents. But the strategy is something to do with the decision problems like which item or skill to be use to thwart them either the fastest time or the more efficient one. Games are now considered much more than the real world right now.
About Minimax Algorithm
This algorithm is designed to determine the optimal strategy for MAX and thus decide what is the best possible move is. There are five steps to achieve them, these are:
About Alpha-Beta Pruning
In implementing the minimax algorithm, there are x positions with a branching factor of y. From these, it is the process of eliminating one of a branch from the selected tree through the use of minimax algorithm. It's effectiveness depends on the ordering in which the successors are examined.
About Alpha-Beta Algorithm
From that concept on Alpha-Beta Pruning, this algorithm is just a copy to the MAX-VALUE function with an extra code to remember and return the best possible move found.
Note: Most of the questions are taken from the reference.
This is the areas of endeavor in artificial intelligence. It is because it requires decision in order to achieve a goal. However, opponents are design to find the possible moves through searching in order to thwart them. One of the examples are chess and even role-playing games in which it requires search problems to achieve the goal.
Games as Decision Problems
Most games today especially on fight-based games in which the user requires strategy to thwart opponents. But the strategy is something to do with the decision problems like which item or skill to be use to thwart them either the fastest time or the more efficient one. Games are now considered much more than the real world right now.
About Minimax Algorithm
This algorithm is designed to determine the optimal strategy for MAX and thus decide what is the best possible move is. There are five steps to achieve them, these are:
- Generate the whole game tree all the way doen to the terminal states.
- Apply the utility function to each terminal state to get the value.
- Use the utility of the terminal states to determine the utlilty of the nodes one level higher up in the search tree.
- Continue backing up the values from leaf nodes towards the root, one layer at the time.
- Eventually, the backed-up values reach the top of the tree: at that point, MAX choses the move that leads to the highest value.
About Alpha-Beta Pruning
In implementing the minimax algorithm, there are x positions with a branching factor of y. From these, it is the process of eliminating one of a branch from the selected tree through the use of minimax algorithm. It's effectiveness depends on the ordering in which the successors are examined.
About Alpha-Beta Algorithm
From that concept on Alpha-Beta Pruning, this algorithm is just a copy to the MAX-VALUE function with an extra code to remember and return the best possible move found.
Note: Most of the questions are taken from the reference.
blacksnake- Posts : 18
Join date : 2010-11-20
Age : 35
Location : Davao -
Re: Chapter 5: Game Playing
fjsanico Sun Mar 06, 2011 8:44 pm
The different defines of a game
- initial state
- includes the board position and an indication of whose move it is
- the operators
- define the legal moves that a player can make
- a terminal test
- determines when the game is over.
- and a utility or payoff function
- which says who won, and by how much. applies to terminal states
The MiniMax Algorithm
It searches all possible moves up to a fixed depth, evaluates all resulting positions and uses these evaluations to track the score down to the root of the search tree.
Alpha-Beta pruning algorithm
does the same calculation as minimax, but is more efficient because it prunes away branches of the search tree that it can prove irrelevant to the final outcome. Pruning is the elimination of nodes found to be unnecessary to process while searching. Alpha-beta pruning is effective in game-tree search because it eliminates parts of the game tree that cannot affect the evaluation of the game tree
http://www.fierz.ch/strategy1.htm#minimax
http://www.hamedahmadi.com/gametree/#alphabeta
Arificial Intelligence - A Modern Approach - Prentice Hall
http://mcs.une.edu.au/~comp508/Exams/pool/
- initial state
- includes the board position and an indication of whose move it is
- the operators
- define the legal moves that a player can make
- a terminal test
- determines when the game is over.
- and a utility or payoff function
- which says who won, and by how much. applies to terminal states
The MiniMax Algorithm
It searches all possible moves up to a fixed depth, evaluates all resulting positions and uses these evaluations to track the score down to the root of the search tree.
Alpha-Beta pruning algorithm
does the same calculation as minimax, but is more efficient because it prunes away branches of the search tree that it can prove irrelevant to the final outcome. Pruning is the elimination of nodes found to be unnecessary to process while searching. Alpha-beta pruning is effective in game-tree search because it eliminates parts of the game tree that cannot affect the evaluation of the game tree
http://www.fierz.ch/strategy1.htm#minimax
http://www.hamedahmadi.com/gametree/#alphabeta
Arificial Intelligence - A Modern Approach - Prentice Hall
http://mcs.une.edu.au/~comp508/Exams/pool/
fjsanico- Posts : 6
Join date : 2011-02-10
Re: Chapter 5: Game Playing
deyong Mon Mar 07, 2011 3:34 pm
- Game can be defined by the initial state (how the board is set up), the operators (which define the legal moves), a terminal test (which says when the game is over), and a utility or payoff function (which says who won, and by how much).
- Minimax algorithm specifically in two-player games with perfect information, can determine the best move for a player (assuming the opponent plays perfectly) by enumerating the entire game tree.
- Alpha-beta algorithm does the same calculation as minimax, but is more efficient
because it prunes away branches of the search tree that it can prove are irrelevant to the final outcome.
- Reference: Artificial Intelligence: A Modern Approach by Stuart J. Russell and Peter Norvig
deyong- Posts : 7
Join date : 2011-01-24
Game Playing
blueacid Thu Mar 24, 2011 9:03 pm
A game is defined with the following components
Minimax Algorithm
Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss while maximizing the potential gain. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.
Alpha-Beta Algorithm
Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated by the minimax algorithm in its search tree. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further.
http://en.wikipedia.org/wiki/Minimax
http://en.wikipedia.org/wiki/Alpha-beta_pruning
- Initial state = This is includes the current status of the board or game and whose turn is it?
- Set of operators = This is the legal moves that a player can make given the current state
- Terminal Test = This the test wherein the board or game is evaluated to find if a winner already exists
- Utility Function = This is the outcome of the game. A Numerical or Quantitative Value that determines the outcome of the game. This is the basically the draw of the game.
-
Minimax Algorithm
Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss while maximizing the potential gain. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.
Alpha-Beta Algorithm
Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated by the minimax algorithm in its search tree. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further.
http://en.wikipedia.org/wiki/Minimax
http://en.wikipedia.org/wiki/Alpha-beta_pruning
blueacid- Posts : 10
Join date : 2011-03-14
game playing
lizyl123 Fri Mar 25, 2011 12:03 am
The different defines of a game are as follows:
1. The initial state
2. A set of operators
3. A terminal test
4. A utility function or also known as a payoff function
Minimax Algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position.
Alpha-Beta Algorithm is a well known optimized algorithm used to compute the values of classical combinatorial games, like chess and checkers. It is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.).
1. The initial state
2. A set of operators
3. A terminal test
4. A utility function or also known as a payoff function
Minimax Algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position.
Alpha-Beta Algorithm is a well known optimized algorithm used to compute the values of classical combinatorial games, like chess and checkers. It is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.).
lizyl123- Posts : 7
Join date : 2011-03-24
Similar topics» Reflections on Chapter 7-10
» Chapter 4: Informed Search Methods
» Chapter 6: Agents that Reason Logically
» Shortest Path Algorithm (in relation to chapter 4)
» Chapter 4: Informed Search Methods
» Chapter 6: Agents that Reason Logically
» Shortest Path Algorithm (in relation to chapter 4)
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum|
|
|