Solving chess
দাবা সমাধানের মধ্যে রয়েছে দাবা খেলার জন্য একটি সর্বোত্তম কৌশল খুঁজে বের করা; অর্থাৎ, যার দ্বারা খেলোয়াড়দের মধ্যে একজন (সাদা বা কালো) সর্বদা একটি জয়কে জোর করতে পারে, অথবা ড্র করতে বাধ্য করতে পারে (সমাধানকৃত খেলা দেখুন)। এটি আরও সাধারণভাবে দাবার মতো গেমগুলি সমাধান করার সাথেও সম্পর্কিত (অর্থাৎ। নিখুঁত তথ্যের সমন্বিত খেলা) যেমন ক্যাপাব্লাঙ্কা দাবা এবং অসীম দাবা। দুর্বল অর্থে, দাবা সমাধান করা বলতে বোঝাতে পারে যে তিনটি সম্ভাব্য ফলাফলের মধ্যে কোনটি (সাদা জয়; কালো জয়; ড্র) দুই নিখুঁত খেলোয়াড়ের ফলাফল, অগত্যা সর্বোত্তম কৌশল নিজেই প্রকাশ না করে (পরোক্ষ প্রমাণ দেখুন)। এই দুটি ইন্দ্রিয়ের কোনওটিতেই দাবার কোনও সম্পূর্ণ সমাধান জানা যায়নি, এবং অদূর ভবিষ্যতে (যদি কখনও হয়) দাবার সমাধান হবে বলেও আশা করা যায় না। কম্পিউটিং শক্তির বর্তমান সূচকীয় বৃদ্ধি এত দীর্ঘ সময় ধরে অব্যাহত থাকবে কিনা তা নিয়ে মতবিরোধ রয়েছে যে কোনও দিন এটি "ব্রুট ফোর্স" দ্বারা সমাধান করার অনুমতি দেবে, অর্থাৎ। সমস্ত সম্ভাবনা পরীক্ষা করে। আজ অবধি অগ্রগতি অত্যন্ত সীমিত; অল্প সংখ্যক টুকরো (সাতটি পর্যন্ত) সহ নিখুঁত এন্ডগেম খেলার টেবিলবেস রয়েছে এবং কিছু দাবার রূপগুলি কমপক্ষে দুর্বলভাবে সমাধান করা হয়েছে। খেলা-গাছের জটিলতা এবং দাবার রাজ্য-স্থান জটিলতার গণনা করা অনুমান বিদ্যমান যা খেলাটি সমাধান করার জন্য প্রয়োজনীয় গণনামূলক প্রচেষ্টার একটি পাখির চোখের দৃশ্য প্রদান করে। আংশিক ফলাফল এন্ডগেম টেবিলবেস এন্ডগেম টেবিলবেস হল কম্পিউটারাইজড ডেটাবেস যা বোর্ডে অল্প সংখ্যক টুকরো অবশিষ্ট থাকা অবস্থানগুলির পূর্বনির্ধারিত সম্পূর্ণ বিশ্লেষণ ধারণ করে। টেবিলবেসগুলি সীমিত মাত্রায় দাবার সমাধান করেছে, বেশ কয়েকটি শেষ খেলায় নিখুঁত খেলা নির্ধারণ করে, যার মধ্যে সমস্ত অ-তুচ্ছ শেষ খেলা রয়েছে যার মধ্যে সাতটির বেশি টুকরো বা প্যাঁচা (দুই রাজা সহ) নেই। সাত-পিস এন্ডগেম টেবিলবেস বিকাশের একটি পরিণতি হ 'ল অনেক আকর্ষণীয় তাত্ত্বিক দাবা সমাপ্তি পাওয়া গেছে। দীর্ঘতম সাত টুকরো উদাহরণ হল 50-পদক্ষেপের নিয়ম উপেক্ষা করে গাই হাওয়র্থ দ্বারা লোমোনোসভ টেবিলবেসে আবিষ্কৃত একটি মেট-ইন-549 অবস্থান। এই ধরনের অবস্থান যে কোনও মানুষের সমাধান করার ক্ষমতার বাইরে, এবং টেবিলবেসে প্রবেশাধিকার ছাড়া কোনও দাবা ইঞ্জিন এটি সঠিকভাবে খেলে না, যার জন্য প্রাথমিকভাবে (2014 সালে) 140 টিবি স্টোরেজ স্পেস এবং একটি সুপার কম্পিউটারের ব্যবহারের প্রয়োজন ছিল কিন্তু পরে সিজিজি টেবিলবেসের মাধ্যমে তা কমিয়ে 18.4 টিবি করা হয়। জানুয়ারী 2023 পর্যন্ত, আট-পিস টেবিলবেসের জন্য দীর্ঘতম পরিচিত জোরপূর্বক সঙ্গমের ক্রম (50-পদক্ষেপের নিয়মকেও উপেক্ষা করে) ছিল 584টি পদক্ষেপ। এটি 2022 সালের মাঝামাঝি সময়ে ডেভেলপার, কম্পিউটার দাবা উৎসাহী এবং পদার্থবিজ্ঞানী মার্ক বুর্জুটস্কি আবিষ্কার করেছিলেন। আট টুকরো টেবিলবেস বর্তমানে অসম্পূর্ণ, তাই এটি নিশ্চিত নয় যে আট টুকরো টেবিলবেসের জন্য এটি পরম সীমা। দাবার রূপগুলি শ্যানন দ্বারা প্রথম বর্ণিত একটি রূপ দাবার খেলা-তাত্ত্বিক মান সম্পর্কে একটি যুক্তি প্রদান করেঃ তিনি "পাস"-এর স্থানান্তরের অনুমতি দেওয়ার প্রস্তাব দেন। এই সংস্করণে, এটি একটি কৌশল চুরি করার যুক্তি দিয়ে প্রমাণ করা যায় যে প্রথম খেলোয়াড়ের অন্তত একটি ড্র রয়েছেঃ যদি প্রথম খেলোয়াড়ের একটি বিজয়ী পদক্ষেপ থাকে, তবে তাকে এটি খেলতে দিন, অন্যথায় পাস করুন। বোর্ডের মিরর ইমেজ প্রতিসাম্যের কারণে দ্বিতীয় খেলোয়াড় এখন একই পরিস্থিতির মুখোমুখি হয়ঃ যদি প্রথম খেলোয়াড়ের প্রথমে কোনও বিজয়ী পদক্ষেপ না থাকে, তবে দ্বিতীয় খেলোয়াড়ের এখন কোনও পদক্ষেপ নেই। অতএব, দ্বিতীয় খেলোয়াড় সেরা ড্র করতে পারে, এবং প্রথম খেলোয়াড় অন্তত ড্র করতে পারে, তাই একটি নিখুঁত খেলা প্রথম খেলোয়াড়ের জয় বা ড্রয়ের ফলাফল দেয়। দাবার কিছু রূপ যা দাবার চেয়ে সহজ তা সমাধান করা হয়েছে। মহারাজা এবং সিপাহীদের মধ্যে কৃষ্ণাঙ্গদের জন্য একটি বিজয়ী কৌশল সহজেই মুখস্থ করা যায়। 5×5 গার্ডনারের মিনিচেসের সংস্করণটি ড্র হিসাবে দুর্বলভাবে সমাধান করা হয়েছে। যদিও দাবা হারানো একটি 8x8 বোর্ডে খেলা হয়, তবে এর জোরপূর্বক ধরার নিয়মটি এর জটিলতাকে ব্যাপকভাবে সীমাবদ্ধ করে এবং একটি গণনামূলক বিশ্লেষণ দুর্বলভাবে এই বৈকল্পিকটিকে হোয়াইটের জয় হিসাবে সমাধান করতে সক্ষম হয়েছিল। পৃথক, নির্দিষ্ট, দাবার মতো গেমগুলি সমাধান করার সম্ভাবনা আরও কঠিন হয়ে ওঠে কারণ বোর্ডের আকার বৃদ্ধি করা হয়, যেমন বড় দাবা রূপ এবং অসীম দাবা। 1950 সালে দাবা তথ্য তাত্ত্বিক ক্লড শ্যাননের জটিলতা একটি নিখুঁত খেলা খেলার জন্য একটি তাত্ত্বিক পদ্ধতির রূপরেখা তৈরি করে (অর্থাৎ। দাবা সমাধান): শ্যানন তখন অনুমান করতে গিয়েছিলেন যে সেই পদ্ধতি অনুসারে দাবা সমাধানের জন্য প্রায় 10টি সম্ভাব্য খেলার বৈচিত্র্যের তুলনা করতে হবে, অথবা একটি "অভিধান" থাকতে হবে যা প্রায় 10টি সম্ভাব্য বোর্ড অবস্থানের (বর্তমানে প্রায় 5x10 হিসাবে পরিচিত) প্রত্যেকটির জন্য একটি সর্বোত্তম পদক্ষেপকে নির্দেশ করে। তবে, দাবা সমাধানের জন্য প্রয়োজনীয় গাণিতিক ক্রিয়াকলাপের সংখ্যা দাবার পুরো গেম-ট্রি তৈরির জন্য প্রয়োজনীয় ক্রিয়াকলাপের সংখ্যার তুলনায় উল্লেখযোগ্যভাবে আলাদা হতে পারে। বিশেষত, যদি হোয়াইট একটি জোরপূর্বক জয় পায়, তবে গেম-ট্রি-র শুধুমাত্র একটি উপসেটকে মূল্যায়ন করতে হবে যে একটি জোরপূর্বক-জয় বিদ্যমান (অর্থাৎ। কালো থেকে কোনও প্রত্যাখ্যান ছাড়াই)। উপরন্তু, দাবার জটিলতার জন্য শ্যাননের গণনাটি খেলার গড় দৈর্ঘ্য 40টি চাল ধরে নেয়, তবে এটি বলার কোনও গাণিতিক ভিত্তি নেই যে উভয় পক্ষের জোরপূর্বক জয়ের এই খেলার দৈর্ঘ্যের সাথে কোনও সম্পর্ক থাকবে। প্রকৃতপক্ষে, কিছু দক্ষতার সাথে খেলা খেলা (গ্র্যান্ডমাস্টার-স্তরের খেলা) 16টি চালের মতো সংক্ষিপ্ত ছিল। এই কারণগুলির জন্য, গণিতবিদ এবং খেলা তাত্ত্বিকরা স্পষ্টভাবে বলতে অনিচ্ছুক যে দাবা সমাধান করা একটি জটিল সমস্যা। দাবা কখন বা কখন সমাধান করা হবে তার পূর্বাভাস 1950 সালে, শ্যানন গণনা করেছিলেন, 10-এর একটি গেম ট্রি জটিলতা এবং এক মেগাহার্টজ-এ পরিচালিত একটি কম্পিউটারের উপর ভিত্তি করে (সেই সময়ে একটি বড় প্রসারিতঃ 1951 সালে প্রবর্তিত ইউনিভ্যাক 1 প্রতি সেকেন্ডে ~ 2000 অপারেশন বা 2 কিলোহার্টজ করতে পারে) যা 1 মাইক্রোসেকেন্ডে একটি টার্মিনাল নোডের মূল্যায়ন করতে পারে যা তার প্রথম পদক্ষেপ নিতে 10 বছর সময় নেবে। এমনকি প্রযুক্তিগত অগ্রগতির অনুমতি দেওয়া, একটি ব্যবহারিক সময়সীমার মধ্যে দাবা সমাধান করা কোনও কল্পনাযোগ্য প্রযুক্তির বাইরে বলে মনে হবে। বার্কলেতে ক্যালিফোর্নিয়া বিশ্ববিদ্যালয়ের গণিত ও জৈব পদার্থবিজ্ঞানের অধ্যাপক হ্যান্স-জোয়াকিম ব্রেমারম্যান 1965 সালের একটি গবেষণাপত্রে আরও যুক্তি দিয়েছিলেন যে "ভবিষ্যতের যে কোনও সম্ভাব্য কম্পিউটার সরঞ্জামের গতি, স্মৃতি এবং প্রক্রিয়াকরণ ক্ষমতা নির্দিষ্ট শারীরিক বাধা দ্বারা সীমাবদ্ধঃ আলোর বাধা, কোয়ান্টাম বাধা এবং তাপগতিবিদ্যার বাধা। উদাহরণস্বরূপ, এই সীমাবদ্ধতাগুলি বোঝায় যে কোনও কম্পিউটার, যতই নির্মিত হোক না কেন, কখনও দাবা খেলার সম্ভাব্য পদক্ষেপের ক্রমের পুরো গাছটি পরীক্ষা করতে সক্ষম হবে না। তা সত্ত্বেও, ব্রেমারম্যান এই সম্ভাবনাকে অগ্রাহ্য করেননি যে একটি কম্পিউটার একদিন দাবার সমাধান করতে সক্ষম হবে। তিনি লিখেছেন, "একটি কম্পিউটার একটি নিখুঁত বা প্রায় নিখুঁত খেলা খেলতে হলে, খেলাটি সম্পূর্ণরূপে বিশ্লেষণ করা বা আনুমানিক উপায়ে খেলাটি বিশ্লেষণ করা এবং সীমিত পরিমাণে গাছ অনুসন্ধানের সাথে এটি একত্রিত করা প্রয়োজন হবে। যাইহোক, এই ধরনের অনুসন্ধানমূলক প্রোগ্রামিং সম্পর্কে একটি তাত্ত্বিক বোঝার এখনও খুব প্রয়োজন। সাম্প্রতিক বৈজ্ঞানিক অগ্রগতি এই মূল্যায়নগুলিকে উল্লেখযোগ্যভাবে পরিবর্তন করেনি। চেকারের খেলাটি 2007 সালে (দুর্বলভাবে) সমাধান করা হয়েছিল, তবে এতে দাবার অবস্থানের সংখ্যার মোটামুটি বর্গমূল রয়েছে। এই প্রচেষ্টার নেতৃত্বদানকারী বিজ্ঞানী জোনাথন শেফার বলেছিলেন যে দাবা সমাধানের চেষ্টা করার আগে কোয়ান্টাম কম্পিউটিংয়ের মতো একটি যুগান্তকারী পদক্ষেপের প্রয়োজন হবে, তবে তিনি এই সম্ভাবনাকে অস্বীকার করেননি, তিনি বলেছিলেন যে চেকারগুলি সমাধান করার 16 বছরের প্রচেষ্টা থেকে তিনি যে একটি জিনিস শিখেছেন তা হল "প্রযুক্তির অগ্রগতিকে কখনই অবমূল্যায়ন করা নয়"। শ্যানন সংখ্যা (দাবার খেলা-গাছের জটিলতার নিম্ন সীমার একটি গণনা) দাবা রেফারেন্সগুলিতে প্রথম পদক্ষেপের সুবিধা বাহ্যিক লিঙ্কগুলি "অসীম দাবা, পিবিএস অসীম সিরিজ" অসীম দাবা, পিবিএস অসীম সিরিজ দেখুন। দাবা তত্ত্ব