Build an Unbeatable Computer Game (freeCodeCamp Tic Tac Toe Project)

Collected from http://pictures.4ever.eu/tag/27244/tic-tac-toe

আমরা অনেকেই আছি যারা ফ্রিকোডক্যাম্পের ইন্টারমিডিয়েট এলগোরিদম, সাইমন গেম, প্রোমোডোরো ক্লক ইত্যাদি প্রোজেক্ট বানাতে পারলেও ফ্রিকোডক্যাম্পের ইন্টারমিডিয়েট ফ্রন্টএন্ড ডেভলপমেন্ট প্রোজেক্ট সেকশনের ৩ নম্বর প্রোজেক্ট Tic Tac Toe বানাতে হিমশিম খাই। কিংবা কোড কপিপেস্ট করে অন্যের কোড দিয়ে একটা নড়বড়ে প্রোটোটাইপ দাড়া করাই। তো আজকে আমি Tic Tac Toe বানানোর পেছনে যে লজিক কাজ করছে সেটা আপনাদের বলবো। লজিক জানলে কোড করতে বেশি সময় লাগার কথা না।

ইতিহাস

প্রথমেই আসেন কিছু ইতিহাস জানি। ধারনা করা হয় Tic Tac Toe এর প্রচলন মিশরীয় সভ্যতার থেকে শুরু। ১৯৫২ সালে Alexander S. Douglas নামের এক ভদ্রলোক EDSAC নামের বিশালদেহী এক কম্পিউটারের জন্য University of Cambridge এ বসে সর্বপ্রথম Tic Tac Toe বানান। যেটাকে প্রথম ভিডিও গেম হিসেবে ধরা হয়। তখনকার Tic Tac Toe আনবিটেবল না হলেও সে হিউম্যান প্লেয়ারের বিপক্ষে খেলতে পারতো। আর ৪ কি ৫ বছর আগে আমরা এই Tic Tac Toe গেম স্কুলের ফ্রিটাইমে খাতায় খেলতাম। যার নাম আমরা দিয়েছিলাম “কাটাকাটি”।

EDSAC নামের বিশালদেহী কম্পিউটার

Alexander S. Douglas. এই ভদ্রলোক ই সর্বপ্রথম ভিডিও গেম বানায়।

আমার বানানো Unbeatable Tic Tac Toe Game. এখানে কম্পিউটার O এবং প‌্লেয়ার X

পেপার লজিক

ইতিহাস তো জানা হলো। এবার আসল কথায় আসি। Tic Tac Toe যদি আমরা খাতায় বা কাগজ কলম ব্যবহার করে খেলি তাহলে আমরা কি করবো? আমরা যদি খাতায় খেলি তাহলে আমরা প্রথম চাল দেয়ার পর আমাদের অপরপক্ষ দিত্বীয় চাল র‌্যান্ডমলি দেয়। কিন্তু আমরা যখন ই তৃতীয় চাল দেই তখনি আমাদের বিপরীতপক্ষ দুইটা জিনিস লক্ষ্য করে।

1. আমার দেয়া দুটো চাল এর মাঝে কোনো ফাকা স্থান আছে কিনা। যেখানে আমি পঞ্চম চাল দিলে আমি জিতে যাবো।
2. তার (অপরপক্ষ) এমন কোনো যায়গা আছে কিনা যেখানে সে তার চাল দিলে তার বিজয়ী হতে সুবিধা হয়।

যদি সে উপরের দুইটা শর্তের একটার সাথে মিল পায় তবে সে সেইযায়গায় ই তার চাল দেয়। আর যদি একটাও মিল না থাকে তবে সে আবার র‌্যান্ডমলি একটা চাল দেয়। রুলস অনুযায়ী আমি সর্বোচ্চ ৫টা চাল আর আমার প্রতিপক্ষ সর্বোচ্চ ৪টা মোট ৯টা চাল দিতে পারবো। মানে যে শুরু করবে সে সর্বোচ্চ ৫ আর তার প্রতিপক্ষ সর্বোচ্চ ৪টা চাল দিতে পারবে। এখন আমার প্রতিপক্ষ যখন তার সুবিধা অনুযায়ী চতুর্থ চাল দেয় তখন আবার আমরা পঞ্চম চাল দেয়ার সময় দুইটা জিনিস লক্ষ্য করি।

1. প্রতিপক্ষের দেয়া দুটো চাল এর মাঝে এমন কোনো গ্যাপ বা ফাকা স্থান আছে কিনা যেখানে সে ৬ষ্ঠ চাল দিলে গেইম এ সে জিতে যাবে।
2. এমন কোনো যায়গা বোর্ডে ফাকা আছে কিনা যেখানে আমার বর্তমান (৫ম) চাল দিলে আমি জিতে যাবো।

উপরের দুটোর যেকোনো একটা এবার আমার ক্ষেত্রে কাজ করবে। কেননা পুরো বোর্ডে ফাকা আছে আর মাত্র ৪ টা ঘর। আমাদের যেই শর্ত কাজ করবে আমরা সেই শর্তের পক্ষে আমাদের চাল দেই।

এভাবে যদি দুজন প্লেয়ার ই হুশিয়ার হয়ে খেলে তাহলে প্রতিবার ই গেম ড্র হবে। কেননা আমরা দুজনেই (প্রতিপক্ষ এবং আমি) নিজেদের সুবিধামত চাল দেয়ার পাশাপাশি প্রতিপক্ষের জেতার রাস্তা ব্লক করে যাচ্ছি।

কম্পিউটার লজিক

কম্পিউটার যখন আমাদের প্রতিপক্ষ হবে তখনও পেপার লজিকের প্রতিটা স্টেপ ফলো করবে। তবে এক্ষেত্রে আমাদের (মানে গেম ডেভলপার) বলে দিতে হবে যে কি কি জিনিশ সে চাল দেয়ার আগে খেয়াল করবে। তবে এক্ষেত্রে সামান্য কিছু গন্ডগোল আছে।

বিহাইন্ড দ্যা সিন (মেইন আনবিটেবল লজিক)‌

প্রথমত আমি যখন প্রথম চাল দেবো তখন “দিত্বীয় চাল কম্পিউটার পেপার লজিকের মত র‌্যান্ডমলি ১-৯ এর ভিতর একটা নম্বর জেনারেট করবে। তারপর সে চেক করবে যে সেই নম্বরের ঘর ফাকা আছে কিনা। যদি থাকে তাহলে সেই ঘরে চাল দেবে।”

না। এক্ষেত্রে তা করবে না। আমরা যখনই আমাদের Computer কে আনবিটেবল করবো তখন ই সে পেপার লজিক এর সাথে দুটো স্পেশাল লজিক এর উপর কাজ করবে।

1. প্রথম চাল দেয়ার পর যদি সর্বমাঝখানের ঘর ফাকা থাকে তবে সে সবার প্রথমে সেই ঘর ব্লক করবে।
2. যদি প্লেয়ার মাঝখানের ঘরেই তার প্রথম চাল দেয় তাহলে Computer তার দিত্বীয় চাল র‌্যান্ডমলি না দিয়ে যেকোনো একটা কর্নার ব্লক করবে।

এবার উপরের দুইটি শর্তের ব্যাখ্যায় আসি।

প্রথমত মাঝখানের ঘর যদি আমি (এখানে আমি হলাম Computer) শুরুতেই ব্লক করি তবে প্রতিপক্ষের জেতার সম্ভাবনা ৯০% কমে আসবে। কারন প্রতিপক্ষ যখনই মাঝখানের ঘর ব্লক করবে তখন আমার জেতার চান্স ১০% এ এসে ঠেকবে।

দিত্বীয়ত যদি প্লেয়ার মাঝখানের ঘরেই তার প্রথম চাল দেয় তাহলে আমার উচিত যেকোনো একটা কর্নারপিস ব্লক করা। কারন যখনি প্লেয়ার প্রথম চাল মাঝখানে আর দিত্বীয় চাল কোনায় এবং আমি আমার প্রথম চাল কোনো কর্নারপিস ছাড়া চারটা মিডেল এজড এ দেবো তখন প্লেয়ার তার পক্ষে ৩য় এবং ৪র্থ চাল পাবে। কারন আমি ২য় চালে যদি তার একসাইড উইনিং পজিশন ব্লক করি তবে প্লেয়ার ৪র্থ চালে কর্নার টু কর্নার বা মিডেল এজড টু মিডেল এজড জেতার চান্স পেয়ে যাবে। আর আমরা বোকার মত কপাল চাপড়াবো। নিচের ছবিটা লক্ষ করুনঃ

এখানে O হচ্ছে কম্পিউটারের চাল আর X হচ্ছে প্লেয়ারের চাল। লাল চাল গুলো সম্ভাব্য চাল।

তো উপরের চিত্র অনুযায়ী যদি খেলা হয় তাহলে চালগুলো হবে যথাক্রমেঃ

1. প্লেয়ারের ১ম চাল ১ম ঘর
2. কম্পিউটারের ১ম চাল ৪র্থ ঘর (র‌্যান্ডমলি)
3. প্লেয়ারের ১ম চাল ২য় ঘর
4. কম্পিউটারের ১ম চাল ৩য় ঘর (ব্লকিং লজিক অনুযায়ী)
5. প্লেয়ারের ৩য় চাল ৫ম ঘর

এবার আমি মানে কম্পিউটার এর ক্ষেত্রে একটা বিরাট সমস্যা। আমি যদি এবার আমার ৪র্থ চাল ৮ম ঘরে ব্লক লজিক অনুযায়ী চাল দেই তাহলে প্লেয়ার ৯ম ঘরে চাল দেয়ার জ্যাকপট পাচ্ছে। আর যদি আমি ৯ম ঘরে চাল দেই তাহলে প্লেয়ার ৮ম ঘরে চাল দেয়ার জ্যাকপট পাচ্ছে। কিন্তু আমি যদি মিডেল এজড বা কর্নার এজড আমার প্রথম চালেই ব্লক করতাম তাহলে কি হত?

মিডল এজড ব্লক

কর্নার এজড ব্লক

উপরের দুইটি ছবি লক্ষ্য করলে দেখা যাবে যে যদি মিডল এজড ব্লক করা হয় তাহলে প্লেয়ারের জেতার চান্স ৬০% এ আসে। আর যদি কর্নার এজড ব্লক করা হয় তাহলেও প্লেয়ারের চান্স ৬০% থাকে।

ফিনিশিং টাচ “দ্যা সিক্রেট রুলস”

আমরা উপরের দুইটি ক্ষেত্রেই দেখছি যে প্রতিটা সময় ই প্লেয়ারের চান্স ৬০% আর কম্পিউটারের চান্স ৪০% থাকছে। কিন্তু তাতে আমাদের Game আনবিটেবল হবেনা। কারন কম্পিউটার হলো বোকা যন্ত্র। সে ০ এবং ১ ছাড়া কিছুই বোঝে না। আমাদেরকে প্রতিটা রুলস তাকে শিখিয়ে দিতে হয়। মেইন Tic Tac Toe বানানো হয় আর্টিফিশিয়াল ইন্টিলিজেন্স এর সাহায্যে। এই ব্যাপারে আমি একদম নতুন। আমার কাছের এক বড়ভাই Aniruddha Adhikary তার ব্লগে মেশিন লার্নিং নিয়ে একটা পোস্ট করেছিলেন। সেখানে বিস্তারিত পাবেন। তাই আমি মেশিন লার্নিং টপিক আপাতত স্কিপ করি। তো যা বলছিলাম, আমাদেরকে এমন একটা Game বানাতে হবে যেটাতে প্রতিটা চালেই কম্পিউটার এর জেতার সম্ভাবনা প্লেয়ারের জেতার সম্ভাবনার থেকে বেশি থাকে।

কিভাবে কোড করবো?

মেইন রুলসঃ এইক্ষেত্রে Game কে আনবিটেবল বানাতে সর্বপ্রথম আমাদের Computer কে প্লেয়ারের চাল দেয়ার পরেই মিডল এজড ব্লক করতে হবে। যদি প্লেয়ার মিডেল এজড ব্লক করে তাহলে কোনোদিকে না তাকিয়ে কোনো র‌্যান্ডম জেনারেটেড চাল না দিয়ে সবার আগে যেকোনো একটা কর্নারপিস ব্লক করতে হবে।

সেকেন্ডারি রুলসঃ যদি মিডল এজড ফাকা না থাকে তবে কর্নারপিস ব্লক করার পর আমাদের তৃতীয় চালে দেখতে হবে যে, যদি প্লেয়ারের দুটো চাল কোনোভাবে (লম্বভাবে, আড়াআড়ি, কোনাকোনি) পর পর হয় এবং যদি প্লেয়ারের দেয়া দুটো চাল এর পরের তৃতীয় ঘর ফাকা থাকে তবে কম্পিউটার সেই ঘরে চাল দেবে। আর যদি মিডল এজড প্রথমেই আমরা ব্লক করতে পারি তাহলে তৃতীয় চালে যেকোনো একটা কর্ণারপিস ব্লক করে দিতে হবে। তাহলে প্লেয়ারের জেতার সম্ভাবনা ০% হয়ে যাবে।

ফাইনাল রুলস (দ্যা র‌্যান্ডম চাল)ঃ আর যদি প্লেয়ারের দেয়া দুটো চালই পরপর হয় কিন্তু তৃতীয় ঘরে আগেই আমার চাল দেয়া থাকে তবে র‌্যান্ডম ভাবে একটা ১-৯ এর ভিতর একটা সংখ্যা জেনারেট করে সেই সংখ্যা অনুযায়ী ঘরে চাল দিতে হবে। আর যদি সেই ঘর ও ফাকা না থাকে তবে আবার র‌্যান্ডম ভাবে একটা ১-৯ এর ভিতর একটা সংখ্যা জেনারেট করে সেই সংখ্যা অনুযায়ী ঘরে চাল দিতে হবে। এভাবে যথক্ষন পর্যন্ত ফাকা ঘর না পাওয়া যাবে ততক্ষন পর্যন্ত “র‌্যান্ডম ভাবে একটা ১-৯ এর ভিতর একটা সংখ্যা জেনারেট করে সেই সংখ্যা অনুযায়ী ঘরে চাল দিতে হবে।” এই মেথডের পুনরাবৃত্তি ঘটতে থাকবে। আর প্লেয়ারের দেয়া প্রতিটা চালের পর রুলস ১, ২, ৩ তিনটা রুলস ই প্রতিবার চেক করতে হবে। তবে রুলস ১ ও ২ প্লেয়ারের প্রথম ও দিত্বীয় চাল পর্যন্ত কাজে লাগে। এরপর আর কোনো কাজে আসে না। তাই প্রতিবার চেক করলে স্পিড স্লো হওয়ার একটা পসিবলিটি থাকে। তাই আমরা গ্লোবালি ভাবে ০ মানযুক্ত একটা ভ্যারিয়েবল ডিক্লিয়ার করে প্লেয়ারের প্রতিটা চালে সেটাকে এক করে ইনক্রিমেন্ট করে দিতে পারি। যখনই সেই ভ্যারিয়েবল এর মান ২ এর বেশি হবে তখনই প্রথম দুইটা কন্ডিশন আমরা স্কিপ করে তৃতীয় কন্ডিশন প্রতিবার ফলো করবো। তাতে আমাদের কাজ আরো দ্রুত হবে।

সারমর্ম

এই একটা প্রজেক্ট নিয়ে আমি টানা ৫দিন চেষ্টা করার পর নিজের প্রজেক্ট সাবমিট করেছিলাম। আমি চাইলেই মিনিম্যাক্স এলগোরিদম প্রয়োগ করতে পারতাম। এবং প্রথমবার করেছিলাম ও। কিন্তু পরে ভেবে দেখলাম যে, আমি যদি অন্যের এলগোরিদম না নিয়ে নিজেই কিছু বানাই তবে সেটা হবে সবচেয়ে বেস্ট। তাই সার্টিফিকেট নেয়ার পরেও ৫ দিন ধরে আমি এই সামান্য প্রোজেক্টে আটকে ছিলাম। মিনিম্যাক্স এলগোরিদম এডভান্স লেভেলের জিনিস। পুরোপুরি এডভান্স। তাই আমার মত মিডল ক্লাশ প্রগ্রামার এর জন্য না ওটা। সেই কথা চিন্তা করেই আমার প্রজেক্ট আমি রিকমপ্লিট করি। আমি এই পাঁচদিন মিনিম্যাক্স এলগোরিদম এর উপর প্রায় শ’খানের ভিডিও ও ব্লগপোস্ট পরেছি। কিন্তু সব মাথার উপর দিয়ে উড়াল দিয়েছে।

যাই হোক, শেষ পর্যন্ত আমি নিজের স্কিল অনুযায়ী নিজের থিওরী দাড়া করাতে সক্ষম হয়েছিলাম। আমার অনেক বন্ধুরা আছে যারা আমার সাথে একসাথে ফ্রিকোডক্যাম্প করেছে বা সামনে করবে। এই পোস্ট টা ওইসকল বন্ধুদের জন্য যারা জাভাস্ক্রিপ্টে আমার মত মধ্যম। মানে একেবারে নতুনও না আবার একেবারে প্রো লেভেলের ও না। আশাকরি তাদের সাহায্য হবে। আর পোস্ট এর থিওরী না বুঝলে গুগলে “Tic Tac Toe” লিখে সার্চ দিলে গুগলের ডেভলপ করা একটা Tic Tac Toe গেম আসে সবার প্রথমে। সেই গেম এর “Impossible” মোড অন করে আমার উপরের দেয়া থিওরীর একটা পার্ট এপ্লাই করলেই বাকিটা পরিষ্কার হয়ে যাবে। তাও যদি না বুঝতে পারেন বা পারো তবে কমেন্টে জানালেই হবে। আমি ইনশাআল্লাহ আগামী ১০ তারিখের ভিতরে আমার থিওরীর উপর একটা এনিমেশন বানিয়ে দেবো সবাইকে।

আল্লাহ হাফেজ।