วันพุธที่ 9 กันยายน พ.ศ. 2558
การตัดสินใจใช้ทฤษฎีเกม(Decision Making using Game Theory)
Games as Search Problems(เกมเป็นปัญหาค้นหา)
Minimax
- ได้รับต้นไม้เกมนี้กลยุทธ์ที่ดีที่สุดสามารถ กำหนดโดยการตรวจสอบค่าของ Minimax แต่ละโหนด
- minimax_value(s)
maxs’ є Successors(s) minimax_value(s’)if s is MAX
mins’ є Successors(s) minimax_value(s’) if s is MIN
คำนวณค่าminimaxจากด้านล่างขึ้น
- ค่าฟังก์ชั่นมินิแมกซ์) พบว่าผลของ MAX MIN สมมติว่ายังเล่นได้อย่างดีที่สุด
- ค่าฟังก์ชั่นมินิแมกซ์) พบว่าผลของ MAX กรณีเลวร้ายที่สุด; ว่ามีที่แม็กซ์อาจได้รับแม้จะเป็นผลดีกว่าถ้า MIN เล่นที่ไม่ได้อย่างดีที่สุด
- ปัญหาที่อาจเกิดขึ้น: จำนวนมากของโหนดในต้นไม้ค้นหา (ชี้แจงในการแยกปัจจัยและความลึก)
- แต่ก็เป็นไปได้ที่จะได้รับการแก้ปัญหาตรงเดียวกันโดยไม่ต้องมองหาที่โหนดในต้นไม้เกมทุก !!
Alpha-Beta Pruning
- จะช่วยให้การแก้ปัญหาเช่นเดียวกับมินิแมกซ์จะโดยไม่ได้มองที่โหนดในต้นไม้เกมทุก
- Prunesไปสาขาที่ไม่สามารถเป็นไปได้ มีอิทธิพลต่อการตัดสินใจครั้งสุดท้าย
- α: ค่าที่ต่ำกว่ามินิแมกซ์มุ่ง MAX
- β: ค่ามินิแมกซ์บนมุ่ง MIN
- ด้วยการตัดแต่งกิ่งα-βดูที่ 6 โหนด
- โดยไม่ต้องมีการตัดแต่งกิ่งα-βดูที่ 9 โหนด
- ยังคงมีการตัดแต่งกิ่งแม้จะมีα-βทำงานในเต็มรูปแบบต้นไม้ที่เป็นไปไม่ได้เกมมากที่สุดในโลกแห่งความจริงปัญหาที่เกิดขึ้น
หมากรุก
- กว่า 1,300 ปี
- เกมกระดานสองคนซึ่งจำลองการต่อสู้ระหว่างกองทัพทั้งสองฝ่ายตรงข้าม
- ผู้เล่นผลัดกันการย้ายหรือการจับ
- วัตถุประสงค์: เพื่อจับกษัตริย์ของฝ่ายตรงข้าม
- ตรวจสอบ: ผู้เล่น declares "ตรวจสอบ" เมื่อเขาย้ายในลักษณะที่คุกคาม พระมหากษัตริย์ของฝ่ายตรงข้ามกับการจับภาพ (และพระมหากษัตริย์มีความหมายของการหลบหนี) ฝ่ายตรงข้ามจะต้องได้รับพระมหากษัตริย์ออกจากการตรวจสอบทันที
- ก่อให้เกิดปัญหา หมากรุกเป็นปัญหาการค้นหาโดยการระบุพื้นที่ของรัฐสถานะเริ่มต้นเป้าหมายการดำเนินการค่าใช้จ่ายในเส้นทาง
- สร้างต้นไม้ค้นหา
- ปัญหาที่อาจเกิดขึ้น
- จะเป็นการดีที่สร้างต้นไม้ค้นหาทั้งหมดทางลงไปทุกใบและใช้มินิแมกซ์ ใช้การตัดแต่งกิ่งα-βเพื่อลดต้นไม้ค้นหา
- ในความเป็นจริงต้นไม้ค้นหาอาจจะมีขนาดใหญ่เกินกว่าที่จะสร้าง
- แทนการสร้างต้นไม้ที่สมบูรณ์หยุดที่จุดหนึ่งและประเมินคุณภาพของโหนดโดยใช้ฟังก์ชั่นการประเมินผล
การตัดสินใจแบบ Real-Time
- โดยประมาณ (และแน่นอน) การแก้ปัญหา
- ใช้ฟังก์ชั่นการประเมินผลการแก้ปัญหา
- กำหนดของสถานะ (หรือขั้วกลาง) ฟังก์ชั่นการประเมินผลตอบแทนประมาณการของยูทิลิตี้ที่คาดหวังของเกมที่
- ควรจะรวดเร็วในการคำนวณ
- Ex: ฟังก์ชั่นการประเมินผลง่ายสำหรับการหมากรุก
Pawn: 1 point
Knight/bishop: 3 points
Rook: 5 points
Queen: 9 points
สรุปผลคะแนนของทุกชิ้นบนกระดาน
ฟังก์ชั่นการประเมินผลที่สูงขึ้นอาจจะยัง
มองไปที่ความสัมพันธ์ระหว่างตำแหน่งในหมู่ชิ้น
- ในการตัดสินใจแบบ real-time ใช้มินิแมกซ์ที่มีการตัดแต่งกิ่งα-βกับสองการปรับเปลี่ยน
-Cut ออกต้นไม้ค้นหาที่ขีด จำกัด ระดับความลึกคงที่
-ฟังก์ชั่นการประเมินผลการใช้งานที่จะประเมินยูทิลิตี้ของสถานะ
- ตัดควรจะนำมาใช้กับนิ่ง (ไม่สำคัญ) รัฐ
