8-Puzzle Solver Part-01

နည်းသစ်ဉာဏ်ရည်တုပညာမိတ်ဆက်၊ အခန်း (၃)၊ စာမျက်နှာ-၈၅ နှင့်

စာ-၄၆၂၊ အသေးစားဉာဏ်ရည်တုပရိုဂရမ် (၂) "8-Puzzle Solver" ကိုကြည့်ပါ။

Stuart Russell နဲ့ Peter Norvig တို့ရဲ့ "Artificial Intelligence: A Modern Approach" စာအုပ်ပါ 8-puzzle ပြဿနာကို ဖြေရှင်းရန်အတွက် အထိရောက်ဆုံးသော နည်းလမ်းမှာ *A Search Algorithm (Informed Search)** ဖြစ်ပါတယ်။

Breadth-First Search (BFS) ကို အသုံးပြုလို့ ရပေမဲ့၊ 8-puzzle ၏ ဖြစ်နိုင်ခြေရှိသော အခြေအနေများ (State Space) က အလွန်များပြားသောကြောင့် (၃၆၂,၈၈၀ ခန့်)၊ BFS ဟာ နှေးကွေးပြီး Memory နေရာများစွာ ယူနိုင်ပါတယ်။ ဒါ့ကြောင့် ပန်းတိုင်ကို ဦးတည်ရှာဖွေနိုင်သော Heuristic (ခန့်မှန်းတွက်ချက်မှု) ပါဝင်တဲ့ *A (A-Star)** နည်းလမ်းကို အသုံးပြုပြီး ဖြေရှင်းပါမယ်။

---

၁။ AI သဘောတရားများ (Problem Formulation)

ကုဒ်မရေးမီ AIMA စာအုပ်ပါ သတ်မှတ်ချက်များအတိုင်း အဓိပ္ပာယ်ဖွင့်ဆိုချက်များကို ကြည့်ကြပါစို့။

• State Representation (အခြေအနေ ဖော်ပြချက်): ၃x၃ ဇယားကွက်ကို ကွန်ပျူတာနားလည်လွယ်စေရန် ကိန်းဂဏန်းများပါသော List တစ်ခုအဖြစ် ပြောင်းလဲပါမည်။ 0 ကို ကွက်လပ် (Blank Space) အဖြစ် သတ်မှတ်သည်။

  • ဥပမာ (ပုံပါ Initial State): [7, 2, 4, 5, 0, 6, 8, 3, 1]

• Initial State (စဦး အခြေအနေ): ပုံ (Figure 3.3) တွင် ပြထားသည့်အတိုင်း - [7, 2, 4, 5, 0, 6, 8, 3, 1]

• Goal State (ပန်းတိုင် အခြေအနေ): ပုံ (Figure 3.3) ၏ ညာဘက်ပုံအတိုင်း (ကွက်လပ် 0 သည် ထိပ်ဆုံးဘယ်ဘက်တွင် ရှိသည်) - [0, 1, 2, 3, 4, 5, 6, 7, 8]

• Actions (ပြုလုပ်နိုင်သော အရာများ): ကွက်လပ် (0) ရွေ့လျားနိုင်သော နေရာများ - Up, Down, Left, Right.

• Transition Model (Successor Function): လက်ရှိ 0 ရှိသော နေရာမှ၊ ဘေးပတ်ဝန်းကျင် ဂဏန်းတစ်ခုနှင့် နေရာချင်းလဲလှယ်ခြင်း (Swap)။

• Cost Function (ကုန်ကျမှု): လှုပ်ရှားမှုတိုင်းအတွက် တန်ဖိုး 1 ဟု သတ်မှတ်သည်။ (g(n) = start node မှ လက်ရှိ node အထိ လာခဲ့ရသော ခြေလှမ်းအရေအတွက်)။

• Heuristic Function (အဆင့်မြင့် AI နည်းစနစ်): A* algorithm ပိုမြန်စေရန် Manhattan Distance ကို အသုံးပြုပါမည်။

  • Manhattan Distance ဆိုသည်မှာ လက်ရှိဂဏန်းတစ်ခုသည် သူရောက်ရမည့် ပန်းတိုင်နေရာနှင့် ဇယားကွက် ဘယ်နှစ်ကွက်ကွာဝေးနေသလဲ ဆိုတာကို တွက်ချက်ခြင်းဖြစ်သည်။ ၎င်းက ရှာဖွေမှုကို လမ်းကြောင်းမှန်ပေါ် ရောက်အောင် လမ်းညွှန်ပေးပါမည်။

---

၂။ Python Program (A* Search Implementation)

ဤပရိုဂရမ်တွင် Priority Queue ကို အသုံးပြုထားပြီး၊ ကုန်ကျစရိတ်အနည်းဆုံးနှင့် ပန်းတိုင်ရောက်နိုင်ခြေ အရှိဆုံး လမ်းကြောင်းကို ဦးစားပေး ရွေးချယ်သွားပါမည်။

Python

import heapq

# ---------------------------------------------------------
# အပိုင်း (၁) - 8-Puzzle ၏ အတန်းအစား (Class) တည်ဆောက်ပုံ
# ---------------------------------------------------------

class PuzzleState:
    def __init__(self, board, parent=None, move="", cost=0):
        self.board = board          # လက်ရှိ ဇယားကွက် အခြေအနေ (Tuple)
        self.parent = parent        # ဘယ်အခြေအနေကနေ ရောက်လာတာလဲ (Backtracking အတွက်)
        self.move = move            # ဘာလုပ်လိုက်လို့ ရောက်လာတာလဲ (Up, Down, etc.)
        self.cost = cost            # g(n): စုစုပေါင်း လာခဲ့ရတဲ့ ခြေလှမ်း (Cost)
        self.heuristic = self.calculate_manhattan() # h(n): ပန်းတိုင်ရောက်ဖို့ ခန့်မှန်းခြေ
        self.f_score = self.cost + self.heuristic   # f(n) = g(n) + h(n)

    def calculate_manhattan(self):
        """
        Manhattan Distance Heuristic တွက်ချက်ခြင်း။
        လက်ရှိဂဏန်းတစ်ခုချင်းစီသည် ပန်းတိုင်တွင်ရှိရမည့်နေရာနှင့် 
        ဘယ်လောက်ဝေးနေသလဲဆိုတာကို ပေါင်းခြင်းဖြစ်ပါသည်။
        """
        distance = 0
        goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]
        
        for i in range(9):
            tile = self.board[i]
            if tile != 0: # ကွက်လပ် (0) ကို ထည့်မတွက်ပါ
                # လက်ရှိ နေရာ (x, y)
                current_row, current_col = divmod(i, 3)
                # ပန်းတိုင်တွင် ရှိရမည့် နေရာ (x, y)
                target_idx = goal_state.index(tile)
                target_row, target_col = divmod(target_idx, 3)
                
                # အကွာအဝေး ပေါင်းထည့်ခြင်း (|x1-x2| + |y1-y2|)
                distance += abs(current_row - target_row) + abs(current_col - target_col)
        return distance

    # Priority Queue အတွက် နှိုင်းယှဉ်မှု (f_score နည်းတာကို ဦးစားပေးမယ်)
    def __lt__(self, other):
        return self.f_score < other.f_score

    def is_goal(self):
        # ပုံပါ Goal State အတိုင်း (0, 1, 2, 3, 4, 5, 6, 7, 8) ဖြစ်မဖြစ် စစ်ဆေး
        return self.board == (0, 1, 2, 3, 4, 5, 6, 7, 8)

    def get_neighbors(self):
        """
        Transition Model:
        ကွက်လပ် (0) ကို ရွှေ့ပြီး ဖြစ်နိုင်ချေရှိသော နောက်ထပ် အခြေအနေများကို ရှာခြင်း
        """
        neighbors = []
        zero_idx = self.board.index(0) # ကွက်လပ်ရှိသော index ကို ရှာမယ်
        row, col = divmod(zero_idx, 3) # (Row, Col) ပြောင်းမယ်

        # ရွေ့နိုင်သော ဦးတည်ချက်များ (Directions)
        directions = {
            "UP": (-1, 0),    # Row လျှော့
            "DOWN": (1, 0),   # Row တိုး
            "LEFT": (0, -1),  # Col လျှော့
            "RIGHT": (0, 1)   # Col တိုး
        }

        for move, (dr, dc) in directions.items():
            new_row, new_col = row + dr, col + dc

            # ဇယားကွက် ဘောင်အတွင်း ရှိနေမှသာ ရွေ့မယ် (0 to 2 range)
            if 0 <= new_row < 3 and 0 <= new_col < 3:
                # Index ပြန်ပြောင်းမယ်
                new_idx = new_row * 3 + new_col
                
                # ဇယားကွက် အသစ်ဖန်တီးမယ် (Swap လုပ်ခြင်း)
                new_board = list(self.board)
                new_board[zero_idx], new_board[new_idx] = new_board[new_idx], new_board[zero_idx]
                
                # State အသစ်ကို List ထဲထည့်မယ်
                neighbors.append(PuzzleState(tuple(new_board), self, move, self.cost + 1))
        
        return neighbors

# ---------------------------------------------------------
# အပိုင်း (၂) - A* Search Algorithm
# ---------------------------------------------------------

def solve_8_puzzle(initial_board):
    start_node = PuzzleState(initial_board)
    
    # Priority Queue (Frontier) - f_score အနည်းဆုံးကို ထိပ်ဆုံးထားမယ်
    frontier = []
    heapq.heappush(frontier, start_node)
    
    # Explored Set (ထပ်မရှာမိအောင် မှတ်သားခြင်း)
    explored = set()
    
    print("Searching for solution using A* Algorithm...")
    
    while frontier:
        # ၁။ f_score အနည်းဆုံး Node ကို ထုတ်ယူမယ်
        current_node = heapq.heappop(frontier)
        
        # ၂။ Goal ရောက်မရောက် စစ်ဆေးမယ် (Goal Test)
        if current_node.is_goal():
            return current_node # အဖြေတွေ့ပြီ
        
        # ၃။ Explored စာရင်းသွင်းမယ်
        explored.add(current_node.board)
        
        # ၄။ Successors (Neighbors) တွေကို ရှာမယ်
        for child in current_node.get_neighbors():
            if child.board not in explored:
                heapq.heappush(frontier, child)

    return None # အဖြေရှာမတွေ့ပါ

# ---------------------------------------------------------
# အပိုင်း (၃) - ရလဒ် ထုတ်ပြခြင်း
# ---------------------------------------------------------

def print_solution_path(node):
    path = []
    while node:
        path.append(node)
        node = node.parent
    path.reverse() # အစ -> အဆုံး ဖြစ်အောင် ပြောင်းပြန်လှန်
    
    print(f"\nSolution Found in {len(path)-1} moves!")
    print("-" * 40)
    
    for i, state in enumerate(path):
        print(f"Step {i}: {state.move if state.move else 'Start'}")
        
        # ဇယားကွက် ပုံစံထုတ်ပြခြင်း
        b = state.board
        print(f"| {b[0]} {b[1]} {b[2]} |")
        print(f"| {b[3]} {b[4]} {b[5]} |")
        print(f"| {b[6]} {b[7]} {b[8]} |")
        print("-" * 13)

# --- Main Execution ---
if __name__ == "__main__":
    # Figure 3.3 တွင် ပါသော Start State
    # 7 2 4
    # 5 0 6
    # 8 3 1
    initial_configuration = (7, 2, 4, 5, 0, 6, 8, 3, 1)
    
    solution_node = solve_8_puzzle(initial_configuration)
    
    if solution_node:
        print_solution_path(solution_node)
    else:
        print("No solution found or puzzle is unsolvable.")

---

၃။ ပရိုဂရမ် လုပ်ဆောင်ပုံ ရှင်းလင်းချက် (မှတ်ချက်များ)

ဤပရိုဂရမ်သည် သာမန် Search ထက် များစွာသာလွန်သော *A (A-Star)** နည်းပညာကို အသုံးပြုထားပါတယ်။

1. Priority Queue (heapq):

   • သာမန် Queue (FIFO) ကိုမသုံးဘဲ၊ Priority Queue ကို သုံးထားပါတယ်။

   • f(n) = g(n) + h(n) တန်ဖိုး အနည်းဆုံးရှိသော State ကို အမြဲတမ်း ဦးစားပေး ထုတ်ယူပြီး ဆက်သွားတယ်။ ဒါကြောင့် လမ်းလွဲတွေကို မသွားဘဲ ပန်းတိုင်ရှိရာဘက်ကို ဦးတည်သွားစေပါတယ်။

2. Manhattan Distance Heuristic:

   • calculate_manhattan function က ပန်းတိုင်ရောက်ဖို့ ဘယ်လောက်နီးစပ်လဲ ဆိုတာကို မှော်မျက်လုံးနဲ့ ကြည့်သလို ခန့်မှန်းပေးတယ်။

   • ဥပမာ- ဂဏန်း '7' သည် လက်ရှိ (၀,၀) မှာ ရှိပြီး သူကပန်းတိုင် (၂,၁) မှာ ရှိရမှာဆိုရင်၊ Manhattan distance သည် |0-2| + |0-1| = 3 ဖြစ်တယ်။

   • ဒီနည်းပညာကြောင့် အေးဂျင့်/ကွန်ပျူတာ ဟာ "မျက်လုံးပိတ် ရှာဖွေခြင်း" (Blind Search) မဟုတ်ဘဲ "အသိဉာဏ်ဖြင့် ရှာဖွေခြင်း" (Informed Search) ဖြစ်လာပါတယ်။

3. State Representation (Tuple):

   • Python တွင် List ကို Set ထဲထည့်၍ မရသောကြောင့် (Un-hashable)၊ Tuple (7, 2, 4, ...) ကို အသုံးပြုထားပါတယ်။ ဒါမှသာ explored set ထဲတွင် ထပ်နေသော အခြေအနေများကို စစ်ဆေးနိုင်မှာ ဖြစ်တယ်။

4. Goal State:

   • AIMA စာအုပ်ပါ ပုံအရ Goal State သည် (0, 1, 2, 3, 4, 5, 6, 7, 8) ဖြစ်ပါသည်။ ပုံမှန် 8-puzzle အချို့တွင် 0 သည် နောက်ဆုံးမှ ရှိတတ်သော်လည်း၊ ဒီပုစ္ဆာတွင် 0 သည် ထိပ်ဆုံးတွင် ရှိရမည်ဟု ပုံက ဆိုလိုသဖြင့် ကုဒ်ကို ပုံအတိုင်း ရေးသားထားပါတယ်။

ဒီကုဒ်ကို Run လိုက်ပါရင် Figure 3.3 ၏ Start State မှ Goal State သို့ ရောက်ရှိရန် အတိုဆုံးလမ်းကြောင်း (Optimal Solution) ကို အဆင့်ဆင့် ထုတ်ပြပေးသွားမှာ ဖြစ်ပါတယ်။