TalChess

介绍

开源的国际象棋AI，名称来源于国际象棋世界冠军米哈伊尔·塔尔(Tal)，使用蒙特卡洛树搜索算法。

软件截图

技术架构

前端:Vue + Electron + Node.js 引擎:Python3.8+ + MCTS + NNUE 通信:TCP协议

安装

# 前端
cd /front
npm i;
npm run dev;

# 引擎
cd /engine
pip3 install -r requirements.txt -i https://pypi.tuna.tsinghua.edu.cn/simple/
# 把引擎的数据集也下载进来
git clone https://gitee.com/Jifashi_619/tal_database.git
python main.py

前后端通信协议

配置

接口数据格式统一为json

ip:127.0.0.1 port:36119(塔尔的生日)

可以通过改引擎的config.ini定制端口

前端作为客户端，引擎作为服务端进行通信

接口

获取开局名

前端每次走棋自动触发

请求:

send = {
        operator: 'get_fen_name',
        data:{
          fen,  // fen数据
            first, //第一步棋的走法 如e4
          step:'e5', //当前棋步 如e5
        }
}

return  {
    'code': 0,
    'message': '获取对局名称成功',
    'data': {
        'name': '意大利开局',
        'name_en': 'Italian Game',
    }
}

保存数据至开局库(只有开发过程会用)

send = {
    operator: 'save_fen',
    data: {
        name, //开局名
        nameEn,//开局名En
        fen: 'fen', //fen
        step,//当前棋步 如 e4
        // 告诉引擎第一步棋是什么 引擎会决定存到哪个数据库里面e4 d4 other
        first: 'e4', // e4 d4 或者其他的值 按实际情况
    }
}

return {
    'code': 0,
    'message': '保存棋谱成功' // 前端根据code和message决定消息提醒类型是成功还是警告
}

分析

前端走棋自动触发

send = {
    operator: 'analyze',
    data: {
        fen //fen
    },
}

return {
    fen,
    step,
    uci:'h2h3', // uci类型的棋步信息
    score:'+1.2' // 局面分
}

技术部分

一、前端

前端采用Vue+Electron进行开发，国际象棋相关逻辑利用Vue-chessboard库，结合代码判断，支持基本的棋盘操作。

二、引擎

引擎采用Python+MCTS算法进行开发，初步结合了估值函数。

估值函数逻辑

I. 解析棋盘的隐含数据

黑白攻击的数组，数字代表攻击的次数。
黑白棋每个棋子的攻击数组。
黑白先锋棋子，其中3，4，5，6线属于先锋。
黑白棋的位置数组
黑白叠兵坐标数组
黑白被堵在里面的车数组
黑白棋受到威胁的棋子坐标数组
黑白棋要升变的兵数组
黑白棋颜色 bool类型

II. 计算分值

先判断对局的进程

calc_piled_pawn

开局：双方兵大于7 轻子也没兑换多少属于开局。
残局：轻子小于等于2 车也少了基本算残局，或者任何一方后被兑换。
中局：其他局面。

判断叠兵，进行估值。

calc_bad_rook

两个自己的兵在一条线上就是叠兵

计算不能王车易位且车被卡住的情况

calc_piece_control_bonus

计算控制格点的奖励

calc_threaten

根据每个棋子类型和控制的格点多少来给予奖励

计算威胁

判断当前是谁在落子如果是白棋那白色的威胁可以忽略一部分比如捉了一个棋子自然可以走开，黑棋的话也只能把价值最大的棋子置0
因为威胁多个棋子也不可能吃掉多个
如果是轮到白棋
黑棋取威胁最大的因为白棋能把黑棋最厉害的棋子吃掉
白棋忽略威胁最大的其他的都算威胁因为只能解决最大的那个威胁

将整个得分数组转化为float

calc_score

之前的得分是和棋盘一样大的数组,方便对每个棋子进行修改

三、蒙特卡洛树搜索概述

基本流程

选择、扩展、仿真、反向传播。

选择：选择能够最大化UCB值的节点
扩展：创建子节点
仿真：在某一节点用随机策略进行游戏
反向传播：用结果更新整棵树

UCB（Upper Confidence Bound）算法

在推荐系统中，通常量化一个物品的收益率（或者说点击率）是使用点击数/展示数，例如点击为10，展示数为8，则估计的点击率为80%，在展示数达到10000后，其表现ctr是否还能达到80%呢？显然是不可能的。而这就是统计学中的置信度问题，计算点击率的置信区间的方法也有很多，比如威尔逊置信空间

UCB算法步骤包括：首先对所有item的尝试一下，然后每次选择score值最大的那个：

该节点平均value值 (value / n) + sqrt(ln总次数 / 当前节点探索次数)

这个公式表明随着每个物品试验次数的增加，其置信区间就越窄，收益概率就越能确定。如果收益均值越大，则被选中的机会就越大（exploit），如果收益均值越小，其被选中的概率也就越少，同时哪些被选次数较少的item也会得到试验机会，起到了explore的作用。

仿真过程

选择一个节点，判断是否为叶节点，如果不是，当前节点为ucb值最大的子节点，继续选择。

然后判断该节点访问次数是否为0，如果不是，枚举所有的可能添加到树中，如果是，进行rollout

rollout算法

无限循环，直到达到游戏的结束，然后返回价值

反向传播

每次会给父节点的探索次数 + 1
value也会累加

四、蒙特卡洛树搜索具体实现

I、选择

如果不是叶子节点，则求UCB的极值，选择UCB值最优的节点继续选择

if self.is_leaf(node) is False:
    if color is evaluate.Color.WHITE:
        max_ucb = 0
        max_index = 0
        invalid = True
        for i in range(len(node.leaf)):
            # 已经到棋局尾声的节点就跳过
            if node.leaf[i].is_end is True:
                continue
            # 求最大值
            leaf_ucb = self.calc_UCB(node.leaf[i], num, color)
            # 无穷大就是最大
            if math.isinf(leaf_ucb):
                max_index = i
                break
            max_ucb = max_ucb if max_ucb > leaf_ucb else leaf_ucb
            max_index = max_index if max_ucb > leaf_ucb else max_index
            invalid = False
        if invalid is True:
            print('已经没有可用节点了')
            return invalid
        return self.select(node.leaf[max_index], num, color)

叶子节点进行扩展

else:
    node, value = self.extend(node, num)
    self.backward(node, num, value)

II、扩展与仿真

当前节点的所有合法棋步全部模拟一次，计算出具体的估值

def extend(node: Node, num: int) -> tuple:
        board = node.board
        legal_list = list(board.legal_moves)
        value = 0

        # 对每个节点按深度模拟一次
        for i in range(len(legal_list)):
            move = legal_list[i]
            temp_board = copy.deepcopy(board)
            temp_board.push(move)
            internal = chess_util.parse_internal_board_info(temp_board, temp_board.fen())
            get_value = chess_util.do_evaluate(temp_board, internal)
            if chess_util.get_current_color_by_fen(temp_board.fen()) is evaluate.Color.WHITE:
                value = value if value > get_value else value
            else:
                value = value if value < get_value else value
            node.leaf.append(Node(temp_board.fen(), move, node, value))
        return node, value

III、回溯

每个父节点都会加上子节点的value

    def backward(self, node: Node, num: int, value: float) -> None:
        node.value += value
        node.times += num
        # 不是父节点就继续增加
        if node.parent is not None:
            return self.backward(node.parent, num, value)

IV、计算UCB值

Tal基于这个算法进行了优化，白棋选择UCB值最大的，黑色会选择UCB值最小的，因此计算方式需要有所改变

@staticmethod
    def calc_UCB(node: Node, all_num: int, color: evaluate.Color) -> float:
        value: float = node.value
        n: int = node.times

        # 没访问过 ucb值是无穷大
        if n == 0 or all_num == 0:
            return float('inf')

        # 如果是复数则只保留实数部分
        if color == evaluate.Color.WHITE:
            res = value / n + cmath.sqrt(math.log(all_num) / n)
        else:
            res = value / n - cmath.sqrt(math.log(all_num) / n)
        return res.real

V、实际运用

# 蒙特卡洛树搜索 分析
    def mct_search_analyze(self, fen: str):
        # 先创建初始局面
        root_board = chess.Board(fen)
        board = self.chess_util.parse_board(root_board)
        # 判断一进来就是棋局结束的特殊情况
        check = self.chess_util.check_board_status(root_board)
        if check['end'] is True:
            return None

        # 根节点
        root_node = Node(fen, None, None)
        color = self.chess_util.get_current_color_by_fen(fen)

        # 开始蒙特卡洛树搜索
        # 这里必须顺序执行 不能多线程! 也不一定
        for i in range(self.move):
            print("模拟[{}]次".format(i + 1))

            # 选择 如果已经到棋局尾声就跳出
            invalid = self.select(root_node, i, color)
            if invalid is True:
                print("已经全部模拟 跳出")
                break
        return self.get_best(root_node)

蒙特卡洛树搜索选择出最优的节点，当做结果返回给网络模块

未完待续

AvenirTech 未来科技 / TalChess

TalChess

介绍

技术架构

安装

前后端通信协议

配置

接口

技术部分

一、前端

二、引擎

估值函数逻辑

I. 解析棋盘的隐含数据

II. 计算分值

三、蒙特卡洛树搜索概述

基本流程

UCB（Upper Confidence Bound）算法

仿真过程

rollout算法

反向传播

四、蒙特卡洛树搜索具体实现

I、选择

II、扩展与仿真

III、回溯

IV、计算UCB值

V、实际运用

简介

发行版

贡献者

近期动态

AvenirTech 未来科技 / TalChess .gitee-modal { width: 500px !important; }

TalChess

介绍

技术架构

安装

前后端通信协议

配置

接口

技术部分

一、前端

二、引擎

估值函数逻辑

I. 解析棋盘的隐含数据

II. 计算分值

三、蒙特卡洛树搜索概述

基本流程

UCB（Upper Confidence Bound）算法

仿真过程

rollout算法

反向传播

四、蒙特卡洛树搜索 具体实现

I、选择

II、扩展与仿真

III、回溯

IV、计算UCB值

V、实际运用

简介

发行版

贡献者

近期动态

搜索帮助

AvenirTech 未来科技 / TalChess

四、蒙特卡洛树搜索具体实现