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

จากวิกิพีเดีย สารานุกรมเสรี
Jump to navigation Jump to search

ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุด (อังกฤษ: 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) เพื่อใช้ในการหลีกเลี่ยงเส้นทางที่จะเกิดความสูญเสียมากที่สุด

อ้างอิง[แก้]

  1. Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 163–171
  2. Von Neumann, J: Zur Theorie der Gesellschaftsspiele Math. Annalen. 100 (1928) 295-320

แหล่งข้อมูลอื่น[แก้]