ขั้นตอนวิธีมินิแมกซ์

ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุด () คือขั้นตอนวิธีในการหลีกเลี่ยงโอกาสที่จะทำให้เกิดความสูญเสียมากที่สุดในการเล่นเกมเชิงตรรกะที่มีผู้เล่นสองคนRussell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 163–171 เช่นหมากรุก, หมากฮอส หรือ โอเอกซ์ โดยมีเป้าหมายเพื่อให้ผู้เล่น A สามารถเลือกเส้นทางที่มีโอกาสมากที่สุดที่จะทำให้ผู้เล่น B ได้เปรียบน้อยที่สุดในแต่ละรอบ โดยในขั้นตอนวิธีนี้ ผู้เล่น A จะถูกเรียกว่าผู้เล่นหาค่าสูงสุด ส่วนผู้เล่น B จะถูกเรียกว่าผู้เล่นหาค่าต่ำสุด เพราะว่าตัวแปรของค่าเสียโอกาสจะเพิ่มขึ้นเมื่อผู้เล่น A ได้เปรียบ และจะลดลงเมื่อผู้เล่น B ได้เปรียบตามทฤษฎีเกมประกอบเชิงการจัด (Combinatorial Game Theory) ของจอห์น ฮอร์ตัน คอนเวย์ (John Horton Conway)

 ที่มาของขั้นตอนวิธี 
ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุดมีที่มาจากทฤษฎีเกมของจอห์น ฟอน นอยมันน์Von Neumann, J: Zur Theorie der Gesellschaftsspiele Math. Annalen. 100 (1928) 295-320 ซึ่งเกิดจากการศึกษาเกมศูนย์เพื่อหาวิธีการลดความเสี่ยงจากการสูญเสียเมื่อแพ้

 หลักการและวิธีค้นหา 
ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุดใช้หลักการของการค้นแบบจำกัดความลึก โดยเก็บค่าตัวแปรของค่าเสียโอกาสไว้ในแต่ละปม (node) ของต้นไม้ค้นหา (Search Tree) ตัวแปรนี้มีค่าได้ตั้งแต่ติดลบอนันต์ถึงอนันต์ ค่ามากกว่าศูนย์บ่งบอกว่าผู้เล่น A ได้เปรียบผู้เล่น B อยู่ ส่วนค่าอนันต์บ่งบอกว่าผู้เล่น A ชนะเกมนั้นอย่างแน่นอน ในทางกลับกันค่าติดลบอนันต์ก็บ่งบอกว่าผู้เล่น B เป็นผู้ชนะเกมนั้นแทน

 ข้อจำกัดของขั้นตอนวิธี 
ในการเลือกค่าเสียโอกาสนั้น ต้นไม้ค้นหาจะทำการค้นค่าเสียโอกาสที่สูงที่สุดมาจากใบ (leaf node) และตัดสินว่าเส้นทางนั้นเป็นเส้นทางที่ดีที่สุด สังเกตว่าเกมที่มีความซับซ้อนสูงอย่างหมากรุกหรือโกะจะไม่สามารถบันทึกทุกความเป็นไปได้ของทั้งเกมได้ทั้งหมดตั้งแต่ต้นเกม เพราะจะต้องบันทึกเยอะมาก หากแต่พอจะอ่านล่วงหน้าไปก่อนได้หลายตาเพื่อหาความได้เปรียบที่มากที่สุดไปเรื่อยๆจนไปจบที่ค่าอนันต์หรือลบอนันต์

 รหัสเทียม 
1.ตรวจค่าที่ส่งเข้ามาว่าเป็นปมบนสุดหรือไม่ ถ้าใช่ให้คืนค่าที่ค้นหามาได้จากปมที่แล้ว
 2.กำหนดค่าลบอนันต์ให้ตัวแปร A
 3.เรียกวงวน (loop) ตามปมลูก (child node) แต่ละตัว
 4.ในวงวนหาค่ามากที่สุดระหว่างค่าที่หามาของปมลูกกับ A แล้วเก็บค่าไว้ใน A
 5.คืนค่า A

 การประยุกต์ใช้ 
ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุดถูกนำไปประยุกต์ใช้กับสาขาวิชาอื่นอยู่มาก ได้แก่เศรษฐศาสตร์, สถิติ, ปรัชญา, ทฤษฎีเกม และทฤษฎีการตัดสินใจ (Decision Theory) เพื่อใช้ในการหลีกเลี่ยงเส้นทางที่จะเกิดความสูญเสียมากที่สุด

 อ้างอิง 

 แหล่งข้อมูลอื่น 
 Minimax Explained - AI Depot 
 Minimax Algorithm Visualization (Java Applet) 
 The Minimax Theorem: an Interactive Gizmo

หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:ขั้นตอนวิธีการค้นหา
หมวดหมู่:ทฤษฎีเกม
หมวดหมู่:ขั้นตอนวิธีกราฟ
หมวดหมู่:ทฤษฎีการตัดสินใจ
หมวดหมู่:ทฤษฎีบทในวิยุตคณิต