Adverserial Search

• e: State -> Number

• how favorable is this state for MAX

• e<0 -> good for MIN

• e>0 -> good for MAX

• use weighted sum of features

• features are extracted from state

• compute MIN or MAX value for each node

  • MIN: choose smallest value of children

  • MAX: choose highest values of children

• start at “leaves” -> then go up the tree

• it its the value of the best state MAX can reach from this node

At each turn we need to compute a deep tree. This can be improved by Pruning-

• Try to figure out if we can ignore certain subtrees

• We can discontiue below any MIN node where beta<=alpha

• explore game tree to depth h using depth-first

• update alpha/beta values of parent of node N if:

  • search under N has been finished

  • search was discontinued

• prune branches

  • discontinue below MAX if: alpha(N) >= beta(any ancestor of N)

  • discontinue below MIN if: beta(N) <= alpha(any ancestor of N)

• best performance if children are ordered (decreasing/increasing backed up values depending on MAX/MIN node)

• getting worse if children are ordered at random

  • use iterative deepending to order nodes