TD-Gammon एक कंप्यूटर बैकगैमन प्रोग्राम है जिसे 1990 के दशक में आईबीएम के थॉमस जे. वॉटसन रिसर्च सेंटर में जेराल्ड टेसauro द्वारा विकसित किया गया था। इसका नाम अस्थायी-अंतर सीखने, विशेष रूप से TD-Lambda द्वारा प्रशिक्षित एक कृत्रिम Neural network के उपयोग से लिया गया है। इसने ऐसी रणनीतियों की खोज की जिन्हें मनुष्यों ने नहीं अपनाया था और सही बैकगैमन खेल के सिद्धांत में प्रगति की। 1993 में, TD-Gammon (संस्करण 2.1) को 1.5 मिलियन आत्म-खेल खेलों के साथ प्रशिक्षित किया गया था और उस समय के शीर्ष मानव बैकगैमन खिलाड़ियों के स्तर से थोड़ा नीचे खेल का स्तर हासिल किया। 1998 में, 100-खेलों की श्रृंखला के दौरान, यह विश्व चैंपियन से केवल 8 अंकों के अंतर से हार गया था। कुछ शुरुआती रणनीतियों का इसका अपरंपरागत मूल्यांकन विशेषज्ञ खिलाड़ियों द्वारा स्वीकार और अपनाया गया था। TD-Gammon को अक्सर Reinforcement learning और तंत्रिका नेटवर्क की प्रारंभिक सफलता के रूप में उद्धृत किया जाता है, और गहरे Q-सीखने और AlphaGo के लिए पेपरों में इसका संदर्भ दिया गया था।
खेल और सीखने के लिए एल्गोरिथ्म
खेल के दौरान, TD-Gammon प्रत्येक मोड़ पर सभी संभावित कानूनी चालों और उनके सभी संभावित प्रतिक्रियाओं (लुकआगे खोज) की जांच करता है, प्रत्येक परिणामी बोर्ड स्थिति को अपने मूल्यांकन फ़ंक्शन में फीड करता है, और उस चाल का चयन करता है जो उच्चतम स्कोर वाली बोर्ड स्थिति की ओर ले जाती है। इस मामले में, TD-Gammon लगभग किसी भी अन्य कंप्यूटर बोर्ड-गेम प्रोग्राम से अलग नहीं है। TD-Gammon का नवाचार यह था कि इसने अपने मूल्यांकन फ़ंक्शन को कैसे सीखा।
TD-Gammon का सीखने का एल्गोरिथ्म प्रत्येक मोड़ के बाद अपने तंत्रिका नेटवर्क में वज़न को अपडेट करने के लिए होता है ताकि पिछले मोड़ों की बोर्ड स्थितियों के अपने मूल्यांकन और वर्तमान मोड़ की बोर्ड स्थिति के अपने मूल्यांकन के बीच अंतर कम हो सके - इसलिए "अस्थायी-अंतर सीखना।" किसी भी बोर्ड स्थिति का स्कोर चार संख्याओं का एक सेट होता है जो प्रत्येक संभावित खेल परिणाम की संभावना के प्रोग्राम के अनुमान को दर्शाता है: सफेद सामान्य रूप से जीतता है, काला सामान्य रूप से जीतता है, सफेद गैमन जीतता है, काला गैमन जीतता है। खेल की अंतिम बोर्ड स्थिति के लिए, एल्गोरिथ्म अपने बोर्ड स्थिति के मूल्यांकन के बजाय खेल के वास्तविक परिणाम के साथ तुलना करता है।
TD-Gammon का मूल 3 परतों वाला एक तंत्रिका नेटवर्क है। इनपुट परत में दो प्रकार के न्यूरॉन होते हैं। एक प्रकार बोर्ड स्थिति को कोड करता है: 0 से 15 तक के गैर-ऋणात्मक पूर्णांक, जो प्रत्येक बोर्ड स्थान पर सफेद या काले चेकर्स की संख्या दर्शाते हैं, प्रत्येक के लिए 99 इनपुट न्यूरॉन्स के साथ, कुल 198 न्यूरॉन्स बनते हैं। एक अन्य प्रकार पहले Neurogammon में उपयोग किए गए हस्त-निर्मित फीचर्स को कोड करता है, जो मानव विशेषज्ञों द्वारा उपयोग की जाने वाली मानक अवधारणाओं को एन्कोड करते हैं जैसे "उन्नत लंगर," "नाकाबंदी ताकत," "घर बोर्ड ताकत," और एक "ब्लॉट" (एकल चेकर) के हिट होने की संभावना। छिपी परत में छिपे हुए न्यूरॉन्स होते हैं, बाद के संस्करणों में अधिक होते हैं। आउटपुट परत में 4 न्यूरॉन्स होते हैं, जो नेटवर्क के अनुमान को दर्शाते हैं कि वर्तमान बोर्ड किस ओर ले जाएगा: सफेद सामान्य जीत, सफेद गैमन जीत, काला सामान्य जीत, काला गैमन जीत। बैकगैमन जीत इतनी दुर्लभ है कि टेसauro ने इसे प्रस्तुत नहीं करने का विकल्प चुना।
प्रत्येक मोड़ के बाद, सीखने का एल्गोरिथ्म प्रत्येक वज़न को नियम के अनुसार अपडेट करता है: w_{t+1} - w_t = alpha (Y_{t+1} - Y_t) sum_{k=1}^{t} lambda^{t-k} grad_w Y_k, जहां alpha सीखने की दर है, Y_t मोड़ t पर मूल्यांकन है, और lambda विक्षय पैरामीटर है। यह पाया गया कि छोटा lambda चुनना लगभग समान रूप से अच्छा प्रदर्शन देता है, और बड़ा lambda प्रदर्शन को खराब करता है। इसके कारण, 1992 के बाद, TD-Gammon को lambda = 0 के साथ प्रशिक्षित किया गया, जो मानक TD-सीखने में परिवर्तित हो गया, जिससे कंप्यूट की गणना 2 के कारक से बच गई।
विकास इतिहास
संस्करण 1.0 ने सरल 1-प्लाई खोज का उपयोग किया: प्रत्येक अगली चाल को तंत्रिका नेटवर्क द्वारा स्कोर किया जाता है, और उच्चतम स्कोरिंग चाल का चयन किया जाता है। संस्करण 2.0 और 2.1 ने 2-प्लाई खोज का उपयोग किया: पहले कम संभावित चालों को हटाने के लिए 1-प्लाई विश्लेषण ("आगे छंटाई"), फिर केवल संभावित चालों के लिए 2-प्लाई मिनिमैक्स विश्लेषण, प्रतिद्वंद्वी के 21 संभावित पासा रोल में से प्रत्येक द्वारा संभावना-भारित सर्वोत्तम चाल का चयन (गैर-डबल को डबल से दोगुना भार देना)। संस्करण 3.0 और 3.1 ने 3-प्लाई खोज का उपयोग किया, जिसमें 21 के बजाय 21^2 = 441 संभावित पासा रोल का उपयोग किया गया। अंतिम संस्करण, 3.1, विशेष रूप से 1998 AAAI हॉल ऑफ चैंपियंस में मैल्कम डेविस के खिलाफ एक प्रदर्शनी मैच के लिए प्रशिक्षित किया गया था। यह -8 अंकों पर हार गया, मुख्य रूप से एक गलती के कारण, जहां TD-Gammon ने डबल करने का विकल्प चुना और -32 अंकों पर गैमन हो गया।
प्रयोग और प्रशिक्षण के चरण
पिछले तंत्रिका-नेटवर्क बैकगैमन प्रोग्राम जैसे Neurogammon (जिसे टेसauro द्वारा भी लिखा गया था) के विपरीत, जहां एक विशेषज्ञ ने प्रत्येक स्थिति का "सही" मूल्यांकन प्रदान करके प्रोग्राम को प्रशिक्षित किया, TD-Gammon को पहले "ज्ञान-मुक्त" प्रोग्राम किया गया था। प्रारंभिक प्रयोग में, केवल कच्चे बोर्ड एन्कोडिंग के साथ और कोई मानव-डिज़ाइन किए गए फीचर नहीं, TD-Gammon Neurogammon के तुलनीय खेल के स्तर तक पहुंच गया: एक मध्यवर्ती-स्तर के मानव बैकगैमन खिलाड़ी का।
यद्यपि TD-Gammon ने अपने दम पर insightful फीचर्स खोजे, टेसauro ने सोचा कि क्या Neurogammon की तरह हस्त-डिज़ाइन किए गए फीचर्स का उपयोग करके इसका खेल सुधारा जा सकता है। वास्तव में, विशेषज्ञ-डिज़ाइन किए गए फीचर्स के साथ आत्म-प्रशिक्षित TD-Gammon जल्द ही सभी पिछले कंप्यूटर बैकगैमन प्रोग्राम से आगे निकल गया। यह तीन-परत तंत्रिका नेटवर्क का उपयोग करके लगभग 1,500,000 खेलों (आत्म-खेल) के बाद सुधारना बंद कर दिया, जिसमें विशेषज्ञ-डिज़ाइन किए गए फीचर्स को एन्कोड करने वाले 198 इनपुट यूनिट, 80 छिपे हुए यूनिट, और जीतने की भविष्यवाणी की संभावना का प्रतिनिधित्व करने वाला एक आउटपुट यूनिट था।
बैकगैमन सिद्धांत में प्रगति
TD-Gammon का विशेष रूप से आत्म-खेल (अनुकरण सीखने के बजाय) के माध्यम से प्रशिक्षण ने इसे उन रणनीतियों की खोज करने में सक्षम बनाया जिन्हें मनुष्यों ने पहले नहीं माना था या गलती से खारिज कर दिया था। अपरंपरागत रणनीतियों के साथ इसकी सफलता का बैकगैमन समुदाय पर महत्वपूर्ण प्रभाव पड़ा। 1991 के अंत में, बिल रॉबर्टी, पॉल मैग्रील और मैल्कम डेविस को TD-Gammon (संस्करण 1.0) के खिलाफ खेलने के लिए आमंत्रित किया गया था। कुल 51 खेल खेले गए, जिसमें TD-Gammon -0.25 ppg पर हार गया। रॉबर्टी ने पाया कि TD-Gammon एक मजबूत मानव खिलाड़ी के स्तर पर था, और इसकी अपरंपरागत चालों को बाद में विशेषज्ञों द्वारा अपनाया गया, जिससे शुरुआती रणनीति की समझ बदल गई।
विरासत और प्रभाव
TD-Gammon को व्यापक रूप से Machine learning और Artificial intelligence में एक मील का पत्थर माना जाता है, जो दर्शाता है कि एक तंत्रिका नेटवर्क आत्म-खेल और अस्थायी-अंतर सीखने के माध्यम से जटिल रणनीतिक खेल सीख सकता है। इसकी सफलता ने सुदृढीकरण सीखने में बाद के काम को प्रेरित किया, जिसमें गहरे Q-नेटवर्क और AlphaGo का विकास शामिल है। प्रोग्राम की नई रणनीतियों की खोज करने की क्षमता जो मनुष्यों से छूट गई थी, ने गेम खेलने में मानव अंतर्ज्ञान से अधिक तंत्रिका नेटवर्क की क्षमता को उजागर किया, और यह एआई अनुसंधान के इतिहास में एक क्लासिक उदाहरण बना हुआ है।