Office of Academic Resources
Chulalongkorn University
Chulalongkorn University

Home / Help

Titleการศึกษาอัลกอริทึมการสืบค้นในเกมหมากรุกไทย / พีรพงษ์ เจียรณัย = A study of search algorithms for Thai Chess
Author Peeraphong Chearanai
Imprint 2538
Connect tohttp://cuir.car.chula.ac.th/handle/123456789/29422
Descript [10], 34 แผ่น : ภาพประกอบ, แผนภูมิ

SUMMARY

การวิจัยครั้งนี้ มีวัตถุประสงค์เพื่อศึกษาเปรียบเทียบอัลกอริทึมแบบเลือกในทางลึก ได้แก่ อัลกอริทึมอัลฟาเบตา และอัลกอริทึมตัวเลขคอนสไปเรซีในเกมหมากรุกไทย พัฒนาโปรแกรมเล่นเกมหมากรุกไทยโดยใช้อัลกอริทึมทั้งสองนี้ และหาข้อสรุปของอัลกอริทึมที่เหมาะสมในเกมหมากรุกไทย การหาข้อสรุปของอัลกอริทึมที่เหมาะสมในเกมหมากรุกไทยนั้น ทำได้โดยการทดลองซึ่งแบ่งออกเป็น 5 กลุ่มแต่ละกลุ่มเป็นการแข่งกันระหว่างอัลกอริทึมเป็นจำนวน 10 เกม การพิจารณาว่าฝ่ายใดฝ่ายหนึ่งชนะจะพิจารณาจากการรุกฆาตหรือการมีค่าคะแนนของตัวหมากสูงกว่า ทั้งนี้ไม่นับกรณีที่เกิดการเดินวนซ้ำ ผลแต่ละชุดการทดลองจะสรุปในรูปสัดส่วนการชนะของอัลกอริทึมตัวเลขคอนสไปเรซีและอัลกอริทึมอัลฟาเบตา เกมใดที่ไม่จบด้วยการรุกฆาตหรือมีผลต่างของคะแนนของตัวหมากจะไม่นำมาพิจารณา การทดลองกลุ่มที่ 1 กำหนดพารามิเตอร์ของอัลกอริทึมทั้งสองเพื่อให้สร้าง โหนดได้จำนวนใกล้เคียงกันตาเดิน ผลที่ได้คือ 6:1 การทดลองกลุ่มที่ 2 จำนวนกิ่งแยกของอัลกอริทึมตัวเลขคอนสไปเรซีเพิ่มขึ้นเพื่อทำให้ได้ตาเดินที่ดีขึ้น ผลที่ได้คือ8:0 การทดลองกลุ่มที่ 3 เมื่อเปรียบเทียบกับกลุ่มที่ 1 เพิ่มความลึกของอัลกอริทึมอัลฟาเบตา เพื่อทำให้เวลาที่ของทั้งสองอัลกอริทึมเพิ่มขึ้นเท่า ๆ กัน ผลที่ได้คืออัลกอริทึมอัลฟาเบตาชนะเพิ่มมากขึ้นเป็น 4:5 การทดลองชุดที่ 4เปรียบเทียบกับชุดที่ 3 เพิ่มค่าขีดแบ่งและจำนวนกิ่งแยกของโหนด เพื่อให้ทั้งสองอัลกอริทึมสร้างโหนดได้จำนวนมากกว่าหนึ่งพันโหนดต่อตาเดิน ผลที่ได้คืออัลกอริทึมตัวเลขคอนสไปเรซีชนะมากกว่าด้วยสัดส่วน 7:3 การทดลองชุดที่ 5 เปรียบเทียบกับการทดลองชุดที่ 3 เพิ่มความลึกของอัลกอริทึมอัลฟาเบตา เพื่อทำให้เวลาที่ใช้ในการสร้างตาเดินของทั้งสองอัลกอริทึมใช้เวลาเท่า ๆ กัน แม้ว่าจะเป็นผลลดีต่ออัลกอริทึมอัลฟาเบตาด้วยสัดส่วน 3:5 แต่ยังแสดงให้เห็นว่าอัลกอริทึมอัลฟาเบตาได้พัฒนาเพิ่มขึ้นเล็กน้อย อัลกอริทึมอัลฟาเบตาที่ทำการศึกษาในครั้งนี้ถูกจำกัดโดยระดับความลึกในการสืบค้นและใช้เวลาในการทำงานน้อยกว่าอัลกอริทึมตัวเลขคอนสไปเรซี ถ้าเวลา ไม่เป็นข้อจำกัดและทั้งสองอัลกอริทึมสร้างจำนวนโหนดได้ใกล้เคียงกันแล้ว อาจสรุปได้ว่าอัลกอริทึมตัวเลขคอนสไปเรซีสร้างตาเดินได้ดีกว่าอัลกอริทึมอัลฟาเบตาในโปรแกรมหมากรุกไทย และการศึกษาในโอกาสต่อไปควรพัฒนาประสิทธิภาพด้านความเร็วในการสืบค้นและพื้นที่หน่วยความจำที่ใช้ของอัลกอริทึมเลขคอนสไปเรซีในโปรแกรมหมากรุกไทยนี้
This study investigates the application of computer programs for playing Thai chess. It consists of three parts; one, study and comparison of two selective-deepening search algorithms: alpha-beta (AB) and conspiracy numbers (CN); two, development of a CN Thai chess program; and three, evaluation of CN and AB (which has been previously developed) Thai chess programs. Findings of the third part were based on five sets of experiments, SE-1 to SE-5, each of 10 games. The algorithm that checkmated or had a higher material value before both algorithms generated repeating moves was considered to have won the game. Results of each set were summarized as number of CN wins to number of AB wins (CN : AB) ; games not ending with a checkmate or a difference in material values were not included. In SE-1, parameters were selected to allow both algorithms to generate approximately similar node-numbers per move. CN:AB result of 6:1 was obtained. In SE-2, CN branching factor was increased to favor CN with CN:AB result of 8:0. In SE-3, as compared to SE-1, AB depth was increased to make move times of both algorithms more equal. This favored AB, and CN:AB result of 4:5 was obtained. In SE-4, as compared to SE-3, CN threshold and branching factor were increased to allow both algorithms to generate more than 1,000 nodes per move. This favored CN, and CN:AB result of 7:3 was obtained. In SE-5, as compared to SE-3, AB depth was increased to make move times of both algorithms more equal. Although this favored AB, CN:AB result of 3:5 showed only a slight improvement for AB. AB lacks search depth and requires less time to generate moves. If time is not a constraint, and if both algorithms are allowed to generate similar node-numbers, the results indicate that CN would outperform AB for Thai chess programs. Further work is needed to improve search speed and memory use of the CN Thai chess program developed in this study.


อัลกอริทึม หมากรุก -- ไทย โปรแกรมคอมพิวเตอร์

LOCATIONCALL#STATUS
Engineering Library : Thesisวิทยานิพนธ์LIB USE ONLY



Location



Office of Academic Resources, Chulalongkorn University, Phayathai Rd. Pathumwan Bangkok 10330 Thailand

Contact Us

Tel. 0-2218-2929,
0-2218-2927 (Library Service)
0-2218-2903 (Administrative Division)
Fax. 0-2215-3617, 0-2218-2907

Social Network

  line

facebook   instragram