eg. chess, othello, backgammon (chance node due to Dice, use Expecti-minimax), tic-tac-toe, Grundy's game
- complete, optimal, like DFS: time complexity - O(b^m), space complexity O(bm)
- players take turn, max-min-max-min-max etc.
An Evaluation Function:
- Estimates how good the current board configuration is for a player.
- linear weighted sum of features eg. Eval(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)
f1 = number of white queens - number of black queens
Ply - number of look-ahead levels
Aplha(max of children)-beta(min of children) pruning
- in practice alpha-beta pruning, often get O(b^(d/2)) rather than O(b^d) remember b^(1/2) = sqrt(b)
Expectiminimax - use weights that are linear due to average score, ie. Sum(prob_state*score), Dice has 21 (1+2+3+4+...+6 = n*(n+1)/2 = 6*7/2 http://polysum.tripod.com/) unique dice rolls (6-5 is the same as rolling 5-6)
No comments:
Post a Comment