คอมพิวเตอร์หมากรุกไทย : รายงานโครงการสิ่งประดิษฐ์

Abstract

การวิจัยนี้ศึกษาเปรียบเทียบอัลกอริทึมค้นหาในหมากรุกไทย ได้แก่ อัลกอริทึมมินิแมกซ์+การลดทอนโดยอัลฟาเบตา อัลกอริทึม B* และอัลกอริทึมตัวเลขคอนสไปเรซี นำอัลกอริทึมมาพัฒนา โปรแกรมเล่นเกมหมากรุกไทยและหาข้อสรุปของอัลกอริทึมที่เหมาะสมในเกมหมากรุกไทยเรานิยามฟังก์ชันฮิวริสที่เหมาะสมต่อการเขียนโปรแกรมของอัลกอริทึมในหมากรุกไทย และทำการทดลองเพื่อเปรียบเทียบอัลกอริทึม การทดลองแบ่งออกเป็น 4 ชุดเพื่อใช้แข่งกันชุดละ 10 เกม การทดลองในแต่ละชุดได้ออกแบบขึ้นเพื่อวัดค่าคะแนนของหมากที่เหลือเมื่อควบคุมให้จำนวนโหนดที่สร้างได้ในแต่ละอัลกอรึทึมใกล้เคียงกัน หรือวัดค่าคะแนนของหมากที่เหลือเมื่อควบคุมเวลาในการสร้างตาเดินจากแต่ละอัลกอริทึมภายในเวลาเท่ากัน ทำการวัดประสิทธิภาพของอัลกอริทึมตามการทดลองที่ออกแบบไว้ โดยใช้โปรแกรมหมากรุกไทยที่พัฒนาขึ้น ผลการวิจัยพบว่า 1.)อัลกอริทึม B* ไม่เหมาะสมกับหมากรุกไทย เนื่องจากการนิยามฟังก์ชันฮิวริสติกสำหรับการลู่เข้าของอัลกอริทึมเป็นไปได้ยาก 2.)อัลกอริทึมตัวเลขคอนสไปเรซีสร้างตาเดินได้ดีกว่าอัลกอริทึมมินิแมกซ์+การลดทอนโดยอัลฟาเบตา เนื่องจากสืบค้นได้ลึกกว่าเมื่อกำหนดให้แต่ละอัลกอริทึมสร้างโหมดได้ใกล้เคียงกัน และ3.)อัลกอริทึมมินิแมกซ์+การลดทอนโดยอัลฟาเบตาสร้างตาเดินได้ดีกว่าอัลกอริทึมตัวเลขคอนสไปเรซี เนื่องจากสร้างโหนดได้มากกว่า เมื่อกำหนดให้แต่ละอัลกอริทึมสร้างตาเดินภายในเวลาเท่ากัน โดยสรุป อัลกอริทึมมินิแมกซ์+การลดทอนโดยอัลฟาเบตามีความเหมาะสมที่จะนำมาใช้ในเกมหมากรุกไทยมากกว่าอัลกอริทึมอื่น เนื่องจากประสิทธิภาพที่เหนือกว่าในด้านความเร็วของการสืบค้น และพื้นที่หน่วยความจำที่ใช้ อย่างไรก็ตามอัลกอริทึมตัวเลขคอนสไปเรซีเป็นอีกทางเลือกหนึ่งที่น่าสนใจ ในแง่ของการสร้างตาเดินที่มีคุณภาพ หากแต่ยังมีความต้องการศึกษาเพิ่มเติมเพื่อปรับปรุงประสิทธิภาพด้านความเร็ว และพื้นที่หน่วยความจำที่ใช้