Announcements. 1. Reading and Homework for this week. 2. Late policy on homework: 10% per day, unless you ask for extension beforehand

Please download to get full document.

View again

of 31
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Recipes/Menus

Published:

Views: 2 | Pages: 31

Extension: PDF | Download: 0

Share
Related documents
Description
Announcements 1. Reading and Homework for this week 2. Late policy on homework: 10% per day, unless you ask for extension beforehand 3. Presentation schedule reminder for upcoming presentations Game Playing:
Transcript
Announcements 1. Reading and Homework for this week 2. Late policy on homework: 10% per day, unless you ask for extension beforehand 3. Presentation schedule reminder for upcoming presentations Game Playing: Adversarial Search Game tree From M. T. Jones, Artificial Intelligence: A Systems Approach Current board: X s move Game tree From M. T. Jones, Artificial Intelligence: A Systems Approach Current board: X s move How many nodes? Evaluation Function From M. T. Jones, Artificial Intelligence: A Systems Approach Current board: O s move Evaluation function f(n) measures goodness of board configuration n. Assumed to be better estimate as search is deepened (i.e., at lower levels of game tree). Evaluation function here: Number of possible wins (rows, columns, diagonals) not blocked by opponent, minus number of possible wins for opponent not blocked by current player. Minimax search From M. T. Jones, Artificial Intelligence: A Systems Approach Current board: X s move Minimax search: Expand the game tree by m ply (levels in game tree) in a limited depth-first search. Then apply evaluation function at lowest level, and propagate results back up the tree. Minimax search From M. T. Jones, Artificial Intelligence: A Systems Approach Current board: X s move Calculate f(n) Minimax search From M. T. Jones, Artificial Intelligence: A Systems Approach Current board: X s move Propagate min value of children to parent Calculate f(n) Minimax search From M. T. Jones, Artificial Intelligence: A Systems Approach Current board: X s move Propagate max value of children to parent Propagate min value of children to parent Calculate f(n) Minimax search From M. T. Jones, Artificial Intelligence: A Systems Approach Current board: X s move Propagate min value of children to parent Propagate max value of children to parent Propagate min value of children to parent Calculate f(n) Minimax search From M. T. Jones, Artificial Intelligence: A Propagate max value of children to parent Systems Approach Current board: X s move Propagate min value of children to parent Propagate max value of children to parent Propagate min value of children to parent Calculate f(n) Minimax algorithm: Example From M. T. Jones, Artificial Intelligence: A Systems Approach Current board X s move What is value at the root? Exercise Alpha-Beta Pruning Problem with minimax: too expensive! Need to prune tree. Solution: alpha-beta pruning algorithm Basic idea: identify non-beneficial moves, and prune branches rooted in those moves Alpha-Beta Pruning Example From M. T. Jones, Artificial Intelligence: A Systems Approach Alpha-Beta Pruning Example From M. T. Jones, Artificial Intelligence: A Systems Approach alpha = value of the best possible move you can make, that you have computed so far beta = value of the best possible move your opponent can make, that you have computed so far If at any time, alpha = beta, then your opponent's best move can force a worse position than your best move so far, and so there is no need to further evaluate this move Alpha-Beta Pruning Applet Algorithm: Minimax with Alpha-Beta Pruning function alphabeta(node, depth, α, β, Player) if depth = 0 or node is a terminal node end return the heuristic value of node if Player = MaxPlayer else ; Initial call for each child of node α := max(α, alphabeta(child, depth-1, α, β, not(player) )) if β α break ; Prune return α for each child of node β := min(β, alphabeta(child, depth-1, α, β, not(player) )) if β α break ; Prune return β alphabeta(origin, depth, -infinity, +infinity, MaxPlayer) Alpha-beta pruning exercise max min max min (a) What is value at the root, using minimax alone? (b) What nodes could have been pruned from the search using alpha-beta pruning? Show values of alpha and beta Alpha-beta pruning exercise Remember: alpha: best move for us seen so far beta: best move for opponent seen so far max If alpha = beta, prune min max min (a) What is value at the root, using minimax alone? (b) What nodes could have been pruned from the search using alpha-beta pruning? Note: Alpha Beta pruning effectiveness is highly depending on the move ordering! How can we improve this ordering? Assumptions: Minimax / Alpha-Beta Minimax / Alpha-Beta Assumptions: Opponent is rational Both players have perfect information at each evaluation Evaluation functions Checkers and chess: Weighted linear sum of features f(s): Eval(s) = w 1 f 1 (s) + w 2 f 2 (s) + + w n f n (s) 24 Arthur Samuel s checkers program, written in the 1950 s. In 1962, running on an IBM 7094, the machine defeated R. W. Nealy, a future Connecticut state checkers champion. One of the first machine learning programs, introducing a number of different learning techniques. Deep Blue First Created in 1997 Algorithm: iterative-deepening alpha-beta search, transposition table, databases including openings of grandmaster games (700,000), and endgames (all with 5 pieces or more pieces remaining) Hardware: 30 IBM RS/6000 processors They do: high level decision making 480 custom chess processors all running in parallel They do : deep searches into the trees move generation and ordering, position evaluation (over 8000 evaluation points) Average performance: 126 million nodes/sec., 30 billion position/move generated, search depth: 14 From Deep Blue (chess computer) On May 11, 1997, the machine won a six-game match by two wins to one with three draws against world champion Garry Kasparov.[1] Kasparov accused IBM of cheating and demanded a rematch, but IBM refused and dismantled Deep Blue.[2] Kasparov had beaten a previous version of Deep Blue in After the loss, Kasparov said that he sometimes saw deep intelligence and creativity in the machine's moves, suggesting that during the second game, human chess players had intervened on behalf of the machine, which would be a violation of the rules. IBM denied that it cheated, saying the only human intervention occurred between games. A decade later: Topalov vs. Kramnik On 14 December 2006, Topalov directly accused Kramnik of using computer assistance [from the Fritz chess computer] in their World Championship match. On 14 February 2007, Topalov's manager released pictures, purporting to show cables in the ceiling of a toilet used by Kramnik during the World Championship match in Elista.
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x