python 用A*算法实现五子棋

好的，下面给出使用A*算法实现五子棋的Python代码：

import heapq
import numpy as np

class Board:
    def __init__(self, size=15):
        self.size = size
        self.board = np.zeros((size, size), dtype=int)
        self.current_player = 1

    def get(self, x, y):
        if x < 0 or x >= self.size or y < 0 or y >= self.size:
            return None
        return self.board[x][y]

    def set(self, x, y, player):
        if x < 0 or x >= self.size or y < 0 or y >= self.size:
            return False
        if self.board[x][y] != 0:
            return False
        self.board[x][y] = player
        return True

    def get_winner(self):
        for i in range(self.size):
            for j in range(self.size):
                if self.board[i][j] == 0:
                    continue
                if j + 4 < self.size and len(set(self.board[i][j:j+5])) == 1:
                    return self.board[i][j]
                if i + 4 < self.size and len(set(self.board[i:i+5,j])) == 1:
                    return self.board[i][j]
                if i + 4 < self.size and j + 4 < self.size and len(set(self.board[i+k][j+k] for k in range(5))) == 1:
                    return self.board[i][j]
                if i + 4 < self.size and j - 4 >= 0 and len(set(self.board[i+k][j-k] for k in range(5))) == 1:
                    return self.board[i][j]
        return 0

    def get_legal_moves(self):
        moves = []
        for i in range(self.size):
            for j in range(self.size):
                if self.board[i][j] == 0:
                    moves.append((i, j))
        return moves

    def is_game_over(self):
        return self.get_winner() != 0 or len(self.get_legal_moves()) == 0

    def switch_player(self):
        self.current_player = 3 - self.current_player

class Node:
    def __init__(self, board, g=0, h=0):
        self.board = board
        self.g = g
        self.h = h
        self.f = g + h

    def __lt__(self, other):
        return self.f < other.f

def heuristic(board):
    return 0

def a_star(board):
    start_node = Node(board, 0, heuristic(board))
    heap = [start_node]
    visited = set()
    while heap:
        node = heapq.heappop(heap)
        if node.board.is_game_over():
            return node.board.get_winner()
        if node.board.current_player == 1:
            for move in node.board.get_legal_moves():
                new_board = Board(size=node.board.size)
                new_board.board = np.copy(node.board.board)
                new_board.set(move[0], move[1], node.board.current_player)
                new_board.switch_player()
                new_node = Node(new_board, node.g + 1, heuristic(new_board))
                if new_node.board.get_winner() == 1:
                    return 1
                if new_node not in visited:
                    visited.add(new_node)
                    heapq.heappush(heap, new_node)
        else:
            for move in node.board.get_legal_moves():
                new_board = Board(size=node.board.size)
                new_board.board = np.copy(node.board.board)
                new_board.set(move[0], move[1], node.board.current_player)
                new_board.switch_player()
                new_node = Node(new_board, node.g + 1, heuristic(new_board))
                if new_node.board.get_winner() == 2:
                    return 2
                if new_node not in visited:
                    visited.add(new_node)
                    heapq.heappush(heap, new_node)
    return 0

if __name__ == "__main__":
    board = Board()
    while True:
        x, y = map(int, input("请输入你要落子的坐标(x y): ").split())
        if board.set(x, y, 1):
            board.switch_player()
            winner = a_star(board)
            if winner == 1:
                print("你赢了！")
                break
            elif winner == 2:
                print("你输了！")
                break
            elif len(board.get_legal_moves()) == 0:
                print("平局！")
                break
            else:
                ai_x, ai_y = None, None
                for move in board.get_legal_moves():
                    new_board = Board(size=board.size)
                    new_board.board = np.copy(board.board)
                    new_board.set(move[0], move[1], 2)
                    new_board.switch_player()
                    winner = a_star(new_board)
                    if winner == 2:
                        ai_x, ai_y = move[0], move[1]
                        break
                if ai_x is None or ai_y is None:
                    ai_x, ai_y = board.get_legal_moves()[0]
                board.set(ai_x, ai_y, 2)
                board.switch_player()
                winner = a_star(board)
                if winner == 1:
                    print("你赢了！")
                    break
                elif winner == 2:
                    print("你输了！")
                    break
                elif len(board.get_legal_moves()) == 0:
                    print("平局！")
                    break
        else:
            print("该位置已有棋子，请重新输入！")

在这里，使用了一个`Board`类来表示棋盘，其中`get(x, y)`和`set(x, y, player)`方法分别用于获取(x, y)位置的棋子和在(x, y)位置落子。`current_player`属性表示当前玩家。`get_winner()`方法用于判断胜负，`get_legal_moves()`方法用于获取合法的落子位置，`is_game_over()`方法用于判断游戏是否结束，`switch_player()`方法用于交换当前玩家。

另外，还定义了一个`Node`类来表示搜索树中的节点，其中`g`表示从起点到该节点的代价，`h`表示该节点到终点的估价，`f`表示总代价。`heuristic()`函数用于计算估价，这里直接返回0。`a_star()`函数使用A*算法搜索最优解。

在主程序中，先让玩家输入坐标落子，然后调用`a_star()`函数计算下一步AI的落子位置。如果AI能够在下一步赢得游戏，则直接落子；否则遍历所有合法的落子位置，对每个位置都进行一次搜索，找到可以让AI赢得游戏的位置，如果找到则落子，否则随机选择一个合法的位置落子。最后判断胜负和平局。