搜索 - 黑白棋 AI 算法

1. 实验介绍

1.1 实验内容

1. 黑方先行，双方交替下棋。

2. 一步合法的棋步包括：

• 在一个空格处落下一个棋子，并且翻转对手一个或多个棋子；

• 新落下的棋子必须落在可夹住对方棋子的位置上，对方被夹住的所有棋子都要翻转过来，可以是横着夹，竖着夹，或是斜着夹。夹住的位置上必须全部是对手的棋子，不能有空格；

• 一步棋可以在数个（横向，纵向，对角线）方向上翻棋，任何被夹住的棋子都必须被翻转过来，棋手无权选择不去翻某个棋子。

1. 如果一方没有合法棋步，也就是说不管他下到哪里，都不能至少翻转对手的一个棋子，那他这一轮只能弃权，而由他的对手继续落子直到他有合法棋步可下。

2. 如果一方至少有一步合法棋步可下，他就必须落子，不得弃权。

3. 棋局持续下去，直到棋盘填满或者双方都无合法棋步可下。

4. 如果某一方落子时间超过 1 分钟 或者 连续落子 3 次不合法，则判该方失败。

1.2 实验要求

• 使用 『蒙特卡洛树搜索算法』 实现 miniAlphaGo for Reversi。

• 使用 Python 语言。

• 算法部分需要自己实现，不要使用现成的包、工具或者接口。

• 请按照 程序报告内容格式要求.docx 编写程序报告；提交程序报告,请在本地编辑并命名为 『程序报告.docx』 或者 『程序报告.pdf』 后，上传到左侧文件列表中。

1.3 注意事项

• Python 与 Python Package 的使用方式，可在右侧 API文档 中查阅。

• 在与人类玩家对奕时，运行环境将等待用户输入座标，此时代码将处于 While..Loop 回圈中，请务必输入'Q'离开，否则将持续系统将等待(hold）。

• 当右上角的『Python 3』长时间指示为运行中的时候，造成代码无法执行时，可以重新启动 Kernel 解决（左上角『Kernel』-『Restart Kernel』）。

2.实验内容

2.1 棋盘介绍

# 导入棋盘文件
from board import Board

# 初始化棋盘
board = Board()

# 打印初始化棋盘
board.display()

2.1.2 棋盘与坐标之间的关系

• board_num(action): 棋盘坐标转化为数字坐标。
• action: 棋盘坐标，e.g. 'G6'
• 返回值: 数字坐标，e.g. (5, 6)

• num_board(action): 数字坐标转化为棋盘坐标。
• action: 数字坐标，e.g. (2, 7)
• 返回值: 棋盘坐标，e.g. 'H3'

# 查看坐标 (4,3) 在棋盘上的位置 
position = (4, 3)
print(board.num_board(position))

# 查看棋盘位置 'G2' 的坐标
position = 'G2'
print(board.board_num(position))

• get_legal_actions(color)： 根据黑白棋的规则获取 color 方棋子的合法落子坐标，用 list() 方法可以获取所有的合法坐标。
• color: 下棋方，'X' - 黑棋，'O' - 白棋
• 返回值: 合法的落子坐标列表

# 棋盘初始化后，黑方可以落子的位置
print(list(board.get_legal_actions('X')))

• _move(action, color)： 根据 color 落子坐标 action 获取翻转棋子的坐标。
• action: 落子的坐标，e.g. 'C4'
• color: 下棋方，'X' - 黑棋，'O' - 白棋
• 返回值: 反转棋子棋盘坐标列表

# 打印初始化后的棋盘
board.display()

# 假设现在黑棋下棋，可以落子的位置有：['D3', 'C4', 'F5', 'E6']，
# 黑棋落子 D3 , 则白棋被翻转的棋子是 D4。 

# 表示黑棋
color = 'X' 

# 落子坐标
action = 'D3' 

# 打印白方被翻转的棋子位置
print(board._move(action,color))

# 打印棋盘
board.display()

2.2 创建随机玩家

# 导入随机包
import random

class RandomPlayer:
    """
    随机玩家, 随机返回一个合法落子位置
    """

    def __init__(self, color):
        """
        玩家初始化
        :param color: 下棋方，'X' - 黑棋，'O' - 白棋
        """
        self.color = color
        

    def random_choice(self, board):
        """
        从合法落子位置中随机选一个落子位置
        :param board: 棋盘
        :return: 随机合法落子位置, e.g. 'A1' 
        """
        # 用 list() 方法获取所有合法落子位置坐标列表
        action_list = list(board.get_legal_actions(self.color))

        # 如果 action_list 为空，则返回 None,否则从中选取一个随机元素，即合法的落子坐标
        if len(action_list) == 0:
            return None
        else:
            return random.choice(action_list)

    def get_move(self, board):
        """
        根据当前棋盘状态获取最佳落子位置
        :param board: 棋盘
        :return: action 最佳落子位置, e.g. 'A1'
        """
        if self.color == 'X':
            player_name = '黑棋'
        else:
            player_name = '白棋'
        print("请等一会，对方 {}-{} 正在思考中...".format(player_name, self.color))
        action = self.random_choice(board)
        return action

• 随机玩家的 get_move() 方法主要调用了 random_choice() 方法。

• random_choice() 方法是：先用 list() 方法获取合法落子位置坐标列表，然后用 random.choice() 方法随机获取合法落子位置中的一个。

# 导入棋盘文件
from board import Board

# 棋盘初始化
board = Board() 

# 打印初始化棋盘
board.display() 

# 玩家初始化，输入黑棋玩家
black_player = RandomPlayer("X") 

# 黑棋玩家的随机落子位置
black_action = black_player.get_move(board)  


print("黑棋玩家落子位置: %s"%(black_action))

# 打印白方被翻转的棋子位置
print("黑棋落子后反转白棋的棋子坐标：",board._move(black_action,black_player.color))

# 打印黑棋随机落子后的棋盘
board.display() 

# 玩家初始化，输入白棋玩家
white_player = RandomPlayer("O") 

# 白棋玩家的随机落子位置
white_action = white_player.get_move(board) 

print("白棋玩家落子位置:%s"%(white_action))

# 打印黑棋方被翻转的棋子位置
print("白棋落子后反转黑棋的棋子坐标：",board._move(white_action,white_player.color))

# 打印白棋随机落子后的棋盘
board.display()

2.3 创建人类玩家

class HumanPlayer:
    """
    人类玩家
    """

    def __init__(self, color):
        """
        玩家初始化
        :param color: 下棋方，'X' - 黑棋，'O' - 白棋
        """
        self.color = color
    

    def get_move(self, board):
        """
        根据当前棋盘输入人类合法落子位置
        :param board: 棋盘
        :return: 人类下棋落子位置
        """
        # 如果 self.color 是黑棋 "X",则 player 是 "黑棋"，否则是 "白棋"
        if self.color == "X":
            player = "黑棋"
        else:
            player = "白棋"

        # 人类玩家输入落子位置，如果输入 'Q', 则返回 'Q'并结束比赛。
        # 如果人类玩家输入棋盘位置，e.g. 'A1'，
        # 首先判断输入是否正确，然后再判断是否符合黑白棋规则的落子位置
        while True:
            action = input(
                    "请'{}-{}'方输入一个合法的坐标(e.g. 'D3'，若不想进行，请务必输入'Q'结束游戏。): ".format(player,
                                                                                 self.color))

            # 如果人类玩家输入 Q 则表示想结束比赛
            if action == "Q" or action == 'q':
                return "Q"
            else:
                row, col = action[1].upper(), action[0].upper()

                # 检查人类输入是否正确
                if row in '12345678' and col in 'ABCDEFGH':
                    # 检查人类输入是否为符合规则的可落子位置
                    if action in board.get_legal_actions(self.color):
                        return action
                else:
                    print("你的输入不合法，请重新输入!")

• 人类玩家输入落子位置，如果输入'Q', 则返回 'Q' 并结束比赛。

• 如果人类玩家输入棋盘位置，e.g. 'A1'，首先判断输入是否正确，然后再判断是否符合黑白棋规则的落子位置。

# 导入棋盘文件
from board import Board

 # 棋盘初始化
board = Board() 

# 打印初始化后棋盘
board.display() 

# 人类玩家黑棋初始化
black_player = HumanPlayer("X") 

# 人类玩家黑棋落子位置
action = black_player.get_move(board)


# 如果人类玩家输入 'Q',则表示想结束比赛，
# 现在只展示人类玩家的输入结果。
if action == "Q":
    print("结束游戏：",action)
else:
    # 打印白方被翻转的棋子位置
    print("黑棋落子后反转白棋的棋子坐标：", board._move(action,black_player.color))

# 打印人类玩家黑棋落子后的棋盘
board.display()

2.4 创建 Game 类

• 属性：
• self.board：棋盘
• self.current_player：定义当前的下棋一方，考虑游戏还未开始我们定义为 None
• self.black_player：定义黑棋玩家 black_player
• self.white_player：定义白棋玩家 white_player

• 方法：
• switch_player()：下棋时切换玩家
• run()：黑白棋游戏的主程序

# 导入黑白棋文件
from game import Game  

# 人类玩家黑棋初始化
black_player = HumanPlayer("X")

# 随机玩家白棋初始化
white_player = RandomPlayer("O")

# 游戏初始化，第一个玩家是黑棋，第二个玩家是白棋
game = Game(black_player, white_player)

# 开始下棋
game.run()

# 导入黑白棋文件
from game import Game  

# 随机玩家黑棋初始化
black_player = RandomPlayer("X")

# 随机玩家白棋初始化
white_player = RandomPlayer("O")

# 游戏初始化，第一个玩家是黑棋，第二个玩家是白棋
game = Game(black_player, white_player)

# 开始下棋
game.run()

2.5 创建 AI 玩家

这有两个方案

#方案一
import math
import random
import time
from copy import deepcopy

class AIPlayer:
    """
    AI 玩家
    """

    def __init__(self, color):
        """
        玩家初始化
        :param color: 下棋方，'X' - 黑棋，'O' - 白棋
        """

        self.color = color

    def get_move(self, board):
        """
        根据当前棋盘状态获取最佳落子位置
        :param board: 棋盘
        :return: action 最佳落子位置, e.g. 'A1'
        """
        if self.color == 'X':
            player_name = '黑棋'
        else:
            player_name = '白棋'
        print("请等一会，对方 {}-{} 正在思考中...".format(player_name, self.color))

        # -----------------请实现你的算法代码--------------------------------------
        
        action = self.mct(board)
        # ------------------------------------------------------------------------

        return action
    
    def mct(self, board):
        MAX_TIME = 0.5
        _board = deepcopy(board)
        def ucb(node_tuple, t, cval):
            name, ptimes, rewards, childrens = node_tuple
            if ptimes==0:
                ptimes=0.0000000001     
            if t==0:
                t=1
            return (rewards/ptimes)+cval*math.sqrt(2*math.log(t)/ptimes)
        
        def find_playout(_board, color, depth=0):
#           black 0, white 1
            legal_choice = list(_board.get_legal_actions(color))
            if depth > 32 or legal_choice == []:
                if _board.count('X') > _board.count('O'):
                    return 0
                else:
                    return 1
            _board._move(random.choice(legal_choice), color)
            if color == 'X':
                color = 'O'
            else:
                color = 'X'
            return find_playout(_board, color, depth=depth+1)
        
        def expand(_board, color):
            legal_choice = list(_board.get_legal_actions(color))
            result = []
            for choice in legal_choice:
                result.append((choice, 0, 0, []))
            return result
        
        def find_path(root, ptimes):
            current_path = []
            child = root
            parent_ptimes = ptimes
            isMCTTurns = True
            
            while True:
                if len(child) == 0:
                    break
                maxidxlist = [0]
                cidx = 0
                if isMCTTurns:
                    maxval = -1
                else:
                    maxval = 2
                for n_tuple in child:
                    n_parent, n_ptimes, n_rewards, n_childrens = n_tuple
                    if isMCTTurns:
                        cval = ucb(n_tuple, parent_ptimes, 0.1)
                        if cval == maxval:
                            maxidxlist.append(cidx)
                        if cval > maxval:
                            maxidxlist = [cidx]
                            maxval = cval
                    else:
                        cval = ucb(n_tuple, parent_ptimes, -0.1)
                        if cval == maxval:
                            maxidxlist.append(cidx)
                        if cval < maxval:
                            maxidxlist = [cidx]
                            maxval = cval
                    cidx += 1
                
                maxidx = maxidxlist[random.randrange(0, len(maxidxlist))]
                parent, t_ptimes, rewards, t_childrens = child[maxidx]
                current_path.append(parent)
                parent_ptimes = t_ptimes
                child = t_childrens
                isMCTTurns = not isMCTTurns
                
            return current_path
        
        root = expand(board, self.color)
        start_time = time.time()
        for i in range(0, 5000):
            current_board = deepcopy(board)
            current_board2 = deepcopy(board)
            if (time.time() - start_time) > MAX_TIME:
                break
            current_path = find_path(root, i)
            color = self.color
            for t in current_path:
                current_board._move(t, color)
                current_board2._move(t, color)
                if color == 'X':
                    color = 'O'
                else:
                    color = 'X'
            playout = find_playout(current_board2, color)# 0: black wins, 1: white wins
            if (color == 'X' and playout == 0) or (color == 'O' and playout == 1):
                isWon = True
            else:
                isWon = False
            
            child = root
            for t in current_path:
                idx = 0
                for n_tuple in child:
                    parent, t_ptimes, reward, t_childrens = n_tuple
                    if parent == t:
                        break
                    idx += 1
                if parent == t:
                    t_ptimes += 1
                    if isWon:
                        reward += 1
                    if t_ptimes > 5 and len(t_childrens) == 0:
                        t_childrens = expand(current_board, color)
                    child[idx] = (parent, t_ptimes, reward, t_childrens)
                child = t_childrens
        max_avg_reward = -1
        mt_result = (0, 0)
        for n_tuple in root:
            parent, t_ptimes, reward, t_childrens = n_tuple
            if(t_ptimes > 0) and (reward/t_ptimes > max_avg_reward):
                mt_result = parent
                max_avg_reward = reward / t_ptimes
        return mt_result

#方案二
class AIPlayer:
    """
    AI 玩家
    """

    def __init__(self, color):
        """
        玩家初始化
        :param color: 下棋方，'X' - 黑棋，'O' - 白棋
        """

        self.color = color

    def get_move(self, board):
        """
        根据当前棋盘状态获取最佳落子位置
        :param board: 棋盘
        :return: action 最佳落子位置, e.g. 'A1'
        """
        if self.color == 'X':
            player_name = '黑棋'
        else:
            player_name = '白棋'
        print("请等一会，对方 {}-{} 正在思考中...".format(player_name, self.color))

        # -----------------请实现你的算法代码--------------------------------------

        legal_moves = board.get_legal_actions(self.color)
        if not legal_moves:
            return None

        # 使用蒙特卡洛树搜索算法选择最佳落子位置
        action = self.monte_carlo_tree_search(board, legal_moves)
        # ------------------------------------------------------------------------

        return action
    
    def monte_carlo_tree_search(self, board, legal_moves, simulations=100):
        # 实现蒙特卡洛树搜索算法
        # 对各个落子位置进行模拟，评估并选择最佳的落子位置
        scores = {move: 0 for move in legal_moves}

        for _ in range(simulations):
            for move in legal_moves:
                # 模拟落子
                temp_board = board.copy()
                temp_board._move(move, self.color)

                # 在模拟中评估棋局的价值
                score = self.simulate(temp_board)

                scores[move] += score

        # 选择评分最高的落子位置
        best_move = max(scores, key=scores.get)
        return best_move
    def simulate(self, board):
        # 模拟游戏并评估棋局的价值
        return random.random()  # 这里暂时使用随机值作为示例

1. 请不要修改get_move方法的输入和输出。

2. 可以添加 AIPlayer 的属性和方法。

3. 完善算法时请注意落子时间：落子需要在 60s 之内！

4. 落子 3 次不在合法范围内即判断该方失败, 故落子前请检查棋子的合法性。

5. 提交作业时请导入必要的包和第三方库 (包括此文件中曾经导入过的)。

2.5.1 测试 AI 玩家

# 导入黑白棋文件
from game import Game  

# 人类玩家黑棋初始化
black_player =  HumanPlayer("X")

# AI 玩家 白棋初始化
white_player = AIPlayer("O")

# 游戏初始化，第一个玩家是黑棋，第二个玩家是白棋
game = Game(black_player, white_player)

# 开始下棋
game.run()

2.5.2 作业提交

• 经过2.5.1 测试 AI 玩家实现人类玩家与 AI 玩家对弈之后，在左侧 提交作业 的标签中，把整个 AIPlayer 转化为 main.py 文件进行系统测试。

• 你可以选择初级、中级或者高级对手进行对弈，对弈时请勾选 main.py 文件。

• 能通过测试就可以提交作业。

• 提交作业时请记得提交勾选 『程序报告.docx』或者 『程序报告.pdf』。