84,688 regular expressions से बनाया गया 2-ply minimax chess engine

• Regex Chess एक 2-ply minimax engine है जो 84,688 regular expression substitutions को क्रम से चलाकर chessboard पर एक legal और “पूरी तरह बेकार नहीं” चाल चुनता है
• state को एक ही string के अंदर stack और variables के साथ रखा जाता है, और push, pop, variable lookup·assignment जैसे commands को regular expression substitutions से प्रोसेस किया जाता है
• conditional branching को active state दर्शाने वाले %% marker को बदलकर emulate किया जाता है, और global substitution की वजह से कई states को एक साथ प्रोसेस करने वाला SIMD-जैसा parallel execution संभव हो जाता है
• engine सभी legal moves को parallel states में बनाता है और opponent responses तक evaluate करता है, लेकिन opponent responses की legality तक पूरी तरह verify करने वाली depth-3 search नहीं करता
• शुरुआत में एक response में लगभग 30 मिनट लगते थे, लेकिन intermediate variable deletion, matching optimization, special-purpose commands, और parallelization के बाद final implementation position के अनुसार 1–10 सेकंड तक आ गया

---

Regex Chess की बुनियादी संरचना

• Regex Chess पूरे chess engine को 84,688 regular expressions की सूची के रूप में बनाता है
• execution structure सरल है
  • regular expression list को क्रम से iterate किया जाता है
  • मौजूदा chessboard state string पर हर pattern और replacement string लागू की जाती है
  • अंतिम state को स्क्रीन पर दिखाया जाता है
• input PGN नहीं, बल्कि e2e4 की तरह source square और destination square को जोड़कर लिखा गया coordinate format है
• project code GitHub पर उपलब्ध है

Regular expression CPU

• chess rules को सीधे regular expressions में लिखने के बजाय, पहले regular expressions पर चलने वाला एक छोटा computer बनाया गया
• यह computer branchless conditional execution, single-instruction multiple-data execution, और stack व variable manipulation वाले instruction set का उपयोग करता है
• current state को एक string के रूप में दर्शाया जाता है
  • %% active execution state की शुरुआत दिखाता है
  • #stack: के नीचे stack items जमा होते हैं
  • variables #variable: value के रूप में store होते हैं

• Stack और variable manipulation

  • push, %%\n#stack:\n header को ढूंढकर उसके नीचे value insert करता है और उसे stack top पर रखता है
  • pop, #stack: के ठीक नीचे की एक line हटाकर stack top value को हटा देता है
  • variable lookup state string में #variable_name: ढूंढकर value copy करता है और उसे stack top पर जोड़ देता है
  • variable assignment, variable के पहले से मौजूद होने और न होने दोनों स्थितियों को संभालता है
    • अगर मौजूद है तो पुरानी variable value को stack value से बदल देता है
    • अगर नहीं है तो नई variable line जोड़ देता है
  • backtick जैसे temporary markers का उपयोग करके यह रोका जाता है कि वही command गलत क्रम में फिर से apply न हो जाए

Branchless conditional execution और loop limitations

• conditional execution को cond(tag) और reactivate(tag) से implement किया गया है
• अगर stack top False है, तो active marker %%, %tag में बदल जाता है और बाद के commands उस state पर लागू नहीं होते
• बाद में reactivate(tag), %tag को फिर %% में बदलकर उस state को दोबारा active करता है
• इस तरीके से explicit branching के बिना conditional execution को emulate किया जाता है
• program regular expressions की sequential list है, इसलिए loops को सीधे execute नहीं किया जा सकता
  • यह Turing-complete computation नहीं कर सकता
  • लेकिन chess की next move calculation जैसी bounded computation को loop unrolling से संभाला जा सकता है

Global substitution से parallel execution

• क्योंकि regular expression substitution पूरी string पर globally लागू होती है, एक state string के अंदर कई %% execution states हों तो वही command कई states पर एक साथ लागू होती है
• उदाहरण के लिए, अगर दो stacks में अलग-अलग दो integers हों, तो binary_add() चलाने पर दोनों additions एक साथ हो जाते हैं
• fork_inactive(tag) current active state को clone करता है और clone को inactive tagged state में रखता है
• fork_bool(variable) एक state को True value और False value वाली दो states में बाँट देता है
• यह संरचना chess में कई possible board states को एक-एक करके process करने के बजाय एक साथ evaluate करने के लिए उपयोग होती है

Macro assembler और symbolic execution

• engine सिर्फ regular expressions को हाथ से लिखकर नहीं बनाया गया, बल्कि एक macro assembler का उपयोग करता है जो Python-जैसे program को छोटे instruction sequences में बदलता है
• fib() जैसे Python-style code को push, lookup, binary_add, assign_pop जैसे instruction lists में convert किया जाता है
• traditional parser और code generation की जगह symbolic execution का उपयोग किया गया है
  • variable objects असली dictionary नहीं, बल्कि किए गए operations को रिकॉर्ड करने वाले special objects हैं
  • a = b + 1 को lookup('b'), push(1), binary_add(), assign_pop('a') के रूप में रिकॉर्ड किया जाता है
• if statement में condition true और false, दोनों paths को रिकॉर्ड करके फिर merge किया जाता है
  • condition branch मिलने पर call tree में दो paths बनाए जाते हैं
  • कई बार trace करते हुए कम-visited branch को चुनकर दोनों paths भरे जाते हैं
  • merge point को reactivate instruction में बदला जाता है

Chess move generation का तरीका

• chess engine लिखना अपने आप में सामान्य language वाले chess engines जैसा है, लेकिन कई states को parallel में process करना इसका मुख्य बिंदु है
• pawn move generation का flow इस तरह है
  • सभी white pawn positions को ढूंढा जाता है
  • हर pawn के लिए parallel state बनाई जाती है
  • मूल main state को रोका जाता है और pawn-specific states को active किया जाता है
  • एक square आगे, दो squares आगे, और diagonal capture candidates को सभी pawn states में एक साथ check किया जाता है
  • हर state की candidate move list को फिर से merge किया जाता है
• explanation के लिए दिया गया example सीधे FEN string को संभालता है, लेकिन असली implementation chessboard को 64 square-wise variables में expand करके पढ़ता और लिखता है
• bishop, rook, queen जैसे sliding pieces, castling, और en passant भी अलग से implement किए गए हैं
• detail implementation chess_engine.py में है

एक turn का processing और move verification

• एक turn में human input move पढ़ी जाती है, उसकी legality verify की जाती है, और फिर computer response move generate की जाती है
• from_pretty_utf8_to_fen() Unicode chessboard display को FEN notation में बदलता है और input के source·destination squares निकालता है
• human move की legality को अलग rules-checking code से नहीं, बल्कि सभी legal next boards generate करके compare करने से verify किया जाता है
  • make_move input move लागू किया हुआ board बनाता है
  • compute_legal_boards current position से सभी possible legal boards generate करता है
  • fork_on_list हर board को parallel state में अलग करता है
  • input move applied result से अलग states को destroy_active_thread() से हटा दिया जाता है
• अगर कोई legal move नहीं मिलती, तो पूरा output hardcoded "Illegal Move" text में बदल जाता है
• computer response में possible black response boards और scores बनाए जाते हैं, फिर keep_best_scoring_board(score) से सबसे अच्छे score वाला board ही रखा जाता है

2-ply minimax और जानबूझकर की गई सरलताएँ

• compute_and_score_legal_boards, depth-2 minimax search का मुख्य हिस्सा है
• पहले computer की candidate moves generate होती हैं, फिर opponent की possible responses बनाई जाती हैं ताकि यह देखा जा सके कि king पकड़ा जा सकता है या नहीं
• check state validation की वजह से opponent responses तक generate करनी पड़ती हैं, इसलिए depth-2 search structure पहले से बन जाता है
• हर candidate position को उस score से evaluate किया जाता है जो opponent के best response पर मिलता है
• यह पूरी तरह का depth-2 minimax नहीं है
  • opponent response move अपने ही king को check में छोड़ने वाली illegal move है या नहीं, यह verify नहीं किया जाता
  • इसे पूरी तरह संभालने के लिए depth-3 search चाहिए और cost बहुत बढ़ जाती है
• computer जो response खुद generate करता है, वह illegal नहीं होता, लेकिन कुछ मामलों में यह opponent की ऐसी move को भी consider कर सकता है जो वास्तव में संभव नहीं है, और इस वजह से वास्तविकता से कमजोर response चुन सकता है

Performance optimization

• शुरुआती implementation को human की एक move के response generate करने में लगभग 30 मिनट लगते थे
• final implementation में, लेखक की machine पर position के हिसाब से 1–10 सेकंड लगते हैं
• लगभग 100x speedup कई optimizations का परिणाम है

• Intermediate variable deletion

  • variable lookup में पूरी state string में variable value ढूंढनी पड़ती है, इसलिए इसकी लागत O(n) होती है
  • execution state fork होने पर variables भी साथ copy होते हैं, जिससे memory usage बढ़ता है
  • जिन variables की अब जरूरत नहीं है उन्हें aggressively delete किया जाता है और variable names को reuse किया जाता है, जिससे time और memory दोनों बचते हैं
  • एक move evaluation की internal state optimization से पहले 10GB से घटकर लगभग 300MB रह गई

• Regular expression matching optimization

  • conditional command के cleanup regular expression में शुरू की newline शामिल करने भर से उस command की efficiency लगभग 2x हो गई
  • state में True और False strings बहुत बार आती हैं, इसलिए pattern को सीमित करके सिर्फ stack top value जल्दी ढूंढनी होती है
  • अनावश्यक candidate matches घटाने वाले छोटे pattern differences पूरे runtime को प्रभावित करते हैं

• Special-purpose commands और parallelization

  • piece positions ढूंढने वाले loops जैसे धीमे हिस्सों को मौजूदा instructions के संयोजन के बजाय एक special regular expression command में मिला दिया गया
  • rook move generation में हर direction को sequentially check करने के बजाय कई parallel states बनाकर एक साथ process किया जाता है
  • position evaluation भी candidate boards के लिए parallel states बनाकर साथ में की जाती है
  • piece value calculation जैसे कामों में, जहाँ वही operation कई states पर दोहराया जाता है, parallel execution खास तौर पर प्रभावी है

Source में शामिल अतिरिक्त implementations

• source में ऐसे implementation details भी हैं जिन्हें लेख में गहराई से नहीं खोला गया
  • bishop, rook, queen जैसे sliding pieces के लिए parallel move generation
  • castling के लिए “क्या यह square attacked है” प्रक्रिया
  • FEN chessboard और per-square variable representation के बीच conversion
  • king और rook positions track करके castling rights detect करना
  • en passant detection और tracking
  • हजारों games में engine accuracy verify करने वाले लगभग 2000 lines के tests
• अंत में यह कहा गया है कि ऐसे बिना किसी व्यावहारिक उद्देश्य वाले projects ने लेखक को अपने क्षेत्र के बाहर के कई computer science topics सीखने में मदद की
• संबंधित projects के रूप में C के printf से tic-tac-toe खेलने वाला printf-tac-toe और 13kB JavaScript Doom clone का भी उल्लेख है

[GN⁺]

Hacker News की टिप्पणियां

• यह वही काम है उस व्यक्ति का, जिसने दिखाया था कि printf() Turing-complete है, और 13kB JavaScript में first-person shooter game बनाया था
  https://github.com/HexHive/printbf
  https://github.com/carlini/js13k2019-yet-another-doom-clone

  • “printf() Turing-complete है, और first-person shooter game …” वाली लाइन पढ़कर, सच कहूं तो मुझे लगा था कि अंत में निकलेगा कि उस shooter game को भी printf से implement किया गया था
  • Doom बनाने की कहानी काफ़ी detail वाली है, इसलिए दिलचस्प है: https://nicholas.carlini.com/writing/2019/javascript-doom-cl...
    प्रतियोगिता में पूरा करने का समय एक महीना था, लेकिन लगता है मौजूदा code reuse किया जा सकता था
    काम अपने-आप में काफ़ी मज़ेदार रहा होगा, और यह सोचकर थोड़ा दुख होता है कि अब परिवार और काम की वजह से ऐसी चीज़ के लिए एक महीने का खाली समय निकाल पाना मेरे लिए बिल्कुल संभव नहीं लगता
  • “13kB JavaScript में first-person shooter game” सुनकर उम्मीद बढ़ गई थी, लेकिन जब पता चला कि graphics rendering के लिए WebGL इस्तेमाल किया गया है, तो थोड़ी निराशा हुई

• इस बिंदु पर मुझे लगा कि यह काम पागलपन भरे मज़े से आगे बढ़कर पूरी तरह असाधारण हो गया है। संभावित कई positions की calculation सब parallel में हो रही थी, और बढ़ते हुए state/variables के set—यानी threads—पर regex चलाया जा रहा था
  “अब हमारी बनाई language का मेरा सबसे पसंदीदा हिस्सा आता है। regex के जादू और पूरे string पर global substitution करने के fact की वजह से हम कई threads को एक साथ चला सकते हैं!”
  निष्कर्ष भी अच्छा था। “ऐसे blog post के निष्कर्ष से आप क्या उम्मीद करते हैं? कोई खास निष्कर्ष नहीं है। बस मैं चाहता हूं कि और लोग ऐसे पूरी तरह बेकार काम करें। यह सचमुच मज़ेदार है, इसे खत्म करने में कितना भी समय लगे किसी को परवाह नहीं, यह चले या न चले किसी को परवाह नहीं, और bonus में आप अपने field के बाहर computer science के कई क्षेत्रों के बारे में जितना सीखना चाहते थे उससे ज़्यादा सीख जाते हैं।”
  सचमुच शानदार attitude है

  • बाकी सारी चिंताओं को हटा दें तो मैं भी सोचने लगता हूं कि क्या मैं ऐसा कुछ कर पाऊंगा
    इससे मिलने वाली चीज़ यह ताकत है कि बैठकर एक चीज़ पर मन लगाकर ध्यान दिया जाए तो पता नहीं कहां तक जा सकते हैं, और साथ ही यह भी कि लेखक साफ़ तौर पर बेहद प्रतिभाशाली, अनुभवी और creative व्यक्ति है

• लगता है कहीं कोई bug है। नीचे वाला game illegal move नहीं है, फिर भी “Illegal move, you lose” पर खत्म हो जाता है

  1. e2e4, e7e5
  2. d2d4, e5d4
  3. d1d4, a7a5
  4. g1f3, b7b5
  5. b1c3, a5a4
  6. c3b5, a4a3
  7. b5a3, a8a3
  8. b2a3 -->
     Illegal Move
     You Lose.
     Game over.
     ऊपर वाले game का FEN:
     1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
  • अगर पहली चाल a2a3 चलें, या e2e4 के बाद दूसरी चाल में a2a3 चलें, तब भी illegal move दिखाता है
    लेकिन दोनों legal moves हैं, इसलिए यह वाकई bug है
  • पहली चाल में सिर्फ a2a4 चलने पर भी यही होता है

• 84,688 regexes से chess खेलने वाले व्यक्ति से मुझे डर नहीं लगता, लेकिन एक regex से chess खेलने वाले व्यक्ति से डर लगता है

  • Sequentially apply होने वाले regexes को linear बनाने के लिए कोई common heuristic—यानी किसी भी दो regexes को एक में merge करने का तरीका—हो तो उसे यहां apply किया जा सकता है
    मदद करो, मैं nerd-sniping का शिकार हो रहा हूं
    तुरंत दिमाग में आने वाली संभावित समस्या backreferences हैं
    regex बहुत लंबा हो जाएगा, लेकिन असल में वह chess engine को encode ही कर रहा होगा…

• ऐसी चीज़ें देखकर टोपी उतारकर मानवता के सच्चे नायकों को गंभीर धन्यवाद देने का मन करता है

• a-file move bug ठीक कर दिया गया है: https://github.com/carlini/regex-chess/issues/1

• पहले का उदाहरण: sed में लिखा chess https://news.ycombinator.com/item?id=6261314
  बेशक sed version sed के control-flow commands का इस्तेमाल करता है, और शायद सिर्फ 1 move ahead search करता है, इसलिए इस मामले में यह version उससे काफ़ी अलग है

• यह सिर्फ chess engine ही नहीं है, बल्कि computer और assembly language को भी सिर्फ regexes से बनाया गया है

• आम तौर पर a2a4 से शुरू करने पर इतनी जल्दी हार नहीं होती!

  • मुझे भी a-file में मिलता-जुलता bug मिला। path था e2e4-d2d4-d1d4-g1f3-f1b5-d4e5-e5c5-e1g1-b2a3

• इसकी तुलना भी की जा सकती है: https://codegolf.stackexchange.com/q/3503/32575

  • सभी divisibility test rules अनिवार्य रूप से regular languages होते हैं, इसलिए यह बहुत चौंकाने वाली बात नहीं है। अगर वे इससे ज़्यादा complex हों, तो वे इंसान द्वारा चलाए जा सकने वाले “rules” नहीं रहेंगे