พื้นฐาน AI 🤖: EP 4 Game Tree Search
หัวข้อใน ep นี้ได้แก่
1. ทฤษฎีเกม
จากประเภทของ environmentที่อธิบายใน EP1 เกมในที่นี้หมายถึงสภาพแวดล้อมของ task ที่เป็น fully observable, multi-agent (มี 2 ผู้เล่น), deterministic และ turn-taking (ผลัดกันเล่น) เกมโดยทั่วไปสามารถแบ่งเป็น zero-sum game และ general game
Zero-Sum Game
agent ทั้ง 2 มี utility ที่ตรงกันข้ามกัน และต้องแข่งขันกันอย่างสมบูรณ์ (pure competition) ผลลัพธ์ของเกมนี้มีเพียงผู้ชนะ และผู้แพ้ โดยผู้ชนะจะได้ไปทุกอย่าง (winner-take-all) และผู้แพ้จะต้องเสียไปทุกอย่าง ดังนั้น utility รวมของทั้ง 2 ฝ่ายจึงเท่ากับ 0
General Game
agent ทั้ง 2 มี utility ที่เป็นอิสระต่อกัน โดยความสัมพันธ์ของ agent ทั้ง 2 สามารถเป็นได้ทั้งแบบ ร่วมมือกัน, แข่งขันกัน, เฉยเมยต่อกัน
โดยเนื้อหาด้านล่างจะกล่าวในกรณีของ “zero-sum game”
จาก EP2 ที่ได้กล่าวถึงองค์ประกอบของปัญหา search ในทฤษฎีเกมก็คล้ายกัน โดยองค์ประกอบของเกมมาตรฐานได้แก่
- state: s คือ สถานะปัจจุบันของเกม
- player: Player(s) คือ ผู้เล่นที่ต้องดำเนินการ ณ สถานะ s
- action: Actions(s) คือ การกระทำ ณ สถานะ s
- transition model: Result(s, a) คือ ผลลัพธ์ของการกระทำ a ณ สถานะ s
- terminal test: Terminal-Test(s) เช็คว่าสถานะ s เป็นสถานะที่ทำให้เกมสิ้นสุดหรือไม่
- utility: Utility(s, p) คือผลประโยชน์ที่ผู้เล่น p ได้รับ ณ สถานะ s
โดย solution ของผู้เล่นเรียกว่า “policy”
ตัวอย่างองค์ประกอบของเกม
หมากรุกสากล
- state: ตำแหน่งของตัวหากทั้งหมดบนกระดาน และเป็นของผู้เล่นคนไหน
- player: {ผู้เล่นหมากสีดำ, ผู้เล่นหมากสีขาว}
- action: การเดินหมากของผู้เล่นที่เป็นไปตามกติกา
- transition model: สถานะต่อไปหลังจากเดินหมากเสร็จ
- terminal test: สถานะปัจจุบันคือรุกฆาตหรือเสมอกันหรือไม่
- utility: สีขาวชนะได้ 1 คะแนน, เสมอกันได้ 0คะแนน, สีขาวแพ้ได้ -1 คะแนน
2. วิธีหาการตัดสินใจที่ดีที่สุด
วิธีหาการตัดสินใจ หรือ policy ที่ดีที่สุดนั้นใช้ “adversarial search”
Adversarial Search
คือการ search โดยมี 2 agent ซึ่งเป็นการวางแผนล่วงหน้า และคำนึงถึงการวางแผนของอีกฝ่านที่พยายามต่อต้านเรา algorithm ที่ใช้คือ “minimax”
Minimax
มีโครงสร้างเป็น tree โดยไล่จากล่างขึ้นบน (backtracking) โดย node ชั้นบนสุดคือสถานะของเรา node ชั้นต่อมาเป็นของอีกฝ่าย แล้วชั้นต่อมาก็เป็นของเรา สลับไปเรื่อยๆ (เพราะเป็นเกมที่สลับกันเล่น) การไล่ขึ้นให้ node ของเราได้ค่าจาก node ลูกที่มีค่ามากที่สุด และ node ของอีกฝ่ายได่ค่าจาก node ลูกที่น้อยที่สุด ตามตัวอย่างในภาพด้านล่าง
1) กำหนดให้วงกลมคือ node ของเรา ส่วนสี่เหลี่ยมคือ node ของอีกฝ่าย ดังนั้นในชั้น 0, 2 เลือก max ในชั้นที่ 1, 3 เลือก min
2) เริ่มไล่จากชั้นล่างสุด เพราะว่าเป็น node ของอีกฝ่าย ดังนั้นแต่ละ node เลือกค่าที่น้อยที่สุด
3) ชั้นต่อมาเป็นของ node เรา ดังนั้นแต่ละ node เลือกค่าที่มากที่สุด
4) ทำแบบเดิมตามขั้นตอน 2), 3) ไปเรื่อยๆจนถึง root node
ในการณีที่ tree มีความลึก m, และแต่ละ node มี children node n node จะได้ว่า
- ความซับซ้อนเชิงเวลาคือ O(bᵐ)
- ความซับซ้อนเชิงพื้นที่คือ O(bm)
ตัวอย่างการใช้ minimax ในเกม OX
3. α-β pruning
จากการหา minimax ด้านบน สามารถลดความซับซ้อนในการหาได้โดยใช้หลักการ α-β pruning (ตัดแต่งกิ่ง) คือกำหนดให้เริ่มต้น α = -∞, β = ∞ ในชั้นไหนที่ต้องการหา max ให้อัปเดตค่า α โดยเลือกค่าที่ทำให้ α มีค่ามากขึ้น, ในชั้นไหนที่ต้องการหา min ให้อัปเดตค่า β โดยเลือกค่าที่ทำให้ β มีค่าลดลง และหากหลังอัปเดตค่าแล้วพบว่า α ≥ β ให้ตัด node ลูกที่ยังไม่ได้พิจารณาของ node นั้นออกให้หมด ตามตัวอย่างในภาพด้านล่าง
1) กำหนดให้ root node มีค่า α = -∞, β = ∞
2) ถ่ายทอดค่า α, β ไปจนถึง leaf node
3) เพราะว่าชั้นที่อยู่ต้องการหา min ดังนั้นอัปเดตค่า β โดยเลือกเปรียบเทียบจากซ้ายไปขวา เริ่มต้นเทียบ ∞ กับ 5 พบว่า 5 น้อยกว่า ดังนั้นอัปเดตค่า β จาก ∞ เป็น 5, ต่อมาเทียบ 5 กับ -3 พบว่า -3 น้อยกว่า ดังนั้นอัปเดตค่า β จาก 5 เป็น -3
4) อัปเดตค่ากลับขึ้นไปด้านบน เพราะว่าชั้นที่อยู่ต้องการหา max ดังนั้นอัปเดตค่า α เมื่อเทียบ -∞ กับ -3 พบว่า -3 มากกว่า ดังนั้นอัปเดเตค่า α จาก -∞ เป็น -3
5) ถ่ายทอดค่า α, β ไปยัง node ลูกด้านขวา เพราะว่าชั้นนี้ต้องการหา min ดังนั้นอัปเดตค่า β เมื่อเทียบระหว่าง ∞ กับ 0 พบว่า 0 น้อยกว่า ดังนั้นจึงอัปเดต β เป็น 0
6) อัปเดตค่ากลับขึ้นไปด้านบน เพราะว่าชั้นนี้ต้องการ max ดังนั้น อัปเดตค่า α เนื่องจาก 0 มากกว่า -3 ดังนั้น อัปเดตค่า α เป็น 0
7) ทำแบบเดิมกับวิธีด้านบนในการอัปเดตค่าขึ้นไปด้านบน และถ่ายทอดค่าลงมาด้านล่าง
8) เพราะว่าตรง node นี้ α = β = 0 ดังนั้นตัด node ลูกที่ยังไม่พิจารณาออก (เหตุผลที่คัดออกไปได้ เพราะว่าค่าด้านล่างเหล่านี้จะไม่ส่งผลต่อ ค่า α, β ด้านบน)
9) อัปเดตค่าขึ้นไปด้านบน แลัถ่ายทอดค่าลงมาตามปกติ
10) เมื่อทำแบบเดิมไปจนถึง leaf node ฝั่งขวาสุด ถือว่าเสร็จสิ้น ไม่ต้องอัปเดตค่ากลับไปด้านบนแล้ว
ในการณีที่ tree มีความลึก m, แต่ละ node มี children node n node และค่าด้านล่างมีการเรียงลำดับอย่างสมบูรณ์ จะได้ว่าความซับซ้อนเชิงเวลาลดลงเหลือ O(bᵐ/²)
4. Heuristic α-β tree search
เนื่องจากในความเป็นจริงแล้ว ไม่สามารถ search ไปจนถึงสถานะสิ้นสุดของ game ได้ วิธีการรับมือคือ
- กำหนดความลึกสูงสุดในการ search (depth limit or horizon)
- ใช้ evaluation function ตันสินสถานะที่ยังไม่สิ้นสุดนั้น
ดังนั้นจึงไม่สามารรับประกันได้ว่าจะได้การตัดสินใจที่ดีที่สุด
Evaluation Function
หรือ heuristic evaluation function ใช้ประมาณ utility ของสถานะปัจจุบัน โดยไม่จำเป็นต้องทราบ leaf node โดยหน้าตาของ function มีได้หลากหลายขึ้นอยู่กับ game แต่ทั่วไปก็จะอยู่ในรูป
Eval(s) = w₁f₁(s) + w₂f₂(s) + ... + wₙfₙ(s) 5. เกมแบบสุ่ม
ต่อยอดจาก minimax ด้านบน แต่เพิ่ม node ความน่าจะเป็นมาคั่นระหว่างชั้น max กับ min เรียกว่า “expectiminimax” ดังนั้นค่าที่จะใช้พิจารณาแต่ละ node นั้น ไม่ใช่ค่าจริงๆ ที่ปรากฎบน node แต่คือค่าความคาดหวัง (exception value) ดังตัวอย่างด้านล่าง
1) กำหนดให้ node สามเหลี่ยมต้องการ expectimax (ค่าความคาดหวังสูงสุด) และ node วงกลมคือ node ความน่าจะเป็น โดยมีเส้นเชื่อมระบุความน่าจะเป็นที่จะได้แต่ละค่า
2) หาค่าความคาดหวังของแต่ละ node ความน่าจะเป็นได้
- ซ้ายสุด: exp = (1/5 × 5) + (2/5 × -3) + (2/5 × 0) = -1/5 = -0.2
- ตรงกลาง: exp = (1/3 × 1) + (1/3 × 7) + (1/3 × 9) = 17/3 ≈ 5.67
- ขวาสุด: exp = (1/2 × 4) + (1/4 × 2) + (1/4 × 3) = 13/4 = 3.25
3) เลือกค่าสูงสุดของ node ความน่าจะเป็นใส่เข้าไปใน node ด้านบน
6. Monte Carlo tree search
หรือ MCTS คือการค่อยๆสร้าง tree ไปเรื่อยๆโดยการสุ่มตัวอย่างการกระทำเพื่อจำลอง (simulate) สถานะสิ้นสุดจากสถานะปัจจุบัน (rollout) แล้วเลือกต่อ tree ไปยังสถานะที่มีค่า UCB (Upper Confidence Bound) สูงสุด MCTS มีขั้นตอนดังต่อไปนี้
1. Selection
เริ่มต้นจาก root node เลือก node ลูกที่มีค่า UCB สูงสุด โดยสมการ UCB คือ
UCB(Sᵢ) = wᵢ/nᵢ + C × √[ln(N)/nᵢ]โดย
- UCB(Sᵢ): ค่า UCB ของ state หรือ node i
- wᵢ: ผลตอบแทนรวมจากเหตุการณ์ทั้งหมดที่รู้ของ node i (เช่นจำนวนครั้งที่ชนะ)
- C: ค่าคงที่ เอาไว้ใช้รักษาสมดุลระหว่าง exploration (การสำรวจไปกว้างๆเพื่อเก็บข้อมูลใหม่) และ exploitation (การมาที่ตำแหน่งเดิมที่ได้ผลประโยชน์สูงสุดตามข้อมูลที่มีซ้ำๆ)
- N: จำนวนครั้งที่ simulate หรือ n₀
- nᵢ: จำนวนครั้งที่ node i ถูกเข้าถึง
จากสมการจะเห็นได้ว่า wᵢ/nᵢ คือ exploitation term และ √[ln(N)/nᵢ] คือ exploration term
2. Expansion
นำ node ลูกที่ถูกเลือกต่อเข้าไปใน tree
3. Simulation
จาก node ใหม่ที่เพิ่งเพิ่มเข้ามา simulate การกระทำจากสถานะปัจจุบันไปยังสถานะสิ้นสุดเกม
4. Backpropagation
นำผลลัพธ์จากการ simulate อัปเดตค่าต่างๆของ node ด้านบนไปจนถึง root node เช่นจำนวนครั้งที่ถูกเข้าถึง, จำนวนครั้งที่ชนะ
ตัวอย่างการทำ MCTS
การทำMCTS จะทำตาม 4 ขั้นตอนด้านบนซ้ำไปเรื่อยๆ ในที่นี้กำหนด C = 3
1) เริ่มต้นที่ root node ยังไม่มีการทำ simulate ดังนั้น wᵢ = 0, N = 0, nᵢ = 0
2) หาค่า UCB ของแต่ละ node ลูก ได้
- UCB(S₁) = 0/0 + 3 × √[ln(0)/0] = ∞
- UCB(S₂) = 0/0 + 3 × √[ln(0)/0] = ∞
เพราะว่า node ลูกมี UCB เท่ากัน ดังนั้นเลือกอันไหนก่อนก็ได้ สมมติเลือก S₁ ทำ simulate
3) สมมติว่าหลังทำ simulate จาก S₁ เมื่อจบเกมได้ผลตอบแทนคือ 10, ทำการอัปเดตค่า wᵢ, nᵢ, N กลับไปด้านบน
4) หาค่า UCB ของแต่ละ node ลูก อีกครั้งได้
- UCB(S₁) = 10/1 + 3 × √[ln(1)/1] = 10
- UCB(S₂) = 0/0 + 3 × √[ln(1)/0] = ∞
เพราะว่า S₂ มี UCB สูงสุด ดังนั้นเลือก S₂ ทำ simulate ต่อ
5) สมมติว่าหลังทำ simulate จาก S₂ เมื่อจบเกมได้ผลตอบแทนคือ 20, ทำการอัปเดตค่า wᵢ, nᵢ, N กลับไปด้านบน
6) หาค่า UCB ของแต่ละ node ลูก อีกครั้งได้
- UCB(S₁) = 10/1 + 3 × √[ln(2)/1] ≈ 12.50
- UCB(S₂) = 20/1 + 3 × √[ln(2)/1] ≈ 22.50
เพราะว่า S₂ มี UCB สูงสุด ดังนั้นเลือก S₂ ทำ simulate ต่อ
7) กำหนด node ลูกของ S₂ คือ S₃, S₄ พบว่า UCB(S₃) = UCB(S₄) = ∞ ดังนั้นเลือก node ไหนก่อนก็ได้ สมมติกว่าเลือก S₃ ทำ simulate ต่อ
8) สมมติว่าหลังทำ simulate จาก S₃ เมื่อจบเกมได้ผลตอบแทนคือ 0, ทำการอัปเดตค่า wᵢ, nᵢ, N กลับไปด้านบน
9) หาค่า UCB อีกครั้ง โดนเริ่มหาจาก node ลูกของ root ใหม่ได้
- UCB(S₁) = 10/1 + 3 × √[ln(3)/1] ≈ 13.14
- UCB(S₂) = 20/2 + 3 × √[ln(3)/2] ≈ 12.22
เพราะว่า S₁ มี UCB สูงสุด ดังนั้นเลือก S₁ ทำ simulate ต่อ (ถ้า S₂ มีค่ามากกว่า ก็เทียบค่า UCB ของ S₃ กับ S₄ ต่อ)
10) ทำตามขั้นตอนด้านบนไปเรื่อยๆ โดยการทำ MCTS สามารถหยุดได้ทุกเมื่อ ขึ้นอยู่กับเงื่อนไขที่กำหนด
อ้างอิง
หนังสือ Artificial Intelligence: A Modern Approach (4th edition)
