# TalChess **Repository Path**: onlyyyy/tal_chess ## Basic Information - **Project Name**: TalChess - **Description**: 开源的国际象棋AI，前端Vue+Electron，后端Python+MCTS+Sqlite3+NNUE。 - **Primary Language**: Python - **License**: GPL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 17 - **Forks**: 3 - **Created**: 2021-11-25 - **Last Updated**: 2024-12-27 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # TalChess ## 介绍 开源的国际象棋AI，名称来源于国际象棋世界冠军 米哈伊尔·塔尔(Tal)，使用蒙特卡洛树搜索算法。 ![软件截图](board.png) ## 技术架构 前端:Vue + Electron + Node.js 引擎:Python3.8+ + MCTS + NNUE 通信:TCP协议 ## 安装 ```shell # 前端 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. 获取开局名 **前端每次走棋自动触发** 请求: ```js send = { operator: 'get_fen_name', data:{ fen, // fen数据 first, //第一步棋的走法 如e4 step:'e5', //当前棋步 如e5 } } ``` ```js return { 'code': 0, 'message': '获取对局名称成功', 'data': { 'name': '意大利开局', 'name_en': 'Italian Game', } } ``` 2. 保存数据至开局库(只有开发过程会用) ```js send = { operator: 'save_fen', data: { name, //开局名 nameEn,//开局名En fen: 'fen', //fen step,//当前棋步 如 e4 // 告诉引擎第一步棋是什么 引擎会决定存到哪个数据库里面e4 d4 other first: 'e4', // e4 d4 或者其他的值 按实际情况 } } ``` ```js return { 'code': 0, 'message': '保存棋谱成功' // 前端根据code和message决定消息提醒类型是成功还是警告 } ``` 3. 分析 **前端走棋自动触发** ```js send = { operator: 'analyze', data: { fen //fen }, } ``` ```js 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 车也少了 基本算残局，或者任何一方后被兑换。 - 中局：其他局面。 2. 判断叠兵，进行估值。 `calc_bad_rook` 两个自己的兵在一条线上就是叠兵 3. 计算不能王车易位且车被卡住的情况 `calc_piece_control_bonus` 4. 计算控制格点的奖励 `calc_threaten` 根据每个棋子类型和控制的格点多少来给予奖励 5. 计算威胁 - 判断当前是谁在落子 如果是白棋 那白色的威胁可以忽略一部分 比如捉了一个棋子自然可以走开，黑棋的话也只能把价值最大的棋子置0 - 因为威胁多个棋子也不可能吃掉多个 - 如果是轮到白棋 - 黑棋取威胁最大的 因为白棋能把黑棋最厉害的棋子吃掉 - 白棋忽略威胁最大的 其他的都算威胁 因为只能解决最大的那个威胁 6. 将整个得分数组转化为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](mcts.png) ### 四、蒙特卡洛树搜索 具体实现 #### I、选择 如果不是叶子节点，则求UCB的极值，选择UCB值最优的节点继续选择 ```Python 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) ``` 叶子节点进行扩展 ```Python else: node, value = self.extend(node, num) self.backward(node, num, value) ``` #### II、扩展与仿真 当前节点的所有合法棋步全部模拟一次，计算出具体的估值 ```python 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 ```python 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值最小的，因此计算方式需要有所改变 ```python @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、实际运用 ```python # 蒙特卡洛树搜索 分析 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) ``` 蒙特卡洛树搜索选择出最优的节点，当做结果返回给网络模块 未完待续