क्या 'Othello' हल हो गया है?

 (arxiv.org)
3 पॉइंट द्वारा GN⁺ 2023-11-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • 8×8 Othello/Reversi के बारे में computationally साबित किया गया है कि जब दोनों पक्ष perfect play करते हैं, तो अंतिम परिणाम ड्रॉ होता है; शोधकर्ताओं के मानक के हिसाब से यह weakly solved स्थिति तक पहुंच गया है
  • संभावित game records करीब 10^58 और board positions करीब 10^28 आंके जाते हैं, इसलिए search space बहुत बड़ा है और यह पहले हल किए गए checkers की तुलना में कहीं ज्यादा कठिन समस्या बनी हुई थी
  • यह परिणाम initial position की game-theoretic value और उस value को हासिल करने वाली strategy निकालने का है; यह सभी intermediate positions की गणना करने वाला strongly solved परिणाम नहीं है
  • शोधकर्ताओं ने Othello software-based heuristic search और alpha-beta search का उपयोग किया, और बताया कि precise solution के लिए जरूरी search scale पहले के अनुमानों से छोटा था
  • परिणाम को reproduce करने के लिए raw data और programs GitHub, Zenodo, figshare पर सार्वजनिक किए गए हैं, जिससे इसे pure strategy games को solve करने के शोध में verifiable case के रूप में इस्तेमाल किया जा सकता है

Othello का computational solution

  • 8×8 board वाला Othello weakly solved हो गया है, और initial position की game-theoretic value ड्रॉ के रूप में calculate की गई है
  • अगर दोनों पक्ष बिना गलती के optimal play करें, तो खेल ड्रॉ होता है; इस शोध ने इसे computationally साबित किया है
  • Figure 1 में एक optimal game record और अंतिम परिणाम दिखाया गया है
    • उस move sequence में किसी भी समय deviation होने पर, शोधकर्ताओं का software विरोधी पक्ष के रूप में ड्रॉ या जीत सुनिश्चित करता है
  • यह परिणाम मानव Othello experts द्वारा लंबे समय से अनुमानित ड्रॉ से मेल खाता है, इसलिए शोधकर्ताओं के अनुसार परिणाम खुद बहुत आश्चर्यजनक नहीं है

solution का scope और game-theoretic value

  • किसी perfect-information game को solve करने का मतलब है कि जब दोनों पक्ष perfect play करें तो अंतिम परिणाम, यानी game-theoretic value, निर्धारित करना
  • solved games को आम तौर पर तीन स्तरों में बांटा जाता है
    • ultra-weakly solved: जब सिर्फ initial board position की game-theoretic value पता हो
    • weakly solved: जब initial position की game-theoretic value और reasonable computational resources के भीतर दोनों पक्षों के लिए उस value को हासिल करने की strategy पता हो
    • strongly solved: जब खेल के दौरान आ सकने वाली हर possible position का result calculate किया गया हो
  • यह शोध Othello को weakly solved करने का उदाहरण है; यह सभी possible positions की गणना करने वाला strong solution नहीं है
  • checkers को भी इसी अर्थ में weakly solved game के रूप में पेश किया गया है

Othello इतने समय तक बाकी क्यों रहा

  • Othello बड़ी strategic depth वाला लोकप्रिय game है; 19वीं सदी में Britain में invent होने के बाद 20वीं सदी में इसका मौजूदा format Japan में व्यापक रूप से फैला और अब इसे पूरी दुनिया में खेला जाता है
  • World Championship 1977 से हर साल आयोजित होती रही है, जो इसकी global popularity दिखाती है
  • search space बहुत बड़ा है
    • प्रति position औसतन करीब 10 moves
    • पूरे game में औसतन करीब 58 moves
    • संभावित game records करीब 10^58
    • संभावित board positions करीब 10^28
  • यह scale अब तक कठिन समस्या के रूप में हल किए गए games, खासकर checkers, से कहीं ज्यादा बड़ा बताया गया है
  • बड़े search space के कारण Othello computer science में लंबे समय से लंबित चुनौती बना हुआ था

search method और computational efficiency

  • शोधकर्ताओं ने weak solution के लक्ष्य से alpha-beta search का उपयोग किया
  • game-solving algorithms लक्ष्य और game की प्रकृति के अनुसार बदलते हैं
    • weak solution में alpha-beta search अक्सर इस्तेमाल होती है
    • strong solution में retrograde analysis अक्सर उपयोग की जाती है
    • बहुत लंबी answer sequences वाली puzzles के लिए df-pn search जैसे तरीके विकसित किए गए हैं
  • alpha-beta search game graph को depth-first तरीके से sequentially explore करने वाला algorithm है, इसलिए सिर्फ simple parallelization से search efficiency बहुत ज्यादा बढ़ाना मुश्किल है
  • parallel search के लिए कई तरीकों पर शोध हुआ है
    • shared memory environment में YBWC और Lazy SMP लोकप्रिय तरीके हैं
    • distributed memory environment में APHID और ABDADA संबंधित algorithms के रूप में पेश किए गए हैं
  • distributed memory environment में nodes के बीच bandwidth और latency जैसी conditions काफी बदलती हैं, इसलिए developers को environment के मुताबिक algorithm चुनना या नया विकसित करना पड़ सकता है
  • latest computer clusters इस्तेमाल करने पर भी Othello को solve करना बड़ी बाधा था, और latest Othello software को modify करके search efficiency बढ़ाना breakthrough बना

दूसरे solved games और संभावित उपयोग

  • Othello से पहले कठिन समस्या के रूप में solve किया गया नवीनतम उदाहरण checkers बताया गया है
  • Connect Four, Qubic, Go-Moku, Nine Men’s Morris, Awari जैसे non-simple games भी solved examples के रूप में सूचीबद्ध हैं
  • game solving की difficulty आम तौर पर game के भीतर positions या states की संख्या पर काफी निर्भर करती है
  • game को solve करने से अंतिम result बताने के अलावा, उस game पर आधारित puzzle generation में भी इसका उपयोग हो सकता है
  • शोधकर्ताओं ने reproducibility के लिए raw data और programs GitHub, Zenodo, figshare पर उपलब्ध कराए हैं

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

1 टिप्पणियां

 
GN⁺ 2023-11-05
Hacker News की राय

  • “2,958,551 स्थितियों में से 2,587 स्थितियाँ चुनकर परिणाम के बारे में एक परिकल्पना बनाई गई, और अगर ये सभी परिकल्पनाएँ सही हों तो यह साबित होता है कि शुरुआती स्थिति ड्रॉ है,” लेकिन इसके बारे में और विस्तार नहीं दिया गया है
    पूरा गेम सचमुच solve हो गया है, ऐसा कम और यह ज़्यादा लगता है कि लेखक ने जीतने की लाइनें खोजने की काफी कोशिश की, लेकिन नहीं खोज पाया

    • मैंने सरसरी तौर पर देखा, लेकिन लगता है कि अगला ही वाक्य और Algorithm 1 इसी हिस्से को समझाते हैं
      इसमें कहा गया है, “शुरुआती स्थिति ड्रॉ है यह साबित करने वाला subset चुनने के कई तरीके हैं, लेकिन हमने Algorithm 1 से एक छोटा subset प्राप्त किया”
      Algorithm 1 को इस तरह समझाया गया है कि यह “50 खाली खानों वाली सभी स्थितियों के predicted scores लेकर ऐसा subset लौटाता है जिसमें subset की सभी स्थितियाँ solve हो जाएँ और उनके solutions prediction से मेल खाएँ, तो शुरुआती स्थिति भी परिणामस्वरूप solve हो जाती है”
    • मैं भी इसी हिस्से पर अटक गया था। पेपर दो बार पढ़ने के बाद भी मुझे यकीन नहीं है कि मैंने method सही से समझा है
      कुल मिलाकर पेपर की लिखावट सहज-बोधगम्य नहीं है। लेखक सही हो सकता है, लेकिन तसल्ली से बैठकर तर्क को step by step follow करना पड़ेगा; पहली नज़र में मैं संशय में हूँ
    • एक ज़्यादा संभावित व्याख्या यह है कि वे 2,587 स्थितियाँ सभी संभावनाओं को cover करती हैं
      इस तरह के proofs और जगहों पर भी मिलते हैं। उदाहरण के लिए 4-color theorem भी सीमित संख्या की configurations तक reduce करने के बाद हाथ से coloring जाँचने जैसा था
    • लगता है कि कई 36 खाली खानों वाली स्थितियों के परिणाम cluster पर compute करके https://figshare.com/articles/dataset/Analyses_of_the_Game_o... पर अपलोड किए गए हैं
      https://github.com/eukaryo/reversi-scripts/blob/main/reversi... में दिया script, यह मानकर कि सब कुछ सही है, perfectly खेलता है। Repository के दूसरे scripts 36 खाली खानों वाली स्थितियों के solutions से निकले computed data का उपयोग करते हैं, और इतना तो सामान्य मशीन पर भी संभव लगता है
      मूल रूप से यह weak solution से पहुँचा जा सकने वाली 37 से 64 खाली खानों वाली सभी स्थितियों को समेटने वाली 300GB से छोटी table को lookup करता है, और 36 या उससे कम खाली खानों वाली स्थितियों को edax के -solve से हल करता है

  • Othello यह दिखाने के लिए अच्छा गेम है कि सिर्फ बुनियादी heuristics से भी कितनी ताकत हासिल की जा सकती है
    गेम के दौरान कुछ खाने ऐसे होते हैं जहाँ कभी चाल नहीं चलनी चाहिए, और कुछ ऐसे जहाँ मौका मिले तो लगभग हमेशा चलनी चाहिए
    सिर्फ ऐसे नियम implement कर देने से भी एक काफ़ी ठीक-ठाक opponent बन जाता है, और यह देखना दिलचस्प है कि लोग कितनी जल्दी बहुत साधारण चीज़ों में भी “बुद्धिमत्ता” देखने लगते हैं

    • बहुत पहले मैंने Othello programming पर एक लेख पढ़ा था, शायद 1980 के शुरुआती दशक की BYTE Magazine में
      उसमें ऐसे ही simple heuristics इस्तेमाल करने वाले एक app को, उतना ही simple लेकिन बेहद खराब “सबसे ज़्यादा discs पलटो” रणनीति वाले app के खिलाफ चलाया गया था
      heuristic algorithm ने उसे बुरी तरह हरा दिया था; याद पड़ता है स्कोर 60 बनाम 4 या उससे भी खराब था
    • मुझे अब भी याद है कि PDP-11 पर चलने वाला 200-line Pascal program लैब के हर व्यक्ति को हरा देता था
      जब 19 खाली खाने बचते थे, तब वह बाकी गेम को पूरी तरह solve कर देता था, और यह काफी प्रभावशाली था
    • सच कहूँ तो समझ नहीं आता कि यहाँ वास्तव में कौन “बुद्धिमत्ता” आरोपित कर रहा है
      Othello तो दो AA batteries से चलने वाले 10-dollar LCD handheld में भी आने वाला गेम था

  • अगर आपको गेम्स में दिलचस्पी है, तो कंप्यूटर साइंस और AI researchers के बीच भी लोकप्रिय Othello World Championship अभी इटली के Rome में चल रही है
    मैच liveothello.com और Youtube @WorldOthello पर live stream किए जा रहे हैं

    • क्या यह पेपर championship का महत्व खत्म कर देता है? यह भी जिज्ञासा है कि क्या पेपर-आधारित software ने इसमें हिस्सा लिया
      यह भी जानना दिलचस्प होगा कि क्या Othello भी checkers की तरह ऐसा गेम है जिसमें शीर्ष स्तर के ज़्यादातर मैच ड्रॉ पर खत्म होते हैं

  • कमाल है
    लगभग 15 साल पहले मैंने अपने भाई के साथ खेले जाने वाले एक और भी सरल खेल को solve किया था। बोर्ड के दोनों तरफ करीब 10-10 गड्ढे होते थे और उनमें पत्थर रखे जाते थे; एक अफ्रीकी खेल था
    मैंने एक alpha-beta engine लिखा और उसने हमारे खेलने के तरीके के हिसाब से एक बेहूदा-सा हमेशा जीतने वाला strategy ढूँढ निकाला
    उसके बाद मैं अचानक हर game जीतने लगा, और मेरे भाई ने फिर कभी मेरे साथ खेलना नहीं चाहा। यह कंप्यूटर साइंटिस्ट बनाम optometrist की एकदम क्लासिक भिड़ंत थी

    • बहुत बढ़िया। मैंने Mancala कुछ साल खेला है और इसके बारे में और सुनना चाहूँगा
      उम्रदराज़ अफ्रीकी लोगों को Mancala खेलते देखो तो सीखने को बहुत कुछ मिलता है। वे बहुत तेज़ खेलते हैं, और उसमें poker जैसा एहसास भी होता है जहाँ cheating गेम का हिस्सा बन जाती है
      अगर आप कंकड़ बहुत तेज़ी से बिखेरें, तो एक कटोरी छोड़ सकते हैं या एक अतिरिक्त कंकड़ गिराकर फायदा ले सकते हैं
      मैं इतना माहिर नहीं हूँ, और परिवार के साथ खेलता हूँ, इसलिए cheating नहीं करता। फिर भी यह एक बिल्कुल अलग गेम बन जाता है। कुछ वैसा फर्क जैसे इंग्लैंड की महिलाएँ चाय पीते हुए आराम से Mahjong खेलें, बनाम चीनी gambling den में पैसे लगाकर वही खेल खेला जाए
    • अगर और जानना हो तो https://en.wikipedia.org/wiki/Mancala देख सकते हैं
    • स्रोत याद नहीं, लेकिन मैंने सुना है कि लोग सिर्फ उन्हीं games को पसंद करते हैं जिनमें उनकी जीत की संभावना 30–70% के बीच हो
      अगर आप बहुत ज़्यादा जीतते हैं या बहुत ज़्यादा हारते हैं, तो गेम का मज़ा खत्म हो जाता है
    • Mancala और Connect Four solved games के क्लासिक उदाहरण हैं
      लेकिन यहाँ optometrist होने का इससे क्या संबंध है, यह समझ नहीं आता

  • क्या यह सचमुच असली है? लेखक एक ही व्यक्ति है, और वह किसी अनजान-सी deep learning startup से है, इसलिए थोड़ा अजीब लगता है

    • जिस जगह लेखक ने अपने ही नतीजों को monumental कहा है, वहाँ मेरी भौंहें उठ गईं
      शायद अभी peer review चल रहा होगा?
    • ऐसा पहली बार नहीं होगा कि कोई कम-ज्ञात व्यक्ति किसी बड़े सवाल को हल कर दे
      और Othello ठीक-ठीक Riemann hypothesis जितना बड़ा विषय भी नहीं है। हो सकता है इस पर अपेक्षाकृत कम शोध हुआ हो, और अभी भी कुछ low-hanging fruit बाकी रहे हों

  • Othello बच्चों के साथ खेलने के लिए सच में सबसे अच्छे खेलों में से एक है
    इसके नियम सरल हैं, इसमें सीखने लायक पैटर्न हैं, और एक साथ बहुत सारी गोटियाँ पलटने में मज़ा आता है। सबसे बढ़कर, यह सिर्फ बच्चों के लिए नहीं बल्कि बड़ों के लिए भी उतना ही मज़ेदार है
    मैं 6 साल के बच्चे पर हावी हुए बिना भी इसे भरपूर एंजॉय कर पाया, और यह कोई सिर्फ किस्मत-आधारित साधारण खेल भी नहीं लगा

    • इसी तरह अफ्रीकी stone game परिवार का Hus भी एक बार देखना चाहिए
      https://mancala.fandom.com/wiki/Hus
      सिद्धांत रूप में इसमें किस्मत की भूमिका नहीं है, लेकिन व्यवहार में chain reactions की वजह से इतनी दूर तक गणना करना संभव नहीं होता
      बोर्ड को आसानी से खुद बनाया जा सकता है
    • इसी तरह की वजहों से Blokus भी पसंद है

  • अगर आप खेल आज़माना चाहते हैं, तो बच्चों के साथ मिलकर बनाया हुआ यह संस्करण मैंने यहाँ रखा है: https://jawj.github.io/fliptiles
    “AI” player बहुत कमजोर है

    • ड्रॉ कितना बड़ी बात है, यह तो नहीं पता, लेकिन पहली ही बाज़ी 32-32 पर खत्म हुई
      आज एक नया खेल सीखा
    • प्रभावशाली है। बचपन में मैं यह खेल हमेशा खेलता था, लेकिन कुछ समय के लिए इसका अस्तित्व ही भूल गया था, और फिर दोबारा खेलकर मज़ा आया
      कंप्यूटर के 33 अंक थे, मेरे 31

  • अगर आपको लगता है कि Othello बहुत मामूली है, तो Zebra खेलकर देखिए
    मूल लेखक की वेबसाइट: http://radagast.se/othello/
    GitHub source: https://github.com/hoshir/zebra

    • अगर आप नहीं जानते कि Othello क्या है, तो इसे Reversi भी कहा जाता है

  • Othello में मुझे जो बात पसंद है, वह है चाल और क्षेत्र के बीच का विरोधाभास
    खेल के दौरान अपनी बारी पर चाल चलना एक मायने में मेरे लिए नुकसानदेह होता है, फिर भी चाल चलना अनिवार्य है
    इसलिए जब तक बोर्ड इतना छोटा न हो जाए कि पक्के प्रभाव को वापस हासिल करना ज़रूरी हो, तब तक जगह घेरते हुए भी छोटा और अंदर की ओर बने रहना पड़ता है

  • इसी से जुड़ा हुआ, 6x6 Reversi को पूरी तरह सही ढंग से खेलने वाला भी है
    https://mame.github.io/6x6-reversi-oracle/
    स्रोत: https://twitter.com/mametter/status/1476379841004183556
    मुझे अब तक पता ही नहीं था कि 8x8 अभी तक solve नहीं हुआ है

    • मैं तो एक भी काली गोटी नहीं ले पा रहा। क्या यही “perfect” होने का मतलब है?