Game tree
સંયુક્ત રમત સિદ્ધાંતના સંદર્ભમાં, જે સામાન્ય રીતે સંપૂર્ણ માહિતી સાથે ક્રમિક રમતોનો અભ્યાસ કરે છે, રમત વૃક્ષ એ એક આલેખ છે જે આવી રમતની અંદરની તમામ સંભવિત રમત સ્થિતિઓનું પ્રતિનિધિત્વ કરે છે. આવી રમતોમાં ચેસ, ચેકર્સ, ગો અને ટિક-ટેક-ટો જેવી જાણીતી રમતો સામેલ છે. આનો ઉપયોગ રમતની જટિલતાને માપવા માટે થઈ શકે છે, કારણ કે તે રમતની તમામ સંભવિત રીતોને રજૂ કરે છે. ચેસ જેવી જટિલ રમતોના મોટા રમત વૃક્ષોને કારણે, આ વર્ગની રમતો રમવા માટે રચાયેલ અલ્ગોરિધમ્સ આંશિક રમત વૃક્ષોનો ઉપયોગ કરશે, જે આધુનિક કમ્પ્યુટર્સ પર ગણતરીને શક્ય બનાવે છે. રમતના વૃક્ષોને ઉકેલવા માટે વિવિધ પદ્ધતિઓ અસ્તિત્વમાં છે. જો સંપૂર્ણ રમત વૃક્ષ પેદા કરી શકાય છે, તો નિર્ધારિત અલ્ગોરિધમનો ઉપયોગ કરી શકાય છે, જેમ કે પછાત ઇન્ડક્શન અથવા પ્રતિગામી વિશ્લેષણ. રેન્ડમાઇઝ્ડ એલ્ગોરિધમ્સ અને એમ. સી. ટી. એસ. જેવા મિનમેક્સ એલ્ગોરિધમ્સનો ઉપયોગ એવા કિસ્સાઓમાં થઈ શકે છે જ્યાં સંપૂર્ણ ગેમ ટ્રી શક્ય નથી. રમતના વૃક્ષને વધુ સારી રીતે સમજવા માટે, તેને પ્રતિકૂળ રમતોનું વિશ્લેષણ કરવાની તકનીક તરીકે વિચારી શકાય છે, જે રમત જીતવા માટે ખેલાડીની ક્રિયાઓ નક્કી કરે છે. રમત સિદ્ધાંતમાં, રમત વૃક્ષ એ એક નિર્દેશિત આલેખ છે, જેના નોડ્સ રમતમાં સ્થિતિ છે (દા. ત., બોર્ડ ગેમમાં ટુકડાઓની ગોઠવણી) અને જેની ધાર ચાલ છે (દા. ત., બોર્ડ પર એક સ્થાનથી બીજામાં ટુકડાઓ ખસેડવા). રમત માટેનું સંપૂર્ણ રમત વૃક્ષ એ રમત વૃક્ષ છે જે પ્રારંભિક સ્થિતિથી શરૂ થાય છે અને દરેક સ્થિતિમાંથી તમામ સંભવિત ચાલ ધરાવે છે; સંપૂર્ણ વૃક્ષ એ જ વૃક્ષ છે જે વ્યાપક સ્વરૂપની રમતની રજૂઆતમાંથી મેળવવામાં આવે છે. વધુ ચોક્કસ બનવા માટે, રમત સિદ્ધાંતમાં રમત માટે સંપૂર્ણ રમત એક ધોરણ છે. જે ઘણા મહત્વપૂર્ણ પાસાઓને સ્પષ્ટ રીતે વ્યક્ત કરી શકે છે. ઉદાહરણ તરીકે, હિતધારકો જે પગલાં લઈ શકે છે તેનો ક્રમ, દરેક નિર્ણયના તબક્કે તેમની પસંદગીઓ, જ્યારે દરેક હિતધારક નિર્ણય લે છે ત્યારે અન્ય હિતધારકો દ્વારા લેવામાં આવતી ક્રિયાઓ વિશેની માહિતી અને તમામ સંભવિત રમત પરિણામોના ફાયદા. આકૃતિ ટિક-ટેક-ટો માટે રમતના વૃક્ષમાં પ્રથમ બે સ્તરો અથવા પ્લીસ દર્શાવે છે. સ્થાનોના પરિભ્રમણ અને પ્રતિબિંબ સમાન હોય છે, તેથી પ્રથમ ખેલાડી પાસે ચાલની ત્રણ પસંદગીઓ હોય છેઃ મધ્યમાં, ધાર પર અથવા ખૂણામાં. જો પ્રથમ ખેલાડી મધ્યમાં રમ્યો હોય તો બીજા ખેલાડી પાસે જવાબ માટે બે પસંદગીઓ હોય છે, અન્યથા પાંચ પસંદગીઓ હોય છે. અને તેથી પર. સંપૂર્ણ રમત વૃક્ષમાં પર્ણ ગાંઠોની સંખ્યા એ રમત રમી શકાય તેવી સંભવિત વિવિધ રીતોની સંખ્યા છે. ઉદાહરણ તરીકે, ટિક-ટેક-ટો માટેના રમત વૃક્ષમાં 255,168 પર્ણ ગાંઠો છે. કૃત્રિમ બુદ્ધિમાં રમત વૃક્ષો મહત્વપૂર્ણ છે કારણ કે રમતમાં શ્રેષ્ઠ ચાલ પસંદ કરવાની એક રીત એ છે કે વૃક્ષને કાપવા માટે મિનિમેક્સ જેવા નિયમો સાથે જોડાયેલા અસંખ્ય વૃક્ષ શોધ અલ્ગોરિધમ્સમાંથી કોઈપણનો ઉપયોગ કરીને રમત વૃક્ષને શોધવું. ટિક-ટેક-ટો માટેનું રમત વૃક્ષ સરળતાથી શોધી શકાય છે, પરંતુ ચેસ જેવી મોટી રમતો માટે સંપૂર્ણ રમત વૃક્ષો શોધવા માટે ખૂબ મોટા છે. તેના બદલે, ચેસ રમવાનો કાર્યક્રમ આંશિક રમતના વૃક્ષને શોધે છેઃ સામાન્ય રીતે વર્તમાન સ્થિતિમાંથી તેટલા પ્લે જે તે ઉપલબ્ધ સમયમાં શોધી શકે છે. "પેથોલોજીકલ" રમત વૃક્ષો (જે વ્યવહારમાં ખૂબ જ દુર્લભ લાગે છે) ના કેસ સિવાય, શોધની ઊંડાઈમાં વધારો (એટલે કે, શોધાયેલ પ્લીસની સંખ્યા) સામાન્ય રીતે શ્રેષ્ઠ ચાલ પસંદ કરવાની તકમાં સુધારો કરે છે. બે વ્યક્તિની રમતને વૃક્ષો અથવા વૃક્ષો તરીકે પણ રજૂ કરી શકાય છે. રમત જીતવા માટે પ્રથમ ખેલાડી માટે, બીજા ખેલાડીની તમામ ચાલ માટે જીતવાની ચાલ હોવી આવશ્યક છે. પ્રથમ ખેલાડીની વૈકલ્પિક ચાલનું પ્રતિનિધિત્વ કરવા માટે વિચ્છેદનનો ઉપયોગ કરીને અને બીજા ખેલાડીની તમામ ચાલનું પ્રતિનિધિત્વ કરવા માટે સંયોજનનો ઉપયોગ કરીને આને અને-અથવા વૃક્ષમાં રજૂ કરવામાં આવે છે. સંપૂર્ણ રમત વૃક્ષ સાથે, રમતને "ઉકેલવી" શક્ય છે-એટલે કે, ચાલનો ક્રમ શોધો કે જે પ્રથમ કે બીજો ખેલાડી અનુસરી શકે છે જે તે ખેલાડી માટે શ્રેષ્ઠ સંભવિત પરિણામની બાંયધરી આપશે (સામાન્ય રીતે જીત અથવા ટાઇ). નિર્ધારક અલ્ગોરિધમ (જેને સામાન્ય રીતે પછાત ઇન્ડક્શન અથવા પ્રતિગામી વિશ્લેષણ કહેવામાં આવે છે) ને નીચે પ્રમાણે પુનરાવર્તિત રીતે વર્ણવી શકાય છે. રમતના વૃક્ષની અંતિમ પટ્ટીને રંગ આપો જેથી ખેલાડી 1 માટે તમામ જીત એક રીતે રંગીન હોય (આકૃતિમાં વાદળી), ખેલાડી 2 માટે તમામ જીત બીજી રીતે રંગીન હોય (આકૃતિમાં લાલ), અને તમામ સંબંધો ત્રીજી રીતે રંગીન હોય (આકૃતિમાં ભૂખરા). આગામી પ્લાય અપ જુઓ. જો વર્તમાન ખેલાડીની વિરુદ્ધ રંગનો નોડ અસ્તિત્વમાં હોય, તો તે ખેલાડી માટે પણ આ નોડને રંગ આપો. જો બધા તરત જ નીચલા ગાંઠો એક જ ખેલાડી માટે રંગીન હોય, તો તે જ ખેલાડી માટે પણ આ ગાંઠો રંગ કરો. નહિંતર, આ નોડને ટાઈમાં રંગાવો. દરેક પ્લાય માટે પુનરાવર્તન કરો, જ્યાં સુધી બધા ગાંઠો રંગીન ન થાય ત્યાં સુધી ઉપરની તરફ આગળ વધો. રુટ નોડનો રંગ રમતની પ્રકૃતિ નક્કી કરશે. આ આકૃતિ મનસ્વી રમત માટે રમતનું વૃક્ષ દર્શાવે છે, જે ઉપરોક્ત અલ્ગોરિધમનો ઉપયોગ કરીને રંગીન છે. સામાન્ય રીતે રમત વૃક્ષના ઉપગણનો ઉપયોગ કરીને રમતને ("ઉકેલ" ના આ તકનીકી અર્થમાં) હલ કરવી શક્ય છે, કારણ કે ઘણી રમતોમાં એક જ ખેલાડી માટે વધુ સારી હોય તેવી બીજી ચાલ હોય તો ચાલનું વિશ્લેષણ કરવાની જરૂર નથી (ઉદાહરણ તરીકે આલ્ફા-બીટા કાપણીનો ઉપયોગ ઘણી નિર્ધારિત રમતોમાં થઈ શકે છે). રમતને ઉકેલવા માટે ઉપયોગમાં લઈ શકાય તેવી કોઈપણ સબટ્રીને નિર્ણય વૃક્ષ તરીકે ઓળખવામાં આવે છે, અને વિવિધ આકારોના નિર્ણય વૃક્ષોના કદનો ઉપયોગ રમતની જટિલતાના માપ તરીકે થાય છે. રેન્ડમાઇઝ્ડ એલ્ગોરિધમ્સ વર્ઝન રેન્ડમાઇઝ્ડ એલ્ગોરિધમ્સનો ઉપયોગ રમતના વૃક્ષોને ઉકેલવામાં થઈ શકે છે. આ પ્રકારના અમલીકરણમાં બે મુખ્ય ફાયદા છેઃ ઝડપ અને કાર્યદક્ષતા. જ્યારે રમત વૃક્ષોને ઉકેલવાનું નિર્ધારક સંસ્કરણ કરી શકાય છે, ત્યારે નીચેના રેન્ડમાઇઝ્ડ અલ્ગોરિધમનો અપેક્ષિત રન ટાઇમ હોય છે જો રમત વૃક્ષના દરેક નોડમાં ડિગ્રી 2 હોય. વધુમાં, તે વ્યવહારુ છે કારણ કે રેન્ડમાઇઝ્ડ અલ્ગોરિધમ્સ "દુશ્મનને નિષ્ફળ બનાવવા" માટે સક્ષમ છે, જેનો અર્થ છે કે વિરોધી રમત વૃક્ષને ઉકેલવા માટે ઉપયોગમાં લેવાતા અલ્ગોરિધમને જાણીને રમત વૃક્ષોની પ્રણાલીને હરાવી શકતો નથી કારણ કે ઉકેલવાનો ક્રમ રેન્ડમ છે. નીચે રેન્ડમાઇઝ્ડ ગેમ ટ્રી સોલ્યુશન અલ્ગોરિધમનો અમલ છેઃ ડેફ જીટી _ ઇવેલ _ રેન્ડ (યુ)-> બૂલઃ "જો આ નોડ જીત માટે મૂલ્યાંકન કરે તો સાચું પરત કરે છે, અન્યથા ખોટું" જો <આઇડી2>: વળતર <આઇડી1> અન્યથાઃ રેન્ડમ _ ચિલ્ડ્રન = (જીટી _ ઇવેલ _ રેન્ડ (ચાઇલ્ડ) રેન્ડમ _ ઓર્ડર (<આઇડી3>) માં બાળક માટે જો યુ. ઓ. પી. = = "ઓઆર": કોઈપણ (રેન્ડમ _ ચિલ્ડ્રન) પરત કરો જો યુ. ઓ. પી. = = "એન્ડ": બધા (રેન્ડમ _ ચિલ્ડ્રન) પરત કરો અલ્ગોરિધમ "શોર્ટ-સર્કિટિંગ" ના વિચારનો ઉપયોગ કરે છેઃ જો રુટ નોડને "ઓપરેટર" ગણવામાં આવે, તો એકવાર એક આલ્ફા-બીટા કાપણી વિસ્તૃત ફોર્મ ગેમ શેનોન નંબર ગેમ જટિલતા સંદર્ભો વધુ વાંચન જુડિયા પર્લ, હ્યુરિસ્ટિક્સ, એડિસન-વેસ્લી, 1984 સંયુક્ત રમત સિદ્ધાંત વૃક્ષો (આલેખ સિદ્ધાંત)