चेकर्स प्रोग्राम कंप्यूटर सॉफ्टवेयर हैं जो बोर्ड गेम चेकर्स खेलने के लिए डिज़ाइन किए गए हैं, जिसे ड्राफ्ट्स के रूप में भी जाना जाता है। ये प्रोग्राम स्थितियों का मूल्यांकन करने, इष्टतम चालों की खोज करने और मानव खिलाड़ियों या अन्य कंप्यूटरों के खिलाफ प्रतिस्पर्धा करने के लिए एल्गोरिथमिक तकनीकों का उपयोग करते हैं। सबसे प्रमुख चेकर्स प्रोग्राम चिनूक है, जिसे अल्बर्टा विश्वविद्यालय में विकसित किया गया था (हालांकि परियोजना वहां आधारित थी, टोरंटो में नहीं), जोनाथन शेफ़र के नेतृत्व में एक टीम द्वारा, जिसने प्रतिस्पर्धात्मक खेल और गेम-सॉल्विंग दोनों में ऐतिहासिक मील के पत्थर हासिल किए।
चिनूक को 1989 और 2007 के बीच अल्बर्टा विश्वविद्यालय की एक टीम द्वारा विकसित किया गया था, जिसमें जोनाथन शेफ़र, रॉब लेक, पॉल लू, मार्टिन ब्रायंट और नॉर्मन ट्रेलोर शामिल थे। मशीन लर्निंग पर निर्भर आधुनिक दृष्टिकोणों के विपरीत, चिनूक का ज्ञान पूरी तरह से इसके निर्माताओं द्वारा हाथ से कोडित किया गया था, जिसमें खोज एल्गोरिदम और मूल्यांकन कार्यों जैसी पारंपरिक कृत्रिम बुद्धिमत्ता तकनीकों का उपयोग किया गया था। यह अंतर नियम-आधारित प्रणालियों से डेटा-संचालित तरीकों तक एआई के विकास को उजागर करता है।
मैन बनाम मशीन विश्व चैंपियन
1990 में, चिनूक ने यूएस नेशनल्स में मैरियन टिन्सले के बाद दूसरा स्थान हासिल करके मानव विश्व चैम्पियनशिप में प्रतिस्पर्धा करने का अधिकार अर्जित किया। प्रारंभ में, अमेरिकन चेकर्स फेडरेशन और इंग्लिश ड्राफ्ट्स एसोसिएशन ने मानव चैंपियनशिप में कंप्यूटर की भागीदारी का विरोध किया। जब टिन्सले ने विरोध में अपनी उपाधि से इस्तीफा दे दिया, तो इन संगठनों ने नया खिताब मैन बनाम मशीन विश्व चैम्पियनशिप बनाया, जिससे प्रतियोगिता आगे बढ़ सकी। टिन्सले ने पहला मैच चार जीत, दो हार और 33 ड्रॉ के साथ जीता।
1994 के रीमैच के परिणामस्वरूप चिनूक को छह ड्रॉ खेलों के बाद मैन-मशीन विश्व चैंपियन घोषित किया गया, क्योंकि टिन्सले अग्नाशय के कैंसर के कारण पीछे हट गए थे। इसने चिनूक को मनुष्यों के खिलाफ विश्व चैम्पियनशिप खिताब जीतने वाला पहला कंप्यूटर प्रोग्राम बना दिया, हालांकि इसने कभी टिन्सले को नहीं हराया, जो अपने निकटतम साथियों से भी काफी बेहतर थे। 1995 में, चिनूक ने डॉन लैफ़र्टी के खिलाफ 32-गेम के मैच में अपना खिताब बचाया, 31 ड्रॉ के साथ 1-0 से जीत हासिल की। इसके बाद, शेफ़र ने प्रतिस्पर्धात्मक खेल रोकने और पूरी तरह से चेकर्स को हल करने पर ध्यान केंद्रित करने का फैसला किया।
एल्गोरिदम
चिनूक के एल्गोरिदम में चार मुख्य घटक शामिल थे: ग्रैंडमास्टर खेलों से चालों वाली एक ओपनिंग बुक, संभावित चालों की खोज के लिए एक गहरी खोज एल्गोरिदम, एक चाल मूल्यांकन फ़ंक्शन, और आठ या उससे कम टुकड़ों वाली सभी स्थितियों को कवर करने वाला एक एंड-गेम डेटाबेस। मूल्यांकन फ़ंक्शन एक रैखिक हस्तनिर्मित फ़ंक्शन था जो टुकड़ों की संख्या, राजाओं की संख्या, फंसे हुए राजा, बारी और भागते हुए चेकर्स (बिना बाधा के राजा बनने के रास्ते वाले टुकड़े) जैसी विशेषताओं पर विचार करता था। सभी ज्ञान निर्माताओं द्वारा सीखे जाने के बजाय प्रोग्राम किया गया था, जो बाद के एआई सिस्टम जैसे डीपमाइंड के दृष्टिकोणों के विपरीत है।
समयरेखा और चेकर्स को हल करना
चिनूक के विकास में प्रमुख मील के पत्थर शामिल हैं: 1997, जब शेफ़र ने पुस्तक "वन जंप अहेड: चैलेंजिंग ह्यूमन सुप्रीमेसी इन चेकर्स" प्रकाशित की (नवंबर 2008 में अद्यतन); 24 मई, 2003, जब 10-टुकड़ा डेटाबेस (प्रति पक्ष 5 टुकड़े) पूरा हुआ; और 2 अगस्त, 2004, जब ओपनिंग "व्हाइट डॉक्टर" (10-14 22-18 12-16) को ड्रॉ साबित किया गया। आगे की ओपनिंग 18 जनवरी, 2006 (09-13 21-17 05-09) और 18 अप्रैल, 2006 (09-13 22-17 13-22) को ड्रॉ साबित हुईं।
10 मार्च, 2007 को, शेफ़र ने ACM SIGCSE सम्मेलन में घोषणा की कि 3-5 महीनों के भीतर एक अंतिम समाधान की उम्मीद है। 19 जुलाई, 2007 को, जर्नल साइंस ने "चेकर्स इज़ सॉल्व्ड" प्रकाशित किया, जिसमें साबित हुआ कि सही खेल के साथ, सबसे अच्छा परिणाम एक ड्रॉ है। इसने चेकर्स को पूरी तरह से हल किया जाने वाला पहला प्रमुख बोर्ड गेम बना दिया, जो सरल खेलों पर पहले के काम के बाद आया। अपने प्रतिस्पर्धात्मक शिखर पर, चिनूक को 2814 एलो रेट किया गया था।
विरासत
चिनूक की सफलता ने शास्त्रीय एआई तकनीकों की शक्ति का प्रदर्शन किया, जिसमें गहरी खोज और हस्तनिर्मित मूल्यांकन शामिल है, डीप लर्निंग के उदय से पहले। चेकर्स का इसका समाधान गेम एआई में एक ऐतिहासिक उपलब्धि बना हुआ है, जो शतरंज कंप्यूटर जैसे डीप ब्लू के बराबर है। जबकि आधुनिक चेकर्स प्रोग्राम तंत्रिका नेटवर्क का उपयोग कर सकते हैं, चिनूक के दृष्टिकोण ने गेम थ्योरी और कॉम्बिनेटोरियल गेम सॉल्विंग में बाद के शोध को प्रभावित किया, और इसके तरीकों का अध्ययन अभी भी कार्नेगी मेलन विश्वविद्यालय और MIT CSAIL जैसे संस्थानों में एआई पाठ्यक्रमों में किया जाता है।