Week 8&9&10 Search & CSP & Game
Search
ไปไนๆฏๆ็ดข๏ผ
ๆ็ดขไธๆฏๅ ณไบ้ขๆต๏ผ่ๆฏๅ ณไบ้ๆฉๅๅณ็ญ๏ผๆฏๅฆ่งๅๅๅ้ ใ
ๆ็ดขๆๆฏๆฏ้็จ็้ฎ้ข่งฃๅณๆนๆณใ
่ทฏๅพ่งๅ๏ผGoogle ๅฐๅพ๏ผ๏ผๅจๆธธๆไธญ่ฟ่กไธไธๆญฅ็งปๅจ๏ผAlphaGo๏ผ๏ผไปฅๅไปปๅกๅ้ ๏ผUber ๅบ็ง่ฝฆ๏ผใ
ๆ็ดขๆฏไป่ตทๅง็ถๆๅฏผ่ชๅฐ็ฎๆ ็ถๆ็่ฟ็จใ
ๆ็ดข้ฎ้ข็ฑไปฅไธๅ ๅฎน็ปๆ๏ผ
State Space: ๅๅผ็ฉบ้ด๏ผๆๆๅๅผ็ๅฏ่ฝ
Start State: agentๅผๅงๆ็ดข็ๅฐๆน
Goal State: agentๅฏปๆพ็desired state
Goal test: ๆฃ้ชๆฏๅฆๅฐ่พพgoal
successor function๏ผ่ฝฌๅๆน็จใ้ๅธธไธไปฃไปทๆๅ ณ
่ฟๆState space graph ๅ Search Tree
State space graph๏ผไธ็งๆ็ดข้ฎ้ข็ๆฐๅญฆ่กจ็คบๅฝขๅผใnodeไปฃ่กจ็ถๆ๏ผarcไปฃ่กจ่ฝฌๆข
Search Tree๏ผ่งฃๅณๆ็ดข้ฎ้ข็่ฟ็จๅฏไปฅ่ขซๆฝ่ฑกๆไธบไธๆฃตๆ็ดขๆ ใ
ๅผๅง็ถๆไธบๆ น่็น๏ผๅญฉๅญๅฏนๅบๅ็ปง๏ผ่็นๆพ็คบ็ถๆ๏ผไฝๅฏนๅบไบๅฎ็ฐ่ฟไบ็ถๆ็่ฎกๅ๏ผๅณ่ทฏๅพ๏ผใ
้็จๆ ๆ็ดข
Frontier: ๅญๅจ็ญๅพ ๆฉๅฑ็่็นใ
Expansion: ๆฅๆพๅนถๆพ็คบ่็น็ๅญ่็นใ
Expansion strategy: ๆฅๅณๅฎๆฉๅฑ Frontier ไธญ็ๅชไธช่็น๏ผไน็งฐไธบexploreใ
DFS
What is the order of the nodes to be expanded by DFS in this example (tie will be broken alphabetically)?
S -> A -> B -> C -> G
BFS
S -> A -> C -> G
Constraint Satisfaction Problems (CSP)
ไธ้ขๅฑ็คบ็ๆ็ดข้ฎ้ข้ฝๆฏplanning้ฎ้ข๏ผๆไปฌๅ ณๅฟๅฐ็ฎๆ ็่ทฏๅพใ
่ฟๆไธ็ง้ฎ้ขๆฏIdentification้ฎ้ข๏ผๆไปฌไธๅ ณๅฟๅ้ ่ฟ็จ๏ผ้กบๅบ๏ผๅชๅ ณๅฟๅ้ ็ปๆ๏ผๆฏๅฆ่ฏดๅบ็ง่ฝฆๅ้ ๏ผn็ๅใ
่CSP้ฎ้ขๅฐฑๆฏไธ็ง็ปๅ็identification้ฎ้ข๏ผCSPๆ้่ฆๆปก่ถณ็็บฆๆ(constraints)๏ผไฝๅฏน็ปๆๆฒกๆๅๅฅฝใ
constraintsๆฏๆๅๆณ่งฃๅณๆนๆกไธ่ฝ่ฟๅ็็กฌๆง็บฆๆใๅๅฅฝๆๆถ่ขซ็งฐไธบ่ฝฏ็บฆๆ๏ผๆ็ฎๆ ๏ผ๏ผๆไปฌ้่ฆไผๅ๏ผไพๅฆ๏ผๆๅฐๅๆๆฌใไนๅฐฑๆฏ่ฏด๏ผCSP้ฎ้ขไธ้่ฆ่่ๆๆฌ๏ผๅช่ฆ่พพๆ็ฎๆ ๅณๅฏใ
CSP็ฑไปฅไธๅ ้จๅ็ปๆ๏ผ
variables
Domain for each variable
constraints
ๅจCSPไธญ๏ผๅฆๆๆฏไธชvariables้ฝๆไธไธชๅผ๏ผๅassignmentๆฏcomplete็๏ผๅฆๅๅฎๆฏpartial็ใsolutionๆฏๆปก่ถณๆๆconstraintsๆกไปถ็complete assignmentใ
ไพๅญ๏ผ
CSPๅๆ ๅๆ็ดข้ฎ้ข็ๅฏนๆฏ๏ผ
ๆ ๅๆ็ดข้ฎ้ข๏ผ
stateๆฏ้ป็๏ผๅฏไปฅๆฏไปปๆ็ๆฐๆฎ็ปๆ
็ฎๆ ๆต่ฏๅฏไปฅๆฏๅฏน็ถๆ็ไปปไฝๅฝๆฐ
CSP๏ผ
็ถๆ่ขซๅฎไนไธบๅ้X1, X2...๏ผdomainไธบD1, D2
็ฎๆ ๆต่ฏๆฏไธ็ปconstraintsๆๅฎๅ้ๅผ็ๅ ่ฎธ็ปๅใ
CSP้ฎ้ขไพๅญ
ไพ1: ๅพ็่ฒ
nodes correspond to the variables and arcs reflect the constraints.ๆไปฅTๅVไธญ้ดๆฒกๆarc
ไพ2: ๆฐ็ฌ
ๅฝconstraintๆถๅๅฐ่ถ ่ฟไธคไธชๅ้ๆถ๏ผ็จsquareๅconnetๆฅ่กจ็คบ็บฆๆ
ไพ3: ๆซ้ท
ไพ4: N็ๅ
่ก็ธๅ๏ผไธๅๅ่ฆไน00 ่ฆไน01 ่ฆไน10.ๅ้ขๅฐฑๅๆๅ็ธๅ๏ผๅฏน่ง็บฟ็ธๅ
CSP็ๅ็ฑป
variables
ๅๆ้็ฆปๆฃๅ้
ๅๆ ้็ฆปๆฃ/่ฟ็ปญๅ้๏ผไพๅฆๆถๅๆถ้ด็ๅ้
constraints
ไธๅ ๏ผไบๅ ๅ้ซ้ถ็บฆๆ๏ผUnary, binary and high-order๏ผ๏ผไนๅฐฑๆฏ่ฟไธช็บฆๆๆถๅๅฐๅคๅฐไธชๅ้
ๅฆๆๆnไธชๅ้๏ผๆฏไธชๅไธบd๏ผ้ฃไนๆO(d^n)็assignmentsใassignmentsไธ็ฎกๅฏน้
ๅฏนไบ4็ๅ้ฎ้ข๏ผๅฐฑๆ2^16็งๅ้
็ๅฎไธ็็CSP
ๅ้ ้ฎ้ข๏ผ่ฐๆๅชไธช็ญ
ๆถ้ด่กจ้ฎ้ข๏ผๆฏไธช็ญๅจไปไนๆถๅๅจๅชไธ่ฏพ
็กฌไปถ้ ็ฝฎ
ไบค้่ฐๅบฆ
ๅทฅๅ่ฐๅบฆ
็ต่ทฏๅธๅฑ
ๆ ้่ฏๆญ
่ฎธๅคCSP้ฎ้ขไนๅฏไปฅ่่ๅๅฅฝ๏ผๅณ็ฎๆ ๏ผ๏ผๅจ่ฟ็งๆ ๅตไธ๏ผๅฎไปฌไผๅๆๅ้ไผๅ้ฎ้ขใ
ไพ้ข
Variables: T, W, O, F, U, R, a1, a2
Domain: T, W, O, F, U, R: {0..9} a1, a2: {0, 1}
Constrain:
O+O = a1*10+R
W+W+a1 = a2*10+U
T+T+a2 = F*10+O
F != 0
ๆณจๆ๏ผalldiff(T,W,O,F,U,R)
Generate and Test - Brute Force
่ฏฆๅฐฝ็็ๆ-ๆต่ฏ็ฎๆณๆฏ็ๆๆๆๅฎๆด็่ตๅผ๏ผ็ถๅไพๆฌกๆต่ฏๅฎไปฌ๏ผๅนถ่ฟๅๆปก่ถณๆๆ็บฆๆๆกไปถ็็ฌฌไธไธชใ
ๅฎ้่ฆๅญๅจๆๆ ๐^๐ ไธชๅฎๆด็่ตๅผ๏ผๅ ถไธญ ๐ ๆฏๅๅคงๅฐ๏ผ๐ ๆฏๅ้ๆฐ้ใ
ๆไปฅๆไปฌ้่ฆๅซ็็ฎๆณ
Solve CSPs by standard search formulation
้่ฟไธ่ฌ็ๆ็ดขๆนๆณ่งฃๅณCSP
Initial state: the empty assignment {}
Successor function: assign a value to an unassigned variable
Goal: the current assignment is complete and satisfies all the constraints.
BFS
DFS
Check constraints as you go
ไพๅญ๏ผๆไธไธชๅ้ AใB ๅ C๏ผๅฎไปฌ็ๅๅผ่ๅดๅไธบ {0, 1, 2}ใ็บฆๆๆกไปถๆฏ A<B<Cใๅฆๆๅบ็ฐๅนณๅฑ๏ผๅๆๅญๆฏ้กบๅบๅๆฐๅญๅคงๅฐๆฅๅณๅฎ่่ดใ
่ฟ็งๆนๆณ็ๆๆณๆฏ๏ผๅจๆฏๆญฅๅ้ ็ๆถๅ๏ผ้ฝๅชๅ้ ไธ็ ดๅconstraints็ๅผใๅฏ่ฝ้่ฆ่ฟ่กไธไบ่ฎก็ฎๆฅๆฃๆฅ็บฆๆๆกไปถ๏ผๆฏๅฆโๅข้็ฎๆ ๆต่ฏโใ
Consider one variable at a layer
ๅๆบฏๆฏไธ็งๆทฑๅบฆไผๅ ๆ็ดขๆนๆณ๏ผๅ ทๆไธคไธช้ขๅค็็น็น๏ผ1๏ผๅจ่ฟ่กๆถๆฃๆฅ็บฆๆๆกไปถ๏ผ2๏ผ่่ไธไธชๅ้ๅจๆฏไธๅฑใ
Basic strategy: Backtracking
Speed-ups
ไธคไธชๆณๆณ๏ผ
โ Filtering๏ผๆไปฌ่ฝๅฆๆฉๆๆฃๆตๅฐไธๅฏ้ฟๅ ็ๆ ้
โ Ordering๏ผไธไธไธชๅบ่ฏฅๅ้ ๅชไธชๅ้
Speed-up: Filtering
่ท่ธชๆชๅ้ ๅ้ๅไบคๅๅ๏ผๆ้คไธ่ฏ้้กนใๆไธๅ็่ฟๆปคๆนๆณใforward checkingๆฏๅ ถไธญไนไธใ
forward checking๏ผๅฝๆทปๅ ๅฐ็ฐๆๅ้ ๆถ่ฟๅ็บฆๆ็็ธ้ปๅ้ๅผ่ฟ่กๅๆใไนๅฐฑๆฏ่ฏด๏ผๅฝๅ้ ไธไธชๅ้ๆถ๏ผๅๆๆๆๅ ถ้ปๅฑ ๅไธ็ฐๅจ่ขซ่ฟๅ็ไปปไฝๅ ๅฎนใ
Forward checking
ๆไธไธชๅ้AใBๅC๏ผๅฎไปฌ็ๅๅผ่ๅดไธบ{0, 1, 2}ใ็บฆๆๆกไปถๆฏB>A>Cใๅฆๆๅบ็ฐๅนณๅฑ๏ผๅๆๅญๆฏ้กบๅบๅๆฐๅญ้กบๅบ่ฟ่กๆ็ ดใ
่ฟๆฏไธๅผๅง็็ถๆใๅฝA่ขซๅ้ ไธบ0ๆถ๏ผๅ ถ้ปๅฑ BๅC็ๅๅๅฐ๏ผๅ ๆญคๅพๅฟซๅฐฑ็ฅ้่ฟไธช่ตๅผๆฏไธๅๆณ็๏ผๅ ไธบC็ฐๅจไธบ็ฉบ๏ผใ
Speed-up: Ordering
่่ๅฉไฝๅผ็ๆๅฐๆฐ้๏ผๅณ้ๆฉๅจๅ ถๅฎไนๅไธญๅฉไฝๅๆณๅผๆๅฐ็ๅ้ใ
ไพๅญ๏ผๆไธไธชๅ้ AใB ๅ C๏ผๅฎไปฌ็ๅๅผ่ๅดๅไธบ {0, 1, 2}ใ็บฆๆๆกไปถๆฏ A โค B < Cใๅฆๆๅบ็ฐๅนณๅฑ๏ผๅๆๅญๆฏ้กบๅบๅๆฐๅญๅคงๅฐๆฅๅณๅฎ่่ดใ
ๅฝA่ขซๅ้ ไธบ0็ๆถๅ๏ผ็ฑไบBๅคงไบ็ญไบA๏ผๆไปฅBไธบ012๏ผCๅคงไบA๏ผๆไปฅไธบ12๏ผๆไปฅๅ ๅ้ C๏ผๅๅ้ B
Also called โmost constrained variableโ or โfail-fastโ ordering
็ปๅ๏ผBacktracking + Forward Checking + Ordering
ๆไธไธชๅ้A๏ผB๏ผC๏ผๆๆ็ๅ้ฝๆฏ{0, 1, 2}ใ็บฆๆๆกไปถ๏ผA โค B < C ๅ A + B + C = 3ใๆ็ ดๅนณๅฑ็้กบๅบๆฏๆๅญๆฏ่กจๅๆฐๅญๆๅบใไฝฟ็จๅๆบฏใๅๅๆฃๆฅๅๆๅบๆฅ่งฃๅณ้ฎ้ข
Local Search
Tree Searchๆนๆณ๏ผ็ณป็ปๅฐๆ็ดขๅ้ ็ฉบ้ดใ
ไปไธไธช็ฉบ็ๅ้ ๅผๅงใ
ไธบๆชๅ้ ็ๅ้่ตๅผ๏ผๅนถๅจๆพๅฐ่งฃๅณๆนๆกไนๅๅค็็บฆๆใ
ไฝๅฆๆ็ฉบ้ดๅคชๅคง็่ณๆฏๆ ้็๏ผ้ฃไนๅจไปปไฝๅ็็ๆถ้ดๅ ๏ผ็ณป็ปๅๆ็ดขๅฏ่ฝไผๅคฑ่ดฅๅฐ่่ๅฐ่ถณๅคๅค็็ฉบ้ดไปฅๆไพไปปไฝๆๆไน็็ปๆใ
Local Searchๆนๆณ๏ผไธๆฏ็ณป็ปๅฐๆ็ดข็ฉบ้ด๏ผ่ๆฏ่ฎพ่ฎกไธบๅจๅนณๅๆ ๅตไธๅฟซ้ๆพๅฐ่งฃๅณๆนๆก
ไป๏ผไปปๆ๏ผๅฎๆดๅ้ ๅผๅง๏ผๅ ๆญคๅฏไปฅ่ฟๅ็บฆๆใ
ๅฐ่ฏ้่ฟ่ฟญไปฃๆน่ฟๅ้ ใ
ๆต็จ๏ผ
้ๆบ็ๆไธไธชcomplete assignment
ๅฝsolutionๆฒกๆๆปก่ถณ๏ผๆ่ stop criterionๆฒกๆ่พพๅฐ
็ฌฌไธๆญฅ๏ผๅ้้ๆฉ - ้ๆบ้ๆฉไธไธช่ฟๅ็บฆๆ็ๅ้ใ
็ฌฌไบ้จ๏ผๅผ้ๆฉ๏ผๆๅฐๅฒ็ชๅฏๅๅผ๏ผ- ้ๆฉ่ฟๅ็บฆๆๆๅฐ็ๅผใ
ไพๅญ๏ผA<=B<C
้ฆๅ ๏ผ้ๆบ็ๆไธไธชๅ้ ๏ผA1๏ผB0, C2
ๅ็ฐA๏ผB่ฟๅ่ฆๆฑ๏ผๆไปฅๆ นๆฎๅญๆฏ่กจ้ๆฉๅ้A๏ผ็ฑไบ0่ฟๅๆๅฐ็็บฆๆ๏ผๆไปฅA้ๆฉ0. A0, B0, C2, ๆปก่ถณๆกไปถใ
้ฎ้ข๏ผ
Local Search็่ฎบไธไธๆปๆฏ่ฝๆพๅฐ็ญๆก๏ผๅบไบ้ฎ้ข็landscapeๅsearch strategy๏ผไฝๆฏๅฎ่ทตไธ๏ผๅบๆฌ่ฝๅจ50ๆญฅไนๅ ๅฎๆmillion-queens.
Local Search - N็ๅ
้ฆๅ ้ๆบ็ๆไธไธช็ถๆ๏ผ{1,1,1,1}
็ถๅๅ็ฐๆฒกๆๆปก่ถณ็ปๆ๏ผๆไปฅ้ๆบ้ๆฉQ3ๅๅใไปๅทฆๅฐๅณ่ฟๅ็ๆฐ้ๅๅซๆฏ๏ผ3 2 1 0๏ผๆไปฅ็ถๆๅไธบ{1,1,4,1}
็ถๅ้ๆฉQ1ๅๅ๏ผไปๅทฆๅฐๅ่ฟๅ2 2 0 2๏ผๆไปฅๅๆ{3,1,4,1}
็ถๅ้ๆฉQ4ๅๅ๏ผไปๅๅฐๅณ่ฟๅ1 0 3 1๏ผๆไปฅๅๆ{3,1,4,2}๏ผๆปก่ถณ๏ผๆพๅฐsolution
Optimisation
ไผๅ้ฎ้ข๏ผๅธฆๆๅๅฅฝ็ๆ็ดข้ฎ้ข๏ผๅณๅ ทๆ็ฎๆ ๅฝๆฐใ
ๅฎไปฌ็ฑVariablesใDomainๅObjective Function็ปๆใ
Objective๏ผ
ๅ็ฎๆ ๏ผSingle-objective๏ผไผๅ้ฎ้ข๏ผไพๅฆ๏ผๆ ่กๅ้ฎ้ข๏ผTSP๏ผ๏ผๆๅฐๅๆ ่กๆๆฌใ
ๅค็ฎๆ (Multi-objective)ไผๅ้ฎ้ข๏ผไพๅฆ๏ผๅจTSPไธญๅขๅ ไธไธช้ขๅค็็ฎๆ ๏ผๆๅฐๅๆ ่กๆถ้ดใ
Constraints:
ๆ ็บฆๆไผๅ้ฎ้ขใ
็บฆๆไผๅ้ฎ้ขใ
Tree Searchๅฏ่ฝไผๅคฑๆ๏ผๅ ไธบๆไบsearch spaceๆฏ่ฟ็ปญ็๏ผLocal Searchๆด็ฎก็จ
Local Search for Optimisation
้ๅธธๅฟซ้ไธ็ๅ ๅญ
ๅฏๅค็ๆ็ดข็ถๆ้พไปฅ่กจ็คบ/ๅถๅฎ็้ฎ้ขใ
ๅจ้ฎ้ขๅ็ๅๅๆถ๏ผไพๅฆๅจ่ช็ฉบๅ ฌๅธ่ฐๅบฆ้ฎ้ขไธญ๏ผๅฏไปฅ็จไบๅจ็บฟ่ฎพ็ฝฎใ
method๏ผ
็ฌๅฑฑ็ฎๆณ๏ผไพๅฆๆขฏๅบฆไธ้ใ
ๆจกๆ้็ซ๏ผ็ฆๅฟๆ็ดข๏ผไฟ็ไธไธชๅฐๅ่กจๆ่ฟ่ฎฟ้ฎ็่งฃๅณๆนๆก๏ผๅนถ็ฆๆญข็ฎๆณ่ฟๅๅฐ่ฟไบ่งฃๅณๆนๆก๏ผใ
Backtracking Homework
่่ไปฅไธ4x4ๆฐ็ฌ้ฎ้ข๏ผๅ ถไธญๆฏๅใๆฏ่กๅๅไธชๅบๅ้ฝๅ ๅซ1ๅฐ4็ๆๆๆฐๅญใไฝฟ็จๅธฆๆๅๅๆฃๆฅๅๆๅบ็ๅๆบฏๆ็ดขๆฅ่งฃๅณ่ฟไธช้ฎ้ขใ
็ปๅบ่ฆ่ฎฟ้ฎ็ๆๆ็ถๆ็้กบๅบใๅ่ฎพๅๅ ๆ ผ็ๅนณๅฑ้ฆๅ ไปไธๅฐไธๆ็ ด๏ผ็ถๅไปๅทฆๅฐๅณๆ็ ด๏ผๅนถไธๆฐๅญ็ๅนณๅฑๆๆฐๅญ้กบๅบๆ็ ดใ
Game is a search problem
ๆธธๆ้ๅธธๆฏไธไธชๅฏนๆๆ็ดข้ฎ้ข๏ผไฝ ็ๅฏนๆไผๅฏนไฝ ็็ญ็ฅๅ่กจๆ่งใ
Games็ฑปๅ
ๆธธๆไธญๆฏๅฆๆไธไบ้ๆบๅ ็ด ๏ผ
็กฎๅฎๆง๏ผไพๅฆ ไบๅญๆฃ๏ผๅฝ้ ่ฑกๆฃ๏ผไธญๅฝ่ฑกๆฃ๏ผๅดๆฃ
ไธ็กฎๅฎๆง๏ผๆๅ ็๏ผ้บปๅฐ
ๅ ไธช็ฉๅฎถ๏ผ
ๆฏๅฆๅฏนๆ๏ผ
้ถๅๅๅผ๏ผไบๅญๆฃ๏ผไธๆฃ๏ผๅดๆฃ๏ผๆๅ
้้ถๅๅๅผ๏ผๅๅพๅฐๅข
็ถๆๆฏๅฆๅฏ่ง๏ผ
ๅฎๆดไฟกๆฏ๏ผไบๅญๆฃ๏ผๅฝ้ ่ฑกๆฃ๏ผไธญๅฝ่ฑกๆฃ๏ผๅดๆฃ
ไธๅฎๆดไฟกๆฏ๏ผๆๅ ๏ผ้บปๅฐ
Formalisation Game to Search
State๏ผS๏ผๅๅงไธบs0
Action๏ผA
Transition function๏ผS x A -> S
Terminal Test: S->(true, false)
Players:P = (1..N)
Utility(ๆ็จ) Function๏ผ๐_๐ก๐๐๐๐๐๐l ร ๐ โ ๐ ๏ผ็ปๆไธ็ๅผ๏ผ
ไธไธชๆ็จๅฝๆฐ๏ผไน็งฐไธบๅฎข่งๅฝๆฐๆๅๆฅๅฝๆฐ๏ผๅฎไนไบไปฅ็ป็ซฏ็ถๆ ๐ ็ปๆ็ๆธธๆๅฏนไบ็ฉๅฎถ ๐ ็ๆ็ปๆฐๅผใ
ๆ็จๅฐฑๆฏachievable outcome๏ผๅ ถๅฎๅฐฑๆฏ็ฎๅๅพๅใ
ๅฏนไบN็ๅ้ฎ้ข๏ผๆๆ็็ปๆๅฐฑๆฏ1๏ผๆ ๆ็ๅฐฑๆฏ0
ๆ็ดข็ฎๆณ็็ฎๆ ๏ผๅฏนไบไธไธช็ฉๅฎถ๏ผๆไปฌๅธๆ่ฏฅ็ฎๆณ่ฝๅคๆพๅฐไธ็ง็ญ็ฅ๏ผๆฟ็ญ๏ผ๏ผไธบๆฏไธช็ถๆๆจ่ไธๆญฅ็งปๅจ๏ผไปฅไพฟไปไปฌๆ็ปๅฏไปฅ่ทๅพๆๅคงๅฏๅฎ็ฐๆ็จใ
ๅฏนไบไบๅญๆฃ็ๆ็จๅฎไน๏ผ
Minmax
่็น็ๆๅฐๅผๆฏ็ป็ซฏ็ถๆ็ๆ็จ๏ผไป่ฏฅ่็นๅผๅง๏ผไธคไธช็ฉๅฎถ้ฝไผๆไผๅฐ่ฟ่กๆธธๆใ
ๅ ๆญค๏ผๅไบบๆธธๆ็่ฟ็จๆฏไธไธช็ฉๅฎถ๏ผ็งฐไธบMax็ฉๅฎถ๏ผ่ฆๆๅคงๅๅ ถๆ็จ๏ผ่ๅ ถๅฏนๆ๏ผ็งฐไธบMin็ฉๅฎถ๏ผ่ฆๆๅฐๅMax็ๆ็จใ
ไพๅญ๏ผ
็ฌฌไธไธช็ฉๅฎถๆๅคงๅ่ชๅทฑ็ๆ็จ๏ผๅฆไธไธช็ฉๅฎถๆๅฐๅ่ชๅทฑ็ๆ็จใ
Minmaxๆถ้ดๅคๆๅบฆไธบO(b^m), ็ฉบ้ดๅคๆๅบฆไธบ(bm)๏ผbไธบๆฏไธช่็น็ๅๆฏๆฐ๏ผmไธบๆๅคงๆทฑๅบฆ
ๅจๅคงๅคๆฐๆ ๅตไธ๏ผ่งฃๅณๅฎไปฌๆฏๅฎๅ จไธๅฏ่ก็๏ผไฝๆไปฌไธ้่ฆๆ็ดขๆดไธชๆ ๏ผๆไปฅ่ฆ็จๅฐPruningๅชๆ
Alpha-Beta Game Tree Pruning
่ฟๆฏไธ้ข้ฃไธชๆ
Alpha-Beta Pruning
โ ไธ่ฌ้ ็ฝฎ๏ผๅฏนไบไปฃ็Max๏ผ
โ ่ฎฉ ๐ ๆฏMax็ฎๅ่ณๅฐๅฏไปฅ่ทๅพ็ไปทๅผใ
โ ๆไปฌ็ฐๅจๆญฃๅจ่ฎก็ฎๆไธช่็น ๐ ็ๆๅฐๅผ
โ ๅฝๆไปฌๆข็ดข ๐ ็ๅญ่็นๆถ๏ผๅฆๆๆไปฌๅ็ฐ่ฏฅ่็น็ไปทๅผๆฐธ่ฟไธไผๆฏ ๐ ๆดๅฅฝ๏ผๅฏนไบไปฃ็Max๏ผ๏ผ้ฃไนๆไปฌๅฏไปฅๅๆญข่่๐็ๅ ถไปๅญ่็นใ
โ Alpha-beta pruning็็นๆง
โ ๅฏนๆ น่็นๆฅ่ฏด๏ผไฟฎๅชๅฏนๆๅฐๅๅผๆฒกๆๅฝฑๅใ
โ ่ฏๅฅฝ็ๅญ่็นๆๅบๆ้ซไบไฟฎๅชๆๆใ
โ ๅฎ็พๆๅบ็ๅคๆๅบฆ๏ผO(b^(๐/2))๏ผ่ฟๆๅณ็ไฝ ๅฏไปฅๆฏๅฏนๆๆทฑๅ ฅๆ็ดขไธคๅใ
โ ่ฎธๅคๆธธๆ๏ผไพๅฆๅฝ้ ่ฑกๆฃใๅดๆฃ๏ผ็ๅฎๅ จๆ็ดขไป็ถๆฏๆ ๆ็ใ
Pruning Exercise
Q1:
Q2:
Last updated