การค้นหาแบบปฏิปักษ์และการเล่นเกม

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

Definition

การค้นหาแบบปฏิปักษ์จะคำนวณการเดินหมากสำหรับผู้เล่นโดยการสำรวจแผนภูมิต้นไม้ของเกมที่ผู้เล่นผลัดกันเดิน โดยใช้หลักการมินิแม็กซ์ (ผู้เล่นแต่ละคนจะปรับให้เหมาะสมโดยสมมติว่าคู่ต่อสู้เล่นได้อย่างเหมาะสมที่สุด) ร่วมกับการตัดกิ่งและการประเมินแบบฮิวริสติกเพื่อรับมือกับแผนภูมิต้นไม้ขนาดใหญ่

Scope

หัวข้อนี้ครอบคลุมการค้นหาในเกมที่มีผู้เล่นสองคน, ผลรวมเป็นศูนย์, และข้อมูลสมบูรณ์: กฎการตัดสินใจแบบมินิแม็กซ์, การตัดกิ่งอัลฟา-เบต้าที่ช่วยให้มินิแม็กซ์ข้ามกิ่งที่ไม่เกี่ยวข้องอย่างชัดเจน, ฟังก์ชันการประเมินและการค้นหาแบบจำกัดความลึกสำหรับเกมที่ใหญ่เกินกว่าจะแก้ได้อย่างแม่นยำ, และการค้นหาแบบต้นไม้มอนติคาร์โลสำหรับเกมที่มีปัจจัยการแตกกิ่งที่ใหญ่มาก หัวข้อนี้กล่าวถึงวิธีการจำลองแผนภูมิต้นไม้ของเกมและข้อจำกัดในการคำนวณที่บังคับให้ต้องมีการตัดตอนแบบฮิวริสติก ไม่ครอบคลุมการวิเคราะห์สมดุลทฤษฎีเกมทั่วไปของแรงจูงใจหลายตัวแทน ซึ่งจะกล่าวถึงภายใต้ระบบหลายตัวแทน

Core questions

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

Key concepts

• แผนภูมิต้นไม้ของเกม
• ค่ามินิแม็กซ์
• การตัดกิ่งอัลฟา-เบต้า
• ฟังก์ชันการประเมิน (ฮิวริสติก)
• การค้นหาแบบจำกัดความลึกและผลกระทบขอบฟ้า
• เกมผลรวมเป็นศูนย์ที่มีข้อมูลสมบูรณ์
• การค้นหาแบบต้นไม้มอนติคาร์โล
• การจัดลำดับการเดินหมาก

Key theories

กฎการตัดสินใจแบบมินิแม็กซ์

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

การตัดกิ่งอัลฟา-เบต้า

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

การค้นหาแบบต้นไม้มอนติคาร์โล

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

Clinical relevance

การค้นหาแบบปฏิปักษ์ได้สร้างระบบ AI ที่เป็นจุดเด่น ตั้งแต่เครื่องยนต์หมากรุกที่ใช้การค้นหาแบบอัลฟา-เบต้า ไปจนถึงโปรแกรมโกะที่อิงจากการค้นหาแบบต้นไม้มอนติคาร์โล และเทคนิคเดียวกันนี้ยังใช้ในการเจรจาอัตโนมัติ เกมรักษาความปลอดภัย และสถานการณ์ใดๆ ที่จำลองเป็นการแข่งขันระหว่างฝ่ายที่ปรับให้เหมาะสม

History

บทความของ Shannon ในปี 1950 ได้วางกรอบการเล่นหมากรุกด้วยคอมพิวเตอร์เป็นการค้นหาแบบมินิแม็กซ์ด้วยฟังก์ชันการประเมิน และทฤษฎีมินิแม็กซ์ของ von Neumann ได้วางรากฐานทางทฤษฎีเกม การตัดกิ่งอัลฟา-เบต้าได้รับการพัฒนาตลอดช่วงทศวรรษ 1950-60 และได้รับการวิเคราะห์อย่างเข้มงวดโดย Knuth และ Moore (1975) การค้นหาแบบต้นไม้มอนติคาร์โล ซึ่งได้รับการจัดรูปแบบอย่างเป็นทางการในทศวรรษ 2000 ได้ขับเคลื่อนการก้าวกระโดดครั้งต่อไปในความแข็งแกร่งของการเล่นเกม โดยเฉพาะอย่างยิ่งในเกมโกะ

Key figures

• Claude E. Shannon
• John von Neumann
• Arthur Samuel
• Donald E. Knuth
• Ronald W. Moore

Seminal works

• shannon1950
• knuth1975
• browne2012

Frequently asked questions

การตัดกิ่งอัลฟา-เบต้าเปลี่ยนการเดินหมากที่มินิแม็กซ์จะเลือกหรือไม่?

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

ทำไมถึงใช้การค้นหาแบบต้นไม้มอนติคาร์โลแทนมินิแม็กซ์ในเกมอย่างโกะ?

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