9 Star 15 Fork 3

AvenirTech 未来科技 / TalChess

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
README.md 9.57 KB
一键复制 编辑 原始数据 按行查看 历史
吉法师 提交于 2022-01-07 14:21 . 更新readme

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定制端口

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

接口

  1. 获取开局名

前端每次走棋自动触发

请求:

send = {
        operator: 'get_fen_name',
        data:{
          fen,  // fen数据
            first, //第一步棋的走法 如e4
          step:'e5', //当前棋步 如e5
        }
}
return  {
    'code': 0,
    'message': '获取对局名称成功',
    'data': {
        'name': '意大利开局',
        'name_en': 'Italian Game',
    }
}
  1. 保存数据至开局库(只有开发过程会用)
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决定消息提醒类型是成功还是警告
}
  1. 分析

前端走棋自动触发

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

技术部分

一、前端

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

二、引擎

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

估值函数逻辑

I. 解析棋盘的隐含数据

  1. 黑白攻击的数组,数字代表攻击的次数。

  2. 黑白棋每个棋子的攻击数组。

  3. 黑白先锋棋子,其中3,4,5,6线属于先锋。

  4. 黑白棋的位置数组

  5. 黑白叠兵坐标数组

  6. 黑白被堵在里面的车数组

  7. 黑白棋受到威胁的棋子坐标数组

  8. 黑白棋要升变的兵数组

  9. 黑白棋颜色 bool类型

II. 计算分值

  1. 先判断对局的进程

calc_piled_pawn

  • 开局:双方兵大于7 轻子也没兑换多少 属于开局。
  • 残局:轻子小于等于2 车也少了 基本算残局,或者任何一方后被兑换。
  • 中局:其他局面。
  1. 判断叠兵,进行估值。

calc_bad_rook

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

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

calc_piece_control_bonus

  1. 计算控制格点的奖励

calc_threaten

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

  1. 计算威胁
  • 判断当前是谁在落子 如果是白棋 那白色的威胁可以忽略一部分 比如捉了一个棋子自然可以走开,黑棋的话也只能把价值最大的棋子置0
  • 因为威胁多个棋子也不可能吃掉多个
  • 如果是轮到白棋
  • 黑棋取威胁最大的 因为白棋能把黑棋最厉害的棋子吃掉
  • 白棋忽略威胁最大的 其他的都算威胁 因为只能解决最大的那个威胁
  1. 将整个得分数组转化为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也会累加 蒙特卡洛树.png

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

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)

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

未完待续

Python
1
https://gitee.com/onlyyyy/tal_chess.git
git@gitee.com:onlyyyy/tal_chess.git
onlyyyy
tal_chess
TalChess
master

搜索帮助