實驗8 搜索技術

一、實驗目的
（1）掌握搜索技術的相關理論，能根據實際情況選取合適的搜索方法；
（2）進一步熟悉盲目搜索技術，掌握其在搜索過程中的優缺點；
（3）掌握啟發式搜索的思想，能針對實際問題選取合適的評價函數；
（4）掌握問題歸約的解決問題的思想，掌握與或圖的搜索技術并能應用；
（5）深入理解博弈樹搜索方法，并能應用于對弈類問題；
（6）根據自身情況，能選擇合適的編程語言，實現啟發式搜索、博弈樹搜索方法、α-β剪枝算法，并能應用于實際AI問題。

二、實驗內容
選擇一種編程語言（最好為python或java），編程實現下面題目要求。
1、八數碼難題
在3×3的棋盤上，擺有八個棋子，每個棋子上標有1至8的某一數字。棋盤中留有一個空格，空格可用0來表示。空格周圍的棋子可以移到空格中。要求解的問題是：給出一種初始布局（初始狀態）和目標布局，找到一種啟發式移動方法，實現從初始布局到目標布局的轉變，并與實驗7 的盲目移動方法對比。

1、需求分析
在一個3×3的九宮格棋盤上，擺有8個正方形方塊，每一個方塊都標有1~8中的某一個數字。棋盤中留有一個空格，要求按照每次只能將與空格相鄰的方塊與空格交換的原則，將任意擺放的數碼盤（初始狀態）逐步擺成某種給定的數碼盤的排列方式（目標狀態）。

2、數據結構、功能模塊設計與說明
運用啟發式搜索，利用問題擁有啟發信息引導搜索，以達到減小搜索范圍、降低問題復雜度的目的。在啟發式搜索過程中，要對Open表進行排序，這就要有一種方法來計算待擴展結點有希望通向目標結點的不同程度，人們總是希望找到最有可能通向目標結點的待擴展結點優先擴展。一種最常用的方法是定義一個評價函數對各個結點進行計算，其目的就是用來估算出“有希望”的結點。用f來標記評價函數，用f(n)表示結點n的評價函數值，并用f來排列等待擴展的結點，然后選擇具有最小f值的結點作為下一個要擴展的結點。
A*算法是一種有序搜索算法，其特點在于對評價函數的定義上。這個評估函數f使得在任意結點上其函數值f(n)能估算出結點S到結點n的最小代價路徑的代價與從節點n到某一目標節點的最小代價路徑的代價的總和，也就是說f(n)是約束通過結點n的一條最小代價路徑的代價的估計。

3、核心代碼（不要將全部代碼貼在報告上）與測試結果說明
核心代碼：
定義A*算法

def A_start(start, end, distance_fn, generate_child_fn, time_limit=10):# 創建起始狀態結點和目標狀態結點對象，并分別計算其哈希值root = State(0, 0, start, hash(str(BLOCK)), None)end_state = State(0, 0, end, hash(str(GOAL)), None)# 檢查起始狀態是否就是目標狀態，如果是，則直接輸出提示信息if root == end_state:print("start == end !")# 將起始狀態結點加入到OPEN表中，并對OPEN表進行堆化操作OPEN.append(root)heapq.heapify(OPEN)# 創建一個哈希集合，用于存儲已經生成的狀態結點的哈希值，并將起始狀態結點的哈希值添加到集合中node_hash_set = set()node_hash_set.add(root.hash_value)# 記錄算法開始的時間start_time = datetime.datetime.now()# 進入主循環，直到OPEN表為空（搜索完成）或達到時間限制while len(OPEN) != 0:top = heapq.heappop(OPEN)# 如果當前結點就是目標狀態結點，則直接輸出路徑if top == end_state:return print_path(top)# 產生孩子節點，孩子節點加入OPEN表generate_child_fn(cur_node=top, end_node=end_state, hash_set=node_hash_set,open_table=OPEN, dis_fn=distance_fn)# 記錄當前時間cur_time = datetime.datetime.now()# 超時處理，如果運行時間超過了設定的時間限制，則輸出超時提示信息并返回if (cur_time - start_time).seconds > time_limit:print("Time running out, break !")print("Number of nodes:", SUM_NODE_NUM)return -1# 如果循環結束時OPEN表為空，則表示沒有找到路徑，輸出提示信息并返回-1print("No road !")  # 沒有路徑return -1

定義曼哈頓距離計算函數

def manhattan_dis(cur_node, end_node):  # 定義一個名為manhattan_dis的函數，接受兩個參數cur_node（當前結點）和end_node（目標結點）# 獲取當前結點和目標結點的狀態矩陣cur_state = cur_node.stateend_state = end_node.statedist = 0N = len(cur_state)  # 獲取狀態矩陣的大小，假設為N# 遍歷狀態矩陣中的每個位置for i in range(N):for j in range(N):# 如果當前結點的值與目標結點的值相等，則跳過當前位置，因為這個位置已經在目標狀態中if cur_state[i][j] == end_state[i][j]:continuenum = cur_state[i][j]  # 獲取當前結點在狀態矩陣中的值# 如果當前結點的值為0（空白格），則將目標位置設置為狀態矩陣的右下角if num == 0:x = N - 1y = N - 1# 如果當前結點的值不為0，則根據當前結點的值計算其目標位置，假設目標位置為（x,y）else:x = num / Ny = num - N * x - 1# 計算當前結點與目標位置之間的曼哈頓距離，并累加到總距離中dist += (abs(x - i) + abs(y - j))# 返回計算得到的曼哈頓距離作為當前結點到目標結點的估計代價
return dist

生成子結點函數

def generate_child(cur_node, end_node, hash_set, open_table, dis_fn):# 如果當前結點就是目標結點，則直接將目標結點假如OPEN表，并返回，表示已經找到了解if cur_node == end_node:heapq.heappush(open_table, end_node)return# 獲取當前結點狀態矩陣的大小num = len(cur_node.state)# 遍歷當前結點狀態矩陣的每一個位置for i in range(0, num):for j in range(0, num):# 如果當前位置不是空格，則跳過，因為空格是可以移動的位置if cur_node.state[i][j] != 0:continue# 遍歷當前位置的四個鄰居位置，即上下左右四個方向for d in direction:x = i + d[0]y = j + d[1]if x < 0 or x >= num or y < 0 or y >=num:continue# 記錄生成的結點數量global SUM_NODE_NUMSUM_NODE_NUM += 1# 交換空格和鄰居位置的數字，生成一個新的狀態矩陣state = copy.deepcopy(cur_node.state)state[i][j], state[x][y] = state[x][y], state[i][j]# 計算新狀態矩陣的哈希值，并檢查是否已經在哈希集合中存在，如果存在則表示已經生成過相同的狀態，跳過h = hash(str(state))if h in hash_set:continue# 將新狀態的哈希值添加到哈希集合中，計算新狀態結點的gn（從起始結點到當前結點的代價）和hn（當前結點到目標結點的估計代價）hash_set.add(h)gn = cur_node.gn + 1hn = dis_fn(cur_node, end_node)# 創建新的狀態結點對象，并將其加入到當前結點的子結點列表中，并將其加入到OPEN表中。node = State(gn, hn, state, h, cur_node)cur_node.child.append(node)heapq.heappush(open_table, node)

結果：

4、實驗存在的問題與體會
學會了用A算法解決搜索問題，在搜索的時候比之前的盲目搜索用時更少，在其他搜索問題上用A算法也可以比盲目搜索更有效率，但前提是找到合適的估計函數。

2、編程實現一字棋游戲人機對弈，在九宮格棋盤上人機輪流在棋盤上擺各自的棋子，每次一枚，誰先取得三子一線結果的一方獲勝。 （請用極小極大值搜索算法或α-β剪枝算法實現）

1、需求分析
用極小極大值搜索算法或α-β剪枝算法編程實現一字棋游戲人機對弈，在九宮格棋盤上人機輪流在棋盤上擺各自的棋子，每次一枚，誰先取得三子一線結果的一方獲勝。
2、數據結構、功能模塊設計與說明
關于核心判斷部分 maxmin()解釋：

該函數根據當前游戲狀態的得分，計算出下一步應該走的位置。該函數的參數如下：

board：表示當前的游戲狀態，是一個 3x3 的二維數組。
depth：表示搜索的深度，即預測未來多少步。
alpha：表示當前最好的評分（對于 maximizing 玩家來說），初始化為負無窮。
beta：表示當前最好的評分（對于 minimizing 玩家來說），初始化為正無窮。
maximizing：表示當前是輪到哪個玩家走棋，True 表示 maximizing 玩家，False 表示 minimizing 玩家。
該函數的返回值包括兩個元素：

best_score：表示當前的最優得分。
best_move：表示當前應該走的位置。
在函數內部，首先使用 check_win 和 check_tie 函數判斷當前游戲狀態，如果存在勝負或平局，則返回對應的得分。如果還沒有到達搜索的深度，則進入下一步的搜索。

如果當前是 maximizing 玩家，則使用 for 循環遍歷棋盤中所有空位，對于每個空位，都假設 maximizing 玩家會走這個位置，并計算下一步的得分。如果得分比當前最優得分更好，則更新最優得分和最優位置。同時，更新 alpha 的值為當前最優得分和 alpha 中的最大值。如果 beta 的值小于或等于 alpha，則可以停止搜索并返回結果。

如果當前是 minimizing 玩家，則與 maximizing 玩家的情況類似，只是更新的是 beta 的值。
最終返回當前的最優得分和最優位置。

3、核心代碼（不要將全部代碼貼在報告上）與測試結果說明
核心代碼：
minmax函數

# 極大極小/α-β剪枝算法
def minmax(board, depth, alpha, beta, maximizing):if check_win(board, "X"):return -10, Noneif check_win(board, "O"):return 10, Noneif check_tie(board):return 0, Noneif maximizing:best_score = -math.infbest_move = Nonefor row in range(3):for col in range(3):if board[row][col] == " ":board[row][col] = "O"score, _ = minmax(board, depth - 1, alpha, beta, False)board[row][col] = " "if score > best_score:best_score = scorebest_move = (row, col)alpha = max(alpha, best_score)if beta <= alpha:breakreturn best_score, best_moveelse:best_score = math.infbest_move = Nonefor row in range(3):for col in range(3):if board[row][col] == " ":board[row][col] = "X"score, _ = minmax(board, depth - 1, alpha, beta, True)board[row][col] = " "if score < best_score:best_score = scorebest_move = (row, col)beta = min(beta, best_score)if beta <= alpha:breakreturn best_score, best_move

結果：

4、實驗存在的問題與體會
掌握了極大極小值搜索算法和α-β算法的算法思想。