การศึกษาอัลกอริทึมการสืบค้นในเกมหมากรุกไทย

พีรพงษ์ เจียรณัย

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/29422

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	บุญเสริม กิจศิริกุล
dc.contributor.author	พีรพงษ์ เจียรณัย
dc.contributor.other	จุฬาลงกรณ์มหาวิทยาลัย. บัณฑิตวิทยาลัย
dc.date.accessioned	2013-03-08T06:46:42Z
dc.date.available	2013-03-08T06:46:42Z
dc.date.issued	2538
dc.identifier.isbn	9746327437
dc.identifier.uri	http://cuir.car.chula.ac.th/handle/123456789/29422
dc.description	วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2538	en
dc.description.abstract	การวิจัยครั้งนี้ มีวัตถุประสงค์เพื่อศึกษาเปรียบเทียบอัลกอริทึมแบบเลือกในทางลึก ได้แก่ อัลกอริทึมอัลฟาเบตา และอัลกอริทึมตัวเลขคอนสไปเรซีในเกมหมากรุกไทย พัฒนาโปรแกรมเล่นเกมหมากรุกไทยโดยใช้อัลกอริทึมทั้งสองนี้ และหาข้อสรุปของอัลกอริทึมที่เหมาะสมในเกมหมากรุกไทย การหาข้อสรุปของอัลกอริทึมที่เหมาะสมในเกมหมากรุกไทยนั้น ทำได้โดยการทดลองซึ่งแบ่งออกเป็น 5 กลุ่มแต่ละกลุ่มเป็นการแข่งกันระหว่างอัลกอริทึมเป็นจำนวน 10 เกม การพิจารณาว่าฝ่ายใดฝ่ายหนึ่งชนะจะพิจารณาจากการรุกฆาตหรือการมีค่าคะแนนของตัวหมากสูงกว่า ทั้งนี้ไม่นับกรณีที่เกิดการเดินวนซ้ำ ผลแต่ละชุดการทดลองจะสรุปในรูปสัดส่วนการชนะของอัลกอริทึมตัวเลขคอนสไปเรซีและอัลกอริทึมอัลฟาเบตา เกมใดที่ไม่จบด้วยการรุกฆาตหรือมีผลต่างของคะแนนของตัวหมากจะไม่นำมาพิจารณา การทดลองกลุ่มที่ 1 กำหนดพารามิเตอร์ของอัลกอริทึมทั้งสองเพื่อให้สร้าง โหนดได้จำนวนใกล้เคียงกันตาเดิน ผลที่ได้คือ 6:1 การทดลองกลุ่มที่ 2 จำนวนกิ่งแยกของอัลกอริทึมตัวเลขคอนสไปเรซีเพิ่มขึ้นเพื่อทำให้ได้ตาเดินที่ดีขึ้น ผลที่ได้คือ8:0 การทดลองกลุ่มที่ 3 เมื่อเปรียบเทียบกับกลุ่มที่ 1 เพิ่มความลึกของอัลกอริทึมอัลฟาเบตา เพื่อทำให้เวลาที่ของทั้งสองอัลกอริทึมเพิ่มขึ้นเท่า ๆ กัน ผลที่ได้คืออัลกอริทึมอัลฟาเบตาชนะเพิ่มมากขึ้นเป็น 4:5 การทดลองชุดที่ 4เปรียบเทียบกับชุดที่ 3 เพิ่มค่าขีดแบ่งและจำนวนกิ่งแยกของโหนด เพื่อให้ทั้งสองอัลกอริทึมสร้างโหนดได้จำนวนมากกว่าหนึ่งพันโหนดต่อตาเดิน ผลที่ได้คืออัลกอริทึมตัวเลขคอนสไปเรซีชนะมากกว่าด้วยสัดส่วน 7:3 การทดลองชุดที่ 5 เปรียบเทียบกับการทดลองชุดที่ 3 เพิ่มความลึกของอัลกอริทึมอัลฟาเบตา เพื่อทำให้เวลาที่ใช้ในการสร้างตาเดินของทั้งสองอัลกอริทึมใช้เวลาเท่า ๆ กัน แม้ว่าจะเป็นผลลดีต่ออัลกอริทึมอัลฟาเบตาด้วยสัดส่วน 3:5 แต่ยังแสดงให้เห็นว่าอัลกอริทึมอัลฟาเบตาได้พัฒนาเพิ่มขึ้นเล็กน้อย อัลกอริทึมอัลฟาเบตาที่ทำการศึกษาในครั้งนี้ถูกจำกัดโดยระดับความลึกในการสืบค้นและใช้เวลาในการทำงานน้อยกว่าอัลกอริทึมตัวเลขคอนสไปเรซี ถ้าเวลา ไม่เป็นข้อจำกัดและทั้งสองอัลกอริทึมสร้างจำนวนโหนดได้ใกล้เคียงกันแล้ว อาจสรุปได้ว่าอัลกอริทึมตัวเลขคอนสไปเรซีสร้างตาเดินได้ดีกว่าอัลกอริทึมอัลฟาเบตาในโปรแกรมหมากรุกไทย และการศึกษาในโอกาสต่อไปควรพัฒนาประสิทธิภาพด้านความเร็วในการสืบค้นและพื้นที่หน่วยความจำที่ใช้ของอัลกอริทึมเลขคอนสไปเรซีในโปรแกรมหมากรุกไทยนี้
dc.description.abstractalternative	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.
dc.format.extent	2593497 bytes
dc.format.extent	995524 bytes
dc.format.extent	4355580 bytes
dc.format.extent	2759533 bytes
dc.format.extent	2486916 bytes
dc.format.extent	1490619 bytes
dc.format.extent	579279 bytes
dc.format.mimetype	application/pdf
dc.format.mimetype	application/pdf
dc.format.mimetype	application/pdf
dc.format.mimetype	application/pdf
dc.format.mimetype	application/pdf
dc.format.mimetype	application/pdf
dc.format.mimetype	application/pdf
dc.language.iso	th	es
dc.publisher	จุฬาลงกรณ์มหาวิทยาลัย	en
dc.rights	จุฬาลงกรณ์มหาวิทยาลัย	en
dc.title	การศึกษาอัลกอริทึมการสืบค้นในเกมหมากรุกไทย	en
dc.title.alternative	A study of search algorithms for Thai Chess	en
dc.type	Thesis	es
dc.degree.name	วิทยาศาสตรมหาบัณฑิต	es
dc.degree.level	ปริญญาโท	es
dc.degree.discipline	วิศวกรรมคอมพิวเตอร์
dc.degree.grantor	จุฬาลงกรณ์มหาวิทยาลัย	en
Appears in Collections:	Grad - Theses

Files in This Item:

File	Size	Format
Peeraphong_ch_front.pdf	2.53 MB	Adobe PDF	View/Open
Peeraphong_ch_ch1.pdf	972.19 kB	Adobe PDF	View/Open
Peeraphong_ch_ch2.pdf	4.25 MB	Adobe PDF	View/Open
Peeraphong_ch_ch3.pdf	2.69 MB	Adobe PDF	View/Open
Peeraphong_ch_ch4.pdf	2.43 MB	Adobe PDF	View/Open
Peeraphong_ch_ch5.pdf	1.46 MB	Adobe PDF	View/Open
Peeraphong_ch_back.pdf	565.7 kB	Adobe PDF	View/Open

Show simple item record