ขั้นตอนวิธีมินิแมกซ์
ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุด (อังกฤษ: Minimax Algorithm) คือขั้นตอนวิธีในการหลีกเลี่ยงโอกาสที่จะทำให้เกิดความสูญเสียมากที่สุดในการเล่นเกมเชิงตรรกะที่มีผู้เล่นสองคน[1] เช่นหมากรุก, หมากฮอส หรือ โอเอกซ์ โดยมีเป้าหมายเพื่อให้ผู้เล่น A สามารถเลือกเส้นทางที่มีโอกาสมากที่สุดที่จะทำให้ผู้เล่น B ได้เปรียบน้อยที่สุดในแต่ละรอบ โดยในขั้นตอนวิธีนี้ ผู้เล่น A จะถูกเรียกว่าผู้เล่นหาค่าสูงสุด ส่วนผู้เล่น B จะถูกเรียกว่าผู้เล่นหาค่าต่ำสุด เพราะว่าตัวแปรของค่าเสียโอกาสจะเพิ่มขึ้นเมื่อผู้เล่น A ได้เปรียบ และจะลดลงเมื่อผู้เล่น B ได้เปรียบตามทฤษฎีเกมประกอบเชิงการจัด (Combinatorial Game Theory) ของจอห์น ฮอร์ตัน คอนเวย์ (John Horton Conway)
ที่มาของขั้นตอนวิธี แก้
ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุดมีที่มาจากทฤษฎีเกมของจอห์น ฟอน นอยมันน์[2] ซึ่งเกิดจากการศึกษาเกมศูนย์เพื่อหาวิธีการลดความเสี่ยงจากการสูญเสียเมื่อแพ้
หลักการและวิธีค้นหา แก้
ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุดใช้หลักการของการค้นแบบจำกัดความลึก โดยเก็บค่าตัวแปรของค่าเสียโอกาสไว้ในแต่ละปม (node) ของต้นไม้ค้นหา (Search Tree) ตัวแปรนี้มีค่าได้ตั้งแต่ติดลบอนันต์ถึงอนันต์ ค่ามากกว่าศูนย์บ่งบอกว่าผู้เล่น A ได้เปรียบผู้เล่น B อยู่ ส่วนค่าอนันต์บ่งบอกว่าผู้เล่น A ชนะเกมนั้นอย่างแน่นอน ในทางกลับกันค่าติดลบอนันต์ก็บ่งบอกว่าผู้เล่น B เป็นผู้ชนะเกมนั้นแทน
ข้อจำกัดของขั้นตอนวิธี แก้
ในการเลือกค่าเสียโอกาสนั้น ต้นไม้ค้นหาจะทำการค้นค่าเสียโอกาสที่สูงที่สุดมาจากใบ (leaf node) และตัดสินว่าเส้นทางนั้นเป็นเส้นทางที่ดีที่สุด สังเกตว่าเกมที่มีความซับซ้อนสูงอย่างหมากรุกหรือโกะจะไม่สามารถบันทึกทุกความเป็นไปได้ของทั้งเกมได้ทั้งหมดตั้งแต่ต้นเกม เพราะจะต้องบันทึกเยอะมาก หากแต่พอจะอ่านล่วงหน้าไปก่อนได้หลายตาเพื่อหาความได้เปรียบที่มากที่สุดไปเรื่อยๆจนไปจบที่ค่าอนันต์หรือลบอนันต์
รหัสเทียม แก้
1.ตรวจค่าที่ส่งเข้ามาว่าเป็นปมบนสุดหรือไม่ ถ้าใช่ให้คืนค่าที่ค้นหามาได้จากปมที่แล้ว
2.กำหนดค่าลบอนันต์ให้ตัวแปร A 3.เรียกวงวน (loop) ตามปมลูก (child node) แต่ละตัว 4.ในวงวนหาค่ามากที่สุดระหว่างค่าที่หามาของปมลูกกับ A แล้วเก็บค่าไว้ใน A 5.คืนค่า A
การประยุกต์ใช้ แก้
ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุดถูกนำไปประยุกต์ใช้กับสาขาวิชาอื่นอยู่มาก ได้แก่เศรษฐศาสตร์, สถิติ, ปรัชญา, ทฤษฎีเกม และทฤษฎีการตัดสินใจ (Decision Theory) เพื่อใช้ในการหลีกเลี่ยงเส้นทางที่จะเกิดความสูญเสียมากที่สุด