CS计算机代考程序代写 algorithm Adversarial Search (Minimax)

Adversarial Search (Minimax)
 Deterministic,zero‐sumgames
5 Max 4 5Min
 Tic‐tac‐toe, chess, go
 One player maximises result and the other minimises result
 Minimaxsearch:
 A state‐space search tree
 Players alternate turns
4 8 17
5
 Compute each node’s minimax value, i.e. the best achievable utility against an optimal adversary

Implementing Minimax
function max_value (state) return its minimax value 􏰛 initialise 􏰛 􏰅 􏰆∞
for each successor of state
function min_value (state) return its minimax value 􏰛 initialise 􏰛 􏰅 􏰠∞
for each successor of state
􏰛 􏰅 max􏰂􏰛, 􏰏􏰐􏰒􏰐􏰏􏰜􏰃 _􏰛􏰜􏰝􏰎􏰞􏰂􏰍􏰎􏰟􏰟􏰞􏰍􏰍􏰓􏰔􏰄􏰄 return 􏰛
􏰛 􏰅 min􏰂􏰛, 􏰏􏰐􏰒􏰐􏰏􏰜􏰃 _􏰛􏰜􏰝􏰎􏰞􏰂􏰍􏰎􏰟􏰟􏰞􏰍􏰍􏰓􏰔􏰄􏰄 return 􏰛
function minimax_value (state) return its minimax value if state is a terminal state
return its utility
if state is for agent Max to take an action
return max_value(state)
if state is for agent Min to take an action
return min_value(state)

Minimax example
Max
Min
v=4
4

Minimax example
Max
v=3
Min
v=43 v=2
438267

Minimax example
Max
v=3
Min
v=3 v=2 v=17
4 3 8 2 6 7 17 1

Minimax example
Max
v=3
Min
v=3 v=2 v=1
4 3 8 2 6 7 17 1 5

Computational Complexity of Minimax
 Howefficientisminimax
Tic‐Tac‐Toe Connect Four Checkers Nine men’s
10􏰗 10􏰀􏰉 10􏰗􏰤
 DFS (exhaustive)
 Time: 􏰡 􏰢􏰖 , 􏰢 is branching factor, 􏰏 is maximum depth of the tree.
morris Draughts Chess Backgammon
10􏰗􏰤
 Space: 􏰡 􏰢􏰏  Examples
10􏰗􏰋 10􏰉􏰀􏰊
 Chess: 􏰢 􏰣 35, 􏰏 􏰣 100  Go:􏰢􏰣250, 􏰏􏰣150
Chinese Chess
10􏰉􏰋􏰋 10􏰉􏰗􏰤
Exact solution is completely infeasible, but do we need to explore the entire tree to find the minimax value?
Game
Game‐tree complexity (appr)
Shoji Go
10􏰀􏰀􏰘 10􏰊􏰘􏰤

Game Tree Pruning
Max
v=3
Min
v=3 v=2 v=1
4 3 8 2 6 7 17 1 5

Game Tree Pruning
Max
Min
v<=4 43 Game Tree Pruning Max Min v<=3 438 Game Tree Pruning Max v>=3
Min
v=3 v<=2 4382 Game Tree Pruning Max v>=3
Min
v=3 v<=2 v<=17 4382 171 Game Tree Pruning Max v>=3
Min
v=3 v<=2 v<=1 4382 171 Game Tree Pruning Max v=3 Min v=3 v<=2 v<=1 4382 171 Alpha‐Beta Pruning  General configuration (for agent Max)  Let􏰜bethevaluethatMaxcancurrentlygetatleast.  Wearenowcomputingthemin_valueatsomenode􏰒  Whenweexplore􏰒’schildren,ifwefindthatthevalue of 􏰒 will never be better than 􏰜 (for agent Max), then we can stop considering 􏰒’s other children.  Properties of alpha‐beta pruning  Thepruninghasnoeffectonminimaxvalueforthe root  Goodchildorderingimproveseffectivenessofpruning  Complexity of perfect ordering: 􏰡 􏰢􏰖/􏰀  Fullsearchofmanygames(e.g.Chess)isstillhopeless Alpha‐Beta quiz Min  Quiz: Find the nodes of the following tree pruned by alpha‐beta pruning algorithm. Assuming child nodes are visited from left to right. There are four layers and you can use L􏰏‐􏰒 to denote the 􏰒th node from left to right in the layer 􏰏, e.g., the first node (with value 8) at the bottom layer can be denoted by L4‐1. Max Max 8 5 20 3 2 4 15 6