ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุด (อังกฤษ : Minimax Algorithm ) คือขั้นตอนวิธีในการหลีกเลี่ยงโอกาสที่จะทำให้เกิดความสูญเสียมากที่สุดในการเล่นเกมเชิงตรรกะที่มีผู้เล่นสองคน เช่นหมากรุก , หมากฮอส หรือ โอเอกซ์ โดยมีเป้าหมายเพื่อให้ผู้เล่น A สามารถเลือกเส้นทางที่มีโอกาสมากที่สุด ที่จะทำให้ผู้เล่น B ได้เปรียบน้อยที่สุด ในแต่ละรอบ โดยในขั้นตอนวิธีนี้ ผู้เล่น A จะถูกเรียกว่าผู้เล่นหาค่าสูงสุด ส่วนผู้เล่น B จะถูกเรียกว่าผู้เล่นหาค่าต่ำสุด เพราะว่าตัวแปรของค่าเสียโอกาสจะเพิ่มขึ้นเมื่อผู้เล่น A ได้เปรียบ และจะลดลงเมื่อผู้เล่น B ได้เปรียบตามทฤษฎีเกมประกอบเชิงการจัด (Combinatorial Game Theory) ของจอห์น ฮอร์ตัน คอนเวย์ (John Horton Conway)
ที่มาของขั้นตอนวิธี
หลักการและวิธีค้นหา ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุดใช้หลักการของการค้นแบบจำกัดความลึก โดยเก็บค่าตัวแปรของค่าเสียโอกาสไว้ในแต่ละปม (node) ของต้นไม้ค้นหา (Search Tree) ตัวแปรนี้มีค่าได้ตั้งแต่ติดลบอนันต์ถึงอนันต์ ค่ามากกว่าศูนย์บ่งบอกว่าผู้เล่น A ได้เปรียบผู้เล่น B อยู่ ส่วนค่าอนันต์บ่งบอกว่าผู้เล่น A ชนะเกมนั้นอย่างแน่นอน ในทางกลับกันค่าติดลบอนันต์ก็บ่งบอกว่าผู้เล่น B เป็นผู้ชนะเกมนั้นแทน
ข้อจำกัดของขั้นตอนวิธี ในการเลือกค่าเสียโอกาสนั้น ต้นไม้ค้นหาจะทำการค้นค่าเสียโอกาสที่สูงที่สุดมาจากใบ (leaf node) และตัดสินว่าเส้นทางนั้นเป็นเส้นทางที่ดีที่สุด สังเกตว่าเกมที่มีความซับซ้อนสูงอย่างหมากรุก หรือโกะ จะไม่สามารถบันทึกทุกความเป็นไปได้ของทั้งเกมได้ทั้งหมดตั้งแต่ต้นเกม เพราะจะต้องบันทึกเยอะมาก หากแต่พอจะอ่านล่วงหน้าไปก่อนได้หลายตาเพื่อหาความได้เปรียบที่มากที่สุดไปเรื่อยๆจนไปจบที่ค่าอนันต์หรือลบอนันต์
รหัสเทียม 1.ตรวจค่าที่ส่งเข้ามาว่าเป็นปมบนสุดหรือไม่ ถ้าใช่ให้คืนค่าที่ค้นหามาได้จากปมที่แล้ว
2.กำหนดค่าลบอนันต์ให้ตัวแปร A 3.เรียกวงวน (loop) ตามปมลูก (child node) แต่ละตัว 4.ในวงวนหาค่ามากที่สุดระหว่างค่าที่หามาของปมลูกกับ A แล้วเก็บค่าไว้ใน A 5.คืนค่า A
การประยุกต์ใช้ ขั้นตอนวิธีการหาเกณฑ์ค่าเสียโอกาสมากน้อยที่สุดถูกนำไปประยุกต์ใช้กับสาขาวิชาอื่นอยู่มาก ได้แก่เศรษฐศาสตร์ , สถิติ , ปรัชญา , ทฤษฎีเกม และทฤษฎีการตัดสินใจ (Decision Theory) เพื่อใช้ในการหลีกเลี่ยงเส้นทางที่จะเกิดความสูญเสียมากที่สุด
อ้างอิง Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 163–171 Von Neumann, J: Zur Theorie der Gesellschaftsspiele Math. Annalen. 100 (1928) 295-320
แหล่งข้อมูลอื่น Minimax Explained - AI Depot 2011-09-26 ที่ เวย์แบ็กแมชชีน Minimax Algorithm Visualization (Java Applet) 2009-03-10 ที่ เวย์แบ็กแมชชีน The Minimax Theorem: an Interactive Gizmo
นตอนว, แมกซ, นตอนว, การหาเกณฑ, าเส, ยโอกาสมากน, อยท, งกฤษ, minimax, algorithm, อข, นตอนว, ในการหล, กเล, ยงโอกาสท, จะทำให, เก, ดความส, ญเส, ยมากท, ดในการเล, นเกมเช, งตรรกะท, เล, นสองคน, เช, นหมากร, หมากฮอส, หร, โอเอกซ, โดยม, เป, าหมายเพ, อให, เล, สามารถเล, อกเส. khntxnwithikarhaeknthkhaesiyoxkasmaknxythisud xngkvs Minimax Algorithm khuxkhntxnwithiinkarhlikeliyngoxkasthicathaihekidkhwamsuyesiymakthisudinkarelnekmechingtrrkathimiphuelnsxngkhn 1 echnhmakruk hmakhxs hrux oxexks odymiepahmayephuxihphueln A samartheluxkesnthangthimioxkasmakthisudthicathaihphueln B idepriybnxythisudinaetlarxb odyinkhntxnwithini phueln A cathukeriykwaphuelnhakhasungsud swnphueln B cathukeriykwaphuelnhakhatasud ephraawatwaeprkhxngkhaesiyoxkascaephimkhunemuxphueln A idepriyb aelacaldlngemuxphueln B idepriybtamthvsdiekmprakxbechingkarcd Combinatorial Game Theory khxngcxhn hxrtn khxnewy John Horton Conway enuxha 1 thimakhxngkhntxnwithi 2 hlkkaraelawithikhnha 2 1 khxcakdkhxngkhntxnwithi 2 2 rhsethiym 3 karprayuktich 4 xangxing 5 aehlngkhxmulxunthimakhxngkhntxnwithi aekikhkhntxnwithikarhaeknthkhaesiyoxkasmaknxythisudmithimacakthvsdiekmkhxngcxhn fxn nxymnn 2 sungekidcakkarsuksaekmsunyephuxhawithikarldkhwamesiyngcakkarsuyesiyemuxaephhlkkaraelawithikhnha aekikhkhntxnwithikarhaeknthkhaesiyoxkasmaknxythisudichhlkkarkhxngkarkhnaebbcakdkhwamluk odyekbkhatwaeprkhxngkhaesiyoxkasiwinaetlapm node khxngtnimkhnha Search Tree twaeprnimikhaidtngaettidlbxnntthungxnnt khamakkwasunybngbxkwaphueln A idepriybphueln B xyu swnkhaxnntbngbxkwaphueln A chnaekmnnxyangaennxn inthangklbknkhatidlbxnntkbngbxkwaphueln B epnphuchnaekmnnaethn khxcakdkhxngkhntxnwithi aekikh inkareluxkkhaesiyoxkasnn tnimkhnhacathakarkhnkhaesiyoxkasthisungthisudmacakib leaf node aelatdsinwaesnthangnnepnesnthangthidithisud sngektwaekmthimikhwamsbsxnsungxyanghmakrukhruxokacaimsamarthbnthukthukkhwamepnipidkhxngthngekmidthnghmdtngaettnekm ephraacatxngbnthukeyxamak hakaetphxcaxanlwnghnaipkxnidhlaytaephuxhakhwamidepriybthimakthisudiperuxycnipcbthikhaxnnthruxlbxnnt rhsethiym aekikh 1 trwckhathisngekhamawaepnpmbnsudhruxim thaichihkhunkhathikhnhamaidcakpmthiaelw 2 kahndkhalbxnntihtwaepr A 3 eriykwngwn loop tampmluk child node aetlatw 4 inwngwnhakhamakthisudrahwangkhathihamakhxngpmlukkb A aelwekbkhaiwin A 5 khunkha Akarprayuktich aekikhkhntxnwithikarhaeknthkhaesiyoxkasmaknxythisudthuknaipprayuktichkbsakhawichaxunxyumak idaekesrsthsastr sthiti prchya thvsdiekm aelathvsdikartdsinic Decision Theory ephuxichinkarhlikeliyngesnthangthicaekidkhwamsuyesiymakthisudxangxing aekikh Russell Stuart J Norvig Peter 2003 Artificial Intelligence A Modern Approach 2nd ed Upper Saddle River New Jersey Prentice Hall pp 163 171 Von Neumann J Zur Theorie der Gesellschaftsspiele Math Annalen 100 1928 295 320aehlngkhxmulxun aekikhMinimax Explained AI Depot Archived 2011 09 26 thi ewyaebkaemchchin Minimax Algorithm Visualization Java Applet Archived 2009 03 10 thi ewyaebkaemchchin The Minimax Theorem an Interactive Gizmoekhathungcak https th wikipedia org w index php title khntxnwithiminiaemks amp oldid 9617482, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ , อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม