cs50ai0-------Search

cs50ai0-------Search

基础知识

(1) search problem

上图是搜索问题的一般形式
每个名词具体解释如下：
initial state：state是agent与environment的一个配置或者说构造，initial state就是初始的state
actions：在state下可以做出的所有action
transition model：
对在任何state下执行可执行的action所产生的状态的描述
goal test：确认当前state是否是goal state
path cost function：与某一个path相关的cost
(2) dfs与bfs

上图就是dfs与bfs的具体算法流程
首先从一个包含着initial state的frontier与空的explored set开始，从frontier中安照规则移除一个node(包含parent state，当前state，以及从parent到当前node的action)，拓展该node，将拓展得到的不在frontier中和explored set中的node加入frontier，重复上述操作，直到frontier为空或者到达目标state
区别就是frontier采用的数据结构不同，dfs是stack，bfs是queue
(3) greedy best-first search(gbs)与A*搜索
上面提到的dfs与bfs属于无信息搜索即盲目搜索
而贪心搜索属于有信息搜索也叫启发式搜索
具体定义为：
扩展最接近目标的节点的搜索算法，这个最接近的节点由启发式函数 h(n) 估计

如上图所示在迷宫问题中的h(n)是到目标的manhattan距离

但是贪心搜索可能导致找到的是局部最优解，不是全局最优路径
而A*搜索则是使用g(n)与h(n)来计算path cost

相当于已经走过的cost和估计的cost之和

A*算法是最优的在如下所示的情况下：

要h(n)要满足不过分估计同时保持一致性
这一点我理解的不是很清楚?

(4)对抗性搜索或者说博弈？?
重要元素：
s0:初始state
Player(s)：定义此时该谁动
Actions(s):此状态下的合法移动集合
Result(s,a):转移模型，定义行动的结果
Terminal(s)：终止测试，游戏结束返回真，否则假。
Utility(s)：效用函数，定义游戏者p在终止状态s下的数值

minmax算法就是其中的一种

如上面几张图所示
极大极小核心算法建立在尽力削弱对手的value上面
比如说下面这颗树：

箭头向上表示该player要最大化得分
向下则表示要最小化得分
那么player想要自己的得分最大，要考虑对手的想法，需要遍历对手的每一种action，比如说让对手走4这颗子树，会产生4 8 5这三种结果，对手绘最小化自己的得分，所以自己最终会得到四分，同样其它两颗子树自己会得到3和2分，应该选择最大的4这颗子树

而这种算法的问题也很明显，遍历对手的所有想法，树的深度一增加，复杂度就会指数倍上升，因此就有了两种方法来解决此问题
一个是剪枝，即假如我们已经能提前估计下面这颗子树的效果不如当前最好的子树效果好，我们可以直接将整颗子树放弃掉
一个是限制树的深度，比如说就限制树只要十层，这里需要额外的一个evaluate function，来估计某个state下预期的utility，从而提前做出action

课后题目

(1)degrees
文件说明：机翻稍改?
small与big是两组csv数据文件

现在，打开small/stars.csv。此文件在 people.csv 中的人物和 movie.csv 中的电影之间建立关系。每行都是一对 person_id 值和 movie_id 值。例如，第一行（忽略标题）指出 id 为 102 的人主演了 id 为 104257 的电影。对照 people.csv 和 movie.csv 检查这一点，您会发现这一行表示 Kevin Bacon 主演电影《好人寥寥无几》。

接下来，看一下 Degrees.py。在顶部，定义了多个数据结构来存储 CSV 文件中的信息。名字字典是一种通过名字查找人的方法：它将名字映射到一组相应的 ID（因为多个演员可能具有相同的名字）。people 字典将每个人的 id 映射到另一个字典，其中包含该人的姓名、出生年份以及他们主演的所有电影的集合。电影字典将每个电影的 id 映射到另一个包含该电影标题值的字典，发行年份，以及所有电影明星的阵容。 load_data 函数将数据从 CSV 文件加载到这些数据结构中。

该程序中的主函数首先将数据加载到内存中（加载数据的目录可以通过命令行参数指定）。然后，该函数提示用户输入两个名字。 person_id_for_name 函数检索任何人的 ID（如果多个人具有相同的名称，则处理提示用户进行澄清）。然后该函数调用shortest_path函数来计算两个人之间的最短路径，并打印出该路径。

然而，shortest_path 函数尚未实现。这就是我们要实现的地方

具体说明：
完成shortest_path函数的实现，使其返回从具有source id的人到具有target id的人的最短路径。

假设存在从源到目标的路径，您的函数应返回一个列表，其中每个列表项都是从源到目标的路径中的下一个 (movie_id, person_id) 对。每对应该是两个字符串的元组。
例如，如果shortest_path的返回值为[(1, 2), (3, 4)]，则意味着source与人物2一起主演电影1，人物2与人物4一起主演电影3，人物 4 是target。
如果从source到target有多个最小长度的路径，则您的函数可以返回其中任何一个。
如果两个参与者之间没有可能的路径，则您的函数应返回 None。
您可以调用neighbors_for_person函数，该函数接受一个人的id作为输入，并为与给定人一起主演电影的所有人返回一组（movie_id，person_id）对。
尽管您可以编写其他函数和/或导入其他 Python 标准库模块，但除了 Shortest_path 函数之外，您不应修改文件中的任何其他内容。

提示：
虽然课程中搜索的实现会在节点从边界弹出时检查目标，但您可以通过在将节点添加到边界时检查目标来提高搜索效率：如果检测到目标节点，则无需要将其添加到边界，您只需立即返回解决方案即可。
欢迎您借用和改编课程示例中的任何代码。我们已经为您提供了一个文件 util.py，其中包含 Node、StackFrontier 和 QueueFrontier 的课程实现，欢迎您使用（如果您愿意，也可以进行修改）。

(2)tic-tac-toe
文件说明
该项目中有两个主要文件：runner.py 和 tictactoe.py。 tictactoe.py 包含玩游戏和做出最佳动作的所有逻辑。 runner.py 已为您实现，并且包含运行游戏图形界面的所有代码。完成 tictactoe.py 中所有必需的功能后，您应该能够运行 python runner.py 来与您的 AI 对战！

让我们打开 tictactoe.py 以了解所提供的内容。首先，我们定义三个变量：X、O 和 EMPTY，来表示棋盘可能的移动。

函数initial_state 返回板的起始状态。对于这个问题，我们选择将棋盘表示为三个列表的列表（表示棋盘的三行），其中每个内部列表包含三个值，即 X、O 或 EMPTY。剩下的函数是我们留给您实现的功能

具体说明
完成player、actions、result、winner、terminal、utility和minimax的实现。

player：应将board作为输入，并返回轮到哪个玩家了（X 或 O）。在初始游戏状态下，X 先走一步。随后，玩家交替进行每个额外的动作。
actions：应该返回一组可以在board上执行的所有可能操作。
每个动作应表示为一个元组 (i, j)，其中 i 对应于该移动的行（0、1 或 2），j 对应于该行中与该移动相对应的单元格（也是 0、1 或 2）。可能的移动是棋盘上尚未包含 X 或 O 的任何单元格。
result：将board和action作为输入，并应返回新的board状态，而不修改原始棋盘。
如果action对于board是非法的，应该raise an exception
返回的board应该是通过获取原始输入棋盘并让轮到的玩家在输入动作指示的单元格处移动而产生的棋盘。
重要的是，原始棋盘应保持不变：因为 Minimax 最终需要在计算过程中考虑许多不同的棋盘状态。这意味着简单地更新板本身的单元并不是结果函数的正确实现。在进行任何更改之前，您可能需要先对板进行deep copy。
winner：应接受一个棋盘作为输入，并返回该棋盘的获胜者（如果有）。如果 X 玩家赢得了游戏，您的函数应返回 X。如果 O 玩家赢得了游戏，您的函数应返回 O。
水平、垂直或对角线连续走三步即可赢得比赛。
您可能会假设最多只有一个获胜者。
如果游戏没有获胜者（因为游戏正在进行中，或者因为平局结束），则该函数应返回 None。
terminal：应该接受board作为输入，并返回一个布尔值来指示游戏是否结束。
如果游戏结束，无论是因为有人赢得了游戏，还是因为所有单元格都已填满而没有人获胜，则该函数应返回 True。
否则，如果游戏仍在进行中，该函数应返回 False。
utility：应接受board作为输入并输出该板的utility。
如果 X 赢得了游戏，则效用为 1。如果 O 赢得了游戏，则效用为 -1。如果比赛以平局结束，则效用为 0。
您可能会假设只有当terminal为 True 时才会在板上调用utility。
minimax: 应将board作为输入，并返回玩家在该board上移动的最佳移动。
返回的移动应该是最优动作 (i, j)，这是棋盘上允许的动作之一。如果多个移动同样是最佳的，那么任何一个移动都是可以接受的。
如果该板是terminal，则 minimax 函数应返回 None。
对于接受板作为输入的所有函数，您可以假设它是一个有效的板（即它是一个包含三行的列表，每行具有 X、O 或 EMPTY 三个值）。您不应修改所提供的函数声明（每个函数的参数的顺序或数量）。
一旦所有功能都正确实现，您应该能够run python runner.py 并与您的 AI 比赛。而且，由于井字游戏是双方都发挥最佳表现的平局，所以你永远无法击败人工智能（尽管如果你表现不佳，它可能会打败你！）

e我还真输了一局?

提示
如果您想在不同的 Python 文件中测试函数，可以使用 from tictactoe import initial_state 等行导入它们。
欢迎您向 tictactoe.py 添加其他辅助函数，前提是它们的名称不会与模块中已有的函数或变量名称冲突。
Alpha-beta 剪枝是可选的，可能会让你的 AI 运行更高效！

代码实践

(1)degrees
采用的是bfs，具体思路见上面的算法流程，基本上是一步步对应的，不过多讲解了
具体代码如下：

def shortest_path(source, target):
    """
    Returns the shortest list of (movie_id, person_id) pairs
    that connect the source to the target.

    If no possible path, returns None.
    """

    # TODO
    start = Node(state=source, parent=None, action=None)
    frontier = QueueFrontier()
    frontier.add(start)
    explore = set()
    while True:
        if frontier.empty():
            return None
        node = frontier.remove()
        if node.state == target:
            ac = []
            while node.parent is not None:
                  ac.append((node.action,node.state))
                  node = node.parent
            ac.reverse()
            return ac
        explore.add(node.state)
        neighbours = neighbors_for_person(node.state)
        for action,state in neighbours:
            if not frontier.contains_state(state) and state not in explore:
                child = Node(state=state, parent=node, action=action)
                frontier.add(child)

(2)tictactoe
前面几个函数都比较简单
minmax函数也是和前面算法流程实现一致
值得注意的是这里并没有使用剪枝函数
还有player的先手判断，涉及到第一步下哪
这里我试了一下发现，如果是ai先手的话运行时间比较慢
感觉是runner.py的逻辑写的有一点问题？

def player(board):
    """
    Returns player who has the next turn on a board.
    """
    ## xo数量判断谁先手，数量一致默认x先手
    xcount = 0
    ocount = 0
    for row in board:
        xcount += row.count(X)
        ocount += row.count(O)
    return X if xcount == ocount else O


def actions(board):
    """
    Returns set of all possible actions (i, j) available on the board.
    """
    ## 返回棋盘上所有可以下的位置
    actionmove = set()
    for row_index, row in enumerate(board):
        for column_index, item in enumerate(row):
            if item is None:
                actionmove.add((row_index, column_index))
    return actionmove


def result(board, action):
    """
    Returns the board that results from making move (i, j) on the board.
    """
    ## 返回做出相应行动的棋盘状态
    player_move = player(board)
    i, j = action
    ## 根据提示这里采用深拷贝
    new_board = deepcopy(board)
    if board[i][j] is not None:
        raise Exception
    else:
        new_board[i][j] = player_move

    return new_board


def winner(board):
    """
    Returns the winner of the game, if there is one.
    """
    # Check rows
    for row in board:
        if all(item == X for item in row):
            return X
        elif all(item == O for item in row):
            return O

    # Check columns
    for col in range(3):
        if all(board[row][col] == X for row in range(3)):
            return X
        elif all(board[row][col] == O for row in range(3)):
            return O

    # Check diagonals
    if board[0][0] == board[1][1] == board[2][2] and board[0][0] in [X, O]:
        return board[0][0]
    if board[0][2] == board[1][1] == board[2][0] and board[0][2] in [X, O]:
        return board[0][2]

    return None  # No winner found


def terminal(board):
    """
    Returns True if game is over, False otherwise.
    """
    if winner(board) is None:
        if not actions(board):
            return True
        else:
            return False
    else:
        return True


def utility(board):
    """
    Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
    """
    if winner(board) == X:
        return 1
    elif winner(board) == O:
        return -1
    elif winner(board) is None:
        return 0


def minimax(board):
    """
    Returns the optimal action for the current player on the board.
    """

    def max_value(board):
        optimal_move = ()
        if terminal(board):
            return utility(board), optimal_move
        else:
            v = -10000
            for action in actions(board):
                minval = min_value(result(board, action))[0]
                if minval > v:
                    v = minval
                    optimal_move = action
            return v, optimal_move

    def min_value(board):
        optimal_move = ()
        if terminal(board):
            return utility(board), optimal_move
        else:
            v = 10000
            for action in actions(board):
                maxval = max_value(result(board, action))[0]
                if maxval < v:
                    v = maxval
                    optimal_move = action
            return v, optimal_move

    curr_player = player(board)

    if terminal(board):
        return None

    if curr_player == X:
        return max_value(board)[1]

    else:
        return min_value(board)[1]