Chapter 5: Game Playing
Page 1 of 1 • Share
Chapter 5: Game Playing
Chapter 5
1. Enumerate and explain the different defines of a game.
2. Explain minimax algorithim.
3. Explain alphabeta algorithm.
1. Enumerate and explain the different defines of a game.
2. Explain minimax algorithim.
3. Explain alphabeta algorithm.
blacksnake Posts : 18
Join date : 20101120
Age : 30
Location : Davao
Minimax ang Alphabeta Algorithm
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 twoplayer zerosum 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 nplayer game, usually a twoplayer game. A value is associated with each position or state of the game.
3.) Alphabeta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated by the minimax algorithm in its search tree. AlphaBeta 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 AlphaBeta 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/?TheMinimaxAlgorithm&id=5125760
http://wwwcsfaculty.stanford.edu/~eroberts/courses/soco/projects/200304/intelligentsearch/minimax.html
http://en.wikipedia.org/wiki/Alphabeta_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.) Alphabeta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated by the minimax algorithm in its search tree. AlphaBeta 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 AlphaBeta 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/?TheMinimaxAlgorithm&id=5125760
http://wwwcsfaculty.stanford.edu/~eroberts/courses/soco/projects/200304/intelligentsearch/minimax.html
http://en.wikipedia.org/wiki/Alphabeta_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 : 20110124
Age : 31
Location : Davao City
Re: Chapter 5: Game Playing
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
tictactoe.
> A uses search tree to determine the next move.
http://www.slideshare.net/lordmwesh/gameplayinginartificialintelligence
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 zerosum games to denote minimizing the opponent's maximum payoff. 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 alphabeta algorithm.
Alphabeta 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/Alphabeta_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 : 20101130
Re: Chapter 5: Game Playing
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 roleplaying games in which it requires search problems to achieve the goal.
Games as Decision Problems
Most games today especially on fightbased 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 AlphaBeta 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 AlphaBeta Algorithm
From that concept on AlphaBeta Pruning, this algorithm is just a copy to the MAXVALUE 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 roleplaying games in which it requires search problems to achieve the goal.
Games as Decision Problems
Most games today especially on fightbased 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 backedup values reach the top of the tree: at that point, MAX choses the move that leads to the highest value.
About AlphaBeta 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 AlphaBeta Algorithm
From that concept on AlphaBeta Pruning, this algorithm is just a copy to the MAXVALUE 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 : 20101120
Age : 30
Location : Davao
Re: Chapter 5: Game Playing
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.
AlphaBeta 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. Alphabeta pruning is effective in gametree 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.
AlphaBeta 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. Alphabeta pruning is effective in gametree 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 : 20110210
Re: Chapter 5: Game Playing
 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 twoplayer games with perfect information, can determine the best move for a player (assuming the opponent plays perfectly) by enumerating the entire game tree.
 Alphabeta 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 : 20110124
Game Playing
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 twoplayer zerosum 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.
AlphaBeta Algorithm
Alphabeta 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 twoplayer games (Tictactoe, 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/Alphabeta_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 twoplayer zerosum 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.
AlphaBeta Algorithm
Alphabeta 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 twoplayer games (Tictactoe, 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/Alphabeta_pruning
blueacid Posts : 10
Join date : 20110314
game playing
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 nplayer game, usually a twoplayer 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.
AlphaBeta 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 twoplayer games (Tictactoe, 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 nplayer game, usually a twoplayer 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.
AlphaBeta 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 twoplayer games (Tictactoe, Chess, Go, etc.).
lizyl123 Posts : 7
Join date : 20110324
Similar topics
» Advice on playing Skaven
» couting game
» What makes a good skirmish game?
» Contruct2  HTML5 Game Engine
» Tournament at Millennium Game World 28 Dec 2010, Tue
» couting game
» What makes a good skirmish game?
» Contruct2  HTML5 Game Engine
» Tournament at Millennium Game World 28 Dec 2010, Tue
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum

