井字棋 tictactoe 极大极小算法 α-β剪枝算法【python】

文章目录一、实验内容二、极大极小算法和α-β剪枝算法总结1.极大极小算法2.α-β剪枝三、实验步骤以及结果1.极大极小算法完成井字棋游戏2.α-β剪枝四、结果、反思与分析1.极大极小算法运行结果、发现的问题与解决方式2.α-β剪枝运行结果、发现的问题与解决方式3.极大极小算法和α-β剪枝的比较总结一、实验内容实验利用极大极小算法和α-β剪枝算法完成对井字游戏的实现。大家首先下载对应代码；另外需要安

秋千的千秋

10866人浏览 · 2021-11-29 11:12:19

秋千的千秋 · 2021-11-29 11:12:19 发布

一、实验内容

实验利用极大极小算法和α-β剪枝算法完成对井字游戏的实现。
大家首先下载对应代码；另外需要安装pygame库；pipinstall pygame
项目中主要包含两个文件 runner.py and tictactoe.py。

其中：tictactoe.py 包含了玩游戏的所有逻辑和函数类等；runner.py是已经实施好的，主要提供了一些图形界面。大家需要做的是将 tictactoe.py中的对应虚拟函数进行实现。若完成了tictactoe.py 中的函数的实现，则可以通过执行 python runner.py来运行游戏来和 AI 进行对弈。
在 tictactoe.py 中：首先定义了三个变量: X, O, and EMPTY,来表示棋盘上可能的走子。棋盘用一个包含三个 list 的 list 来表示，其中的每个 list 表示棋盘上的一行；例如：初始状态为：[[EMPTY, EMPTY, EMPTY], [EMPTY, EMPTY, EMPTY], [EMPTY, EMPTY, EMPTY]]

tictactoe.py 中有关函数的说明：

player function 应该接受棋盘状态作为输入，返回现在该哪方走棋 (either X or O).初始状态下，X 方先走棋。然后轮流走。如果传入的是一个终局状态（游戏已结束状态），则任何返回值都是可以的。
actions function 应该返回在当前状态下可能的行为。每个行为应该被表示为一个元组 (i, j)，i 对应于移动的行 (0, 1, or 2)，j 对应于在该行的哪个单元对应于移动 (also 0, 1, or 2)。可能的移动是任何棋盘上的空的格子（没有 X 或 O 在其中的格子）；如果传入的是终局状态，则任何返回值都是可以的。
result function 接受棋盘和一个行为作为输入，返回一个新的棋盘状态，注意：不要修改传入的初始的棋盘。如果行为不是一个合法的行为，你应该 raise anexception。强调：初始的棋盘不应被修改：你的 result函数不能简单的更新棋盘状态中cell 的值，而应该在做任何更改时先做一个 a deep copy of the board . The winner function接受一个棋盘作为输入，若该状态是终止状态则返回赢家。（X 或 O）。（若三个相同的棋子在水平、竖直或斜向连接，则赢），若没有赢家，返回 None。
terminal function 接受一个棋盘作为输入，并返回布尔值表明该状态是否终局状态。（要么一方赢了，或者棋盘被填满了；此时应返回 True，否则返回 False）。
The utility function 接受一个终局棋盘状态作为输入并输出该状态的效用值。（若 X 赢，效用值 1；若 O 赢，-1；其他 0）你可以认为该函数知识在终局状态才被调用（即：terminal(board) is True 时才被调用）。
The minimax function 接受棋盘作为输入，返回对当前玩家的最佳移动。返回的移动应该是最佳移动(i, j)，若过个移动都是最优，则任何一个都是可以的。若传入的棋盘是终止状态，则 minimax function 应该返回 None。

在编写 minimax 函数时，可以参照课堂上老师给定伪代码，根据该伪代码，还应该写两个函数分别是：求极大值的函数 max-value 和求极小值的函数min-value 函数。
Alpha-beta 剪枝算法：
定义函数，利用 alpha-beta 剪枝算法来实现搜索树的动态剪枝。请按照老师课堂上给定伪代码来编写该算法。

二、极大极小算法和α-β剪枝算法总结

1.极大极小算法

对于一棵博弈树，我们检测最优策略的方式可以按照极大极小值来决定。两个游戏者始终按照最优策略的方式行棋，Max优先移动到具有极大值的状态，而Min最先移动到有极小值的状态。
为了计算极大极小的得分，我们需要定义一个估价函数，通过端结点的估值计算出父节点的得分。
具体的伪代码如下：

2.α-β剪枝

α-β剪枝是在极大极小算法上的改进方法，剪掉不影响决策的分支，从而提高博弈树搜索的效率。
它是一种边生成结点，边估值和倒推值得方法。在这个过程中会剪掉某些分支。
α指的是到目前为止路径上发现的极大值的最佳选择。Β指的是到目前为止路径上发现的极大值的最佳选择。
α剪枝指的是——若任何“与”结点的β值无法降低其父结点的α值，则对该节点的其余分支结点可以停止搜索，并记录它的倒推值为β。β剪枝指的是——若任何“或”结点的α值无法降低其父结点的β值，则对该节点的其余分支结点可以停止搜索，并记录它的倒推值为α。
进行剪枝至少需要一部分的搜索树生长到最大深度，可以剪去子树。

三、实验步骤以及结果

1.极大极小算法完成井字棋游戏

根据题目中给出的描述信息，我们需要对tictactoe.py中的函数进行补充，均在题目中给出，在此就不多做赘述。传入函数的参数有board是一个二维的列表，还有action是表示行为的一个坐标元组。返回的信息分别有布尔变量，board，0、1、-1，或者行为action。
补充完的代码如下：


import math
import copy

X = "X"
O = "O"
EMPTY = None


def initial_state():
    """
    Returns starting state of the board.
    """
    return [[EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY]]


def player(board):
    """
    Returns player who has the next turn on a board.
    """
    x_num = 0
    o_num = 0
    for i in board:
        for j in i:
            if j == "X":
                x_num += 1
            elif j == "O":
                o_num += 1
    if x_num == 0 and o_num == 0:
        return X
    elif x_num > o_num:
        return O
    elif x_num == o_num:
        return X


def actions(board):
    """
    Returns set of all possible actions (i, j) available on the board.
    """
    action_list = []
    for a in range(3):
        for b in range(3):
            if board[a][b] == EMPTY:
                action_list.append((a, b))
    return action_list


def result(board, action):
    """
    Returns the board that results from making move (i, j) on the board.
    """
    board_copy = copy.deepcopy(board)
    add = player(board_copy)
    board_copy[action[0]][action[1]] = add
    return board_copy


def winner(board):
    """
    Returns the winner of the game, if there is one.
    """
    '''行'''
    for i in board:
        if i[0] == i[1] == i[2]:
            return i[0]
    '''列'''
    for j in range(3):
        if board[0][j] == board[1][j] == board[2][j]:
            return board[0][j]
    '''对角线'''
    if board[0][0] == board[1][1] == board[2][2]:
        return board[0][0]
    if board[0][2] == board[1][1] == board[2][0]:
        return board[0][2]
    return None


def terminal(board):
    """
    Returns True if game is over, False otherwise.
    """
    if winner(board) is not None:
        return True
    else:
        for i in board:
            for j in i:
                if j == EMPTY:
                    return False
        return True


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

然后我们需要依据上课所学的内容和上述伪代码进行相应的补充，需要注意的是，由于我们选择的玩家角色不同，则一个对应极大方，一个对应极小方。在此我们应当对行棋方的角色进行判断。



def minimax(board):
    """
    Returns the optimal action for the current player on the board.
    """
    a = actions(board)
    v11 = float('-inf')
    v12 = float('inf')
    judge_for_player = player(board)
    if judge_for_player is X:
        # print(judge_for_player)
        for i11 in a:
            # print(result(board, i11))
            v1_every = min_value(result(board, i11))
            # print(v1_every)
            if v11 <= v1_every:
                v11 = v1_every
                marks = i11
        # print(marks, v11)
    else:
        # print(judge_for_player)
        for i12 in a:
            # print(result(board, i12))
            v2_every = max_value(result(board, i12))
            # print(v2_every)
            if v12 >= v2_every:
                v12 = v2_every
                marks = i12
        # print(marks, v12)
    return marks


def max_value(board):
    if terminal(board):
        return utility(board)
    v2 = float('-inf')
    for i2 in actions(board):
        v2_every = min_value(result(board, i2))
        if v2 <= v2_every:
            v2 = copy.deepcopy(v2_every)
    return v2


def min_value(board):
    if terminal(board):
        return utility(board)
    v3 = float('inf')
    for i3 in actions(board):
        v3_every = max_value(result(board, i3))
        if v3 >= v3_every:
            v3 = copy.deepcopy(v3_every)
    return v3

2.α-β剪枝

同理，剪枝算法是在极大极小算法的基础上进行优化，所以其大体思路于极大极小算法类似。我们在此基础上，依据课堂上讲的伪代码进行编写。需要注意在为代码中判断action时，我们同样需要在第一步极大极小的算法设计中带入通过result函数中依据行为action返回的新board。


def alphbetaSearch(board):
    """
    v ←MaxValue（board，-∞，+∞）
    Returns the action in actions(board) with value v.
    """
    a = actions(board)
    v11 = float('-inf')
    v12 = float('inf')
    judge_for_player = player(board)
    if judge_for_player is X:
        # print(judge_for_player)
        for i11 in a:
            v1_every = min_value_ab(result(board, i11), v11, v12)
            if v11 <= v1_every:
                v11 = v1_every
                marks = i11
        return marks
    else:
        # print(judge_for_player)
        for i12 in a:
            v2_every = max_value_ab(result(board, i12), v11, v12)
            if v12 >= v2_every:
                v12 = v2_every
                marks = i12
        return marks


def max_value_ab(board, alph, beta):
    if terminal(board):
        return utility(board)
    v2 = float('-inf')
    for i2 in actions(board):
        v2 = max(v2, min_value_ab(result(board, i2), alph, beta))
        if v2 >= beta:
            return v2
        alph = max(alph, v2)
    return v2


def min_value_ab(board, alph, beta):
    if terminal(board):
        return utility(board)
    v3 = float('inf')
    for i3 in actions(board):
        v3 = min(v3, max_value_ab(result(board, i3), alph, beta))
        if v3 <= alph:
            return v3
        beta = min(beta, v3)
    return v3

最后我们还需要在runner.py中加入剪枝算法的方法即可进行游戏。

'''极大极小算法和 Alpha-beta 剪枝算法'''
move = ttt.minimax(board)
# move = ttt.alphbetaSearch(board)
board = ttt.result(board, move)

四、结果、反思与分析

1.极大极小算法运行结果、发现的问题与解决方式

在实验中，我最初未对玩家进行判断，单纯套用方法进行代码编写。通过测试和不断对错误状态的分析，最终发现了需要对玩家进行判断。
错误的结果有如下几种，分别对应——由于没判断玩家而导致的使玩家轻松获胜和对角线判断胜利代码错误。

在这里插入图片描述

以下是正确的结果。

玩家使用X棋的平局状态。
玩家使用O棋平局状态。
玩家使用X棋输局状态。
玩家使用O棋输局状态。
不存在玩家使用X棋赢局状态。
不存在玩家使用O棋的赢局状态。

2.α-β剪枝运行结果、发现的问题与解决方式

剪枝里面发现的问题就是上文中提到的内容——需要注意在为代码中判断action时，我们同样需要在第一步极大极小的算法设计中带入通过result函数中依据行为action返回的新board。
其具体结果于极大极小算法相似，在此不做图片描述。

3.极大极小算法和α-β剪枝的比较

从完备性和最优性角度上分析，两个算法都可以满足寻找最优解的过程。
从时间复杂度角度上分析：极大极小算法是
在这里插入图片描述
,α-β剪枝在最好的顺序下是

。可见优化策略有一定的效果。
从空间复杂度角度上分析：极大极小算法是

（当一次性生成所有后继时）、

（当一次性生成一个后继时）。