Games as Adversarial Search
• States:
– board configurations
• Initial state:
– the board position and which player will move
• Successor function:
– returns list of (move, state) pairs, each indicating a legal
move and the resulting state
• Terminal test:
– determines when the game is over
• Utility function:
– gives a numeric value in terminal states
(e.g., -1, 0, +1 for loss, tie, win)
CSP
A binary constraint relates two variables.
Forward Checking
每次进行操作后，Keep track of remaining legal values for unassigned variables，Terminate search when any variable has no legal values
Arc Consistency (AC-3)
arc consistency: Xi arc-consistent with Xj if for every value in Di there exists a value in Dj that satisfies the binary constraints on arc (Xi, Xj)
维护一个queue，初始状态下queue里面包含所有的arcs, 然后pop出来一个，Pop one arc (Xi, Xj) and make Xi arc-consistent with respect to Xj：
如果Di没变，continue
如果Di变了，重新检查和Xi相连的arcs,add all connected arcs (Xk, Xi) to the queue.
If Di is revised to empty, then the CSP problem has no solution.
Time complexity: O(n2d3) (n variables, d values)一共n个变量，每个变量里有d个取值
(each arc can be queued only d times, n^2 arcs (at most), checking one arc is O(d^2))
Min-confilcts
如果是解，那就返回解
如果不是解，随机选择一个冲突的变量，找到一个值能够使改变量冲突降到最低的，将变量设置为该值
实质上是一种Local Search
Adversarial SEARCH
Minimax
MINIMAX-VALUE(n)= UTILITY(n)
maxs ∈ successors(n) MINIMAX-VALUE(s) mins ∈ successors(n) MINIMAX-VALUE(s)
If n is a terminal If n is a max node If n is a min node
实质上是一种回溯
Completeness
• Yes (exhaustive) Optimality
• Yes (exhaustive)
•Time complexity O(b^m) 要遍历一遍节点
•Space complexity O(bm) or O(m)
Alpha-Beta pruning
http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/ 这个网站有动画模拟功能
在min节点只更新beta值，在max节点只更新alpha值 alpha 》= beta时进行pruning
Cutting off search
replace the two lines in Figure 5.7 that mention TERMINAL-TEST with the following line:
if CUTOFF-TEST(state, depth) then return EVAL(state)
网友评论