Ans. Game playing
Games are well-defined problems that are generally interpreted as requiring intelligence to play well.
Introduces uncertainty since opponents moves can not be determined in advance
• Computer programs which play 2-player games
– game-playing as search
– with the complication of an opponent
• General principles of game-playing and search
– evaluation functions
– minimax principle
– alpha-beta-pruning
– heuristic techniques
• Status of Game-Playing Systems
– in chess, checkers, backgammon, Othello, etc, computers routinely defeat leading world players
• Applications?
– think of “nature” as an opponent
– economics, war-gaming, medical drug treatment
Alpha-beta pruning
• Idea:
– Do depth first search to generate partial game tree,
– Give static evaluation function to leaves,
– Compute bound on internal nodes.
• Alpha, Beta bounds:
– Alpha value for max node means that max real value is at least alpha.
– Beta for min node means that min can guarantee a value below beta.
• Computation:
– Alpha of a max node is the maximum value of its seen children.
– Beta of a min node is the minimum value seen of its child node .
• Pruning
– Below a Min node whose beta value is lower than or equal to the alpha value of its ancestors.
– Below a Max node having an alpha value greater than or equal to the beta value of any of its Min nodes ancestors.
– Worst-Case
– Branches are ordered so that no pruning takes place. In this case alpha-beta gives no improvement over exhaustive search
– Best-Case
– Each player’s best move is the left-most alternative (i.e., evaluated first)
– In practice, performance is closer to best rather than worst-case
– In practice often get O(b(d/2)) rather than O(bd)
– This is the same as having a branching factor of sqrt(b),
– since (sqrt(b))d = b(d/2) (i.e., we have effectively gone from b to square root of b)
– In chess go from b ~ 35 to b ~ 6
– permiting much deeper search in the same amount of time
Alpha-Beta General Principle
•Consider a node n where it is Player’s choice of moving to that node. If Player has a better choice m at either the parent node of n or at any choice point further up, then n will never be reached in actual play.
•Maintain two parameters in depth-first search, a, the value of the best (highest) value found so far for MAX along any path; and b, the best (lowest) value found along any path for MIN. Prune a subtree once it is known to be worse than the current a or b.
Effectiveness of Alpha-Beta
•Amount of pruning depends on the order in which siblings are explored.
•In optimal case where the best options are explored first, time complexity reduces from O(bd) to O(bd/2), a dramatic improvement. But entails knowledge of best move in advance!
•With successors randomly ordered, assymptotic bound is O((b/logb)d) which is not much help but only accurate for b>1000. More realistic expectation is something like O(b3d/4).
•Fairly simple ordering heuristic can produce closer to optimal results than random results (e.g. check captures & threats first).
•Theoretical analysis makes unrealistic assumptions such as utility values distributed randomly across leaves and therefore experimental results are necessary.