দাবা খেলার সাথে আমরা সবাই কম বেশি পরিচিত। এটি অত্যন্ত জনপ্রিয় একটি বোর্ড গেম। দাবার উৎপত্তি সম্পর্কে সঠিক তথ্য পাওয়া না গেলেও খেলার পাশাপাশি বিভিন্ন ধরণের বুদ্ধিবৃত্তিক‌‌ ধাঁধায় দাবাকে ব্যবহার করা হয়। তার মধ্যে একটি N-Queen হিসেবে পরিচিত।

N-Queen

N-Queen হলো এমন একটি চ্যালেঞ্জ যেখানে N টি রাণী (queen) কে একটি N x N দাবার বোর্ডে এমন ভাবে বসাতে হবে যেন কোন রাণী অন্য কোন রাণীর চলার পথে না থাকে বা কাটতে না পারে। দাবা খেলায় রাণী সবচেয়ে শক্তিশালী  হিসাবে গন্য বলে উক্ত কাজটি যথেষ্টই কঠিন। বিশ্বাস না হলে একটি সাধারণ দাবার বোর্ড নিয়ে এখনই চেষ্টা করে দেখতে পারো। সাধারণ দাবার বোর্ড হয় ৮ x ৮ ঘরের।

জেনেটিক অ্যালগোরিদম (Genetic Algorithm)

Genetic Algorithm সম্পর্কে বিস্তারিত জানতে পড়ে আসতে পারো এই ব্লগটি। অমিত ভাইয়ার লেখা ব্লগটিতে অত্যন্ত চমৎকার ভাবে genetic algorithm এর সকল ধাপ এবং সেই ধাপের করণীয় বর্ণনা করা আছে। তাই আমি সরাসরি হাতের সমস্যা সমাধানের pseudo code দেখিয়ে সমাধান প্রক্রিয়ায় চলে যাবো।

অ্যালগোরিদম (Algorithm)

  1. Random solution তৈরি করা
  2. র‍্যান্ডম সমাধানের ফিটনেস বের করা
  3. ন্যাচারাল সিলেকশনের সাহায্যে ন্যূনতম ফিটনেসের নিচের সমাধান বাদ দেয়া
  4. থেকে যাওয়া সমাধানের সেট থেকে র‍্যান্ডম কাপল নিয়ে ক্রসওভার করানো
  5. ক্রসওভারের সময় দৈবচয়ন ভিত্তিতে মিউটেশন করানো
  6. সমাধান না পাওয়া পর্যন্ত করতে থাকা।

কিছু পূর্ববিবেচনা (Pre-Assumptions)

সমাধান করার পূর্বে আমরা কিছু জিনিস ধরে নিতে হবে।

দাবার বোর্ড প্রকাশক

দাবার বোর্ড

‌একটি সাধারণ দাবার বোর্ডে যেকোন গুটির অবস্থান কার্তেশিয় স্থানাংকের মত প্রকাশ করা হয়- যেমন A1, B2, C3 ইত্যাদি। সবগুলোই একটি করে চলমান ধারা (a - h, উক্ত ছবির বোর্ডের জন্য) এবং (1 - N, N হচ্ছে ঘরের সংখ্যা)।‌‌ যেহেতু আমাদের সমস্যার ক্ষেত্রে সমাধান এবং বোর্ডের মাত্রা সমান তাই আমরা চাইলে একটি N সাইজের array দিয়ে একটি সমাধানকে প্রকাশ করতে পারি। যেমন-

নমুনা সমাধান

এই ছবির সমাধানকে আমরা প্রকাশ করতে পারি এইভাবে - [6, 3, 7, 4, 1, 5, 2]। বলাই বাহুল্য এখানে বাম থেকে ডানে রয়েছে [a - g] এবং উপর থেকে নিচে [1 - 7] এবং এটি একটি 7 x 7 দাবার বোর্ড। সুবিধার্থে আমরা আমাদের সমাধান এইভাবেই প্রকাশ করবো এখন থেকে।

সমাধান সেট (Population)

যেকোন সময়ে থাকা সমাধানের সেটকে আমরা Population বলব। এই পপুলেশন সেটের উপরেই আমাদের যাবতীয় মেথড ব্যবহার করা হবে।

সমাধান সেট আকার (Population Size)

প্রোগ্রাম শুরুর সময়ে পপুলেশনে কতগুলো সমাধান থাকবে।

সর্বোচ্চ বাধা সংখ্যা (Maximum Conflict)

দাবার রানী গুটিটির পথ হয় এরকম -

রাণীর পথ

সুতরাং এই পথের যেকোন এক ঘরে যদি আরেকটি রানী থাকে তাহলে গুটি ২টিই একে অপরের পথে পড়েছে বলা যায় সেক্ষেত্রে এটিকে আমরা ২টি কনফ্লিক্ট বা সংঘর্ষ বলতে পারি।

  • ১টি কুইনের জন্য ম্যাক্সিমাম কনফ্লিক্টঃ ০
  • ২টির জন্য: ১
  • ... ...
  • ... ...
  • ৮টির জন্যঃ ২৮

তাহলে এরকম Nটি কুইনের জন্য একটি বোর্ডে সর্বোচ্চ NC2 টি কনফ্লিক্ট সম্ভব। তাহলে আমরা যেকোনো N সাইজের বোর্ডের ম্যাক্সিমাম বের করার জন্য নিমোক্ত মেথডটি লিখে ফেলতে পারি -

def ncr(n, r):
    def fact(n):
        res = 1
        for i in range(2, n + 1):
            res = res * i
        return res
    return (fact(n) // (fact(r) * fact(n - r)))

ফিটনেস (Fitness)

যেকোন genetic algorithm এর সমাধান প্রকাশে ফিটনেস ফাংশনের গুরত্ব অপরিসীম। ফিটনেস দিয়ে বোঝানো হয় প্রদত্ত সমাধানটি কতটা উপযুক্ত। আমাদের দাবার জন্য ফিটনেসের প্রকাশক হচ্ছে প্রদত্ত সমাধানে কতগুলো কুইন অন্য কোন কুইনের চলার পথে পরেনি। অর্থাৎ যদি কোন বোর্ডের সমাধানের জন্য কুইনদের কনফ্লিক্ট স্কোর শূন্য হয় তাহলে সেটিই আমাদের সমাধান। তবে আমাদের ফিটনেস ফাংশনটি একটু ভিন্ন ভাবে কাজ করবে এখানে আমরা প্রাপ্ত সমাধানের কনফ্লিক্টকে ম্যাক্সিমাম কনফ্লিক্ট এর ব্যবধান হিসেবে পাঠাব। তাহলে আমাদের ফিটনেস ফাংশনটি দাঁড়াচ্ছে -

def fitness (self, arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if math.fabs(arr[i] - arr[j]) == j - i or arr[i] == arr[j]:
                count += 1
    return self.maximum_conflict - count

মেথডটি একটি ক্লাসের অংশ যেখানে maximum_conflict একটি ভ্যারিয়েবল।

ন্যাচারাল সিলেকশন (Natural Selection)

যেসব সমাধান threshold এর নিচে থাকবে তাদের বাদ দেয়ার জন্য আমরা এই মেথডটি ব্যবহার করবো-

def naturalselection(self):
    # only keep the solution that matches the minimum fitness threshold
    self.current_solutions = [x for x in self.current_solutions if self.fitness(x) >= self.threshold]
    if len(self.current_solutions) == 0:
        self.current_solutions = self.generateRandomSolution(self.population_size)

যদি কোন population এর জন্য ন্যাচারাল সিলেকশনের পরে কোন সমাধান অবশিষ্ট না থাকে তাহলে আমরা নতুন দৈব সমাধান দিয়ে নতুন পপুলেশন তৈরি করব।

ক্রসওভার (Crossover)

এই ধাপের প্রধান উদ্দেশ্য বর্তমান সমাধানগুলো ব্যবহার করে নতুন সমাধানের পপুলেশন বের করা। এটি কয়েকটি ধাপে সম্পন্ন হয় -

  • প্রথমে আমরা বর্তমান সমাধানের সেট থেকে দৈব পদ্ধতিতে কাপল বা জোড়া তৈরি করবো-
def getrandomcouples(self):
    number_couple = self.population_size // 2      
    couples = []
    for i in range(number_couple):
        all_couples = list(combinations(self.current_solutions, 2))
        if len(all_couples) == 0:
            break
        random_selection = random.randint(0, len(all_couples)-1)
        chosen_couple = all_couples[random_selection]
        # removing the chosen solutions from current solutions 
        self.removeSolution(chosen_couple[0])
        self.removeSolution(chosen_couple[1])
        
        couples.append(chosen_couple)
    return couples

def removeSolution(self, sol):
    index_sol = self.current_solutions.index(sol)
    solution_current_length = len(self.current_solutions)
    self.current_solutions = self.current_solutions[0 : index_sol] + self.current_solutions[index_sol + 1: solution_current_length]

উক্ত মেথডে আমরা প্রথমে সমাধানের সেট থেকে সকল জোড়ার একটি লিস্ট তৈরি করি। সেখান থেকে আমরা র‍্যান্ডম জোড়া নেই। এখানে আমরা যেই পূর্ব সমাধান ব্যবহার করছি তাকে বাদ দিয়ে দিচ্ছি। এতে করে আমাদের সমাধানের সেট এর আকার সব সময় সমান থাকছে। যদিও তার প্রয়োজন নেই।

  • জোড়াগুলোর ব্যবহার করে নতুন সমাধানের সেট তৈরি করা হবে -
def reproduce(self, parent1, parent2):
    break_point = random.randint(0, len(parent1) - 1)
    parent_length = len(parent1)
    child_1 = parent1[0: break_point] + parent2[break_point: parent_length]
    if random.random() < self.MUTATION_PROBABILITY:
        child_1 = self.mutate(child_1)
    child_2 = parent2[0: break_point] + parent1[break_point: parent_length]
    if random.random() < self.MUTATION_PROBABILITY:
        child_2 = self.mutate(child_2)
    return [child_1, child_2]
  • মিউটেশনঃ reproduce এর সময় দৈব ভাবে কোন একটি সমাধানের মধ্যে কোন পরিবর্তন করা হয় একে মিউটেশন বলা হয়। এর জন্য আমরা এই মেথডটি ব্যবহার করতে পারি -
def mutate(self, sol):
    n = random.randint(0, len(sol) - 1)
    val = random.randint(1, self.N)
    sol[n] = val
    return sol

এখানে আমরা প্রদত্ত সমাধানের একটি ইনডেক্স এর মান পরিবর্তন করে র‍্যান্ডম একটি মান বসিয়ে দিব।

  • এখন আমরা উপরোক্ত এলগোরিদম এ মেথডগুলো ব্যবহার করে সমাধান বের করতে পারবো।

সিমুলেশন

এখন আমরা উক্ত সমাধানের একটি সিমুলেশন এই ভিডিওতে দেখতে পারি। এখানে লাল রঙ দিয়ে লেখা ফিটনেসসহ সমাধানটি আমাদের প্রাপ্ত সমাধান।

সম্পূর্ণ কোড

সম্পূর্ণ কোডে আমি PyGame ব্যবহার করে সিমুলেশন সহ দেখিয়েছি। সম্পূর্ণ কোড এখানে পাওয়া যাবে।