ইঞ্জিন কীভাবে কাজ করে

দুটি অংশ: অনুসন্ধান ও মূল্যায়ন

দাবা ইঞ্জিন আসলে একসঙ্গে কাজ করা দুটি প্রোগ্রাম। অনুসন্ধান সামনে তাকায়: “আমি এটা খেললে ওরা ওটা দিয়ে জবাব দিতে পারে, তারপর আমি এটা খেলব…”। মূল্যায়ন কিছু না সরিয়ে একটিমাত্র অবস্থান দেখে তাকে একটি সংখ্যা দেয়: কে এগিয়ে, আর কতটা।

দুটিই একে অপরের ওপর নির্ভরশীল। অনুসন্ধান যত গভীর, দুর্বল মূল্যায়নে তত কম ক্ষতি; মূল্যায়ন যত ভালো, তত কম গভীরতা লাগে। যেহেতু মূল্যায়ন চলে প্রতিটি লাইনের প্রতিটি প্রান্তে — সেকেন্ডে কয়েক লক্ষ বার — তাই তাকে একই সঙ্গে ভালো আর খুব দ্রুত হতে হয়।

অনুসন্ধান

ইঞ্জিন প্রতিবার এক ধাপ করে আরও গভীরে ভাবে (iterative deepening), তাই ঘড়ি ফুরোলেও তার হাতে সবসময় একটি চাল তৈরি থাকে। প্রতিটি চাল প্রতিটি গভীরতা পর্যন্ত দেখতে গেলে অনন্তকাল লেগে যেত, তাই কাজের বেশির ভাগটাই যায় এমন চাল না দেখায়, যেগুলো কোনো তফাত গড়তে পারে না:

• আলফা-বিটা। একটি জবাব কোনো চালকে খণ্ডন করে দিলেই ইঞ্জিন সেই চাল আর খতিয়ে দেখে না। চালগুলো ভালোভাবে সাজানো থাকলে এতে ফলাফল না বদলেই গাছের বেশির ভাগ অংশ বাদ পড়ে যায়।
• সেরা চাল আগে। আগের বার এই অবস্থানে যে চালটি সেরা ছিল, দামি ঘুঁটি কাটার চাল, আর একই ধরনের অবস্থানে কাজে লেগেছে এমন শান্ত চাল (killer moves আর একটি history table) — এগুলোই আগে চেষ্টা করা হয়।
• স্মৃতি। একটি ট্রান্সপোজিশন টেবিল আগেই খোঁজা অবস্থানগুলো মনে রাখে, কারণ একই অবস্থানে প্রায়ই চালের ভিন্ন ভিন্ন ক্রমে পৌঁছানো যায়।
• বুঝেশুনে শর্টকাট। কম সম্ভাবনাময় পরের দিকের চালগুলো কম গভীরে খোঁজা হয় (late move reductions); এমন ভালো অবস্থান, যেখানে একটি চাল ছেড়ে দিলেও সুবিধা থেকে যায়, আগেভাগেই ছেঁটে ফেলা হয় (null move pruning); কিস্তির চালগুলো এক চাল বেশি গভীরে খোঁজা হয়।
• কেবল শান্ত অবস্থান। অনুসন্ধান কখনো কাটাকাটির মাঝপথে থামে না: প্রতিটি লাইনের শেষে অবস্থান থিতু না হওয়া পর্যন্ত সে কাটাকাটি অনুসরণ করে চলে (quiescence search), তাই মূল্যায়ন কখনো এমন মন্ত্রী দেখে না, যাকে পরের চালেই পাল্টা কেটে নেওয়া হবে।
• একাধিক কোর। ইঞ্জিন একসঙ্গে কয়েকটি থ্রেডে খুঁজতে পারে, আর সবগুলো থ্রেড একটিই ট্রান্সপোজিশন টেবিল ভাগ করে নেয় (Lazy SMP)।

বোর্ড

ইঞ্জিনের ভেতরে বোর্ড হলো কয়েকটি 64-বিট সংখ্যার সমষ্টি, প্রতিটি ঘরের জন্য একটি বিট (bitboards): সাদা ঘোড়াগুলোর জন্য একটি সংখ্যা, কালো নৌকাগুলোর জন্য একটি, এভাবেই চলে। চাল আর আক্রমণ হয়ে যায় কয়েকটি বিট অপারেশন, আর দূরপাল্লার ঘুঁটিরা নিজেদের আক্রমণ খুঁজে নেয় আগে থেকে হিসাব করে রাখা টেবিলে (magic bitboards)। রূপভেদের যৌগিক ঘুঁটি — মহারাজা, আর্চবিশপ ও চ্যান্সেলর — তাদের উপাদানগুলোর মিলিত চালে চলে, তাই তারাও ওই একই টেবিল ব্যবহার করে।

হাতে লেখা নিয়মে অবস্থান বিচার

ইঞ্জিনের আদি মূল্যায়ন হলো দাবার অভিজ্ঞতালব্ধ কিছু নিয়মের তালিকা, প্রতিটির নিজস্ব ওজন: ঘুঁটির মোট মূল্য, কোন ঘুঁটি কোথায় দাঁড়িয়ে, কতগুলো ঘর সে নিয়ন্ত্রণ করে, মুক্ত ও বিচ্ছিন্ন বোড়ে, গজ-জোড়া, খোলা কলামে নৌকা, রাজার সামনে বোড়ের ঢাল। ওপেনিং থেকে শেষপর্বের দিকে ওজনগুলো ধীরে ধীরে বদলায়।

এটি কাজ করে, আর আজ অ্যাপে এটিই খেলে, কিন্তু কেউ যা লিখে রাখার কথা ভেবেছে, এটি কেবল সেটুকুই জানে। বাকি সবকিছু তার চোখে অদৃশ্য।

নিউরাল নেটওয়ার্ক

নিউরাল নেটওয়ার্ক কেবল মূল্যায়নটিকেই বদলে দেয়। অনুসন্ধান যেমন ছিল ঠিক তেমনই থাকে — নেটওয়ার্ক চাল বাছে না, সে সেকেন্ডে বহুবার একটিই প্রশ্নের উত্তর দেয়: এই অবস্থানটি কতটা ভালো?

• ইনপুট হলো বোর্ড নিজেই। ঘুঁটি আছে 18 রকমের — বোড়ে, ঘোড়া, গজ, নৌকা, মন্ত্রী, রাজা আর তিনটি যৌগিক ঘুঁটি, দুই রঙে — আর ঘর 64টি: 18 × 64 = 1152টি হ্যাঁ-না প্রশ্ন, যেমন “f3-এ কি সাদা ঘোড়া আছে?”। সাধারণ একটি অবস্থানে এদের প্রায় 32টির উত্তর “হ্যাঁ”। যৌগিক ঘুঁটিগুলো আলাদা ইনপুট, অন্য ঘুঁটির মিশেল নয়, তাই নেটওয়ার্ক নিজের মতো করেই শেখে একটি মহারাজার মূল্য কত।
• দুই দৃষ্টিকোণই। বোর্ড দু'বার ঢোকে: যার চাল সে যেভাবে দেখে, আর আয়নার মতো উল্টে, প্রতিপক্ষ যেভাবে দেখে। নেটওয়ার্ককে কখনো দাবা দু'বার শিখতে হয় না, একবার সাদার জন্য আর একবার কালোর জন্য।
• নিউরনগুলো প্রোগ্রাম করা নয়। কোনো নিউরনকে কেউ বলে দেয় না কী খুঁজতে হবে। প্রশিক্ষণের সময় তারা নিজেরাই একেকটি শনাক্তকারী হয়ে ওঠে — অনেকটা “বোড়ের আড়ালহীন রাজা” বা “সপ্তম সারিতে পৌঁছে যাওয়া নৌকা”-র মতো।

কেন এটি দ্রুত

নেটওয়ার্কের নাম NNUE, যার পূর্ণরূপ Efficiently Updatable Neural Network — দক্ষভাবে হালনাগাদযোগ্য নিউরাল নেটওয়ার্ক। প্রথম স্তরটি একটি টেবিল, যাতে প্রতিটি ইনপুটের জন্য সংখ্যার একটি কলাম, আর নিউরনগুলো কেবল সেই ইনপুটগুলোর কলামের যোগফল, যাদের উত্তর “হ্যাঁ”। একটি চাল মাত্র দুই থেকে চারটি ইনপুট বদলায়, তাই যোগফল কখনো নতুন করে গোনা হয় না — সেটি হালনাগাদ করা হয়:

সবকিছু হিসাব হয় ছোট পূর্ণসংখ্যায়, প্রসেসরের ভেক্টর নির্দেশ দিয়ে একসঙ্গে অনেকগুলো করে। আমাদের মাপে, নেটওয়ার্কসহ ইঞ্জিন একই অনুসন্ধান-গভীরতায় পৌঁছায় হাতে লেখা মূল্যায়নের চেয়ে প্রায় দ্বিগুণ দ্রুত (আমাদের বেঞ্চমার্ক অবস্থানগুলোয় 0.95 বনাম 2.0 সেকেন্ড, আমাদের পরীক্ষার যন্ত্রের একটি কোরে)।

এটি কীভাবে শেখে

প্রশিক্ষণের প্রতিটি উদাহরণ হলো দুটি লেবেলসহ একটি অবস্থান: কয়েক চাল গভীর একটি অনুসন্ধান তাকে যে স্কোর দিয়েছিল, আর খেলাটি শেষমেশ কীভাবে শেষ হয়েছিল। নেটওয়ার্ক এক নজরেই দুটোই আন্দাজ করতে শেখে। পুরো কৌশলটা এখানেই: অনুসন্ধান যখন নেটওয়ার্ককে কোনো অবস্থান নিয়ে প্রশ্ন করে, উত্তরের মধ্যেই থাকে আরও গভীরে দেখলে যা পাওয়া যেত, যেন অনুসন্ধান বিনা খরচে আরও দূর পর্যন্ত গেছে।

ইঞ্জিন শেখে কেবল নিজের খেলা থেকে, যৌগিক ঘুঁটি আর নিজের বাহিনীসহ — অন্য কোনো ইঞ্জিনের বিশ্লেষণ এতে ঢোকে না। নতুন নেটওয়ার্ক রাখা হয় কেবল তখনই, যখন সে কয়েকশো খেলার ম্যাচে আগেরটিকে হারায়। এ পর্যন্ত প্রতিটি দফা আগেরটির চেয়ে স্পষ্টভাবেই শক্তিশালী হয়েছে:

এই সংখ্যাগুলো এসেছে আমাদের নিজেদের ইঞ্জিনের বিভিন্ন সংস্করণের মধ্যে চিরায়ত ওপেনিং থেকে শুরু হওয়া খেলা থেকে, ম্যাচপ্রতি 600টি খেলা। নিজের সঙ্গে খেলায় উন্নতি সাধারণত বাড়িয়ে দেখায়; বাইরের একটি ইঞ্জিনের বিরুদ্ধে মাপ আছে ইঞ্জিনের শক্তির পাতায়।

এখন কোথায় দাঁড়িয়ে

• চতুর্থ নেটওয়ার্কটি ইঞ্জিনে বসানো হয়েছে। 2500 শক্তিতে বসানো Fairy-Stockfish-এর বিরুদ্ধে সে 55% পয়েন্ট পায়, অর্থাৎ ওই মাপকাঠিতে প্রায় 2535; একই পরীক্ষায় হাতে লেখা মূল্যায়ন পৌঁছায় প্রায় 2210-এ।
• নেটওয়ার্ক রূপভেদকে চিরায়ত দাবার মতো ভালো চেনে না। যেসব নিজের বাহিনীতে সে শিখেছে, সবই এসেছে আমাদের জেনারেটর থেকে, কোনো খেলোয়াড়ের কাছ থেকে নয়, তাই এই শুরুর অবস্থানগুলো কিছুটা কৃত্রিম। আসল খেলোয়াড়েরা কেমন বাহিনী সাজাতেন, তা আমরা এখনো জানি না। তার ওপর রূপভেদ খেলাটাই বেশি কঠিন: ঘুঁটির ধরন বেশি, আর প্রায় প্রতিটি খেলায় নতুন শুরুর অবস্থান।
• খেলোয়াড়দের খেলা এখনো সংগ্রহ করা হয় না। পরিকল্পনা হলো, সার্ভার সেইসব খেলা রাখবে যেখানে খেলোয়াড় স্তর 5 বেছে নিয়ে নিজের বাহিনী দিয়ে ইঞ্জিনকে হারিয়েছেন। এটি এখনো সম্ভব নয়। একটি নেটওয়ার্কের শেখার জন্য কয়েক কোটি অবস্থান দরকার — চতুর্থটি শিখেছে 6.8 কোটি থেকে — আর খেলোয়াড়েরা এখনো রূপভেদের এত খেলা খেলেননি যে তা জোগানো যায়।