218 से अधिक चालों वाले कोई भी पहुँचने योग्य chess position मौजूद नहीं हैं

 (lichess.org)
1 पॉइंट द्वारा GN⁺ 2025-09-27 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • 1964 में Nenad Petrović द्वारा प्रकाशित 218 चालों वाले chess position से अधिक चालें देने वाला कोई position मौजूद नहीं है
  • सभी positions को खोजना व्यावहारिक रूप से असंभव है, इसलिए गणितीय optimization और computer-aided modeling तकनीकों से इसकी सीमा साबित की गई
  • गैर-ज़रूरी pieces हटाना, partial piece placement की अनुमति देना, castling को सरल बनाना जैसी तकनीकों से search space को प्रभावी ढंग से घटाया गया
  • अंत में Gurobi optimization tool से पुष्टि की गई कि 218 चालें ही अधिकतम हैं, और 144 चालों (promotion को छोड़कर) जैसे रिकॉर्ड भी अतिरिक्त रूप से सत्यापित किए गए
  • इस शोध से chess engine और compression developers को maximum move limit को लेकर मौजूद अनिश्चितता दूर करने में मदद मिली

परिचय: 218-चाल वाले chess position पर बहस

1964 में chess composition grandmaster Nenad Petrović ने 218 चालों वाला position प्रकाशित किया था, और उसके बाद से इस रिकॉर्ड को तोड़ने की कोशिशें चलती रहीं। लेखक ने एक computer scientist के रूप में कंप्यूटर से सभी positions का विश्लेषण करके इस सवाल का अंतिम जवाब देने का प्रयास किया। लगभग 4.8 × 10^44 पहुँचने योग्य chess positions मौजूद हैं, लेकिन इतनी विशाल खोज व्यावहारिक रूप से असंभव है.

गणितीय optimization का उपयोग

गैर-ज़रूरी pieces और combinations को न्यूनतम करना

  • chessboard पर black pieces के अतिरिक्त होने से चालों की संख्या बढ़ने के मामले सीमित हैं
    • जैसे white pawn उन्हें capture कर सके, या opponent king पर check की स्थिति से बचना हो
  • अधिकांश black pieces को हटाने पर अधिकतम चालों की संख्या पर कोई असर नहीं पड़ता
  • जहाँ pieces की संख्या अनुमति दे, वहाँ black pieces को कमजोर pieces से बदला जा सकता है या कुछ constraints (जैसे pin) के तहत उनकी placement बदली जा सकती है
  • white pieces के मामले में उलटा है; optimal position बनाते समय उन्हें queen जैसे मजबूत pieces से पूरी तरह बदलने पर illegal position बन सकती है, इसलिए सूक्ष्म समायोजन ज़रूरी है

check की स्थिति और चालों की सीमा

  • black king का check में होना legal position नहीं है, इसलिए उसे विचार में लेने की आवश्यकता नहीं
  • white king check में हो तो उसकी चालें बहुत गंभीर रूप से सीमित हो जाती हैं (अधिकतम 120 चालें), इसलिए 218 तक पहुँचना असंभव है
  • इसलिए केवल वे positions खोजी जा सकती हैं जहाँ check न हो

partial piece placement और mathematical modeling

combinational complexity घटाने के लिए partial (fractional) piece placement, movement, और कुछ chess rules को ढीला करने वाले model का उपयोग किया गया

  • उदाहरण के लिए, कोई piece 27.3% संभावना के साथ e4 पर हो सकता है और 72.7% संभावना के साथ किसी दूसरी जगह
  • this तरीके को Gurobi जैसे आधुनिक optimization tools में integer programming (ILP, Integer Linear Programming) के रूप में लागू किया गया
  • शुरुआत में memory और time limits की समस्या आई (लगभग 55,000 सेकंड बाद memory खत्म हो गई)
  • search space को सरल बनाने के लिए castling rules, check, pin, और en passant conditions को सरल करने जैसे अतिरिक्त कदम उठाए गए

optimization और निष्कर्ष

अंत में, गैर-ज़रूरी combination search को रोकने वाले auxiliary constraints जोड़कर model को सुधारा गया, और Gurobi program के माध्यम से optimization पूरा किया गया

  • upper bound को 305 चालों → 271.67 चालों → 218 चालों तक क्रमशः घटाया गया
  • यह पुष्टि हुई कि 218 चालों वाले केवल 12 प्रतिनिधि positions ही वास्तव में पहुँचने योग्य हैं
  • यह भी साबित किया गया कि ये positions proof game के माध्यम से बिना किसी कठिनाई के पहुँचने योग्य legal positions हैं

साथ ही, promotion के बिना अधिकतम 144 चालें, illegal positions में अधिकतम 288 चालें, और पहुँच से बाहर legal positions में 271 चालों के रिकॉर्ड भी सत्यापित किए गए

परिणाम और महत्व

  • इस शोध के कारण chess engine developers और compression algorithm researchers को memory design जैसी स्थितियों में 256 चालों की सीमा पर्याप्त है यह भरोसा मिला
  • यह गणितीय रूप से सिद्ध हो गया कि legal path से 218 से अधिक चालों वाला कोई position मौजूद नहीं है

FAQ सारांश

  • chess game 218 चालों से लंबा हो सकता है, लेकिन यह शोध एक turn में उपलब्ध विकल्पों की अधिकतम संख्या पर केंद्रित है
  • अगर कुछ positions पहुँचने योग्य नहीं लगते, तो लेखक कहते हैं कि कई रास्ते संभव हैं, जैसे पिछली चाल capture पर समाप्त हुई हो
  • इस शोध-पद्धति में विशाल combinational space से 'बिल्कुल असंभव combinations' को जल्दी हटाने के लिए mathematical oracle तकनीक लागू की गई
  • उपयोग किए गए code और निकाले गए प्रमाण की गणितीय वैधता भी सार्वजनिक की गई, जिससे विश्वसनीयता बढ़ी

आगे के कार्य और अतिरिक्त शोध के प्रस्ताव

इस तकनीक का उपयोग करके 'सबसे अधिक captures', 'सबसे अधिक stalemate', 'सबसे अधिक check', 'सबसे अधिक checkmate', 'सबसे अधिक mate in 2' जैसे कई chess problems पर काम किया जा सकता है। हालांकि, कुछ मामलों में अलग तरह के रचनात्मक optimization algorithms की आवश्यकता हो सकती है.

निष्कर्ष

  • 218 चालें किसी chess position में एक turn पर उपलब्ध आधिकारिक अधिकतम चालों की संख्या है
  • व्यावहारिक रूप से chess software और शोधकर्ता 218 (या 256) के अनुसार अपनी structures डिजाइन कर सकते हैं
  • संबंधित code और optimization results GitHub पर सार्वजनिक हैं

संदर्भ

  • Nenad Petrović के 218-चाल वाले position, Jenő Bán के 144-चाल वाले (बिना promotion) position आदि के proof game और position links शामिल हैं
  • विस्तृत विवरण और code Github repository में देखे जा सकते हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-09-27
Hacker News टिप्पणी
  • उन्होंने इसे सीधे तौर पर नहीं कहा, लेकिन यहाँ मतलब यह है कि "इस पोज़िशन में खिलाड़ी के पास चुनने के लिए 218 वैध चालें हैं"
    • हैरानी हुई कि मैं अब तक इस लेख को गलत पढ़ता रहा, धन्यवाद। मैंने इसे ऐसे समझा था कि "किसी भी chess position तक पहुँचने के लिए अधिकतम 218 चालें चाहिए होती हैं"। इसलिए सोच रहा था कि यह लेख मुझे बिल्कुल समझ क्यों नहीं आ रहा था
    • मैं भी यही सोच रहा था: "इस पोज़िशन तक पहुँचने के लिए गेम में कितनी चालें लगी होंगी?"
    • हाँ, यह सचमुच अजीब है कि लेख में "possible moves" वाक्यांश एक बार भी नहीं आया। यहाँ मुख्य शब्द "possible" है। लेख बार-बार "have moves" जैसी अभिव्यक्ति इस्तेमाल करता है, जो आम पाठकों के लिए परिचित नहीं है (हालाँकि chess terminology में शायद अधिक सामान्य हो)
    • धन्यवाद। मैं भी इस लेख को लेकर उलझन में था, मुझे लगा था कि यह उस पोज़िशन के बारे में है जिसे पाने के लिए सबसे ज़्यादा चालें लगती हैं
  • मैं Lichess की ज़रूर तारीफ़ करना चाहूँगा। यह शानदार service और content मुफ्त में देता है, और Chess.com पर जो features paid हैं वे भी यहाँ free हैं। साथ ही इसमें variant games भी बहुत ज़्यादा हैं
    Lichess पर 960 या Crazyhouse जैसे variant chess का स्तर Chess.com से कहीं ऊँचा है
    • यह मुफ्त है, commercial servers जैसी ही functionality देता है, open source है और developer-friendly भी। इसमें ads नहीं हैं (free accounts पर भी बिल्कुल नहीं), और यह French law के तहत एक transparent organizational structure रखता है
      सचमुच हास्यास्पद रूप से शानदार है। अगर संभव हो तो donation की सलाह दूँगा
  • https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow वाली पोस्ट में लेखक बताते हैं कि उन्होंने शुरुआत में कुछ जटिल नियम हटा दिए थे, और ज़रूरत पड़ने पर (अगर समाधान उन नियमों का उल्लंघन करता) उन्हें फिर से जोड़ने के लिए तैयार थे
    दिलचस्प बात यह है कि mixed-integer linear programming (MILP) solvers पहले से ही इस तरह की प्रक्रिया को support करते हैं। तकनीकी भाषा में इसे 'row generation' कहा जाता है, आम तौर पर तब जब समस्या को matrix form में लिखा जाता है जहाँ rows constraints होती हैं और columns variables
    (डायनामिक रूप से) नई rows जोड़ना वही बात है जो केवल उल्लंघन होने पर constraints लागू करना
    यह तरीका अक्सर Traveling Salesman Problem हल करने में उपयोग होता है
    (वैसे Wikipedia पर Column generation है, लेकिन row generation नहीं है)
    • नमस्ते, मैं Lichess लेख का लेखक हूँ
      Chess rules को relax या omit करने का असर variable selection पर भी पड़ा। mathematical modeling में जाने से पहले मैंने lazy constraints जैसी चीज़ें आज़माई थीं, लेकिन उनसे meaningful speedup नहीं मिला। उदाहरण के लिए, सिर्फ यह ignore करना कि white king check में है या नहीं, इससे भी काफी simplification हुई
    • इस approach को आम तौर पर lazy constraints ही कहा जाता है (संबंधित विवरण)
    • सच में जिज्ञासा है कि क्या कोई MILP solver (इतने विशाल search space में) terminate कर सकता है; मेरा अंदाज़ा है कि नहीं
  • ईमानदारी से पूछ रहा हूँ: अगर Gurobi के integer programming solver को 218 से बेहतर solution नहीं मिला, तो क्या यह गारंटी है कि 218 से बेहतर solution मौजूद नहीं है? और क्या यह गणितीय प्रमाण के बराबर है?
    (मान लेते हैं कि Gurobi में bug नहीं है, और लेखक की problem definition तथा implementation में भी bug नहीं है)
    मैं जानना चाहता हूँ कि क्या Gurobi किसी local maximum में फँस सकता है, या उसने सच में globally optimal solution साबित किया है
    • Gurobi अब तक मिले सबसे अच्छे integer solution के साथ-साथ optimal solution की एक bound भी देता है। इस bound के लिए problem relaxation, cutting planes जैसी कई तकनीकें इस्तेमाल होती हैं। इसलिए अगर solver में bug नहीं है, तो solution वास्तव में optimal है
    • लेखक यहाँ!
      अगर Gurobi और मेरा code जैसा intended है वैसा ही काम कर रहे हैं, और chess model को simplify करने की प्रक्रिया में कोई logical error नहीं है, तो मेरा परिणाम यह साबित करता है कि "initial position से legal move sequence द्वारा पहुँची जा सकने वाली chess positions में possible legal moves का maximum ऊपर और नीचे, दोनों ओर से 218 है"। यानी Gurobi ने पूरे search space को bound करके दिखा दिया कि इससे बेहतर कुछ नहीं है
    • मुझे नहीं पता कि यहाँ Gurobi specifically कैसे apply किया गया, लेकिन सामान्य तौर पर ऐसे combinatorial optimization solvers एक proof tree बनाते हैं जो दिखाता है कि variable assignment के किसी भी case में बेहतर solution नहीं मिल सकता। छोटे मामलों में उस tree को manually जाँचकर contradiction तक पहुँचना संभव होता है। इस लेख वाले मामले में proof tree बेहद विशाल होगा। चाहें तो सिद्धांततः उसका audit किया जा सकता है
    • सिद्धांत में यह proof नहीं है, लेकिन व्यवहार में यह proof जैसा ही है

  • किसी reachable chess position में 218 से ज़्यादा moves नहीं होते
    इसे "आगे चलकर की जा सकने वाली legal moves की संख्या 218 से अधिक नहीं है" कहना कहीं ज़्यादा स्पष्ट होता

क्या आपने लगभग 8.7x10^45 reachable chess positions सभी जाँच लीं?
यह संख्या वास्तव में overestimate है
https://github.com/tromp/ChessPositionRanking में legal chess positions की संख्या लगभग 4.8x10^44 अधिक सटीक रूप से आँकी गई है

  • वह estimate बस लगभग 20 गुना का अंतर नहीं है? इस scale पर यह कोई बहुत बड़ा फर्क नहीं लगता
  • एक "legal" है, और दूसरा "entire problem space"
    Computing के नज़रिए से entire problem space ज़्यादा महत्वपूर्ण है। क्योंकि legal है या नहीं यह तय करने से पहले भी सबको "compute" करना पड़ता है। सिर्फ legal positions को iterate करने का कोई आसान तरीका नहीं है
  • सबको नमस्ते
    एक परिचित की सूचना से पता चला कि यहाँ मेरे लेख पर चर्चा हो रही है
    कम स्पष्ट title चुनने के लिए माफ़ी चाहता हूँ, उम्मीद है अब बात स्पष्ट हो गई होगी। feedback और गर्मजोशी भरी बातों के लिए धन्यवाद
    अगर ऐसे ही chess facts के proofs को लेकर कोई सवाल हो, तो मैं जवाब देने की कोशिश कर सकता हूँ ^^
    धन्यवाद
    Tobi
    • तो पुष्टि के लिए: आपका मतलब यह है कि किसी भी board position में available moves की संख्या 218 से ज़्यादा नहीं हो सकती? क्या यही सही समझ है?
  • reachable chess board को represent करने के लिए कम से कम कितने bits चाहिए होंगे?
    अपडेट: लेख में लगभग 8.7x10^45 reachable chess positions का ज़िक्र है, और https://github.com/lechmazur/ChessCounter इस संख्या को upper bound के रूप में रखता है
    (यह लगभग 153 bits के बराबर है)
    • अगर लगभग 4.8x10^44 मानें, तो log2(4.8x10^44) के हिसाब से यह 149 bits बनता है
      लेकिन efficiently decode करने के लिए ChessPositionRanking project द्वारा सुझाई गई संख्या (8726713169886222032347729969256422370854716254) के log2 के ceiling के अनुसार 153 bits चाहिए। ChessCounter efficient decoding code नहीं देता
    • king 64 में से किसी भी tile पर हो सकता है
      rook/queen/knight भी, लेकिन chess में वे capture हो चुके हो सकते हैं, इसलिए इन 5 pieces में से हर एक के लिए कुल 65 states चाहिए
      bishop सिर्फ आधे tiles पर जा सकता है, इसलिए प्रत्येक के लिए 33 states
      pawn के लिए 4 promotion possibilities, captured होना, और स्थिति के अनुसार लगभग 20~30 positions, कुल मिलाकर प्रति pawn लगभग 290 states
      इस तरह एक color के pieces के लिए board state को represent करने में लगभग 112 bits लगते हैं, rounding के बाद दोनों पक्षों के लिए 224 bits
      En Passant और castling restrictions (जैसे castling unavailable होना) के लिए rounding के कारण अलग से अतिरिक्त bits की ज़रूरत नहीं पड़ती; वे बस हर piece की कुछ अतिरिक्त states बन जाती हैं
      शायद fixed-length board representation के लिए यह सबसे compressed form है
      Sparse representation में, चूँकि दोनों kings हमेशा मौजूद होते हैं, जीवित pieces को n-digit decimal संख्या से और उनकी positions को n+2 64-bit numbers से दिखाया जा सकता है; castling, en passant आदि के लिए थोड़ा extra metadata चाहिए। अगर औसतन आधे pieces हट चुके हों, तो board state representation लगभग 180 bits में आ जाती है
      Move history के लिए भी हर move पर लगभग 10 bits चाहिए (black/white की एक जोड़ी चालों पर, एक ply के लिए 5 bits), तो लगभग 18 moves तक जाया जा सकता है। यह औसत chess game length के मध्य बिंदु से कुछ कम है
      इससे ज़्यादा compression के लिए शायद बहुत विशाल dictionary लागू करनी पड़ेगी
    • piece type और color को 4 bits में represent किया जा सकता है
      तो पूरे board की fixed-length encoding होगी 644=256 bits=32 bytes
      या, सिर्फ pieces के लिए variable-length representation में, हर occupied square का index 6 bits में, यानी pieces की संख्या      10 bits
      उदाहरण के लिए initial position होगी 32*10=320 bits=40 bytes
    • उस GitHub का 8.7e45 "restricted" मान कुछ pawn promotion patterns को सीमित करता है
      5.68e50 "general" असली upper bound है, और वह सभी possible promotions की अनुमति देता है
  • b2 पर मौजूद black pawn बाकी pieces की possible moves को काफ़ी कम कर रहा है
    उस pawn के पास सिर्फ एक ही move है (बगल के knight को capture करना)। अगर वह pawn न हो, तो चार white queens और knight b2 में जा सकते हैं। लेकिन वास्तव में black king पहले से checkmate में है, इसलिए वे moves असल में संभव नहीं हो सकते
    लुभावना लगता है कि e5 वाली queen को कहीं और रखकर immediate checkmate टाला जाए और b2 square को और खोला जाए
    पुनश्च: लगता है वह pawn stalemate रोकने के लिए वहाँ जीवित रहना चाहिए
    • b2 वाला black pawn White to move position में चल नहीं सकता
      अगर Black to move हो, तो भी e5 की white queen के कारण king pinned है, इसलिए वह फिर भी नहीं चल सकता। अगर pin न हो, तो वह 4 बार चल सकता है। underpromotion भी संभव है
    • मैं भी "black pieces बेकार हैं" वाली बात से भ्रमित था। लगा कि दो queens को आमने-सामने रखने के बजाय उनमें से एक को black कर दें ताकि वे एक-दूसरे को capture करने वाली moves दें... लेकिन फिर समझ आया कि अंत में "सिर्फ एक ही पक्ष चल सकता है"
    • लेखक यहाँ
      Position White to move है। भले ही b2 का pawn white queen की वजह से king को pin न कर रहा हो, black pawn चल नहीं सकता
      b2 का pawn black king को check से बचाने के लिए अनिवार्य है। उसके बिना यह position खुद legal नहीं रहेगी
      मैंने सब कुछ बहुत ध्यान से जाँचा है, इसलिए निश्चिंत रहें, white के लिए 218 से ज़्यादा moves बनाने की कोशिश संभव नहीं थी। फिर भी बहुत लोगों ने मेरे लेख में रुचि दिखाई, इससे मैं आश्चर्यचकित और आभारी हूँ, haha ^^
    • White की चाल है। अगर Black check में हो और फिर भी White की चाल हो, तो वह legal और reachable position नहीं हो सकती। पिछली Black turn में इसे legal तरीके से बनाना संभव नहीं होता
      ऐसा लग सकता है कि black pawns में से किसी एक को white knight से बदलकर moves बढ़ाई जा सकती हैं, लेकिन दोनों knights पहले से मौजूद हैं, और सारे pawns promoted हैं, इसलिए यह संभव नहीं। (अगर दोनों pawns बदल दिए जाएँ, तो Black का पिछली चाल में इस स्थिति तक पहुँचना असंभव हो जाता)
  • मैं confused हूँ। 271 वाली model के बाद, जानना चाहता हूँ कि किस बदलाव ने optimal solution दिलाया। वहाँ सिर्फ इतना लिखा है, "इस improved model से..."
    • लेखक यहाँ!
      क्या आपने पूरा लेख पढ़ा?
      271 नहीं, 271.666... :) यह मान उस model से आता है जहाँ सभी decisions (0 या 1) को continuous values (0.0~1.0 और बीच के मान) में relax किया गया है। यानी आप मान सकते हैं कि कोई piece 0.23 जितना मौजूद है। किसी खास move को चल पाने की "संभावना" भी 0.843 जैसी हो सकती है।
      इस तरह के 'black magic' से computation बहुत तेज़ हो जाती है, और यह असली दुनिया से ज़्यादा moves दे सकता है।
      इसलिए इस पद्धति से तेज़ी से उन subspaces को हटाया जा सकता है जो संभावित रूप से खराब partial solutions देते हैं। ऐसी techniques के बिना पूरे search space को exhaustively जाँचना असंभव है
  • क्या मैं कुछ मिस कर रहा हूँ, या शुरुआत में दिखाई गई position खुद ही असल में unreachable नहीं है? White to move है, black pawns अपनी शुरुआती जगहों पर हैं, king के पास कोई खाली adjacent square नहीं है, और वह pieces और pawns में घिरा हुआ है, इसलिए यह position पहुँची जा सकने वाली नहीं लगती
    • उस position के वास्तव में reachable होने का प्रमाण यहाँ है: https://lichess.org/study/PLtuv3v5/zWPNxbSA
      वैसे, लगता है आपने black pawns को उनकी शुरुआती positions पर समझ लिया। असल में black pawn board के दूसरी तरफ तक पहुँच चुका है (white side में)
    • black pawn white side (1st~2nd rank) में है