- ไม่มีตำแหน่งใดที่สามารถเดินได้มากกว่าตำแหน่งหมากรุก 218 ตา ที่ Nenad Petrović เผยแพร่ไว้ในปี 1964
- เนื่องจากการสำรวจทุกตำแหน่งเป็นไปไม่ได้ในทางปฏิบัติ จึงใช้การเพิ่มประสิทธิภาพทางคณิตศาสตร์และเทคนิค การสร้างแบบจำลองด้วยคอมพิวเตอร์ เพื่อพิสูจน์ขีดจำกัดนี้
- ลดพื้นที่ค้นหาได้อย่างมีประสิทธิภาพด้วยการตัดหมากที่ไม่จำเป็น อนุญาตให้มี การจัดวางหมากบางส่วน และทำกติกาการเข้าป้อมให้ง่ายขึ้น เป็นต้น
- สุดท้ายยืนยันด้วย เครื่องมือเพิ่มประสิทธิภาพ Gurobi ว่า 218 ตาเป็นค่าสูงสุด และตรวจสอบสถิติอื่นเพิ่มเติม เช่น 144 ตา (ไม่รวมการโปรโมต)
- งานวิจัยนี้ช่วยให้นักพัฒนาเอนจินหมากรุกและผู้พัฒนาระบบบีบอัดข้อมูลหมดความไม่แน่นอนเกี่ยวกับ ขีดจำกัดจำนวนตาสูงสุด
บทนำ: ข้อถกเถียงเรื่องตำแหน่งหมากรุก 218 ตา
หลังจากที่ปรมาจารย์การจัดองค์ประกอบหมากรุก Nenad Petrović เผยแพร่ตำแหน่ง 218 ตาในปี 1964 ก็มีความพยายามต่อเนื่องที่จะทำลายสถิตินี้ ผู้เขียนในฐานะ นักวิทยาการคอมพิวเตอร์ ต้องการปิดฉากคำถามนี้ด้วยการวิเคราะห์ทุกตำแหน่งผ่านคอมพิวเตอร์ แม้จะมีตำแหน่งหมากรุกที่เข้าถึงได้มากถึงประมาณ 4.8 × 10^44 ตำแหน่ง แต่การค้นหาในขนาดมหาศาลเช่นนั้นเป็นไปไม่ได้ในทางปฏิบัติ
การนำการเพิ่มประสิทธิภาพทางคณิตศาสตร์มาใช้
ลดหมากและชุดผสมที่ไม่จำเป็นให้เหลือน้อยที่สุด
- กรณีที่ หมากดำ เพิ่มจำนวนทางเลือกในการเดินมีอยู่จำกัด
- เช่น ทำให้เบี้ยขาวสามารถกินได้ หรือช่วยหลีกเลี่ยงสถานการณ์เช็กคิงฝ่ายตรงข้าม
- หมากดำส่วนใหญ่ตัดออกได้โดยไม่กระทบจำนวนทางเดินสูงสุด
- ตราบใดที่จำนวนหมากยังอยู่ในข้อกำหนด ก็สามารถ แทนหมากดำด้วยหมากที่อ่อนกว่า หรือปรับการวางภายใต้ข้อจำกัดบางอย่าง (เช่น pin) ได้
- ในทางกลับกัน สำหรับหมากขาว หากแทนทั้งหมดด้วยหมากที่แข็งแกร่งกว่าอย่างควีนเพื่อสร้างตำแหน่งที่ดีที่สุด อาจทำให้เกิดตำแหน่งที่ไม่ถูกกติกา จึงต้องปรับอย่างละเอียด
สถานการณ์เช็กและข้อจำกัดของจำนวนตาเดิน
- สถานะที่คิงดำถูกเช็กไม่ใช่ตำแหน่งที่ถูกกติกา จึงไม่จำเป็นต้องพิจารณา
- เมื่อคิงขาวถูกเช็ก การเคลื่อนไหวจะถูกจำกัดอย่างมาก (สูงสุด 120 ตา) จึงไม่มีทางถึง 218 ตาได้
- ดังนั้นจึงค้นหาเฉพาะตำแหน่งที่ไม่มีการเช็กได้
การจัดวางหมากบางส่วนและการสร้างแบบจำลองทางคณิตศาสตร์
เพื่อลดความซับซ้อนเชิงจัดหมู่ จึงใช้แบบจำลองที่ผ่อนปรนด้วย การจัดวางหมากแบบบางส่วน (fractional) การเดิน และกติกาหมากรุกบางข้อ
- ตัวอย่างเช่น หมากหนึ่งตัวอาจอยู่ที่ e4 ด้วยความน่าจะเป็น 27.3% และอยู่ตำแหน่งอื่น 72.7%
- วิธีนี้ทำให้สามารถนำไปใช้ในเครื่องมือเพิ่มประสิทธิภาพสมัยใหม่อย่าง Gurobi ในรูปแบบ การโปรแกรมจำนวนเต็มเชิงเส้น (ILP, Integer Linear Programming)
- ช่วงแรกติดข้อจำกัดด้านหน่วยความจำและเวลา (หน่วยความจำไม่พอหลังผ่านไปประมาณ 55,000 วินาที)
- เพื่อทำให้พื้นที่ค้นหาง่ายขึ้น จึงใช้มาตรการเพิ่มเติม เช่น ทำกติกาการเข้าป้อมให้ง่ายขึ้น ละเลยการเช็ก ละเลย pin และทำเงื่อนไข en passant ให้ง่ายลง
การเพิ่มประสิทธิภาพและบทสรุป
ท้ายที่สุด หลังจากปรับปรุงแบบจำลองด้วยการเพิ่ม เงื่อนไขข้อจำกัดเสริม เพื่อกันไม่ให้สำรวจชุดผสมที่ไม่จำเป็น ก็สามารถทำการเพิ่มประสิทธิภาพจนเสร็จสมบูรณ์ผ่านโปรแกรม Gurobi
- ทำให้เพดานบนแคบลงจาก 305 ตา → 271.67 ตา → 218 ตา
- ยืนยันว่ามีเพียง 12 ตำแหน่งตัวแทนของกรณี 218 ตาเท่านั้นที่สามารถเข้าถึงได้
- พิสูจน์ว่าตำแหน่งเหล่านี้เป็นตำแหน่งถูกกติกาที่เข้าถึงได้จริงโดยไม่ยากผ่าน proof game
นอกจากนี้ ยังยืนยันได้ด้วยว่าหาก ไม่มีการโปรโมตจะมีได้สูงสุด 144 ตา, ตำแหน่งที่ไม่ถูกกติกามีได้สูงสุด 288 ตา และตำแหน่งถูกกติกาที่เข้าถึงไม่ได้มีสถิติ 271 ตา
ผลลัพธ์และความสำคัญ
- จากผลการวิจัยนี้ นักพัฒนาเอนจินหมากรุกและนักวิจัยอัลกอริทึมการบีบอัดข้อมูลจึงมั่นใจได้ว่า การจำกัดไว้ที่ 256 ตาก็เพียงพอ สำหรับเรื่องอย่างการออกแบบหน่วยความจำ
- ได้รับการพิสูจน์ทางคณิตศาสตร์แล้วว่าไม่มีตำแหน่งใดที่สามารถเข้าถึงได้ตามเส้นทางที่ถูกกติกาและมีทางเดินเกิน 218 ตา
สรุป FAQ
- เกมหมากรุกอาจยาวกว่า 218 ตาได้ แต่การวิจัยนี้ว่าด้วยจำนวนตัวเลือกสูงสุดที่เป็นไปได้ใน 'หนึ่งตาเดิน'
- หากบางตำแหน่งดูเหมือนจะเข้าถึงไม่ได้ ก็มีการกล่าวถึงว่ามีหลายเส้นทาง เช่น กรณีที่ตาก่อนหน้าจบลงด้วยการกิน
- วิธีวิจัยนี้ใช้เทคนิค ออราเคิลทางคณิตศาสตร์ เพื่อคัดกรอง 'ชุดผสมที่เป็นไปไม่ได้โดยสิ้นเชิง' อย่างรวดเร็วในพื้นที่เชิงจัดหมู่ขนาดมหาศาล
- มีการเปิดเผยทั้งโค้ดที่ใช้และความถูกต้องทางคณิตศาสตร์ของหลักฐานที่ได้มา เพื่อสร้างความน่าเชื่อถือ
งานต่อไปและข้อเสนอวิจัยเพิ่มเติม
สามารถประยุกต์เทคนิคนี้เพื่อท้าทายปัญหาหมากรุกอีกหลายแบบ เช่น 'จำนวนการกินสูงสุด', 'สเตลเมตสูงสุด', 'จำนวนเช็กสูงสุด', 'จำนวนเช็กเมตสูงสุด', 'จำนวนเมตใน 2 สูงสุด' เป็นต้น แต่บางกรณีอาจต้องใช้อัลกอริทึมเพิ่มประสิทธิภาพเชิงสร้างสรรค์แบบเฉพาะทางเพิ่มเติม
บทสรุป
- 218 ตา คือ จำนวนตาที่เป็นทางการสูงสุด ที่สามารถเล่นได้ในหนึ่งตาจากตำแหน่งหมากรุก
- ในเชิงปฏิบัติ ซอฟต์แวร์หมากรุกและนักวิจัยสามารถออกแบบโครงสร้างโดยอิงกับ 218 (หรือ 256) ได้
- โค้ดที่เกี่ยวข้องและผลการเพิ่มประสิทธิภาพถูกเผยแพร่บน GitHub
อ้างอิง
- มีลิงก์ไปยัง proof game และตำแหน่งต่าง ๆ เช่น ตำแหน่ง 218 ตาของ Nenad Petrović และ 144 ตาของ Jenő Bán (ไม่มีการโปรโมต)
- ดูคำอธิบายและโค้ดเพิ่มเติมได้ที่ Github repository
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
ระดับการเล่นของหมากรุกแบบ 960 หรือ Crazyhouse บน Lichess สูงกว่า Chess.com มาก
พูดตรง ๆ คือดีเกินจริงมาก ถ้าไหวก็แนะนำให้สนับสนุน
สิ่งที่น่าสนใจคือ ตัวแก้ปัญหา mixed integer linear programming (MILP) รองรับการทำแบบนี้อยู่แล้ว ในทางเทคนิคเรียกว่า 'row generation' ซึ่งมักใช้เมื่อเขียนปัญหาในรูปเมทริกซ์ที่แถวคือข้อจำกัดและคอลัมน์คือตัวแปร
การเพิ่มแถวใหม่แบบ (ไดนามิก) ก็เท่ากับการใส่ข้อจำกัดเฉพาะเมื่อมีการละเมิดเกิดขึ้น
แนวทางนี้มักใช้แก้ปัญหา Traveling Salesman Problem
(ว่าแต่ ใน Wikipedia มี Column generation แต่ไม่มี row generation)
การผ่อนปรนหรือละกฎหมากรุกบางอย่างยังส่งผลต่อการเลือกตัวแปรด้วย ก่อนจะไปถึงขั้นการสร้างแบบจำลองทางคณิตศาสตร์ ผมก็ลองอะไรทำนอง lazy constraints แล้ว แต่ไม่ได้ช่วยให้เร็วขึ้นอย่างมีนัยสำคัญ ตัวอย่างเช่น แค่ไม่ต้องพิจารณาว่าคิงขาวกำลังถูกเช็กหรือไม่ ก็ทำให้เกิดการลดรูปได้เยอะมากแล้ว
(ตั้งต้นด้วยสมมติฐานว่า Gurobi ไม่มีบั๊ก และนิยามปัญหากับการเขียนโปรแกรมของผู้เขียนก็ไม่มีบั๊กเช่นกัน)
ผมสงสัยว่ามีโอกาสไหมที่ Gurobi จะติดอยู่ที่ค่าสูงสุดเฉพาะที่ หรือว่ามันพิสูจน์ได้จริง ๆ ว่านี่คือคำตอบเหมาะที่สุดโดยรวม
ถ้า Gurobi และโค้ดของผมทำงานตรงตามที่ตั้งใจไว้ และไม่มีข้อผิดพลาดทางตรรกะในขั้นตอนลดทอนโมเดลหมากรุก ผลที่ผมได้ก็คือการพิสูจน์ว่า "ในบรรดาตำแหน่งหมากรุกที่ไปถึงได้จากตำแหน่งเริ่มต้นด้วยลำดับการเดินที่ถูกกติกา ค่าสูงสุดของจำนวนทางเดินที่ถูกกติกาซึ่งเป็นไปได้ มีทั้งขอบบนและขอบล่างเท่ากับ 218" กล่าวคือ Gurobi พิสูจน์ด้วยขอบเขตครอบคลุมพื้นที่ค้นหาทั้งหมดแล้วว่า "ไม่มีกรณีที่ดีกว่านี้"
ในมุมมองการคำนวณ พื้นที่ปัญหาทั้งหมดสำคัญกว่า เพราะต้อง "คำนวณ" ทั้งหมดก่อนจะรู้ด้วยซ้ำว่าตำแหน่งไหนถูกกติกา ไม่มีวิธีง่าย ๆ ที่จะไล่ดูเฉพาะตำแหน่งที่ถูกกติกาเท่านั้น
มีคนรู้จักบอกผมว่าบทความของผมกำลังถูกคุยกันอยู่ที่นี่
ต้องขอโทษที่เลือกหัวข้อได้ไม่ชัดเจนนัก หวังว่าตอนนี้จะชัดขึ้นแล้ว ขอบคุณสำหรับคำติชมและคำพูดดี ๆ
ถ้ามีคำถามเกี่ยวกับการพิสูจน์ข้อเท็จจริงหมากรุกแบบคล้าย ๆ กัน ผมก็ยินดีตอบนะ ^^
ขอบคุณครับ
Tobi
อัปเดต: ในบทความบอกว่ามีตำแหน่งหมากรุกที่ไปถึงได้ประมาณ 8.7x10^45 ตำแหน่ง และ https://github.com/lechmazur/ChessCounter ใช้ตัวเลขนี้เป็นขอบบน
(ซึ่งเทียบได้กับประมาณ 153 บิต)
แต่ถ้าต้องการถอดรหัสได้อย่างมีประสิทธิภาพ จะต้องใช้ 153 บิตตามค่าเพดานของ log2 ของตัวเลขที่โปรเจกต์ ChessPositionRanking แนะนำ (8726713169886222032347729969256422370854716254) ส่วน ChessCounter ไม่ได้ให้โค้ดสำหรับการถอดรหัสอย่างมีประสิทธิภาพ
รู๊ก/ควีน/ไนต์ก็เช่นกัน แต่ในหมากรุกมันอาจถูกกินไปแล้ว จึงต้องมีทั้งหมด 65 สถานะสำหรับหมากแต่ละตัวในกลุ่ม 5 ตัวนั้น
บิชอปไปได้แค่ครึ่งหนึ่งของช่องเหล่านั้น จึงมี 33 สถานะต่อชิ้น
เบี้ยมี 4 ทางเลือกในการโปรโมต อาจถูกกินได้ และสถานะเบี้ยบนกระดานมีประมาณ 20-30 ตำแหน่งแล้วแต่กรณี รวม ๆ แล้วตกประมาณ 290 สถานะต่อเบี้ยหนึ่งตัว
คิดแบบนี้จะได้ว่าต้องใช้ประมาณ 112 บิตในการแทนสถานะกระดานสำหรับหมากสีหนึ่ง และปัดรวมทั้งสองฝั่งเป็น 224 บิต
En Passant และข้อจำกัดเรื่อง castling (เช่น หมดสิทธิ์ castling) ไม่ทำให้ต้องใช้บิตเพิ่มถ้าปัดเศษ เพราะมันแค่เพิ่มสถานะอีกเล็กน้อยให้หมากแต่ละตัว
นี่น่าจะเป็นรูปแบบการแทนกระดานแบบความยาวคงที่ที่บีบอัดได้มากที่สุดแล้ว
ถ้าเป็นการแทนแบบ sparse เนื่องจากคิงสองตัวต้องมีอยู่เสมอ เราอาจแทนหมากที่ยังอยู่ด้วยเลขฐานสิบ n หลักและตัวเลข 64 บิตจำนวน n+2 ตัวสำหรับตำแหน่ง พร้อมข้อมูลเพิ่มเล็กน้อยสำหรับ castling, en passant ฯลฯ โดยเฉลี่ยถ้าหมากหายไปประมาณครึ่งหนึ่ง จะใช้ราว 180 บิตในการแทนสถานะกระดาน
ประวัติการเดินก็ต้องใช้ประมาณ 10 บิตต่อหนึ่งตาเดิน (ขาว/ดำหนึ่งคู่, หนึ่ง ply คือ 5 บิต) ดังนั้นเก็บได้ราว 18 ตาเดิน ซึ่งสั้นกว่าจุดกึ่งกลางของความยาวเกมหมากรุกเฉลี่ยเล็กน้อย
ถ้าจะบีบอัดมากกว่านี้ คงต้องทำพจนานุกรมขนาดมหึมา
ดังนั้นถ้าเข้ารหัสทั้งกระดานแบบความยาวคงที่ ก็เป็น 644=256 บิต = 32 ไบต์
หรือถ้าใช้รูปแบบความยาวแปรผันเฉพาะสำหรับหมากที่มีอยู่ ก็ใช้อินเด็กซ์ 6 บิตของแต่ละช่องใน 64 ช่อง ดังนั้นจะใช้ จำนวนหมาก10 บิต
ตัวอย่างเช่น ตำแหน่งเริ่มต้นคือ 32*10=320 บิต = 40 ไบต์
ส่วน 5.68e50 แบบ "general" คือขอบบนที่แท้จริงและยอมให้มีการโปรโมตได้ทุกรูปแบบ
เบี้ยตัวนั้นทำอะไรได้แค่ครั้งเดียว (กินไนต์ข้าง ๆ) ถ้าไม่มีมัน ควีนขาวทั้งสี่ตัวและไนต์จะสามารถเข้ามาที่ b2 ได้ แต่ในความเป็นจริงการเดินเหล่านั้นเกิดขึ้นไม่ได้ เพราะคิงดำอยู่ในสถานะ checkmate อยู่แล้ว
มันชวนให้คิดว่าถ้าเอาควีนที่ e5 ไปไว้ที่อื่นเพื่อไม่ให้เป็น checkmate ทันที และเปิดช่อง b2 มากขึ้นก็น่าจะดี
ป.ล. ดูเหมือนว่าเบี้ยตัวนั้นต้องรอดอยู่ตรงนั้นเพื่อกันไม่ให้เป็น stalemate
ถ้าเป็นตาดำเดิน มันก็ยังขยับไม่ได้อยู่ดี เพราะคิงถูกตรึงไว้โดยควีนขาวที่ e5 ถ้าไม่มีการ pin นี้ มันจะเดินได้ 4 แบบ และ underpromotion ก็เป็นไปได้ด้วย
ตำแหน่งนี้เป็น White to move ต่อให้เบี้ย b2 ไม่ได้ตรึงคิงดำไว้ผ่านควีนขาว เบี้ยดำก็ยังเดินไม่ได้อยู่ดี
เบี้ยที่ b2 จำเป็นต้องอยู่เพื่อป้องกันคิงดำจากการถูกเช็ก ไม่เช่นนั้นตำแหน่งนี้จะไม่ถูกกติกาตั้งแต่แรก
ผมตรวจทุกอย่างละเอียดมากแล้ว มั่นใจได้เลยว่าความพยายามจะทำให้เกิน 218 ทางเดินสำหรับฝั่งขาวนั้นไม่สำเร็จจริง ๆ แต่ก็ทั้งประหลาดใจและขอบคุณมากที่หลายคนสนใจบทความของผมนะ ฮ่า ๆ ^^
ดูเหมือนอาจเพิ่มจำนวนทางเดินได้ด้วยการเปลี่ยนเบี้ยดำตัวหนึ่งเป็นไนต์ขาว แต่ไนต์ทั้งสองตัวมีอยู่แล้ว และเบี้ยทุกตัวก็ถูกโปรโมตไปหมดแล้วจึงทำไม่ได้ (และถ้าเปลี่ยนเบี้ยทั้งสองตัว ตาดำก่อนหน้าก็จะไม่สามารถไปถึงสถานะนี้ได้อยู่ดี)
ได้อ่านทั้งบทความหรือยัง?
ไม่ใช่ 271 แต่เป็น 271.666... :) ค่านี้มาจากโมเดลที่ผ่อนปรนการตัดสินใจทั้งหมด (0 หรือ 1) ให้กลายเป็นค่าต่อเนื่องได้ (0.0 ถึง 1.0 และค่าระหว่างนั้น) หมายความว่าเราสามารถสมมติได้ว่าหมากชิ้นหนึ่งมีอยู่ 0.23 ชิ้น หรือโอกาสที่จะเดินบางตาได้เป็น 0.843 เป็นต้น
การใช้ 'มนตร์ดำ' แบบนี้ทำให้คำนวณได้เร็วขึ้นมาก และอาจได้จำนวนทางเดินที่มากกว่าที่มีอยู่จริง
ดังนั้นวิธีนี้จึงเอาไว้ใช้ตัดพื้นที่ย่อยที่แย่ ๆ ซึ่งเป็นไปได้ออกอย่างรวดเร็วได้ ถ้าไม่มีเทคนิคแบบนี้ การไล่ตรวจพื้นที่ค้นหาทั้งหมดเป็นไปไม่ได้เลย
อีกอย่าง ดูเหมือนคุณจะเข้าใจผิดว่าเบี้ยดำอยู่ตำแหน่งเริ่มต้น จริง ๆ แล้วเบี้ยดำได้เดินข้ามไปอีกฝั่งของกระดานแล้ว (ฝั่งของขาว)