chess_engine_using_python

โปรแกรมหมากรุกใช้ Python

พื้นที่เก็บข้อมูลนี้มีการใช้งานกลไกหมากรุกโดยใช้ Minimax การตัดแต่ง Alpha-Beta และอัลกอริธึม การค้นหา Quiescence สมุดบันทึก Jupyter ภายใน Docker Container ใช้สำหรับการเข้ารหัส Jupyter Notebook ทั้งหมดมีจำหน่ายในรูปแบบอิมเมจนักเทียบท่าด้วย

ตรวจสอบเอกสารโครงการเพื่อดูการวิเคราะห์โดยละเอียด

ใช้โมดูลภายนอก

• หมากรุกหลาม

วิธีรันโดยใช้นักเทียบท่า

docker pull codewithnk/chess-engine-using-python:latest

docker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest

อัลกอริธึมเครื่องยนต์หมากรุก

ขั้นต่ำแม็กซ์

ทฤษฎี

แก่นแท้ของการเล่นหมากรุกใน minmax โดยปกติ Minmax จะเชื่อมโยงชิ้นส่วนสีดำเข้ากับ MAX และชิ้นส่วนสีขาวจะเชื่อมโยงเข้ากับ MIN และจะประเมินจากมุมมองสีขาวเสมอ

อัลกอริธึม Minmax เป็นอัลกอริธึมการค้นหาฝ่ายตรงข้ามในทฤษฎีเกม มันใช้แผนผังเกมและรวมถึงผู้เล่นสองคน MIN และ MAX ผู้เล่นทั้งสองพยายามทำให้การกระทำของผู้อื่นเป็นโมฆะ Max พยายามทำให้ผลลัพธ์สูงสุด ในขณะที่ MIN พยายามย่อผลลัพธ์ให้เล็กสุด ผู้เล่นทั้งสองเล่นสลับกัน ภายใต้สมมติฐานว่าทั้งคู่เล่นได้อย่างเหมาะสมที่สุด การเล่นที่เหมาะสมที่สุดหมายถึงผู้เล่นทั้งสองคนกำลังเล่นตามกฎ กล่าวคือ MIN กำลังลดผลลัพธ์ให้เหลือน้อยที่สุด และ MAX กำลังเพิ่มผลลัพธ์ให้สูงสุด

อัลกอริธึม minmax ใช้แนวทาง Depth First Search เพื่อค้นหาผลลัพธ์ นอกจากนี้ยังใช้การย้อนรอยและการเรียกซ้ำอีกด้วย อัลกอริทึมจะสำรวจจนถึงโหนดเทอร์มินัล จากนั้นจะย้อนรอยในขณะที่เปรียบเทียบค่าลูกทั้งหมด มันจะเลือกค่าต่ำสุดหรือสูงสุดตามตาของใคร จากนั้นจะเผยแพร่ค่ากลับไปยังพาเรนต์ ใช้ฟังก์ชันการประเมินแบบคงที่เพื่อกำหนดค่าที่โหนดแต่ละโหนด มันใช้ประโยชน์จากเกม Zero-Sum

การนำไปปฏิบัติ

Ches Engine โดยใช้ Minmax

ความซับซ้อนของเวลา

Minmax ใช้ Depth First Search (DFS) บน Game Tree ดังนั้นความซับซ้อนของเวลาของอัลกอริทึม minmax คือ O(b**m) โดยที่ b คือปัจจัยการแตกแขนงของแผนผังเกม และ m คือความลึกสูงสุดของแผนผัง

ความซับซ้อนของอวกาศ

ความซับซ้อนของพื้นที่ของอัลกอริธึม minmax ก็คล้ายคลึงกับ DFS ซึ่งก็คือ O(bm) โดยที่ b คือปัจจัยการแตกแขนงของแผนผังเกม และ m คือความลึกสูงสุดของแผนผัง

ความสมบูรณ์

อัลกอริธึม Minmax เสร็จสมบูรณ์ มันจะพบวิธีแก้ปัญหาอย่างแน่นอน ถ้ามี ในแผนผังการค้นหาที่มีขอบเขตจำกัด

การเพิ่มประสิทธิภาพ

อัลกอริธึม Minmax จะเหมาะสมที่สุดหากทั้งสองฝ่ายเล่นได้อย่างเหมาะสมที่สุด

---

การตัดแต่งกิ่งอัลฟ่าเบต้า

ทฤษฎี

อัลกอริธึม minmax สามารถปรับให้เหมาะสมได้โดยการตัดกิ่งไม่กี่สาขา กิ่งที่ตัดแต่งแล้วเป็นกิ่งที่ไม่ส่งผลต่อผลลัพธ์ มันจะปรับปรุงความซับซ้อนของเวลา minmax เวอร์ชันนี้เรียกว่า minmax พร้อมการตัดแต่งอัลฟ่าเบต้า มันถูกเรียกว่าเป็นอัลกอริทึมอัลฟาเบต้า
ในการตัดแต่งกิ่ง Alpha-Beta มีสองค่าคือ Alpha และ Beta ต่อไปนี้เป็นจุดที่ควรพิจารณาเกี่ยวกับอัลฟ่าและเบต้า:

บางจุดเกี่ยวกับอัลฟ่า (α)

• อัลฟ่าคือค่าสูงสุดที่พบในเส้นทาง MAX
• ค่าเริ่มต้นของอัลฟ่าคือค่าอนันต์ติดลบ เนื่องจากค่าอัลฟ่าจะเพิ่มขึ้นเรื่อยๆ หรือคงเดิมในทุกการเคลื่อนไหว หากเราเลือกค่าอื่นที่ไม่ใช่ค่าอนันต์เชิงลบ สถานการณ์อาจเกิดขึ้นโดยค่าอัลฟ่าทั้งหมดอาจน้อยกว่าค่าที่เลือก เราจึงต้องเลือกค่าต่ำสุดที่เป็นไปได้ และนั่นคือลบอนันต์
• อัลฟ่าได้รับการอัพเดตโดยผู้เล่น MAX เท่านั้น

บางประเด็นเกี่ยวกับ Beta(β)

• เบต้าคือค่าต่ำสุดที่พบในเส้นทาง MIN
• ค่าเริ่มต้นของเบต้าคือค่าอนันต์บวก เนื่องจากค่าเบต้าจะลดลงเรื่อยๆ หรือคงเดิมในทุกการเคลื่อนไหว หากเราเลือกค่าอื่นที่ไม่ใช่ค่าอนันต์บวก สถานการณ์อาจเกิดขึ้นโดยที่ค่าเบต้าทั้งหมดอาจมากกว่าค่าที่เลือก เราจึงต้องเลือกค่าสูงสุดที่เป็นไปได้ และนั่นคือค่าอนันต์บวก
• ค่าเบต้าได้รับการอัพเดตโดยผู้เล่น MIN เท่านั้น

ในขณะที่การย้อนรอยเฉพาะค่าโหนดเท่านั้นที่จะถูกส่งผ่านไปยังพาเรนต์ ไม่ใช่ค่าอัลฟ่าและเบต้า

เงื่อนไขสำหรับการตัดแต่งกิ่งอัลฟ่าเบต้า:

 α >= β

ย้ายคำสั่ง

ประสิทธิผลของอัลกอริธึมอัลฟ่า-เบต้านั้นขึ้นอยู่กับลำดับการเคลื่อนที่เป็นอย่างมาก มันมีบทบาทสำคัญในความซับซ้อนของเวลาและพื้นที่

การสั่งซื้อที่แย่ที่สุด

ในบางกรณี ไม่มีการตัดโหนดหรือแผนผังย่อยออกจากแผนผังเกม ในกรณีนี้ การเคลื่อนไหวที่ดีที่สุดจะเกิดขึ้นในแผนผังย่อยทางขวาของ Game Tree ซึ่งจะส่งผลให้ความซับซ้อนของเวลาเพิ่มขึ้น

การสั่งซื้อในอุดมคติ

ในกรณีนี้ จำนวนสูงสุดของโหนดและแผนผังย่อยจะถูกตัดออก การเคลื่อนไหวที่ดีที่สุดเกิดขึ้นในทรีย่อยด้านซ้าย จะช่วยลดความซับซ้อนของเวลาและพื้นที่

การนำไปปฏิบัติ

Chess Engine ที่ใช้ Alpha-Beta Pruning

ความซับซ้อนของเวลา

อัลฟ่าเบต้าอัลกอริธึม ยังใช้ Depth First Search (DFS) บน Game Tree อีกด้วย

• ในกรณีที่มีการสั่งซื้อแย่ที่สุด: O(b^m)
• ในกรณีที่เป็นการสั่งซื้อในอุดมคติ: O(b^m/2)

ความซับซ้อนของอวกาศ

• ในกรณีที่มีการสั่งซื้อแย่ที่สุด: O(bm)
• ในกรณีที่ต้องการสั่งซื้อ: O(b(m/2))

ความสมบูรณ์

อัลกอริธึมอัลฟ่า-เบต้าเสร็จสมบูรณ์ มันจะพบวิธีแก้ปัญหาอย่างแน่นอน ถ้ามี ในแผนผังการค้นหาที่มีขอบเขตจำกัด

การเพิ่มประสิทธิภาพ

อัลกอริธึมอัลฟ่า-เบต้าจะเหมาะสมที่สุดหากทั้งสองฝ่ายเล่นได้อย่างเหมาะสมที่สุด

---

ค้นหาความสงบ

Quiescence Search เป็นการปรับเปลี่ยนที่อยู่ด้านบนของการตัดแต่งอัลฟ่าเบต้าด้วยค่าต่ำสุด-สูงสุด Quiscence ความหมายคือ ความเงียบ การค้นหานี้จะประเมินเฉพาะการเคลื่อนไหวที่เงียบๆ เท่านั้น กล่าวอีกนัยหนึ่ง หลังจากความลึกระดับหนึ่ง ระบบจะใช้เฉพาะการเคลื่อนไหวแบบจับเพื่อคำนวณการเคลื่อนไหวถัดไป การค้นหาความสงบสามารถหลีกเลี่ยงเอฟเฟกต์ขอบฟ้าได้
เอฟเฟ็กต์ขอบฟ้าเกิดขึ้นเมื่อเราค้นหาเพียงความลึกระดับหนึ่งเท่านั้น แต่อาจเกิดขึ้นได้ว่าหากเรามองลึกลงไปอีกระดับหนึ่ง การเคลื่อนที่ก็อาจได้คะแนนน้อยลง การค้นหาความสงบจะใช้เพียงการเคลื่อนไหวเพื่อจับภาพเพื่อป้องกันสิ่งนี้ การค้นหาแบบสงบยังช่วยลดปัจจัยการแตกแขนงในระดับต่างๆ ส่งผลให้อัลกอริธึมรวดเร็ว

ความซับซ้อนของเวลา

อัลกอริธึมการค้นหาแบบ Quiescence ยังใช้ Depth First Search (DFS) บน Game Tree อีกด้วย

• ในกรณีที่มีการสั่งซื้อแย่ที่สุด: O(b^m)
• ในกรณีที่เป็นการสั่งซื้อในอุดมคติ: O(b^m/2)

ความซับซ้อนของอวกาศ

• ในกรณีที่มีการสั่งซื้อแย่ที่สุด: O(bm)
• ในกรณีที่ต้องการสั่งซื้อ: O(b(m/2))

ความสมบูรณ์

อัลกอริธึมการค้นหา Quiescence เสร็จสมบูรณ์ มันจะพบวิธีแก้ปัญหาอย่างแน่นอน ถ้ามี ในแผนผังการค้นหาที่มีขอบเขตจำกัด

การเพิ่มประสิทธิภาพ

อัลกอริธึมการค้นหาแบบเงียบจะเหมาะสมที่สุดหากทั้งสองฝ่ายเล่นได้อย่างเหมาะสมที่สุด

---

คีย์ Takeaway

• โหนดที่สำรวจต่อการเคลื่อนไหวจะลดลง 10 เท่าใน Alpha Beta เมื่อเทียบกับ Minmax
• เวลาที่ใช้เพื่อค้นหาการเคลื่อนไหวที่ดีที่สุดจะลดลง 10 เท่าใน Alpha Beta เมื่อเทียบกับ Minmax
• การค้นหาความสงบทำงานได้ดีในระดับความลึกที่สูงขึ้น
• การค้นหาแบบ Quiescence เป็นอัลกอริธึมที่เร็วที่สุดในทั้งสามอัลกอริธึม
• การค้นหาแบบ Quiescence จะประเมินโหนดน้อยลง
• การค้นหาที่สงบนิ่งอาจส่งผลให้เกิดการเคลื่อนไหวซ้ำๆ หากไม่ได้รับการจัดการอย่างเหมาะสม