WordChess · विचार के लिए भोजन

कंप्यूटर शब्द कैसे चुनता है

AI खेलने से पहले, उसे सौ पचास हज़ार शब्दों के ढेर में अपनी चाल खोजनी होती है, और फिर खोजना बंद कर देना होता है।

अंग्रेज़ी में लिखा और संपादित। यह हिन्दी संस्करण मशीनी अनुवाद से तैयार किया गया है; जहाँ सटीकता महत्वपूर्ण हो, वहाँ अंग्रेज़ी मूल ही प्रामाणिक है। मूल अंग्रेज़ी में पढ़ें →

01 · घास का ढेर

देखने के लिए बहुत बड़ा स्थान

किसी व्यक्ति को WordChess टाइलों का एक पूरा सेट दें और निर्देश दें "एक अच्छा शब्द खेलो," तो वह बिना ध्यान दिए ही समस्या को सीमित कर लेता है। कंप्यूटर को ऐसी कोई सहज समझ नहीं मिलती। 25×25 बोर्ड पर, सौ टाइलों का अपना पूरा सेट लिए हुए, वह शब्दकोश के 148,941 शब्दों में से लगभग किसी का भी प्रयास कर सकता है, और हर शब्द को हज़ारों वैध निर्देशांकों और दिशाओं में रखा जा सकता है। इससे भी बुरा, कोई प्लेसमेंट तभी वैध है जब उसके द्वारा जोड़ा गया हर नया अक्षर, जहाँ वह बोर्ड पर पहले से मौजूद शब्दों को काटता है, वहाँ भी एक वास्तविक शब्द पूरा करे। शब्दों को प्लेसमेंट से और फिर उस क्रॉसिंग शर्त से गुणा करें, और आपके सामने ऐसा खोज-क्षेत्र होता है जिसे कोई भी खिलाड़ी, सिलिकॉन का हो या नहीं, पूरी तरह गिन और क्रमबद्ध नहीं कर सकता।

यही वजह है कि गंभीर वर्ड-गेम इंजन, जिनमें Quackle, ओपन-सोर्स रेफरेंस इम्प्लीमेंटेशन, शामिल हैं, कभी भी शब्दकोश का ब्रूट-फोर्स नहीं करते। ⁴ स्टीवन गॉर्डन की 1994 की GADDAG संरचना, और उसके पहले DAWG, एक प्रोग्राम को बोर्ड पर पहले से मौजूद टाइलों से शब्दों को बाहर की ओर बढ़ने और क्रॉसिंग जांचने की अनुमति देती हैं, ताकि अवैध शाखाएं जल्दी मर जाएं, स्कोर किए जाने और हटाए जाने के बजाय। ¹ कार्य "हर शब्द की सूची बनाना" नहीं है। यह "केवल उन चालों को जनरेट करना है जो संभवतः वैध हो सकती हैं, और इसे तेज़ी से करना है" है।

02 · घड़ी

पर्याप्त अच्छा, पूर्णता से बेहतर है

एक किफ़ायती जनरेटर भी इतनी उम्मीदवार चालें लौटाता है जितनी का गहराई से मूल्यांकन नहीं किया जा सकता, इसलिए दूसरी समस्या समय की है। ब्रायन शेपर्ड का Maven, शीर्ष मानव प्रतिद्वंद्वियों को मात देने वाला पहला प्रोग्राम, ठीक इसी समस्या से जूझा और उसने इसे दो चरणों में सुलझाया: एक तेज़ हेयुरिस्टिक कच्ची चालों को गुणवत्ता के मोटे क्रम में छाँटता है, और केवल सबसे आशाजनक चालों की एक छोटी सूची का ध्यान से अध्ययन किया जाता है, खेल को कई बार आगे तक सिमुलेट करके यह देखने के लिए कि कौन-सा उम्मीदवार वास्तव में सबसे अच्छा प्रदर्शन करता है। ² दूसरे खेल इसी विचार को दूसरे नामों से जानते हैं, बैकगैमन का रोलआउट (rollout) और गो प्रोग्राम का प्लेआउट (playout); Maven में इसे सिमुलेशन (simulation) कहा जाता है।

WordChess एक कठोर प्रतिबंध के तहत उसी भावना में काम करता है: प्रत्येक चाल के लिए एक निश्चित खोज-समय बजट। जब बजट खत्म हो जाता है, तो AI उस सबसे अच्छे शब्द को स्वीकार कर लेता है जिसे उसने अब तक खोजा है। यह कोई समझौता नहीं है जिसकी इंजीनियरों को पछतावा होता है; यह पूरा डिज़ाइन है। एक खिलाड़ी जो हमेशा सोचता है, एक बेहतर प्रतिद्वंद्वी नहीं है, बस एक धीमा है। घड़ी मशीन को वही करने के लिए मजबूर करती है जो लोग सहज रूप से करते हैं, एक चाल के लिए तय हो जाना जो स्पष्ट रूप से अच्छी है, प्रमाणित सबसे अच्छी के बजाय।

शब्दकोश जानना आसान हिस्सा है। उसमें खोज कब रोकनी है, यह जानना कठिन हिस्सा है।

03 · ईमानदार कठिनाई

कमज़ोरी जिस पर भरोसा किया जा सकता है

गेम AI को आसान बनाने का आलसी तरीका है उसे बेतरतीब ढंग से मूर्ख बना देना, ताकि वह ऐसी चाल बिगाड़ दे जो उसे साफ़ दिख रही थी। खिलाड़ी इसे भाँप लेते हैं, और उन्हें यह बुरा लगता है। डिज़ाइनर सिड मियर का अक्सर उल्लेख इस बात के लिए किया जाता है कि उन्होंने Civilization से गठबंधन (alliance) सुविधाएँ इसलिए हटा दीं क्योंकि कंप्यूटर उनका लगभग उतना ही अच्छा फ़ायदा उठा सकता था जितना कोई खिलाड़ी; इसका प्रभाव, AI-प्रतिद्वंद्वी डिज़ाइन के एक विवरण में उद्धृत मियर के शब्दों में, "गेमर्स को यह एहसास कराता कि वे जीत नहीं सकते क्योंकि कंप्यूटर बेईमानी कर रहा था।" ³ जो कठिनाई बेईमानी जैसी लगे, वह खेल को विषाक्त कर देती है, और इसीलिए गतिशील कठिनाई समायोजन (dynamic difficulty adjustment) पर शोध साहित्य इस बात को ट्यून करने पर ध्यान देता है कि AI क्या करने में सक्षम है, न कि उसे क्या देखने की अनुमति है। ⁵

WordChess अपने चार स्तरों को उन धुरियों पर ट्यून करता है जिन्हें कोई मनुष्य पहचान लेगा, AI को छिपी जानकारी देकर कभी नहीं। स्तरों में अंतर इस बात का है कि वे कितनी देर खोज सकते हैं, उनका शब्दभंडार दुर्लभ शब्दकोश में कितनी गहराई तक पहुँचता है, और वे किन शब्द-लंबाई बैंडों को तरजीह देते हैं। एक आसान प्रतिद्वंद्वी विश्वसनीय ढंग से कमज़ोर शब्द खेलता है, वास्तविक, समझदार, छोटे, कचरा नहीं। ग्रैंडमास्टर के पास कठिन स्तर जैसा ही पूरा अप्रचलित शब्दभंडार है, और उसे खंगालने के लिए सबसे अधिक समय भी। खिलाड़ी उस चीज़ से हारता है जो बेहतर शब्दभंडार और पैनी समझ जैसी दिखती है, क्योंकि वह ठीक वही है।

चार स्तर, सीमाओं से ट्यून किए गए, इस परियोजना के डिज़ाइन और बिल्ड नोट्स से मापे गए

स्तर	शब्दभंडार की पहुँच	खोज बजट	शब्द-लंबाई का झुकाव
आसान	केवल आम	सबसे छोटा	छोटे
सामान्य	आम + मध्यम + आधा दुर्लभ	छोटा	मिश्रित
कठिन	पूरा	लंबा	अधिक लंबे
ग्रैंडमास्टर	पूरा	सबसे लंबा	असीमित

04 · एक प्रतिद्वंद्वी, कैलकुलेटर नहीं

क्या इसे इंसान जैसा महसूस कराता है

एक कैलकुलेटर हर बार वही उत्तर देता है; एक प्रतिद्वंद्वी आपको चौंकाता है। WordChess चयन में जानबूझकर एक यादृच्छिक चरण जोड़ता है, ताकि लगभग बराबर चालें हमेशा एक ही तरह से तय न हों और AI हर बार वही शब्द दोबारा न खेले। स्तर-वार शब्दभंडार की सीमाओं के साथ मिलकर, इसका प्रभाव विविधता है, यह एहसास कि बोर्ड के उस पार कोई बैठा है जो चुनाव कर रहा है, जिनमें से कुछ आप भी कर सकते थे।

यही इसका शांत कला है। एक विश्वसनीय प्रतिद्वंद्वी को बल के साथ-साथ संयम की भी ज़रूरत होती है: बस अच्छे शब्द को खेलने की तैयारी, अंक टेबल पर छोड़ देने की, और हारने की ऐसी शैली जिसमें कमाई का अहसास हो। मशीन का सबसे कठिन इंजीनियरिंग मुद्दा घास के ढेर में खोज करना था। इसका सबसे सूक्ष्म मुद्दा यह सीखना था कि कब खोज रोकनी है, क्या जानना है, और कितना पीछे रखना है।

Sources & notes

1. Wikipedia, "GADDAG", the move-generation data structure introduced by Steven A. Gordon (1994) that grows words from placed tiles and validates crossings during generation. en.wikipedia.org/wiki/GADDAG
2. Brian Sheppard, "World-Championship-Caliber Scrabble," Artificial Intelligence 134 (2002): 241–275, describes Maven, the first program to outperform the strongest human players against human opposition, with its selective move generation and its simulations of likely game scenarios. doi.org/10.1016/S0004-3702(01)00166-7. Overview of the program: en.wikipedia.org/wiki/Maven_(Scrabble)
3. Vina Nguyen, "How to Design a Worthy Opponent: AI in Game Development", on believable difficulty, deliberately handicapping the AI, and the resentment bred by opponents that appear to cheat (source of the quoted Sid Meier / Civilization account). vinawrites.com
4. Quackle (Jason Katz-Brown, John O'Laughlin, et al.), an open-source Scrabble engine bundling a GADDAG move generator, evaluator, and simulator for any lexicon or board. Source: github.com/quackle/quackle; project page: people.csail.mit.edu/jasonkb/quackle
5. M. Zohaib, "Dynamic Difficulty Adjustment (DDA) in Computer Games: A Review," Advances in Human-Computer Interaction (2018), survey of tuning challenge by adjusting AI capability rather than cheating. onlinelibrary.wiley.com/doi/10.1155/2018/5681652
6. WordChess-specific facts, the four difficulty tiers, the time/vocabulary/word-length levers, the randomized selection, and the opening-book collapse ("MY" fifteen times), are measured from this project's design and build notes.