2012-03-19
#8 Practice Midterm.
Originally Posted By: gina.ma
8. Give the minimax algorithm. Give an example of a situation in which an alpha-cut might be made. Give an example of a situation in which a beta-cut might be made.
(The following algorithm is from the textbook Ch. 5, page 164)
MINIMAX(current state) =
....UTILITY(cs, player) if TERMINAL-TEST(cs)
....max_aєPossibleActions(cs) MINIMAX(RESULT(cs, a)) if player = MAX
....min_aєPossibleActions(cs) MINIMAX(RESULT(cs, a)) if player = MIN
TERMINAL-TEST: true if game is over, false otherwise
UTILITY: defines final numeric value for a game that ends in terminal state (s) for player (p)
RESULT: defines the result of the move
Alpha-cut example:
alphaCut.PNG
B’s backup value is 3 so A’s backup value is 3. At C, the backup value is at most 2. Since 2 6, so do a beta-cut on D’s remaining branches.
Done by:
Gina Ma
Tomas Tupy
(The following algorithm is from the textbook Ch. 5, page 164)
MINIMAX(current state) =
....UTILITY(cs, player) if TERMINAL-TEST(cs)
....max_aєPossibleActions(cs) MINIMAX(RESULT(cs, a)) if player = MAX
....min_aєPossibleActions(cs) MINIMAX(RESULT(cs, a)) if player = MIN
TERMINAL-TEST: true if game is over, false otherwise
UTILITY: defines final numeric value for a game that ends in terminal state (s) for player (p)
RESULT: defines the result of the move
Alpha-cut example:
alphaCut.PNG
B’s backup value is 3 so A’s backup value is 3. At C, the backup value is at most 2. Since 2 6, so do a beta-cut on D’s remaining branches.
Done by:
Gina Ma
Tomas Tupy
'''Originally Posted By: gina.ma'''
8. Give the minimax algorithm. Give an example of a situation in which an alpha-cut might be made. Give an example of a situation in which a beta-cut might be made.<br><br>(The following algorithm is from the textbook Ch. 5, page 164)<br>MINIMAX(current state) = <br>....UTILITY(cs, player) if TERMINAL-TEST(cs)<br>....max_aŃ”PossibleActions(cs) MINIMAX(RESULT(cs, a)) if player = MAX<br>....min_aŃ”PossibleActions(cs) MINIMAX(RESULT(cs, a)) if player = MIN<br><br>TERMINAL-TEST: true if game is over, false otherwise<br>UTILITY: defines final numeric value for a game that ends in terminal state (s) for player (p)<br>RESULT: defines the result of the move<br><br>Alpha-cut example:<br>alphaCut.PNG<br>B’s backup value is 3 so A’s backup value is 3. At C, the backup value is at most 2. Since 2 6, so do a beta-cut on D’s remaining branches.<br><br>Done by:<br>Gina Ma<br>Tomas Tupy
2012-03-21
Originally Posted By: yazdankhah
I think that is not minimax algorithm. That's the minimax heuristic function.
Ahmad
Ahmad
'''Originally Posted By: yazdankhah'''
I think that is not minimax algorithm. That's the minimax heuristic function.<br><br>Ahmad
Originally Posted By: tomtupy
It's the outline of the minimax algorithm...
'''Originally Posted By: tomtupy'''
It's the outline of the minimax algorithm...
(c) 2025 Yioop - PHP Search Engine