โจทย์
การตัดกิ่งแบบ alpha-beta ให้คำตอบเดียวกับ minimax แต่ข้ามกิ่งที่ไม่มีทางเปลี่ยนผลลัพธ์ได้ โดยติดตามขอบเขตสองค่า: alpha คือคะแนนดีที่สุดที่ MAX มั่นใจได้แล้ว และ beta คือคะแนนดีที่สุดที่ MIN มั่นใจได้แล้ว
ต้นไม้เกมเป็นต้นไม้สมบูรณ์: ทุกโหนดภายในมีลูก branching ตัว และใบไม้ทั้งหมดอยู่ที่ความลึกเดียวกัน leaves แสดงคะแนนของใบไม้จากซ้ายไปขวา รากเป็นโหนด MAX และระดับสลับกันเป็น MAX, MIN, MAX, …
ค้นหาลูกจากซ้ายไปขวา เริ่มด้วย alpha = -∞ และ beta = +∞:
- 'ที่โหนด MAX หลังลูกแต่ละตัว: best = max(best, value) แล้ว alpha = max(alpha, best)'
- 'ที่โหนด MIN หลังลูกแต่ละตัว: best = min(best, value) แล้ว beta = min(beta, best)'
- ทันทีที่ alpha ≥ beta ให้ข้ามลูกที่เหลือของโหนดนั้น
จง implement alpha_beta(leaves, branching)
อินพุต
leaves: คะแนนของใบไม้จากซ้ายไปขวา ความยาวเป็นเลขยกกำลังของ branching
branching: จำนวนลูกต่อโหนดภายใน
เอาต์พุต
คืน [value, evaluated]: ค่า minimax ของราก และจำนวนใบไม้ที่ถูกประเมิน
เงื่อนไข
2 ≤ branching ≤ 5, ความยาวของ leaves = branching^depth โดย 1 ≤ depth ≤ 8, ใบไม้ไม่เกิน 10,000 ใบ
-1,000 ≤ แต่ละใบ ≤ 1,000
ตัวอย่าง
อินพุต:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
ผลลัพธ์ที่คาดหวัง:
expected = [3, 7]อินพุต:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {3, 7};อินพุต:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {3, 7};คำอธิบาย
โหนด MIN แรกเห็น 3, 12, 8 และคืน 3 ดังนั้น alpha = 3 โหนด MIN ที่สองเห็น 2 ได้ beta = 2 ≤ alpha จึงข้าม 4 และ 6 โหนดที่สามเห็น 14, 5, 2 และคืน 2 ค่าของรากคือ max(3, 2, 2) = 3 หลังดูใบไม้ 7 จาก 9 ใบ
อินพุต:
leaves = [5, 6, 7, 4]
branching = 2
ผลลัพธ์ที่คาดหวัง:
expected = [5, 4]อินพุต:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {5, 4};อินพุต:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {5, 4};คำอธิบาย
โหนด MIN ซ้ายประเมิน 5 และ 6 แล้วคืน 5 ดังนั้น alpha = 5 โหนด MIN ขวาประเมิน 7 (beta = 7) แล้ว 4 (beta = 4 ≤ 5) ใบไม้ทั้ง 4 ใบถูกประเมิน และค่าคือ 5
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ไล่ต้นไม้เกมจากซ้ายไปขวา พร้อมพกขอบเขตที่ดีที่สุดที่การันตีได้ของ MAX และ MIN ไปด้วย
คำใบ้ 2
ใช้ recursive minimax search ที่อัปเดต bound ปัจจุบันหลังลูกแต่ละตัว และหยุดเมื่อสอง bound ตัดกัน
คำใบ้ 3
ระวังให้นับเฉพาะ leaf ที่ถูกเยี่ยมจริง และจำไว้ว่า root เริ่มเป็น MAX node
ความซับซ้อนที่คาดหวัง
O(b^d) time in the worst case, O(d) extra space
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน