Software เดินหมากฮอร์สไทยอัจริยะ

ชื่อผู้จัดทำโครงงานวิทยาศาสตร์
  • พุฒิพันธ์ พลยานันท์

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์
  • สุรพันธ์ เมฆนาวิน

สถาบันการศึกษาที่กำกับดูแลโครงงานวิทยาศาสตร์

นิสิตระดับปริญญาตรีปีที่ 3 มหาวิทยาลัยเกษตรศาสตร์

ระดับการศึกษา

โครงงานวิทยาศาสตร์ในระดับการศึกษาปริญญาโทขึ้นไป

หมวดวิชา

โครงงานวิทยาศาสตร์ในสาขาวิชาคอมพิวเตอร์

วันที่จัดทำโครงงานวิทยาศาสตร์

01 มกราคม 2541

บทคัดย่อโครงงานวิทยาศาสตร์

ซอฟท์แวร์เกม เป็นซอฟท์แวร์ที่ได้รับความนิยมอย่างมากในประเทศไทย แต่เกมส์ที่ได้รับความนิยมในประเทศไทยกลับเป็นของต่างประเทศส่วนใหญ่ การวิจัยเพื่อพัฒนาซอฟท์แวร์เกมจึงเป็นสิ่งที่จำเป็นต่อการพัฒนาซอฟท์แวร์เกมเพื่อให้คนไทยและคนต่างประเทศนิยมเล่นเกมไทยมากขึ้น สำหรับโปรแกรมเดินหมากฮอร์สไทยเป็นโปรแกรมที่มีเอกลักษณ์ความเป็นไทยเพราะโปรแกรมที่ช่วยฝึกสมองไหวพริบ เชาว์ปัญญา สมาธิความรอบคอบ ฯลฯ ให้แก่ผู้เล่น การพัฒนาโปรแกรมเดินหมากรุกไทยสามารถช่วยให้คนเล่นหมากฮอร์สไทยคนเดียวได้ ผู้เล่นสามารถฝึกทักษะการเดินหมาก ไปตามขั้นตอนเพราะโปรแกรมสามารถรับความฉลาดได้ ผู้เล่นสามารถเรียนรู้กลยุทธ์การเดินหมาก จากโปรแกรมได้เพราะโปรแกรมสามารถแสดงวิธีคิดและเหตุผลอย่างเป็นขั้นตอนได้ และการพัฒนาโปรแกรมเดินหมากฮอร์สไทยสามารถช่วยเผยแพร่เกมหมากฮอร์สไทยสู่คนต่างประเทศและคนไทยได้ง่าย เช่น การเผยแพร่ผ่านอินเตอร์เน็ต ต่างประเทศได้มีการพัฒนาโปรแกรมเดินหมากรุกสากลที่สามารถเอาชนะแชมป์โลกสำเร็จแล้ว ดังนั้นประเทศไทยควรมีโปรแกรมเดินหมากประสิทธิภาพสูงเช่นกัน จุดประสงค์หลักในการวิจัยโปรแกรมเดินหมากฮอร์สไทยครั้งนี้คือ เพื่อพัฒนาโปรแกรมเดินหมากฮอร์สไทยประสิทธิภาพสูงที่สามารถเอาชนะแชมป์หมากฮอร์สไทยระดับมือ ก ได้ และเพื่อหาอัลกอลิทึมและวิธีการพัฒนาโปรแกรมที่สามารถใช้พัฒนาโปรแกรมเดินหมากกระดานได้ทุกหมากซึ่งช่วยให้ ในอนาคตไม่ต้องวิจัยโปรแกรมเดินหมากกระดานอื่นๆอีก หรือวิจัยต่อเพียงเล็กน้อย การวิจัยครั้งนี้ ได้เน้นในส่วนอัลกอลิทึมที่ไม่ขึ้นต่อกติกาหมากฮอร์สไทยเป็นหลัก เช่น อัลกอลิทึมในการสืบค้นวิธีการเดินหมากที่ดีที่สุด เทคนิคการลดทอนปัญหา เทคนิคช่วยให้ใช้เวลาเดินหมากอย่างคุ้มค่า ฯลฯ ซึ่งไม่ขึ้นต่อกติกาหมากรุกไทยจึงสามารถใช้อัลกอลิทึมเดียวกันนี้กับหมากกระดานอื่นได้ แต่ทั้งที่พัฒนาโปรแกรมด้วยอัลกอลิทึมดังกล่าวทั้งหมดรวมกันแล้ว โปรแกรมก็ยังไม่สามารถเอาชนะแชมป์หมากฮอร์สไทยระดับมือ ข จึงต้องวิจัยเทคนิคที่ขึ้นต่อกติกาควบคู่กันไป เช่น การให้น้ำหนักหรือการวิเคราะห์ข้อดีข้อเสียของรูปแบบกระดานหนึ่งๆเพื่อใช้ประกอบการตัดสินใจขณะเดินหมาก เทคนิคการขึ้นกระดาน ฯลฯ อัลกอลิทึมสำคัญที่ศึกษาจากเอกสารอ้างอิงก่อนการวิจัยได้แก่ Minimax Search Algorithm เป็นอัลกอลิทึมในการสืบค้นหาคำตอบโดยการลองเดินล่วงหน้าไปหลายๆตา เพื่อพิจารณารูปแบบที่เป็นไปได้ทุกลักษณะและให้คะแนนหรือน้ำหนัก หรือข้อดีข้อเสียของแต่ละแบบ แล้วเลือกทางที่ดีที่สุดมาเดินจริงๆ กล่าวคือใน search tree1 ถ้าเป็นฝ่ายเราเดินจะต้องเลือกค่า cost ที่สูงที่สุด แต่ถ้าเป็นฝ่ายตรงข้ามเดินจะต้องเลือกค่า cost ที่ต่ำที่สุดมาเป็นค่า cost ของ parent node Alpha & Beta Pruning เป็นเทคนิคการปรับปรุง Minimax Search ให้ search node ลดลงโดยไม่มีผลข้างเคียง คือใน search tree สมมติว่าชั้นที่ n ต้องหา max cost ชั้นที่ n+1 หา min cost ในขณะที่กำลัง search ชั้นที่ n+1 อยู่ถ้า min cost เท่าที่หาได้มีค่าน้อยกว่า max cost ของชั้นที่ n จะสรุปได้ว่าไม่มีทางที่ min cost ของชั้นที่ n+1 จะมีผลต่อ max cost ของชั้นที่ n ดังนั้นจึงหยุด search ชั้นที่ n+1 ทันที อัลกอลิทึมและเทคนิคสำคัญที่พบว่าสามารถนำมาประยุกต์ใช้กับการวิจัยครั้งนี้ได้ ได้แก่Memorized Algorithm เป็นการเก็บค่า cost และ deep search ของกระดานที่ search แล้วไว้ในตาราง เพื่อจะได้ไม่ต้อง search ซ้ำในรูปแบบที่กระดานนั้นเคย search ด้วย deep ที่มากกว่าหรือเท่ากับ deep ที่อยู่ในตาราง แต่เนื่องจากรูปแบบของกระดานมีมากเกินไปจึงต้อง encode กระดานเป็นเลข n bit แล้วเก็บใน hash table จากการทดลองมากกว่า 100 ครั้งพบว่า Memorized Algorithm ช่วยเพิ่มประสิทธิภาพให้กับโปรแกรมได้มากกว่า Alpha Bata Pruning มาก DFID เป็นเทคนิคที่ประยุกต์ใช้ในระหว่างทำ Minimax Search เพื่อLimit เวลาแทนการ Limit จำนวนตาที่จะมองล่วงหน้า สำหรับรูปแบบกระดานต่างกันเวลาที่ใช้ในการมองล่วงหน้าไปเป็นจำนวนตาคงที่นั้นจะมีความแตกต่างกันอย่างมากในการเดินหมากจริงจะ Limit ไม่ให้ตาที่คิดนานนั้น นานเกินไป ซึ่งทำให้ตาอื่นๆมีเวลาเหลือมากเกินไป แต่ถ้าให้โปรแกรมคิดเต็มเวลาทุกครั้งจะทำให้ประสิทธิภาพรวมสูงขึ้น Preprocessing คือการเก็บ search tree ของตาแรกไว้ก่อนแล้วนำมาใช้เดินจริงๆในตาแรก เพราะสามารถหา search ของตาแรกไว้ก่อน แล้วนำมาใช้เดินจริงๆในตาแรก เพราะสามารถหา search tree ล่วงหน้าสามารถใช้เวลาได้นานกว่าและ search ได้ลึกถึง 17 ตาเป็นอย่างต่ำ และสามารถเพิ่มได้ถึง 30 ตา หากทำ Preprocessing บนเครื่องคอมพิวเตอร์ประสิทธิภาพสูง เทคนิคการขึ้นกระดาน เนื่องจากโปรแกรมยังไม่สามารถมองล่วงหน้าจากตาแรกๆได้ไกลมากนัก ประกอบกับการขึ้นกระดานมีเพียง 1 2 รูปแบบ จึงควรใส่วิธีการขึ้นกระดานที่ดีไว้เป็นสูตรให้กับโปรแกรม ไม่หยุด search ในตาที่มีการกิน เนื่องจากในตาที่ตัวหมากกำลังจะโดนกิจอย่างแน่นอน ถ้าหยุด search ที่แล้วให้คะแนน โดยการนับจำนวนตัวหมากที่เหลืออยู่ในตานั้น จะทำให้คะแนนที่ได้ไม่ตรงกับสภาพสถานการณ์จริง เทคนิคการคิด cost function เช่นการให้คะแนนรูปแบบกระดาษที่มีการเดินเกาะกลุ่มและอยู่บริเวณกระดาษมากขึ้น ฯลฯ จะเป็นการเพิ่มเซ้นส์ในการตัดสินใจให้กับโปรแกรม Pruning อื่นๆ เช่นการหยุด search ต่อในแนวลึกเมื่อค่า cost มากหรือน้อยจนคิดว่าน่าจะเดาผลแพ้ชนะได้ แต่คำตอบที่ได้จะเป็นคำตอบแบบ near optimal แทนที่จะเป็นแบบ optimal ซึ่งอาจทำให้ผลการเดินผิดพลาดมากในบางครั้ง ซึ่งต้องทำการทดลองจริงเพื่อหาประสิทธิภาพของแต่ละเทคนิคว่าคุ้มค่าหรือไม่ และนำเฉพาะเทคนิคที่สามารถเพิ่มประสิทธิภาพรวมของโปรแกรมได้จริงมาใช้งาน มีอุปสรรคในการพัฒนามาก เนื่องจากเป็นโปรแกรมที่ต้องใช้อัลกอลิทึมขั้นสูงในการทำให้ คอมพิวเตอร์คิดเป็นและมีความสามารถในการเดินหมากสูง และทั้งที่ใช้อัลกอลิทึมหลายอย่างร่วมกันแล้วยังเดินหมากฮอร์สไทยแพ้แชมป์ระดับมือ ข อยู่ จึงต้องคิดค้นและประยุกต์ใช้อัลกอลิทึมเพิ่มอีก ซึ่งการหาอัลกอลิทึมแต่ละอย่างนั้นทำได้อย่างยากลำบากมาก โดยเฉพาะการหาอัลกอลิทึมเพิ่มเติมสำหรับโปรแกรมมีอัลกอลิทึมอยู่แล้วยิ่งทำได้ยากเพิ่มขึ้นอีกเป็นเท่าตัว และเนื่องจากเป็นปัญหาที่มีขนาดปัญหาใหญ่มากจึงต้องการเครื่องคอมพิวเตอร์ประสิทธิภาพสูงในการทำ Preprocessing ซึ่งหากทำได้ถึง 30 ตา เทคนิคนี้จะกลายเป็นเทคนิคที่สำคัญที่สุด แต่ไม่สามารถหาคอมพิวเตอร์ดังกล่าวในบริเวณที่ใกล้ที่พักได