Game tree
مشترکہ گیم تھیوری کے تناظر میں، جو عام طور پر کامل معلومات کے ساتھ ترتیب وار گیمز کا مطالعہ کرتا ہے، گیم ٹری ایک گراف ہے جو اس طرح کے گیم کے اندر تمام ممکنہ گیم اسٹیٹس کی نمائندگی کرتا ہے۔ اس طرح کے کھیلوں میں شطرنج، چیکرز، گو، اور ٹک ٹیک پیر جیسے معروف کھیل شامل ہیں۔ اس کا استعمال کھیل کی پیچیدگی کی پیمائش کے لیے کیا جا سکتا ہے، کیونکہ یہ ان تمام ممکنہ طریقوں کی نمائندگی کرتا ہے جن سے کھیل ختم ہو سکتا ہے۔ شطرنج جیسے پیچیدہ کھیلوں کے بڑے گیم ٹری کی وجہ سے، الگورتھم جو اس طبقے کے کھیلوں کو کھیلنے کے لیے بنائے گئے ہیں وہ جزوی گیم ٹری کا استعمال کریں گے، جو جدید کمپیوٹرز پر کمپیوٹیشن کو ممکن بناتا ہے۔ گیم ٹری کو حل کرنے کے مختلف طریقے موجود ہیں۔ اگر ایک مکمل گیم ٹری تیار کیا جا سکتا ہے، تو ایک تعیناتی الگورتھم، جیسے کہ بیکورڈ انڈکشن یا ریٹروگریڈ تجزیہ استعمال کیا جا سکتا ہے۔ بے ترتیب الگورتھم اور منی میکس الگورتھم جیسے ایم سی ٹی ایس کو ان صورتوں میں استعمال کیا جا سکتا ہے جہاں ایک مکمل گیم ٹری ممکن نہیں ہے۔ گیم ٹری کو بہتر طور پر سمجھنے کے لیے، اسے مخالفانہ گیمز کا تجزیہ کرنے کی ایک تکنیک کے طور پر سوچا جا سکتا ہے، جو کھلاڑی کے گیم جیتنے کے لیے کیے جانے والے اقدامات کا تعین کرتا ہے۔ گیم تھیوری میں، گیم ٹری ایک ہدایت شدہ گراف ہوتا ہے جس کے نوڈس کسی گیم میں پوزیشن ہوتے ہیں (مثال کے طور پر، بورڈ گیم میں ٹکڑوں کا انتظام) اور جس کے کناروں پر حرکتیں ہوتی ہیں (مثال کے طور پر، ٹکڑوں کو بورڈ پر ایک پوزیشن سے دوسری پوزیشن پر منتقل کرنا)۔ گیم کے لیے مکمل گیم ٹری گیم ٹری ہے جو ابتدائی پوزیشن سے شروع ہوتا ہے اور ہر پوزیشن سے تمام ممکنہ چالوں پر مشتمل ہوتا ہے۔ مکمل ٹری وہی ٹری ہے جو وسیع فارم گیم کی نمائندگی سے حاصل ہوتا ہے۔ مزید مخصوص ہونے کے لیے، گیم تھیوری میں گیم کے لیے مکمل گیم ایک معمول ہے۔ جو بہت سے اہم پہلوؤں کو واضح طور پر ظاہر کر سکتا ہے۔ مثال کے طور پر، اسٹیک ہولڈرز کے اقدامات کا سلسلہ، ہر فیصلے کے مقام پر ان کے انتخاب، جب ہر اسٹیک ہولڈر فیصلہ کرتا ہے تو دوسرے اسٹیک ہولڈرز کے اقدامات کے بارے میں معلومات، اور کھیل کے تمام ممکنہ نتائج کے فوائد۔ خاکہ ٹک-ٹیک-پیر کے لیے گیم ٹری میں پہلے دو درجے، یا پلیز کو دکھاتا ہے۔ پوزیشنوں کی گردش اور عکاسی مساوی ہوتی ہے، لہذا پہلے کھلاڑی کے پاس حرکت کے تین انتخاب ہوتے ہیں: مرکز میں، کنارے پر، یا کونے میں۔ دوسرے کھلاڑی کے پاس جواب کے لیے دو انتخاب ہوتے ہیں اگر پہلا کھلاڑی مرکز میں کھیلتا ہے، ورنہ پانچ انتخاب ہوتے ہیں۔ اور اسی طرح۔ مکمل گیم ٹری میں لیف نوڈس کی تعداد ممکنہ مختلف طریقوں کی تعداد ہے جو گیم کو کھیلا جا سکتا ہے۔ مثال کے طور پر، ٹک-ٹیک-پیر کے گیم ٹری میں 255,168 لیف نوڈس ہوتے ہیں۔ مصنوعی ذہانت میں گیم ٹری اہم ہیں کیونکہ گیم میں بہترین اقدام کو منتخب کرنے کا ایک طریقہ یہ ہے کہ ٹری کی کٹائی کے لیے منی میکس جیسے اصولوں کے ساتھ مل کر متعدد ٹری سرچ الگورتھم میں سے کسی کا استعمال کرتے ہوئے گیم ٹری کو تلاش کیا جائے۔ ٹک ٹیک پیر کے لیے گیم ٹری آسانی سے تلاش کیا جا سکتا ہے، لیکن شطرنج جیسے بڑے کھیلوں کے لیے مکمل گیم ٹری تلاش کرنے کے لیے بہت بڑے ہیں۔ اس کے بجائے، شطرنج کھیلنے والا پروگرام جزوی گیم ٹری کو تلاش کرتا ہے: عام طور پر موجودہ پوزیشن سے اتنے ہی لوگ جو دستیاب وقت میں تلاش کر سکتے ہیں۔ سوائے "پیتھولوجیکل" گیم ٹریز کے معاملے کے (جو عملی طور پر کافی نایاب معلوم ہوتے ہیں)، تلاش کی گہرائی میں اضافہ (یعنی، تلاش کی گئی پلیز کی تعداد) عام طور پر بہترین حرکت کو منتخب کرنے کے امکان کو بہتر بناتا ہے۔ دو افراد کے کھیلوں کو اور یا درختوں کے طور پر بھی پیش کیا جا سکتا ہے۔ کھیل جیتنے والے پہلے کھلاڑی کے لیے، دوسرے کھلاڑی کی تمام چالوں کے لیے ایک جیتنے والی حرکت موجود ہونی چاہیے۔ اس کی نمائندگی پہلے کھلاڑی کی متبادل چالوں کی نمائندگی کرنے کے لیے اختلاط کا استعمال کرتے ہوئے اور دوسرے کھلاڑی کی تمام چالوں کی نمائندگی کرنے کے لیے امتزاج کا استعمال کرتے ہوئے کی جاتی ہے۔ گیم کے درختوں کو حل کرنا تعیناتی الگورتھم ورژن ایک مکمل گیم ٹری کے ساتھ، گیم کو "حل" کرنا ممکن ہے-یعنی، چالوں کا ایک سلسلہ تلاش کریں جس کی پیروی پہلا یا دوسرا کھلاڑی کر سکتا ہے جو اس کھلاڑی کے لیے بہترین ممکنہ نتائج کی ضمانت دے گا (عام طور پر جیت یا ٹائی)۔ تعیناتی الگورتھم (جسے عام طور پر بیکورڈ انڈکشن یا ریٹروگریڈ تجزیہ کہا جاتا ہے) کو درج ذیل طریقے سے بیان کیا جا سکتا ہے۔ گیم ٹری کے آخری پلائی کو رنگ دیں تاکہ کھلاڑی 1 کے لیے تمام جیت ایک طرح سے رنگین ہوں (خاکہ میں نیلا)، کھلاڑی 2 کے لیے تمام جیت دوسرے طریقے سے رنگین ہوں (خاکہ میں سرخ)، اور تمام تعلقات تیسرے طریقے سے رنگین ہوں (خاکہ میں سرمئی)۔ اگلے پلائی اپ کو دیکھیں۔ اگر موجودہ کھلاڑی کے مخالف رنگ کا کوئی نوڈ موجود ہے، تو اس نوڈ کو اس کھلاڑی کے لیے بھی رنگ دیں۔ اگر تمام فوری طور پر نچلے نوڈس ایک ہی کھلاڑی کے لیے رنگین ہیں، تو اسی کھلاڑی کے لیے بھی اس نوڈ کو رنگ دیں۔ ورنہ، اس نوڈ کو ٹائی رنگ دیں۔ ہر پلائی کے لیے دہرائیں، اوپر کی طرف بڑھیں، جب تک کہ تمام نوڈس رنگین نہ ہو جائیں۔ جڑ نوڈ کا رنگ کھیل کی نوعیت کا تعین کرے گا۔ خاکہ ایک صوابدیدی کھیل کے لیے گیم ٹری دکھاتا ہے، جو مندرجہ بالا الگورتھم کا استعمال کرتے ہوئے رنگین ہے۔ گیم ٹری کے صرف ایک ذیلی سیٹ کا استعمال کرتے ہوئے گیم کو حل کرنا ("حل" کے اس تکنیکی معنی میں) عام طور پر ممکن ہے، کیونکہ بہت سے کھیلوں میں کسی حرکت کا تجزیہ کرنے کی ضرورت نہیں ہوتی ہے اگر کوئی اور حرکت ہو جو اسی کھلاڑی کے لیے بہتر ہو (مثال کے طور پر الفا-بیٹا کٹائی کو بہت سے متعین کھیلوں میں استعمال کیا جا سکتا ہے)۔ کوئی بھی ذیلی درخت جسے کھیل کو حل کرنے کے لیے استعمال کیا جا سکتا ہے اسے فیصلہ درخت کہا جاتا ہے، اور مختلف شکلوں کے فیصلہ درختوں کے سائز کو کھیل کی پیچیدگی کی پیمائش کے طور پر استعمال کیا جاتا ہے۔ بے ترتیب الگورتھم ورژن بے ترتیب الگورتھم کو گیم ٹری کو حل کرنے میں استعمال کیا جا سکتا ہے۔ اس قسم کے نفاذ میں دو اہم فوائد ہیں: رفتار اور عملیت۔ جبکہ گیم ٹری کو حل کرنے کا ایک متعین ورژن میں کیا جا سکتا ہے، مندرجہ ذیل بے ترتیب الگورتھم کا متوقع رن ٹائم ہوتا ہے اگر گیم ٹری میں ہر نوڈ کی ڈگری 2 ہو۔ مزید برآں، یہ عملی ہے کیونکہ بے ترتیب الگورتھم "دشمن کو ناکام بنانے" کی صلاحیت رکھتے ہیں، جس کا مطلب ہے کہ مخالف گیم ٹری کو حل کرنے کے لیے استعمال ہونے والے الگورتھم کو جان کر گیم ٹری کے نظام کو شکست نہیں دے سکتا کیونکہ حل کرنے کی ترتیب بے ترتیب ہوتی ہے۔ مندرجہ ذیل بے ترتیب گیم ٹری حل الگورتھم کا نفاذ ہے: ڈیف جی ٹی _ ایول _ رینڈ (یو)-> بول: "" اگر یہ نوڈ جیت کا اندازہ لگاتا ہے تو درست واپسی کرتا ہے، بصورت دیگر غلط "اگر u.leaf: ریٹرن u.win بصورت دیگر: بے ترتیب _ چلڈرن = (جی ٹی _ ایول _ رینڈ (چائلڈ) بے ترتیب _ ترتیب (u.children) میں بچے کے لیے اگر یو۔ او۔ پی = =" او آر ": کسی بھی (بے ترتیب _ چلڈرن) کو واپس کریں اگر یو۔ او۔ پی = =" اے این ڈی ": تمام (بے ترتیب _ چلڈرن) کو واپس کریں الگورتھم" شارٹ سرکٹنگ "کے خیال کو استعمال کرتا ہے: اگر روٹ نوڈ کو" آپریٹر "سمجھا جاتا ہے، تو ایک بار مزید دیکھیں الفا-بیٹا کٹائی وسیع فارم گیم شینن نمبر گیم پیچیدگی حوالہ جات مزید پڑھنا جوڈیا پرل، ہیورسٹکس، ایڈیسن-ویسلی، 1984 مشترکہ گیم تھیوری درخت (گراف تھیوری)