Game tree
ஒருங்கிணைந்த விளையாட்டு கோட்பாட்டின் சூழலில், இது பொதுவாக தொடர்ச்சியான விளையாட்டுகளை சரியான தகவல்களுடன் ஆய்வு செய்கிறது, ஒரு விளையாட்டு மரம் என்பது அத்தகைய விளையாட்டிற்குள் சாத்தியமான அனைத்து விளையாட்டு நிலைகளையும் குறிக்கும் ஒரு வரைபடமாகும். இத்தகைய விளையாட்டுகளில் சதுரங்கம், செக்கர்ஸ், கோ மற்றும் டிக்-டாக்-டோ போன்ற நன்கு அறியப்பட்ட விளையாட்டுகள் அடங்கும். இது ஒரு விளையாட்டின் சிக்கலை அளவிட பயன்படுத்தப்படலாம், ஏனெனில் இது ஒரு விளையாட்டின் சாத்தியமான அனைத்து வழிகளையும் குறிக்கிறது. சதுரங்கம் போன்ற சிக்கலான விளையாட்டுகளின் பெரிய விளையாட்டு மரங்கள் காரணமாக, இந்த வகை விளையாட்டுகளை விளையாட வடிவமைக்கப்பட்ட வழிமுறைகள் பகுதி விளையாட்டு மரங்களைப் பயன்படுத்தும், இது நவீன கணினிகளில் கணக்கீட்டை சாத்தியமாக்குகிறது. விளையாட்டு மரங்களைத் தீர்க்க பல்வேறு முறைகள் உள்ளன. ஒரு முழுமையான விளையாட்டு மரத்தை உருவாக்க முடிந்தால், பின்தங்கிய தூண்டல் அல்லது பின்னோக்கிய பகுப்பாய்வு போன்ற ஒரு தீர்மானகரமான வழிமுறையைப் பயன்படுத்தலாம். ஒரு முழுமையான விளையாட்டு மரம் சாத்தியமில்லாத சந்தர்ப்பங்களில் சீரற்ற வழிமுறைகள் மற்றும் எம். சி. டி. எஸ் போன்ற மின்மாக்ஸ் வழிமுறைகளைப் பயன்படுத்தலாம். விளையாட்டு மரத்தைப் புரிந்துகொள்வது விளையாட்டு மரத்தை நன்கு புரிந்துகொள்ள, இது எதிர்மறையான விளையாட்டுகளை பகுப்பாய்வு செய்வதற்கான ஒரு நுட்பமாக கருதப்படலாம், இது விளையாட்டை வெல்ல வீரர் எடுக்கும் செயல்களை தீர்மானிக்கிறது. விளையாட்டு கோட்பாட்டில், ஒரு விளையாட்டு மரம் என்பது ஒரு திசையில் உள்ள வரைபடமாகும், அதன் முனைகள் ஒரு விளையாட்டில் நிலைகள் (எ. கா., ஒரு பலகை விளையாட்டில் துண்டுகளின் ஏற்பாடு) மற்றும் அதன் விளிம்புகள் நகர்வுகள் (எ. கா., ஒரு பலகையில் ஒரு நிலையில் இருந்து துண்டுகளை நகர்த்துவது மற்றொரு). ஒரு விளையாட்டின் முழுமையான விளையாட்டு மரம் ஆரம்ப நிலையில் தொடங்கி ஒவ்வொரு நிலையிலிருந்தும் சாத்தியமான அனைத்து நகர்வுகளையும் கொண்ட விளையாட்டு மரம் ஆகும்; முழுமையான மரம் விரிவான வடிவ விளையாட்டு பிரதிநிதித்துவத்திலிருந்து பெறப்பட்ட அதே மரம். இன்னும் குறிப்பாகச் சொல்வதானால், விளையாட்டுக் கோட்பாட்டில் முழுமையான விளையாட்டு என்பது விளையாட்டுக்கான ஒரு நெறிமுறையாகும். இது பல முக்கியமான அம்சங்களை தெளிவாக வெளிப்படுத்த முடியும். எடுத்துக்காட்டாக, பங்குதாரர்கள் எடுக்கக்கூடிய நடவடிக்கைகளின் வரிசை, ஒவ்வொரு முடிவு கட்டத்திலும் அவர்களின் தேர்வுகள், ஒவ்வொரு பங்குதாரரும் ஒரு முடிவை எடுக்கும்போது மற்ற பங்குதாரர்கள் எடுக்கும் நடவடிக்கைகள் பற்றிய தகவல்கள் மற்றும் சாத்தியமான அனைத்து விளையாட்டு முடிவுகளின் நன்மைகள். இந்த வரைபடம் டிக்-டாக்-டோவிற்கான விளையாட்டு மரத்தில் முதல் இரண்டு நிலைகளைக் காட்டுகிறது. நிலைகளின் சுழற்சிகள் மற்றும் பிரதிபலிப்புகள் சமமானவை, எனவே முதல் வீரருக்கு மூன்று நகர்வுகள் உள்ளனஃ மையத்தில், விளிம்பில் அல்லது மூலையில். முதல் வீரர் மையத்தில் விளையாடினால் இரண்டாவது வீரருக்கு பதிலுக்கு இரண்டு தேர்வுகள் உள்ளன, இல்லையெனில் ஐந்து தேர்வுகள் உள்ளன. மற்றும் பல. முழுமையான விளையாட்டு மரத்தில் உள்ள இலை முனைகளின் எண்ணிக்கை என்பது விளையாட்டை விளையாடக்கூடிய பல்வேறு வழிகளின் எண்ணிக்கை ஆகும். எடுத்துக்காட்டாக, டிக்-டாக்-டோவிற்கான விளையாட்டு மரத்தில் 255,168 இலை முனைகள் உள்ளன. செயற்கை நுண்ணறிவில் விளையாட்டு மரங்கள் முக்கியம், ஏனென்றால் ஒரு விளையாட்டில் சிறந்த நகர்வைத் தேர்ந்தெடுப்பதற்கான ஒரு வழி, மரத்தை வெட்டுவதற்கு மினிமேக்ஸ் போன்ற விதிகளுடன் இணைந்து ஏராளமான மரத் தேடல் வழிமுறைகளில் ஏதேனும் ஒன்றைப் பயன்படுத்தி விளையாட்டு மரத்தைத் தேடுவதாகும். டிக்-டாக்-டோவிற்கான விளையாட்டு மரம் எளிதில் தேடக்கூடியது, ஆனால் சதுரங்கம் போன்ற பெரிய விளையாட்டுகளுக்கான முழுமையான விளையாட்டு மரங்கள் தேடுவதற்கு மிகப் பெரியவை. அதற்கு பதிலாக, ஒரு சதுரங்க விளையாட்டு நிரல் ஒரு பகுதி விளையாட்டு மரத்தைத் தேடுகிறதுஃ பொதுவாக தற்போதைய நிலையில் இருந்து கிடைக்கக்கூடிய நேரத்தில் தேடக்கூடிய பல பிளைஸ். "நோயியல்" விளையாட்டு மரங்கள் (நடைமுறையில் மிகவும் அரிதாகத் தோன்றும்) தவிர, தேடல் ஆழத்தை அதிகரிப்பது (அதாவது, தேடப்பட்ட பிளைக்களின் எண்ணிக்கை) பொதுவாக சிறந்த நகர்வைத் தேர்ந்தெடுப்பதற்கான வாய்ப்பை மேம்படுத்துகிறது. இரண்டு நபர்களின் விளையாட்டுகளை மரங்கள் அல்லது மரங்களாகவும் குறிப்பிடலாம். ஒரு விளையாட்டை வெல்லும் முதல் வீரருக்கு, இரண்டாவது வீரரின் அனைத்து நகர்வுகளுக்கும் ஒரு வெற்றி நகர்வு இருக்க வேண்டும். முதல் வீரரின் மாற்று நகர்வுகளைக் குறிக்கவும், இரண்டாவது வீரரின் அனைத்து நகர்வுகளையும் குறிக்க இணைப்பைப் பயன்படுத்துவதன் மூலமும் இது மற்றும்-அல்லது மரத்தில் குறிப்பிடப்படுகிறது. ஒரு முழுமையான விளையாட்டு மரத்துடன், விளையாட்டை "தீர்க்க" முடியும்-அதாவது, முதல் அல்லது இரண்டாவது வீரர் பின்பற்றக்கூடிய நகர்வுகளின் வரிசையைக் கண்டறியவும், அது அந்த வீரருக்கு சிறந்த முடிவை உறுதி செய்யும் (பொதுவாக ஒரு வெற்றி அல்லது ஒரு டை). தீர்மானகரமான வழிமுறை (இது பொதுவாக பின்தங்கிய தூண்டல் அல்லது பின்னோக்கிய பகுப்பாய்வு என்று அழைக்கப்படுகிறது) பின்வருமாறு மீண்டும் மீண்டும் விவரிக்கப்படலாம். விளையாட்டு மரத்தின் இறுதி பலகையை வண்ணமயமாக்குங்கள், இதனால் வீரர் 1 க்கான அனைத்து வெற்றிகளும் ஒரு வழியில் (வரைபடத்தில் நீலம்), வீரர் 2 க்கான அனைத்து வெற்றிகளும் மற்றொரு வழியில் (வரைபடத்தில் சிவப்பு) வண்ணமயமாக்கப்படுகின்றன, மேலும் அனைத்து உறவுகளும் மூன்றாவது வழியில் (வரைபடத்தில் சாம்பல்) வண்ணமயமாக்கப்படுகின்றன. அடுத்த பிளை அப்பைப் பாருங்கள். தற்போதைய வீரருக்கு எதிர் நிறத்தில் ஒரு முனை இருந்தால், அந்த வீரருக்கும் இந்த முனையை வண்ணமயமாக்குங்கள். அனைத்து உடனடியாக கீழ் முனைகளும் ஒரே வீரருக்கு வண்ணமயமாக இருந்தால், அதே வீரருக்கும் இந்த முனையை வண்ணமயமாக்குங்கள். இல்லையெனில், இந்த முனையை ஒரு டை என்று நிறப்படுத்துங்கள். அனைத்து முனைகளும் வண்ணமயமாகும் வரை, மேல்நோக்கி நகர்ந்து, ஒவ்வொரு பிளைக்கும் மீண்டும் செய்யவும். வேர் முனையின் நிறம் விளையாட்டின் தன்மையை தீர்மானிக்கும். மேலே உள்ள வழிமுறையைப் பயன்படுத்தி வண்ணமயமான ஒரு தன்னிச்சையான விளையாட்டுக்கான விளையாட்டு மரத்தை வரைபடம் காட்டுகிறது. விளையாட்டு மரத்தின் ஒரு துணைக்குழுவை மட்டுமே பயன்படுத்தி ஒரு விளையாட்டைத் தீர்ப்பது ("தீர்" என்ற இந்த தொழில்நுட்ப அர்த்தத்தில்) பொதுவாக சாத்தியமாகும், ஏனெனில் பல விளையாட்டுகளில் அதே வீரருக்கு சிறந்த மற்றொரு நகர்வு இருந்தால் ஒரு நகர்வை பகுப்பாய்வு செய்ய வேண்டிய அவசியமில்லை (எடுத்துக்காட்டாக ஆல்பா-பீட்டா சீரமைப்பு பல தீர்மானகரமான விளையாட்டுகளில் பயன்படுத்தப்படலாம்). விளையாட்டைத் தீர்க்கப் பயன்படுத்தக்கூடிய எந்தவொரு துணை மரமும் முடிவு மரம் என்று அழைக்கப்படுகிறது, மேலும் பல்வேறு வடிவங்களின் முடிவு மரங்களின் அளவுகள் விளையாட்டு சிக்கலின் அளவீடுகளாகப் பயன்படுத்தப்படுகின்றன. சீரற்ற வழிமுறைகள் பதிப்பு சீரற்ற வழிமுறைகள் விளையாட்டு மரங்களைத் தீர்ப்பதில் பயன்படுத்தப்படலாம். இந்த வகை செயல்பாட்டில் இரண்டு முக்கிய நன்மைகள் உள்ளனஃ வேகம் மற்றும் நடைமுறை. விளையாட்டு மரங்களைத் தீர்ப்பதற்கான ஒரு தீர்மானகரமான பதிப்பைச் செய்ய முடியும் என்றாலும், விளையாட்டு மரத்தில் உள்ள ஒவ்வொரு முனையிலும் டிகிரி 2 இருந்தால் பின்வரும் சீரற்ற வழிமுறை எதிர்பார்க்கப்படும் இயக்க நேரத்தைக் கொண்டுள்ளது. மேலும், இது நடைமுறைக்குரியது, ஏனெனில் சீரற்ற வழிமுறைகள் "எதிரியை முறியடிக்கும்" திறன் கொண்டவை, அதாவது கேம் ட்ரீயைத் தீர்க்கப் பயன்படுத்தப்படும் வழிமுறையை அறிந்து கொள்வதன் மூலம் ஒரு எதிரியால் கேம் ட்ரீய்களின் அமைப்பை வெல்ல முடியாது, ஏனெனில் தீர்க்கும் வரிசை சீரற்றது. பின்வருபவை சீரற்ற கேம் ட்ரீ தீர்வு வழிமுறையின் அமலாக்கமாகும்ஃ டிஃப் ஜிடி _ இவைல் _ ரேண்ட் (யு)-> பூல்ஃ "" இந்த முனை ஒரு வெற்றிக்கு மதிப்பீடு செய்தால் உண்மை என்று திரும்புகிறது, இல்லையெனில் தவறானது "" என்றால் u.leaf: திரும்பும் u.win வேறுவிதமாகஃ ரேண்டம் _ குழந்தைகள் = (ஜிடி _ இவைல் _ ரேண்ட் (குழந்தை) ரேண்டம் _ வரிசையில் (u.children)) குழந்தைக்கு யு. ஓ. பி = = "ஓஆர்": ஏதேனும் (ரேண்டம் _ குழந்தைகள்) திருப்பினால் யு. ஓ. பி = = "ஏஎன்டி": அனைத்து (ரேண்டம் _ குழந்தைகள்) திரும்பவும் வழிமுறை "குறுகிய சுற்று" யோசனையைப் பயன்படுத்துகிறதுஃ ரூட் முனை ஒரு "ஆபரேட்டர்" என்று கருதப்பட்டால், பின்னர் ஒரு முறை. மேலும் காண்கஃ ஆல்பா-பீட்டா சீரமைப்பு விரிவான வடிவ விளையாட்டு ஷானன் எண் விளையாட்டு சிக்கலானது குறிப்புகள் மேலும் வாசிப்பு ஜூடியா பேர்ல், ஹூரிஸ்டிக்ஸ், அடிசன்-வெஸ்லி, 1984 ஒருங்கிணைந்த விளையாட்டு கோட்பாடு மரங்கள் (வரைபடக் கோட்பாடு)