Solving chess
ચેસને ઉકેલવામાં ચેસની રમત માટે શ્રેષ્ઠ વ્યૂહરચના શોધવાનો સમાવેશ થાય છે; એટલે કે, જેના દ્વારા ખેલાડીઓમાંથી એક (સફેદ અથવા કાળો) હંમેશા જીત માટે દબાણ કરી શકે છે, અથવા કાં તો ડ્રો માટે દબાણ કરી શકે છે (ઉકેલાયેલી રમત જુઓ). તે વધુ સામાન્ય રીતે ચેસ જેવી રમતો હલ કરવા સાથે પણ સંબંધિત છે (એટલે કે. સંપૂર્ણ માહિતીની સંયુક્ત રમતો) જેમ કે કેપાબ્લાન્કા ચેસ અને અનંત ચેસ. નબળા અર્થમાં, શતરંજને ઉકેલવું એ સાબિત કરવા માટે સંદર્ભિત કરી શકે છે કે ત્રણ સંભવિત પરિણામોમાંથી કયું એક (સફેદ જીત; કાળી જીત; ડ્રો) બે સંપૂર્ણ ખેલાડીઓનું પરિણામ છે, જરૂરી રીતે શ્રેષ્ઠ વ્યૂહરચનાને જ છતી કર્યા વિના (પરોક્ષ પુરાવા જુઓ). બંનેમાંથી કોઈ પણ ઇન્દ્રિયોમાં ચેસ માટે કોઈ સંપૂર્ણ ઉકેલ જાણી શકાયો નથી, ન તો એવી અપેક્ષા રાખવામાં આવે છે કે નજીકના ભવિષ્યમાં (જો ક્યારેય હોય તો) ચેસનો ઉકેલ આવી જશે. કમ્પ્યુટિંગ શક્તિની વર્તમાન ઘાતાંકીય વૃદ્ધિ લાંબા સમય સુધી ચાલુ રહેશે કે કેમ તે અંગે મતભેદ છે કે કેમ તે એક દિવસ તેને "બ્રુટ ફોર્સ" દ્વારા ઉકેલવાની મંજૂરી આપે છે, એટલે કે. તમામ શક્યતાઓ ચકાસીને. આજ સુધીની પ્રગતિ અત્યંત મર્યાદિત છે; ત્યાં નાની સંખ્યામાં ટુકડાઓ (સાત સુધી) સાથે સંપૂર્ણ અંતિમ રમતના ટેબલબેઝ છે, અને કેટલાક ચેસના પ્રકારોને ઓછામાં ઓછા નબળા રીતે ઉકેલવામાં આવ્યા છે. રમત-વૃક્ષની જટિલતા અને ચેસની રાજ્ય-અવકાશ જટિલતાના ગણતરી કરેલ અંદાજો અસ્તિત્વમાં છે જે રમતને ઉકેલવા માટે જરૂરી હોઈ શકે તેવા કોમ્પ્યુટેશનલ પ્રયાસોનું વિહંગાવલોકન પ્રદાન કરે છે. આંશિક પરિણામો એન્ડગેમ ટેબલબેઝ એન્ડગેમ ટેબલબેઝ એ કોમ્પ્યુટરાઈઝ્ડ ડેટાબેઝ છે જેમાં બોર્ડ પર બાકી રહેલા નાના ટુકડાઓ સાથે સ્થિતિનું પૂર્વગણતરી કરેલ સંપૂર્ણ વિશ્લેષણ હોય છે. ટેબલબેઝે ચેસને મર્યાદિત પ્રમાણમાં હલ કરી છે, જેમાં સાતથી વધુ ટુકડાઓ અથવા પ્યાદાઓ (બે રાજાઓ સહિત) સાથે તમામ બિન-તુચ્છ અંતિમ રમતો સહિત સંખ્યાબંધ અંતિમ રમતોમાં સંપૂર્ણ રમત નક્કી કરવામાં આવે છે. સાત-પીસ એન્ડગેમ ટેબલબેઝ વિકસાવવાનું એક પરિણામ એ છે કે ચેસના ઘણા રસપ્રદ સૈદ્ધાંતિક અંત મળી આવ્યા છે. સૌથી લાંબુ સાત ટુકડાનું ઉદાહરણ ગાય હાવર્થ દ્વારા લોમોનોસોવ ટેબલબેઝમાં શોધાયેલ મેટ-ઇન-549 સ્થિતિ છે, જે 50-ચાલના નિયમની અવગણના કરે છે. આવી સ્થિતિ કોઈપણ માનવની ઉકેલવાની ક્ષમતાની બહાર છે, અને કોઈ પણ ચેસ એન્જિન તેને ટેબલબેઝની પહોંચ વિના યોગ્ય રીતે વગાડતું નથી, જેને શરૂઆતમાં (2014 માં) 140 ટીબી સંગ્રહસ્થાન અને સુપરકોમ્પ્યુટરના ઉપયોગની જરૂર હતી પરંતુ બાદમાં સિઝીજી ટેબલબેઝ દ્વારા ઘટાડીને 18.4 ટીબી કરવામાં આવી હતી. જાન્યુઆરી 2023 સુધીમાં, આઠ ટુકડાના ટેબલબેઝ (50 ચાલના નિયમને પણ અવગણીને) માટે સૌથી લાંબો જાણીતો બળજબરીથી સમાગમ ક્રમ 584 ચાલનો હતો. આની શોધ 2022ના મધ્યમાં વિકાસકર્તા, કોમ્પ્યુટર ચેસ ઉત્સાહી અને ભૌતિકશાસ્ત્રી માર્ક બોર્ઝુત્સ્કી દ્વારા કરવામાં આવી હતી. આઠ ટુકડાનો ટેબલબેઝ હાલમાં અપૂર્ણ છે, જોકે, તે ખાતરીપૂર્વક નથી કે આઠ ટુકડાનો ટેબલબેઝ માટે આ સંપૂર્ણ મર્યાદા છે. ચેસના પ્રકારો શેનોન દ્વારા સૌપ્રથમ વર્ણવેલ એક પ્રકાર ચેસના રમત-સૈદ્ધાંતિક મૂલ્ય વિશે દલીલ પૂરી પાડે છેઃ તે "પાસ" ની હિલચાલને મંજૂરી આપવાની દરખાસ્ત કરે છે. આ પ્રકારમાં, વ્યૂહરચના ચોરીની દલીલ સાથે તે સાબિત થઈ શકે છે કે પ્રથમ ખેલાડી ઓછામાં ઓછો ડ્રો ધરાવે છેઃ જો પ્રથમ ખેલાડીની જીતવાની ચાલ હોય, તો તેને રમવા દો, નહીં તો પાસ કરો. બોર્ડની મિરર ઇમેજ સમપ્રમાણતાને કારણે બીજા ખેલાડીને હવે સમાન પરિસ્થિતિનો સામનો કરવો પડે છેઃ જો પ્રથમ ખેલાડી પાસે પ્રથમ વખતમાં કોઈ વિજેતા ચાલ ન હોય, તો બીજા ખેલાડી પાસે હવે કોઈ ચાલ નથી. તેથી, બીજો ખેલાડી શ્રેષ્ઠ રીતે ડ્રો કરી શકે છે, અને પ્રથમ ખેલાડી ઓછામાં ઓછો ડ્રો કરી શકે છે, તેથી એક સંપૂર્ણ રમત પ્રથમ ખેલાડીને જીતવા અથવા ડ્રોમાં પરિણમે છે. ચેસ કરતાં સરળ હોય તેવા ચેસના કેટલાક પ્રકારો હલ કરવામાં આવ્યા છે. મહારાજા અને સિપાહીઓમાં કાળા માટે જીતવાની વ્યૂહરચના સરળતાથી યાદ કરી શકાય છે. 5×5 ગાર્ડનરની મિનિચેસના પ્રકારને ડ્રો તરીકે નબળી રીતે ઉકેલવામાં આવ્યો છે. ચેસ હારવું એ 8x8 બોર્ડ પર રમવામાં આવે છે, તેમ છતાં તેનો ફરજિયાત કેપ્ચર નિયમ તેની જટિલતાને મોટા પ્રમાણમાં મર્યાદિત કરે છે, અને કોમ્પ્યુટેશનલ વિશ્લેષણ સફેદ માટે જીત તરીકે આ પ્રકારને નબળી રીતે ઉકેલવામાં સફળ રહ્યું. વ્યક્તિગત, વિશિષ્ટ, ચેસ જેવી રમતો હલ કરવાની સંભાવના વધુ મુશ્કેલ બની જાય છે કારણ કે મોટા ચેસ પ્રકારો અને અનંત ચેસ જેવા બોર્ડ-કદમાં વધારો કરવામાં આવે છે. 1950માં ચેસ ઇન્ફર્મેશન થિયરીસ્ટ ક્લાઉડ શેનોનની જટિલતાએ એક સંપૂર્ણ રમત રમવા માટેની સૈદ્ધાંતિક પ્રક્રિયાની રૂપરેખા આપી હતી (એટલે કે. ચેસ હલ કરવું): શેનને પછી અંદાજ મૂક્યો કે તે પ્રક્રિયા અનુસાર ચેસ હલ કરવા માટે લગભગ 10 સંભવિત રમતની વિવિધતાઓની સરખામણી કરવાની જરૂર પડશે, અથવા લગભગ 10 સંભવિત બોર્ડ સ્થાનો (હાલમાં લગભગ 5x10 તરીકે ઓળખાય છે) માંથી દરેક માટે શ્રેષ્ઠ ચાલ દર્શાવતો "શબ્દકોશ" હોવો જરૂરી છે. જોકે, ચેસને ઉકેલવા માટે જરૂરી ગાણિતિક કામગીરીની સંખ્યા, ચેસના સમગ્ર રમત-વૃક્ષના ઉત્પાદન માટે જરૂરી કામગીરીની સંખ્યા કરતાં નોંધપાત્ર રીતે અલગ હોઈ શકે છે. ખાસ કરીને, જો સફેદને બળજબરીથી જીત મળે છે, તો રમત-વૃક્ષના માત્ર એક ઉપગણને ખાતરી કરવા માટે મૂલ્યાંકનની જરૂર પડશે કે બળજબરીથી જીત અસ્તિત્વમાં છે (એટલે કે. બ્લેક તરફથી કોઈ ખંડન વિના). વધુમાં, ચેસની જટિલતા માટે શેનોનની ગણતરી રમતની સરેરાશ લંબાઈ 40 ચાલ ધારે છે, પરંતુ એમ કહેવા માટે કોઈ ગાણિતિક આધાર નથી કે બંને પક્ષો દ્વારા બળજબરીથી જીતનો આ રમતની લંબાઈ સાથે કોઈ સંબંધ હશે. ખરેખર, કેટલીક કુશળતાપૂર્વક રમાયેલી રમતો (ગ્રાન્ડમાસ્ટર-સ્તરની રમત) 16 ચાલ જેટલી ટૂંકી રહી છે. આ કારણોસર, ગણિતશાસ્ત્રીઓ અને રમત સિદ્ધાંતવાદીઓ સ્પષ્ટપણે જણાવવા માટે અનિચ્છા ધરાવે છે કે ચેસ હલ કરવી એ એક જટિલ સમસ્યા છે. ચેસ ક્યારે અને ક્યારે હલ થશે તેની આગાહીઓ 1950 માં, શેનને 10 ની રમત વૃક્ષની જટિલતા અને એક મેગાહર્ટ્ઝ પર કાર્યરત કમ્પ્યુટર (તે સમયે એક મોટો વિસ્તારઃ 1951 માં રજૂ કરાયેલ UNIVAC 1 પ્રતિ સેકન્ડ ~ 2000 કામગીરી અથવા 2 કિલોહર્ટ્ઝ કરી શકે છે) ના આધારે ગણતરી કરી હતી, જે 1 માઇક્રોસેકન્ડમાં ટર્મિનલ નોડનું મૂલ્યાંકન કરી શકે છે, જે તેની પ્રથમ ચાલ કરવા માટે 10 વર્ષ લેશે. તકનીકી પ્રગતિને મંજૂરી આપવી પણ, વ્યવહારુ સમયમર્યાદામાં ચેસને ઉકેલવી એ કોઈપણ કલ્પનીય તકનીકની બહાર લાગે છે. બર્કલે ખાતે યુનિવર્સિટી ઓફ કેલિફોર્નિયામાં ગણિત અને બાયોફિઝિક્સના પ્રોફેસર હંસ-જોઆચિમ બ્રેમરમેને 1965ના એક પેપરમાં દલીલ કરી હતી કે "ભવિષ્યના કોઈપણ સંભવિત કમ્પ્યુટર સાધનોની ઝડપ, યાદશક્તિ અને પ્રક્રિયા કરવાની ક્ષમતા ચોક્કસ ભૌતિક અવરોધો દ્વારા મર્યાદિત છેઃ પ્રકાશ અવરોધ, ક્વોન્ટમ અવરોધ અને થર્મોડાયનેમિકલ અવરોધ. આ મર્યાદાઓ સૂચવે છે, ઉદાહરણ તરીકે, કોઈ પણ કમ્પ્યુટર, ભલે ગમે તે રીતે બાંધવામાં આવ્યું હોય, તે ક્યારેય ચેસની રમતના સંભવિત ચાલ ક્રમના સમગ્ર વૃક્ષની તપાસ કરી શકશે નહીં. તેમ છતાં, બ્રેમરમેને એવી શક્યતાને અટકાવી ન હતી કે કમ્પ્યુટર એક દિવસ ચેસને ઉકેલવામાં સક્ષમ હશે. તેમણે લખ્યું, "કમ્પ્યુટરને સંપૂર્ણ અથવા લગભગ સંપૂર્ણ રમત રમવા માટે, કાં તો રમતનું સંપૂર્ણ વિશ્લેષણ કરવું જરૂરી છે. અથવા રમતનું અંદાજિત રીતે વિશ્લેષણ કરવું અને તેને મર્યાદિત માત્રામાં વૃક્ષ શોધ સાથે જોડવું જરૂરી છે. જો કે, આવા સંશોધનાત્મક પ્રોગ્રામિંગની સૈદ્ધાંતિક સમજણ હજુ પણ ખૂબ જ જરૂરી છે ". તાજેતરની વૈજ્ઞાનિક પ્રગતિઓએ આ મૂલ્યાંકનોમાં નોંધપાત્ર ફેરફાર કર્યો નથી. ચેકર્સની રમત 2007 માં (નબળી રીતે) હલ કરવામાં આવી હતી, પરંતુ તે ચેસમાં સ્થાનોની સંખ્યાના આશરે વર્ગમૂળ ધરાવે છે. આ પ્રયાસની આગેવાની કરનાર વૈજ્ઞાનિક જોનાથન શેફરે જણાવ્યું હતું કે ચેસ હલ કરવાનો પ્રયાસ કરવામાં આવે તે પહેલાં ક્વોન્ટમ કમ્પ્યુટિંગ જેવી સફળતાની જરૂર પડશે, પરંતુ તેઓ આ શક્યતાને નકારી કાઢતા નથી, એમ કહીને કે ચેકર્સને હલ કરવાના તેમના 16 વર્ષના પ્રયાસમાંથી તેમણે જે એક વસ્તુ શીખી છે તે છે "ટેકનોલોજીમાં પ્રગતિને ક્યારેય ઓછો અંદાજ ન આપવો". શેનોન નંબર (ચેસની રમત-વૃક્ષની જટિલતાની નીચલી મર્યાદાની ગણતરી) ચેસ સંદર્ભોમાં પ્રથમ-ચાલનો ફાયદો બાહ્ય કડીઓ "અનંત ચેસ, પીબીએસ અનંત શ્રેણી" અનંત ચેસ, પીબીએસ અનંત શ્રેણી પણ જુઓ. ચેસ સિદ્ધાંત