Min Max Algorithm ใน AI: ส่วนประกอบ คุณสมบัติ ข้อดี & ข้อจำกัด

อัลกอริธึมขั้นต่ำสุดใน AI หรือ ที่เรียกกันทั่วไปว่า minimax เป็นอัลกอริธึมย้อนรอยที่ใช้ในการตัดสินใจ ทฤษฎีเกม และปัญญาประดิษฐ์ (AI) ใช้เพื่อค้นหาการเคลื่อนไหวที่เหมาะสมที่สุดสำหรับผู้เล่น โดยถือว่าคู่ต่อสู้เล่นอย่างเหมาะสมด้วย คอมพิวเตอร์เล่นสองคนยอดนิยมหรือเกมออนไลน์ เช่น Chess, Tic-Tac-Toe, Checkers, Go เป็นต้น ใช้อัลกอริทึมนี้

อัลกอริธึมย้อนรอยถูกใช้เพื่อค้นหาวิธีแก้ไขปัญหาการคำนวณในลักษณะที่ผู้สมัครถูกสร้างขึ้นทีละขั้นเพื่อแก้ปัญหา ทีละขั้น และผู้สมัครที่ไม่สำเร็จในการแก้ปัญหาจะถูกละทิ้งทันที

มันทำงานอย่างไร?

ใน อัลกอริธึมขั้นต่ำสุดใน AI มีผู้เล่นสองคนคือ Maximiser และ Minimiser ผู้เล่นทั้งสองนี้เล่นเกมโดยพยายามทำคะแนนให้สูงสุดหรือให้ประโยชน์สูงสุดในขณะที่ฝ่ายตรงข้ามพยายามทำคะแนนให้ต่ำที่สุดหรือให้ผลประโยชน์ขั้นต่ำ

กระดานเกมทุกกระดานมีคะแนนการประเมินที่กำหนดไว้ ดังนั้น Maximiser จะเลือกค่าสูงสุด และ Minimiser จะเลือกค่าที่น้อยที่สุดด้วยการเคลื่อนไหวตอบโต้ หาก Maximiser ได้เปรียบ คะแนนของกระดานจะเป็นค่าบวก และหาก Minimiser ได้เปรียบ คะแนนของกระดานจะเป็นค่าลบ

ขึ้นอยู่กับแนวคิดของเกมที่ไม่มีผลรวมซึ่งคะแนนยูทิลิตี้ทั้งหมดจะถูกแบ่งระหว่างผู้เล่นสองคน ดังนั้น การเพิ่มคะแนนของผู้เล่นคนหนึ่งจะทำให้คะแนนของผู้เล่นฝ่ายตรงข้ามลดลง ทำให้คะแนนรวมเป็นศูนย์เสมอ ดังนั้น เพื่อให้ผู้เล่นคนหนึ่งชนะ อีกคนต้องแพ้

เข้าร่วม หลักสูตร Machine Learning Certification & AI ออนไลน์จากมหาวิทยาลัยชั้นนำของโลก รับ Masters, Executive PGP หรือ ACP เพื่อติดตามอาชีพของคุณอย่างรวดเร็ว

แยกย่อยอัลกอริธึมขั้นต่ำสูงสุดใน AI

มีการสำรวจแผนผังเกมที่สมบูรณ์ด้วยอัลกอริธึมการค้นหาเชิงลึกในอัลกอริธึมขั้น ต่ำสูงสุดใน AI มันดำเนินลงไปที่โหนดปลายทางของต้นไม้ทั้งหมดแล้วย้อนกลับผ่านต้นไม้

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

แหล่งที่มา

โครงสร้างเกมด้านบนเป็นโครงสร้างข้อมูลที่ซ้อนกันซึ่งใช้ในการประเมินการเคลื่อนไหว ที่นี่โหนดรูทคือระดับ 0 ซึ่งแตกแขนงออกเป็นระดับ 1 หรือโหนดหลัก ซึ่งแยกย่อยออกเป็นระดับ 2 หรือโหนดย่อย การแตกแขนงออกไปสามารถดำเนินต่อไปได้หลายระดับ โดยมีศักยภาพในระดับอนันต์ ระดับ 0 เหมือนกับสถานะปัจจุบันของกระดาน ในขณะที่ระดับ 1 เป็นสถานะที่เป็นไปได้ทั้งหมดของกระดานขึ้นอยู่กับการย้ายครั้งต่อไป

ดังนั้น หากผู้เล่น 2 ทำการย้าย เราสามารถสันนิษฐานได้ว่าโหนดรูทเป็นสถานะปัจจุบันของกระดาน รอการเคลื่อนไหวของผู้เล่น 1 โหนดระดับ 1 มีการเคลื่อนไหวที่เป็นไปได้ทั้งหมดสำหรับผู้เล่น 1 และโหนดระดับ 2 มีการเคลื่อนไหวที่เป็นไปได้ทั้งหมดสำหรับผู้เล่น 2 ตามการย้ายที่เป็นไปได้ของผู้เล่น 1

ลองพิจารณาตัวอย่างที่มีสี่สถานะสุดท้ายและเส้นทางที่จะไปถึงสิ่งเหล่านี้คือจากรากถึงใบทั้งสี่ของต้นไม้ ค่าของสี่ใบคือ 3, 6 ทางด้านซ้ายและ 4, 7 ทางด้านขวา ถึงตาของ Maximiser/Player 1 ที่จะเคลื่อนไหว ในการรันอัลกอริธึม ต้องมีสมมติฐานสำหรับการเคลื่อนไหวแต่ละครั้ง

หากผู้เล่น 1 เลือกที่จะไปทางซ้าย Minimiser/ผู้เล่น 2 จะต้องเลือกอย่างน้อยระหว่าง 3 ถึง 6 ดังนั้นพวกเขาจะเลือก 3 ในขณะที่หากผู้เล่น 1 เลือกถูก ผู้เล่น 2 จะเลือก 4 ซึ่งเป็นขั้นต่ำ ของสองค่าคือ 4 และ 7 ดังนั้น ระดับ 1 ตอนนี้มีค่า 3 และ 4

เนื่องจากเป็นเทิร์นของ Player 1/Maximiser พวกเขาจึงต้องเลือกโหนดระดับ 1 สูงสุด ดังนั้นพวกเขาจะเลือก 3 จากนั้นตัวเลือกที่เหมาะสมที่สุดคือไปทางซ้าย

ขั้นตอนสำหรับ อัลกอริธึมขั้นต่ำสุดใน AI สามารถระบุได้ดังนี้:

1. สร้างแผนผังเกมทั้งหมด
2. ประเมินคะแนนสำหรับโหนดปลายสุดตามฟังก์ชันการประเมิน
3. ย้อนรอยจากลีฟไปยังโหนดรูท:

สำหรับ Maximizer ให้เลือกโหนดที่มีคะแนนสูงสุด

สำหรับ Minimizer ให้เลือกโหนดที่มีคะแนนขั้นต่ำ

4. ที่โหนดรูท เลือกโหนดที่มีค่าสูงสุดและเลือกการย้ายที่เกี่ยวข้อง

อ่านเพิ่มเติม: แนวคิดโครงการการเรียนรู้ของเครื่อง

คุณสมบัติของอัลกอริธึมสูงสุดขั้นต่ำใน AI

• อัลกอริธึมเสร็จสมบูรณ์ หมายความว่าในแผนผังการค้นหาที่มีขอบเขตจำกัด จะพบวิธีแก้ปัญหาอย่างแน่นอน
• จะเป็นการดีที่สุดหากผู้เล่นทั้งสองเล่นอย่างเหมาะสมที่สุด
• เนื่องจาก Depth-First Search (DFS) สำหรับแผนผังเกม ความซับซ้อนของเวลาของอัลกอริทึมคือ O(b m ) โดยที่ b คือปัจจัยการแตกแขนง และ m คือความลึกสูงสุดของทรี
• เช่นเดียวกับ DFS ความซับซ้อนของพื้นที่ของอัลกอริทึมนี้คือ O(bm)

ข้อดี

• มีการประเมินพื้นที่การค้นหาอย่างละเอียด
• การตัดสินใจในเรื่อง AI นั้นทำได้ง่าย
• เครื่องจักรใหม่และสมาร์ทได้รับการพัฒนาด้วยอัลกอริธึมนี้

ข้อจำกัด

• เนื่องจากปัจจัยการแตกแขนงที่ใหญ่มาก กระบวนการในการบรรลุเป้าหมายจึงช้ากว่า
• การประเมินและการค้นหาโหนดและสาขาที่เป็นไปได้ทั้งหมดจะลดประสิทธิภาพและประสิทธิภาพของเครื่องยนต์
• ผู้เล่นทั้งสองมีทางเลือกมากเกินไปในการตัดสินใจ
• หากมีการจำกัดเวลาและพื้นที่ จะไม่สามารถสำรวจต้นไม้ทั้งหมดได้

แต่ด้วยการตัดแต่งกิ่งอัลฟ่า-เบต้า อัลกอริธึมสามารถปรับปรุงได้

บทสรุป

บทความนี้จะอธิบายทุกแง่มุมของ อัลกอริทึม min-max ใน AI ประการแรก การแนะนำทฤษฎีมีตัวอย่างสถานที่ที่ใช้ หลังจากนั้นจะมีคำอธิบายว่าอัลกอริทึมทำงานอย่างไรในเกม

อัลกอริธึมถูกแบ่งย่อยเพื่ออธิบายว่าการตัดสินใจในการเคลื่อนไหวที่เหมาะสมนั้นขึ้นอยู่กับการเคลื่อนไหวและการโต้กลับของผู้เล่นอย่างไร คุณสมบัติของอัลกอริทึมจะแสดงรายการแล้ว สุดท้ายนี้ มีข้อดีและข้อเสียของอัลกอริทึมไว้ด้วย

หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับแมชชีนเลิร์นนิง โปรดดูที่ IIIT-B & upGrad's Executive PG Program in Machine Learning & AI ซึ่งออกแบบมาสำหรับมืออาชีพที่ทำงานและมีการฝึกอบรมที่เข้มงวดมากกว่า 450 ชั่วโมง กรณีศึกษาและการมอบหมายมากกว่า 30 รายการ IIIT -B สถานะศิษย์เก่า 5+ โครงการหลักที่ปฏิบัติได้จริง & ความช่วยเหลืองานกับ บริษัท ชั้นนำ