Game tree
সমন্বিত গেম তত্ত্বের প্রসঙ্গে, যা সাধারণত নিখুঁত তথ্য সহ ক্রমিক গেমগুলি অধ্যয়ন করে, একটি গেম ট্রি এমন একটি গ্রাফ যা এই জাতীয় গেমের মধ্যে সমস্ত সম্ভাব্য গেমের অবস্থার প্রতিনিধিত্ব করে। এই ধরনের খেলার মধ্যে রয়েছে দাবা, চেকার্স, গো এবং টিক-ট্যাক-টো-এর মতো সুপরিচিত খেলাগুলি। এটি একটি খেলার জটিলতা পরিমাপ করতে ব্যবহার করা যেতে পারে, কারণ এটি একটি খেলার সম্ভাব্য সমস্ত উপায়ের প্রতিনিধিত্ব করে। দাবার মতো জটিল গেমগুলির বড় খেলার গাছের কারণে, এই শ্রেণীর গেমগুলি খেলার জন্য ডিজাইন করা অ্যালগরিদমগুলি আংশিক গেম ট্রি ব্যবহার করবে, যা আধুনিক কম্পিউটারে গণনাকে সম্ভব করে তোলে। গেম ট্রি সমাধানের জন্য বিভিন্ন পদ্ধতি রয়েছে। যদি একটি সম্পূর্ণ গেম ট্রি তৈরি করা যায়, তবে একটি নির্ধারক অ্যালগরিদম, যেমন ব্যাকওয়ার্ড ইন্ডাকশন বা রেট্রোগ্রেড বিশ্লেষণ ব্যবহার করা যেতে পারে। এলোমেলো অ্যালগরিদম এবং এমসিটিএস-এর মতো মিনম্যাক্স অ্যালগরিদমগুলি এমন ক্ষেত্রে ব্যবহার করা যেতে পারে যেখানে একটি সম্পূর্ণ গেম ট্রি সম্ভব নয়। গেম ট্রি বোঝা গেম ট্রি আরও ভালভাবে বোঝার জন্য, এটিকে প্রতিকূল গেমগুলি বিশ্লেষণ করার একটি কৌশল হিসাবে ভাবা যেতে পারে, যা গেমটি জেতার জন্য খেলোয়াড়ের পদক্ষেপগুলি নির্ধারণ করে। গেম থিওরিতে, একটি গেম ট্রি হল একটি নির্দেশিত গ্রাফ যার নোডগুলি একটি গেমের অবস্থান (উদাহরণস্বরূপ, একটি বোর্ড গেমের টুকরোগুলির বিন্যাস) এবং যার প্রান্তগুলি সরানো হয় (উদাহরণস্বরূপ, একটি বোর্ডের এক অবস্থান থেকে অন্য অবস্থানে টুকরোগুলি সরানো)। একটি গেমের জন্য সম্পূর্ণ গেম ট্রি হল গেম ট্রি যা প্রাথমিক অবস্থান থেকে শুরু হয় এবং প্রতিটি অবস্থান থেকে সমস্ত সম্ভাব্য পদক্ষেপ ধারণ করে; সম্পূর্ণ গাছটি একই গাছ যা বিস্তৃত-ফর্ম গেম উপস্থাপনা থেকে প্রাপ্ত। আরও সুনির্দিষ্টভাবে বলতে গেলে, গেম থিওরিতে গেমটির জন্য সম্পূর্ণ গেমটি একটি আদর্শ। যা অনেক গুরুত্বপূর্ণ দিক স্পষ্টভাবে প্রকাশ করতে পারে। উদাহরণস্বরূপ, অংশীদাররা যে পদক্ষেপ নিতে পারে তার ক্রম, প্রতিটি সিদ্ধান্তের সময়ে তাদের পছন্দ, প্রতিটি অংশীদার যখন সিদ্ধান্ত নেয় তখন অন্যান্য অংশীদারদের দ্বারা গৃহীত পদক্ষেপ সম্পর্কে তথ্য এবং সমস্ত সম্ভাব্য খেলার ফলাফলের সুবিধা। চিত্রটি টিক-ট্যাক-পায়ের আঙ্গুলের জন্য গেম ট্রি-তে প্রথম দুটি স্তর বা প্লাইস দেখায়। অবস্থানের ঘূর্ণন এবং প্রতিফলন সমতুল্য, তাই প্রথম খেলোয়াড়ের তিনটি বিকল্প রয়েছেঃ কেন্দ্রে, প্রান্তে বা কোণে। দ্বিতীয় খেলোয়াড়ের কাছে উত্তরের জন্য দুটি পছন্দ থাকে যদি প্রথম খেলোয়াড় কেন্দ্রে খেলে, অন্যথায় পাঁচটি পছন্দ। এবং ইত্যাদি। সম্পূর্ণ গেম ট্রি-তে লিফ নোডের সংখ্যা হল সম্ভাব্য বিভিন্ন উপায়ে খেলাটি খেলা যেতে পারে। উদাহরণস্বরূপ, টিক-ট্যাক-পায়ের আঙ্গুলের জন্য গেম ট্রিটিতে 255,168 টি পাতার নোড রয়েছে। কৃত্রিম বুদ্ধিমত্তায় গেম ট্রি গুরুত্বপূর্ণ কারণ একটি খেলায় সেরা পদক্ষেপ বেছে নেওয়ার একটি উপায় হল অসংখ্য ট্রি সার্চ অ্যালগরিদম ব্যবহার করে গেম ট্রি অনুসন্ধান করা, গাছটি ছাঁটাই করার জন্য মিনিম্যাক্স-এর মতো নিয়মের সাথে মিলিত করা। টিক-ট্যাক-পায়ের আঙ্গুলের জন্য গেম ট্রি সহজেই অনুসন্ধানযোগ্য, তবে দাবার মতো বড় গেমগুলির জন্য সম্পূর্ণ গেম ট্রিগুলি অনুসন্ধান করা খুব বড়। পরিবর্তে, একটি দাবা খেলার প্রোগ্রাম একটি আংশিক গেম ট্রি অনুসন্ধান করেঃ সাধারণত বর্তমান অবস্থান থেকে যতগুলি প্লে উপলব্ধ সময়ে অনুসন্ধান করতে পারে। "প্যাথোলজিক্যাল" গেম ট্রি ব্যতীত (যা বাস্তবে বেশ বিরল বলে মনে হয়), অনুসন্ধানের গভীরতা বৃদ্ধি (অর্থাৎ, অনুসন্ধান করা প্লিসের সংখ্যা) সাধারণত সেরা পদক্ষেপটি বেছে নেওয়ার সম্ভাবনাকে উন্নত করে। দুই ব্যক্তির খেলাকে এবং বা গাছ হিসাবেও উপস্থাপন করা যেতে পারে। প্রথম খেলোয়াড়ের একটি খেলা জেতার জন্য, দ্বিতীয় খেলোয়াড়ের সমস্ত পদক্ষেপের জন্য অবশ্যই একটি বিজয়ী পদক্ষেপ থাকতে হবে। প্রথম খেলোয়াড়ের বিকল্প পদক্ষেপের প্রতিনিধিত্ব করার জন্য বিচ্ছিন্নতা ব্যবহার করে এবং দ্বিতীয় খেলোয়াড়ের সমস্ত পদক্ষেপের প্রতিনিধিত্ব করার জন্য সংযোগ ব্যবহার করে এটি এবং-বা গাছে প্রতিনিধিত্ব করা হয়। একটি সম্পূর্ণ গেম ট্রি দিয়ে, গেমটিকে "সমাধান" করা সম্ভব-অর্থাৎ, এমন একটি পদক্ষেপের ক্রম খুঁজে বের করুন যা প্রথম বা দ্বিতীয় খেলোয়াড় অনুসরণ করতে পারে যা সেই খেলোয়াড়ের জন্য সর্বোত্তম সম্ভাব্য ফলাফলের নিশ্চয়তা দেবে (সাধারণত একটি জয় বা একটি টাই)। নির্ধারণমূলক অ্যালগরিদম (যাকে সাধারণত পশ্চাদগামী আবেশ বা পশ্চাদগামী বিশ্লেষণ বলা হয়) নিম্নরূপ পুনরাবৃত্তিমূলকভাবে বর্ণনা করা যেতে পারে। গেম ট্রির চূড়ান্ত প্লাই রঙ করুন যাতে খেলোয়াড় 1-এর সমস্ত জয় একদিকে রঙিন হয় (রেখাচিত্রে নীল), খেলোয়াড় 2-এর সমস্ত জয় অন্য দিকে রঙিন হয় (রেখাচিত্রে লাল), এবং সমস্ত টাই তৃতীয় দিকে রঙিন হয় (রেখাচিত্রে ধূসর)। পরের প্লাই আপ দেখুন। যদি বর্তমান খেলোয়াড়ের বিপরীতে রঙের কোনও নোড থাকে, তবে সেই খেলোয়াড়ের জন্যও এই নোডটি রঙ করুন। যদি সমস্ত অবিলম্বে নিচের নোডগুলি একই খেলোয়াড়ের জন্য রঙিন হয়, তবে একই খেলোয়াড়ের জন্যও এই নোডটি রঙ করুন। অন্যথায়, এই নোডটিকে একটি টাই রঙ করুন। প্রতিটি প্লাইয়ের জন্য পুনরাবৃত্তি করুন, উপরের দিকে সরান, যতক্ষণ না সমস্ত নোড রঙিন হয়। মূল নোডের রঙ খেলার প্রকৃতি নির্ধারণ করবে। চিত্রটি একটি নির্বিচারে খেলার জন্য একটি গেম ট্রি দেখায়, যা উপরের অ্যালগরিদম ব্যবহার করে রঙিন। সাধারণত গেম ট্রি-র একটি উপসেট ব্যবহার করে একটি গেম ("সমাধান"-এর এই প্রযুক্তিগত অর্থে) সমাধান করা সম্ভব, কারণ অনেক খেলায় একই খেলোয়াড়ের জন্য আরও ভাল অন্য কোনও পদক্ষেপ থাকলে একটি পদক্ষেপ বিশ্লেষণ করার প্রয়োজন হয় না (উদাহরণস্বরূপ, অনেক নির্ধারক খেলায় আলফা-বিটা ছাঁটাই ব্যবহার করা যেতে পারে)। যে কোনও সাবট্রি যা গেমটি সমাধান করতে ব্যবহার করা যেতে পারে তা ডিসিশন ট্রি হিসাবে পরিচিত এবং বিভিন্ন আকারের ডিসিশন ট্রিগুলির আকার গেমের জটিলতার পরিমাপ হিসাবে ব্যবহৃত হয়। র্যান্ডমাইজড অ্যালগরিদম সংস্করণ র্যান্ডমাইজড অ্যালগরিদম গেম ট্রি সমাধানে ব্যবহার করা যেতে পারে। এই ধরনের বাস্তবায়নের দুটি প্রধান সুবিধা রয়েছেঃ গতি এবং ব্যবহারিকতা। যেখানে গেম ট্রি সমাধানের একটি নির্ধারক সংস্করণ করা যেতে পারে, নিম্নলিখিত র্যান্ডমাইজড অ্যালগরিদমের একটি প্রত্যাশিত রান টাইম থাকে যদি গেম ট্রি-র প্রতিটি নোডের ডিগ্রি 2 থাকে। অধিকন্তু, এটি ব্যবহারিক কারণ র্যান্ডমাইজড অ্যালগরিদমগুলি "শত্রুকে ব্যর্থ করতে" সক্ষম, যার অর্থ কোনও প্রতিপক্ষ গেম ট্রি সমাধানের জন্য ব্যবহৃত অ্যালগরিদম জেনে গেম ট্রি সিস্টেমকে পরাজিত করতে পারে না কারণ সমাধানের ক্রমটি এলোমেলো। নিম্নলিখিতটি র্যান্ডমাইজড গেম ট্রি সলিউশন অ্যালগরিদমের একটি বাস্তবায়নঃ ডেফ জিটি _ ইভাল _ র্যান্ড (ইউ)-> বূলঃ "" সত্য ফিরে আসে যদি এই নোডটি একটি জয়ের জন্য মূল্যায়ন করে, অন্যথায় মিথ্যা "" যদি u.leaf: ফিরে আসে u.win অন্যথায়ঃ র্যান্ডম _ চিলড = (জিটি _ ইভাল _ র্যান্ড (চাইল্ড) র্যান্ডম _ অর্ডারে (u.children) সন্তানের জন্য যদি ইউ. অপ = = "ওআর": কোনও (র্যান্ডম _ চিলড) ফেরত দেয় যদি ইউ. অপ = = "এ. এন. ডি": সমস্ত (র্যান্ডম _ চিলড) ফেরত দেয় অ্যালগরিদম "শর্ট-সার্কিটিং" ধারণাটি ব্যবহার করেঃ যদি রুট নোডটিকে "অপারেটর" হিসাবে বিবেচনা করা হয়, তবে একবার আরও দেখুন আলফা-বিটা ছাঁটাই এক্সটেনসিভ ফর্ম গেম শ্যানন নম্বর গেম জটিলতা রেফারেন্স আরও পড়া জুডিয়া পার্ল, হিউরিস্টিক্স, অ্যাডিসন-ওয়েসলি, 1984 কম্বিনেটরিয়াল গেম থিওরি ট্রি (গ্রাফ তত্ত্ব)