रेगुलर एक्सप्रेशन से इम्प्लीमेंट किया गया मिनीमैक्स शतरंज इंजन

2-प्लाई मिनीमैक्स शतरंज इंजन

• शतरंज और रेगुलर एक्सप्रेशन (regex): लेखक ने केवल regex का इस्तेमाल करके शतरंज खेलने वाला एक प्रोग्राम बनाया। यह प्रोग्राम चेसबोर्ड को इनपुट के रूप में लेकर वैध चालें चलाने के लिए 84,688 regex का उपयोग करता है।

• रेगुलर एक्सप्रेशन CPU डिज़ाइन: regex का उपयोग करके condition-free execution और single instruction multiple data (SIMD) instruction set डिज़ाइन किया गया। इसी से शतरंज खेल पाने वाला प्रोग्राम लिखा जा सका।

• डेटा संरचना: कंप्यूटर की वर्तमान स्थिति को एक अकेली स्ट्रिंग में दर्शाया जाता है जिसमें प्रोग्राम "स्टैक" और सभी variables शामिल होते हैं। हर कमांड या तो स्टैक का कोई variable बदलता है या किसी निश्चित variable पर read/write करता है।

• मूल स्टैक ऑपरेशन:

  • push कमांड: स्टैक के शीर्ष पर value जोड़ता है।
  • pop कमांड: स्टैक के शीर्ष तत्व को हटाता है।

• वेरिएबल <-> स्टैक निर्देश:

  • वेरिएबल लुकअप: किसी variable की सामग्री को स्टैक के शीर्ष पर लोड करता है।
  • वेरिएबल असाइनमेंट: किसी variable को value देता है; यदि variable मौजूद हो तो अपडेट करता है, वरना नया बनाता है।

• कंडीशनल स्टेटमेंट: कंडीशनल स्टेटमेंट से प्रोग्राम का flow कंट्रोल होता है। शर्त के आधार पर प्रोग्राम का कोई हिस्सा active या inactive किया जाता है।

• लूप की असंभवता: केवल regex से loops इम्प्लीमेंट नहीं किए जा सकते, इसलिए सभी iterative गणनाओं को पहले से unroll करना पड़ता है।

• मल्टी-थ्रेडेड execution: regex के ग्लोबल replacement फीचर का उपयोग करके कई थ्रेड्स को साथ-साथ चलाया जा सकता है।

• शतरंज इंजन लिखना: यह शतरंज इंजन अन्य प्रोग्रामिंग भाषाओं की तरह ही लिखा जाता है और parallel processing के कारण तेज़ी से काम करता है।

• टर्न प्ले:

  • प्लेयर का मूव पढ़ना: इनपुट किए गए मूव को पढ़कर उसकी वैधता जाँची जाती है।
  • कंप्यूटर का जवाब बनाना: सभी संभव जवाब (responses) generate करके सर्वोत्तम मूव चुना जाता है।

• मिनीमैक्स खोज: depth 2 मिनीमैक्स खोज के माध्यम से best move चुना जाता है। यह प्रक्रिया भी parallel execution से कुशलता से की जाती है।

यह प्रोजेक्ट regex के अनोखे इस्तेमाल से एक शतरंज इंजन लागू करने का उदाहरण है, जो regex की ताकत और रचनात्मक कंप्यूटर डिज़ाइन को दिखाता है।

[GN⁺]

Hacker News टिप्पणी

• यह वही डेवलपर है जिसने printf() की Turing completeness साबित की थी और 13kB JavaScript से एक first-person shooter गेम लिखा था

  • GitHub लिंक: printf() Turing पूर्णता
  • GitHub लिंक: 13kB JavaScript गेम

• कई संभावित चालों की गणना को एक साथ करने के कारण यह प्रोजेक्ट बहुत खास लगता है

  • रेगुलर एक्सप्रेशन का उपयोग करके कई थ्रेड्स एक साथ रन किए जा सकते हैं

• ब्लाॅग पोस्ट के निष्कर्ष पर मेरी कोई खास टिप्पणी नहीं है, लेकिन अच्छा लगता कि और लोग ऐसे seemingly pointless प्रोजेक्ट्स का प्रयास करें

  • यह मजेदार है क्योंकि इसमें पूरा करने का समय-सीमा या सफल होने का दबाव नहीं होता, और कंप्यूटर साइंस के कई अलग क्षेत्रों के बारे में बहुत कुछ सीखने को मिलता है

• शतरंज गेम में "illegal move, loss" वाला बग दिखता है

  • उदाहरण गेम में वैध चाल होने के बावजूद गेम बंद हो जाता है

• 84,688 रेगुलर एक्सप्रेशंस से शतरंज खेलने वाले की तुलना में एक ही रेगुलर एक्सप्रेशन से शतरंज खेलने वाला ज़्यादा डरावना लगता है

• ऐसी परियोजनाओं को देखकर मैं सम्मान व्यक्त करना चाहता हूँ

• a-file move से जुड़ा बग ठीक किया गया है

  • GitHub लिंक: बग फिक्स

• यह सिर्फ़ एक chess engine नहीं, बल्कि सिर्फ रेगुलर एक्सप्रेशन से बना एक कंप्यूटर और assembly language भी है

• पहले भी एक sed-आधारित शतरंज प्रोजेक्ट था

  • sed संस्करण control-flow instructions का उपयोग करता था और केवल 1ply खोजता था

• a2a4 से शुरुआत करने पर यह इतनी जल्दी हार नहीं खाता

• बिना किसी साफ़ "productive" लक्ष्य के कुछ कोशिश करना नए तरीके खोजने और इन्नोवेशन को आगे बढ़ा सकता है

  • इंजन शुरुआत में ही pieces खो देता है
  • uppercase इनपुट करने पर इसे illegal move दिखता है

• इन्नोवेट करने और productive बने रहने की कोशिश चल रही है