Hill-climbing Algorithm for 8-Queens Problem

Stuart Russell နဲ့ Peter Norvig တို့ ရေးသားတဲ့၊ “Artificial Intelligence: A Modern Approach, Fourth Edition” စာအုပ် ရဲ့၊ "CHAPTER 4 SEARCH IN COMPLEX ENVIRONMENTS" အခန်းမှာ ပါတဲ့ "Hill-climbing Algorithm" ကို "8-queens problem" နဲ့ ပေါင်းစပ်ပြီး အပြည့်အစုံ ရှင်းလင်းတင်ပြပေးပါမယ်။

Figure 4.3 (က) ဘုရင်မ ၈-ပါးပြဿနာ။ ဘုရင်မ ၈-ပါးကို စစ်တုရင်ဘုတ်ပေါ်တွင် ဘုရင်မတစ်ပါးနှင့်တစ်ပါး မတိုက်ခိုက်စေရန် ထားပါ။ (ဘုရင်မသည် အတန်း၊ ကော်လံ သို့မဟုတ် ထောင့်ဖြတ် ပေါ်ရှိ မည်သည့် အရာကိုမဆို တိုက်ခိုက်နိုင်ပါသည်။) ပုံတွင် ထောင့်ဖြတ်မျဉ်းတစ်လျှောက်တွင် တစ်ခုနှင့်တစ်ခု တိုက်ခိုက်နေသော စတုတ္ထနှင့် သတ္တမကော်လံရှိ ဘုရင်မနှစ်ပါးမှလွဲ၍ ဤအနေအထားသည် အဖြေတစ်ခု ရလုနီးပါးအဆင့်ဖြစ်သည်။ 

(ခ) heuristic cost estimate [current state အတွက်၊ ကျန်ရှိနေသေးတဲ့ ပဋိပက္ခ conflicts အရေအတွက် ကို တိုင်းတာတဲ့ဖန်ရှင်] h = 17 ပါသော ဘုရင်မ ၈-ပါးအခြေအနေ။ လက်ရှိအခြေအနေ။ စစ်တုရင်ဘုတ်သည် ၎င်း၏ကော်လံအတွင်း ဘုရင်မတစ်ပါးကို ရွှေ့ခြင်းဖြင့် ရရှိနိုင်သော ဆက်ခံသူတိုင်းအတွက် h ၏တန်ဖိုးကို ပြသည်။ h = 12 ဖြင့် အကောင်းဆုံးတွဲဖက်ထားသော ရွေ့လျားမှု ၈-ခုရှိသည်။ hill-climbing algorithm သည် ဤအရာများထဲမှ တစ်ခုကို ရွေးပါမည်။

(နည်းသစ်ဉာဏ်ရည်တုပညာမိတ်ဆက်, စာ-၁၆၀)

ပြီးပြည့်စုံသောအခြေအနေ တည်ဆောက်ခြင်း (Complete-state Formulation)

8-queens ပြဿနာကို ဖြေရှင်းရာမှာ နည်းလမ်းအမျိုးမျိုးရှိပါတယ်။ ဥပမာ - ဘုတ်ပြားအလွတ်ကနေ စပြီး ဘုရင်မ တစ်ပါးချင်းစီကို အဆင့်လိုက် နေရာချသွားတဲ့ နည်းလမ်းရှိသလို၊ ယခု ကျွန်တော်တို့ အသုံးပြုမယ့် Complete-state formulation လိုမျိုး နည်းလမ်းလည်း ရှိပါတယ်။

Complete-state formulation ဆိုတာ အစကတည်းက စစ်တုရင်ဘုတ်ပြားပေါ်မှာ ကော်လံ (Column) တစ်ခုကို ဘုရင်မတစ်ပါးစီနှုန်းနဲ့ ၈ ပါးလုံးကို နေရာချထားလိုက်ခြင်းပါ။ ဆိုလိုတာက အခြေအနေတိုင်းမှာ အဖြေတစ်ခု ဖြစ်လာဖို့ လိုအပ်တဲ့ "အစိတ်အပိုင်းများ အားလုံး (ဘုရင်မ ၈ ပါးလုံး)" ပါရှိနေပြီးသား ဖြစ်ပါတယ်။ ဒါပေမဲ့ ၎င်းတို့ဟာ အချင်းချင်း တိုက်ခိုက်နိုင်တဲ့ (စားနိုင်တဲ့) နေရာတွေမှာ ရှိနေနိုင်တဲ့အတွက် အားလုံးက မှန်ကန်တဲ့ နေရာမှာတော့ ရှိမနေသေးပါဘူး။ ကျွန်တော်တို့ရဲ့ အဓိက ရည်ရွယ်ချက်က အဲဒီ ပဋိပက္ခ (Conflicts) တွေကို တစ်ဆင့်ချင်း လျှော့ချသွားဖို့ပဲ ဖြစ်ပါတယ်။

---

Heuristic Cost Estimate

Hill-climbing (တောင်တက်ခြင်း) အယ်လဂိုရီသမ်က အကောင်းဆုံး အဖြေကို ရှာဖွေဖို့ Heuristic cost ကို အသုံးပြုပါတယ်။ 8-queens ပြဿနာအတွက် Heuristic ဆိုတာ "လက်ရှိအခြေအနေမှာ အချင်းချင်း တိုက်ခိုက်နေတဲ့ (စားလို့ရနေတဲ့) ဘုရင်မ စုံတွဲအရေအတွက် (Number of attacking pairs)" ကို တွက်ချက်တာပါ။ ပဋိပက္ခ လုံးဝမရှိတဲ့ ပြီးပြည့်စုံတဲ့ အဖြေမှန်ကို ရဖို့ဆိုရင် ဒီ Cost တန်ဖိုးက 0 ဖြစ်သွားရပါမယ်။

Python Code

 
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 21 20:59:50 2026
@author: kks
"""
import random
# ဘုရင်မ ၈ ပါးရဲ့ အခြေအနေကို list တစ်ခုအနေနဲ့ ဖော်ပြပါမယ်။
# ဥပမာ - state = [3, 0, 4, 7, 5, 2, 6, 1] ဆိုပါစို့။
# index (0 မှ 7 အထိ) က ကော်လံ (Column) ကို ကိုယ်စားပြုပြီး၊ 
# ထိုနေရာရှိ တန်ဖိုးက အဲဒီကော်လံမှာရှိတဲ့ ဘုရင်မရဲ့ အတန်း (Row) ကို ကိုယ်စားပြုပါတယ်။
# ဒါဟာ Complete-state formulation ကို ကိုယ်စားပြုတဲ့ အကောင်းဆုံး Data Structure ဖြစ်ပါတယ်။
def calculate_conflicts(state):
    """
    Heuristic cost estimate function ပါ။
    လက်ရှိ board အခြေအနေ (state) မှာ အချင်းချင်း တိုက်ခိုက်နိုင်တဲ့ ဘုရင်မ စုံတွဲ အရေအတွက်ကို တွက်ချက်ပေးပါတယ်။
    """
    conflicts = 0
    n = len(state)
    for i in range(n):
        for j in range(i + 1, n):
            # တိုက်ခိုက်နိုင်ခြေ (၂) မျိုးကို စစ်ဆေးရပါမယ်။
            # ၁။ အတန်း (Row) တူနေသလား စစ်ဆေးခြင်း -> state[i] == state[j]
            # ၂။ ထောင့်ဖြတ် (Diagonal) တူနေသလား စစ်ဆေးခြင်း -> abs(state[i] - state[j]) == abs(i - j)
            # မှတ်ချက် - ကော်လံ (Column) ကတော့ Array ရဲ့ Index မတူတဲ့အတွက် အမြဲတမ်း ကွဲပြားနေပြီးသားပါ။
            if state[i] == state[j] or abs(state[i] - state[j]) == abs(i - j):
                conflicts += 1
    return conflicts
def get_best_neighbor(state):
    """
    လက်ရှိအခြေအနေကနေ သွားနိုင်တဲ့ အိမ်နီးချင်း (Neighbors) ၅၆ ခုထဲက
    conflicts အနည်းဆုံးဖြစ်မယ့် အကောင်းဆုံး အိမ်နီးချင်းကို ရှာဖွေပေးပါတယ်။
    (ကော်လံ ၈ ခုမှာရှိတဲ့ ဘုရင်မတွေကို ကိုယ်ပိုင်ကော်လံအတွင်း အခြား row ၇ ခုဆီ တစ်ပါးချင်း ရွှေ့ကြည့်ခြင်းဖြစ်ပါတယ်၊ ၈ x ၇ = ၅၆)
    """
    best_neighbors = []
    # လက်ရှိ cost ကို အနည်းဆုံး cost အဖြစ် အရင်သတ်မှတ်ထားပါမယ်။
    min_conflicts = calculate_conflicts(state)
    n = len(state)
    for col in range(n):
        for row in range(n):
            if state[col] == row:
                continue # လက်ရှိရှိနေတဲ့နေရာကို ရွှေ့စရာမလိုလို့ ကျော်သွားပါမယ်
            # အိမ်နီးချင်း အခြေအနေသစ် တစ်ခု ဖန်တီးပါမယ်
            neighbor = list(state)
            neighbor[col] = row
            
            # အိမ်နီးချင်းအသစ်ရဲ့ Heuristic cost (conflicts) ကို တွက်ချက်ပါမယ်
            neighbor_conflicts = calculate_conflicts(neighbor)
            if neighbor_conflicts < min_conflicts:
                # ပိုကောင်းတဲ့ အခြေအနေ (conflicts ပိုနည်းတဲ့ အခြေအနေ) ကို တွေ့ရင်
                min_conflicts = neighbor_conflicts
                best_neighbors = [neighbor] # တွေ့ထားသမျှ အကောင်းဆုံး list ကို အသစ်ပြန်စပါမယ်
            elif neighbor_conflicts == min_conflicts:
                # တူညီတဲ့ အကောင်းဆုံး အခြေအနေတွေကို list ထဲ ထပ်ထည့်ပါမယ်
                best_neighbors.append(neighbor)
    # အကောင်းဆုံး အိမ်နီးချင်းတွေထဲက တစ်ခုကို ကျပန်းရွေးချယ်ပါမယ်
    if best_neighbors:
        return random.choice(best_neighbors), min_conflicts
    else:
        return state, min_conflicts # ပိုကောင်းတဲ့ အိမ်နီးချင်း မရှိရင် လက်ရှိကိုပဲ ပြန်ပေးပါမယ်
def hill_climbing(initial_state):
    """
    Steepest-ascent Hill-climbing algorithm ရဲ့ အဓိက အပိုင်းဖြစ်ပါတယ်။
    """
    current_state = initial_state
    current_conflicts = calculate_conflicts(current_state)
    step = 0
    print(f"Step {step}: Initial State = {current_state}, Conflicts = {current_conflicts}")
    while True:
        # အကောင်းဆုံး အိမ်နီးချင်းကို ရှာပါမယ်
        neighbor, neighbor_conflicts = get_best_neighbor(current_state)
        # Hill-climbing ရဲ့ အားနည်းချက် သဘောတရားအရ၊ ပိုကောင်းတဲ့ အိမ်နီးချင်း မရှိတော့ရင် (သို့) 
        # လက်ရှိထက် ပဋိပက္ခ မနည်းတော့ဘူးဆိုရင် တောင်ထိပ် (Local Maxima သို့မဟုတ် Global Maxima) ကို ရောက်ပြီဖြစ်လို့ ဆက်မရှာဘဲ ရပ်ပါမယ်။
        if neighbor_conflicts >= current_conflicts:
            print(f"\nSearch stopped. Reached a peak (cost cannot be decreased further).")
            break
        # အခြေအနေသစ်ကို ပြောင်းလဲပါမယ်
        current_state = neighbor
        current_conflicts = neighbor_conflicts
        step += 1
        print(f"Step {step}: Moved to = {current_state}, Conflicts = {current_conflicts}")
    return current_state, current_conflicts
# ပရိုဂရမ် စတင်ခြင်း
if __name__ == "__main__":
    # Complete-state formulation အရ ဘုရင်မ ၈ ပါးကို ကျပန်း နေရာချပါမယ်
    # (ကော်လံတစ်ခုစီအတွက် row 0 ကနေ 7 အထိ ကျပန်းရွေးချယ်ပါမယ်)
    initial_board = [random.randint(0, 7) for _ in range(8)]
    
    print("--- Hill-Climbing Algorithm for 8-Queens ---")
    final_state, final_cost = hill_climbing(initial_board)
    
    print("\n--- Final Result ---")
    print(f"Final State: {final_state}")
    print(f"Remaining Conflicts: {final_cost}")
    
    if final_cost == 0:
        print("Success! A complete solution without any conflicts was found.")
    else:
        print("Failed to find a perfect solution. Got stuck in a Local Maximum.")
        print("(မှတ်ချက် - ရိုးရှင်းသော Hill-climbing သည် တောင်ကုန်းငယ်များ (Local Maxima) တွင် ပိတ်မိလေ့ရှိပါသည်။ ၎င်းသည် ဤ Algorithm ရဲ့ သဘာဝ အားနည်းချက်ဖြစ်ပါသည်။)")

ပရိုဂရမ် အနှစ်ချုပ်

ဒီပရိုဂရမ်က၊ ဘုရင်မ ၈ ပါးကို ကျပန်းချထားခြင်းမှ စတင်ပြီး၊ တစ်ဆင့်ချင်းစီမှာ၊ အချင်းချင်းတိုက်ခိုက်မှု (Conflicts) အနည်းဆုံးဖြစ်စေမဲ့ အိမ်နီးချင်းအခြေအနေဆီသို့ ရွှေ့လျားသွားပါတယ်။ တိုက်ခိုက်မှု လုံးဝမရှိတော့သည့် အခြေအနေ (သို့မဟုတ်) ထပ်မံ၍ လျှော့ချ၍ မရနိုင်တော့သည့် အခြေအနေ (Local Maxima) သို့ရောက်သောအခါ ရပ်တန့်သွားမှာဖြစ်ပါတယ်။

နောက် ပို့စ်မှာ Hill-Climbing ရဲ့ အဓိကပြဿနာဖြစ်တဲ့ "Local Maxima မှာ ပိတ်မိတတ်ခြင်း" ကို ဖြေရှင်းပေးနိုင်တဲ့ "Random-restart hill-climbing" အကြောင်းကိုဆက်လက်တင်ပြပေးပါမယ်။

Inductive Logic Programming (ILP)

REF:

AIMA 4th Edition

Chapter 20 Knowledge in Learning

20.5 Inductive Logic Programming

p-758

                                 Inductive Logic Programming (ILP) ဟူသည် စက်သင်ယူမှု (Machine Learning) နှင့် လောဂျစ်ပရိုဂရမ်ရေးသားခြင်း (Logic Programming) တို့ကို ပေါင်းစပ်ထားသော ပညာရပ်တစ်ခု ဖြစ်ပါတယ်။ ၎င်းသည် "နမူနာများမှတစ်ဆင့် ယေဘုယျကျသော စည်းမျဉ်းများကို လောဂျစ်နည်းကျ ဖော်ထုတ်ခြင်း" ဟု အဓိပ္ပာယ်ရတယ်။ အောက်မှာ ILP ရဲ့ လက်တွေ့လုပ်ဆောင်ပုံကို အတိုချုပ်ပြီး အဆင့်ဆင့် ရှင်းလင်းတင်ပြပေးလိုက်ပါတယ်။

---

ILP ၏ လက်တွေ့လုပ်ဆောင်ပုံ (Step-by-Step)

ILP စနစ်တစ်ခု အလုပ်လုပ်ရန်အတွက် အဓိက အစိတ်အပိုင်း (၃) ခု လိုအပ်ပါတယ်။

1. နောက်ခံဗဟုသုတ (Background Knowledge - BK) ကျွန်ုပ်တို့ ကြိုတင်သိရှိထားပြီးသား အချက်အလက်များ။
2. အပြုသဘောဆောင်သော နမူနာများ (Positive Examples – E⁺ ) မှန်ကန်ကြောင်း ကျွန်ုပ်တို့ သိရှိသော အချက်များ။
3. အနုတ်လက္ခဏာဆောင်သော နမူနာများ (Negative Examples -E^-) မမှန်ကန်ကြောင်း (သို့မဟုတ်) မဖြစ်နိုင်ကြောင်း ကျွန်ုပ်တို့ သိရှိသော အချက်များ။

ပန်းတိုင်: E⁺ အားလုံးကို ရှင်းပြနိုင်ပြီး E^- တစ်ခုမှ မပါဝင်သော လောဂျစ်စည်းမျဉ်း (Hypothesis - H) ကို ရှာဖွေရန်။

ဥပမာ - "ဘိုးဘွား" (Grandparent) တော်စပ်မှုကို သင်ယူခြင်း

အဆင့် (၁) - အချက်အလက်များ ထည့်သွင်းခြင်း (Inputs)

• BK: parent(maung_maung, zaw_zaw), parent(zaw_zaw, hla_hla) (မောင်မောင်သည် ဇော်ဇော်၏ အဖေ၊ ဇော်ဇော်သည် လှလှ၏ အဖေ)
• E⁺: grandparent(maung_maung, hla_hla) (မောင်မောင်သည် လှလှ၏ ဘိုးဘွားဖြစ်သည် - မှန်)
• E^-: grandparent(hla_hla, maung_maung) (လှလှသည် မောင်မောင်၏ ဘိုးဘွားဖြစ်သည် - မှား)

အဆင့် (၂) - ယူဆချက်ကို စတင်ရှာဖွေခြင်း (Hypothesis Construction)

ILP သည် အောက်ပါအတိုင်း စည်းမျဉ်းများကို စမ်းသပ်ပါမည် -

• ယူဆချက် ၁: grandparent(X, Y) :- parent(X, Y). (X သည် Y ၏ မိဘဖြစ်လျှင် ဘိုးဘွားဖြစ်သည်)
• ရလဒ်: E⁺ ကို မရှင်းပြနိုင်ပါ။ (မောင်မောင်သည် လှလှ၏ မိဘမဟုတ်ပါ)။
• ယူဆချက် ၂: grandparent(X, Y) :- parent(X, Z), parent(Z, Y). (X သည် Z ၏ မိဘဖြစ်ပြီး၊ ထို Z သည် Y ၏ မိဘဖြစ်လျှင် X သည် Y ၏ ဘိုးဘွားဖြစ်သည်)
• ရလဒ်: E⁺ ကို ရှင်းပြနိုင်သည် (မောင်မောင် → ဇော်ဇော် → လှလှ)။ E^- ကိုလည်း ရှောင်လွှဲနိုင်ပါတယ်။

အဆင့် (၃) - ယေဘုယျပြုခြင်း (Generalization)

ရှာဖွေတွေ့ရှိထားသော စည်းမျဉ်းကို အခြားဒေတာအသစ်များတွင် အသုံးပြုနိုင်ရန် အတည်ပြုလိုက်ပါတယ်။ ဤနည်းဖြင့် ILP သည် 'Grandparent' ဆိုသော အဓိပ္ပာယ်ကို ဒေတာများမှတစ်ဆင့် ကိုယ်တိုင် သင်ယူသွားခြင်း ဖြစ်ပါတယ်။

---

လက်တွေ့လုပ်ဆောင်နိုင်သော Python ပရိုဂရမ်

လက်တွေ့မှာ ILP ကို Prolog ဘာသာစကားနဲ့ အရေးအများဆုံး ဖြစ်ပေမဲ့, Python တွင် Kanren သို့မဟုတ် SymPy တို့ကဲ့သို့သော Logic library များ ရှိပါတယ်။ ဒီနေရာမှာ ILP ရဲ့ သဘောသဘာဝကို နားလည်စေဖို့ Simple Rule Learner ပုံစံမျိုးကို Python ဖြင့် ဖန်တီးပြပါမယ်။ 

ဒီပရိုဂရမ်က ပေးထားသော မိဘတော်စပ်မှု (Parent) ဒေတာများမှ ဘိုးဘွားတော်စပ်မှု (Grandparent) စည်းမျဉ်းကို အလိုအလျောက် ရှာဖွေပေးပါမယ်။

 

Python
# Simple ILP-style Rule Learner in Python
 
class SimpleILP:
    def __init__(self, background_knowledge, pos_examples, neg_examples):
        self.bk = background_knowledge
        self.pos = pos_examples
        self.neg = neg_examples
 
    def test_rule(self, rule_func):
        # အပြုသဘောဆောင်သော နမူနာအားလုံး မှန်ရမည်
        for p in self.pos:
            if not rule_func(p[0], p[1], self.bk):
                return False
        # အနုတ်လက္ခဏာဆောင်သော နမူနာအားလုံး မှားရမည်
        for n in self.neg:
            if rule_func(n[0], n[1], self.bk):
                return False
        return True
 
# နောက်ခံဗဟုသုတ (Parent Relationship)
# parent(parent_name, child_name)
bk_data = [
    ('Maung Maung', 'Zaw Zaw'),
    ('Zaw Zaw', 'Hla Hla'),
    ('Aung Aung', 'Kyaw Kyaw'),
    ('Kyaw Kyaw', 'Mya Mya')
]
 
# သင်ယူရမည့် နမူနာများ (Positive & Negative)
pos_examples = [('Maung Maung', 'Hla Hla'), ('Aung Aung', 'Mya Mya')]
neg_examples = [('Hla Hla', 'Maung Maung'), ('Zaw Zaw', 'Maung Maung')]
 
# စမ်းသပ်မည့် ယူဆချက်များ (Hypotheses)
def hypothesis_1(X, Y, bk):
    # Rule: grandparent(X, Y) :- parent(X, Y)
    return (X, Y) in bk
 
def hypothesis_2(X, Y, bk):
    # Rule: grandparent(X, Y) :- parent(X, Z), parent(Z, Y)
    for parent, child in bk:
        if parent == X:
            Z = child
            if (Z, Y) in bk:
                return True
    return False
 
# ILP Engine စတင်လည်ပတ်ခြင်း
learner = SimpleILP(bk_data, pos_examples, neg_examples)
 
print("--- ILP Learning Process ---")
for i, hyp in enumerate([hypothesis_1, hypothesis_2], 1):
    result = learner.test_rule(hyp)
    status = "Passed ✅" if result else "Failed ❌"
    print(f"Testing Hypothesis {i}: {status}")
    if result:
        print(f"Found Correct Rule: grandparent(X, Y) :- parent(X, Z), parent(Z, Y)")

 ရှင်းလင်းချက်:

1. BK Data မိသားစု ဆက်နွယ်မှုများကို Tuple အဖြစ် သိမ်းထားပါတယ်။
2. SimpleILP Class ၎င်းသည် ပေးထားသော Rule တစ်ခုသည် Positive examples များကို အကုန်လက်ခံပြီး Negative များကို ငြင်းပယ်ခြင်း ရှိမရှိ စစ်ဆေးပေးသည့် "Evaluator" ဖြစ်တယ်။
3. Hypothesis 1 ၎င်းသည် "မိဘဖြစ်လျှင် ဘိုးဘွားဖြစ်သည်" ဟု ယူဆသောကြောင့် စစ်ဆေးမှု ကျရှုံးပါတယ်။
4. Hypothesis 2 ၎င်းသည် "မိဘ၏ မိဘ" (Grandparent) ဖြစ်သည်ကို စစ်ဆေးနိုင်သောကြောင့် စစ်ဆေးမှု အောင်မြင်သွားပါတယ်။

လက်တွေ့အသုံးချမှု

အစစ်အမှန် ILP စနစ်များ (ဥပမာ - Aleph, Metagol) သည် ဤထက်မက ရှုပ်ထွေးသော စည်းမျဉ်းများကို ဒေတာ သန်းပေါင်းများစွာထဲမှ ရှာဖွေနိုင်ပါတယ်။ ၎င်းတို့ကို ဇီဝဗေဒဆိုင်ရာ မော်လီကျူးများ တည်ဆောက်ပုံ လေ့လာခြင်း (Drug discovery) နှင့် သဘာဝဘာသာစကား နားလည်ခြင်း (NLP) တို့တွင် အသုံးချကြပါတယ်။