开源的国际象棋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算法进行开发,初步结合了估值函数。
黑白攻击的数组,数字代表攻击的次数。
黑白棋每个棋子的攻击数组。
黑白先锋棋子,其中3,4,5,6线属于先锋。
黑白棋的位置数组
黑白叠兵坐标数组
黑白被堵在里面的车数组
黑白棋受到威胁的棋子坐标数组
黑白棋要升变的兵数组
黑白棋颜色 bool类型
calc_piled_pawn
calc_bad_rook
两个自己的兵在一条线上就是叠兵
calc_piece_control_bonus
calc_threaten
根据每个棋子类型和控制的格点多少来给予奖励
calc_score
之前的得分是和棋盘一样大的数组,方便对每个棋子进行修改
选择、扩展、仿真、反向传播。
选择:选择能够最大化UCB值的节点
扩展:创建子节点
仿真:在某一节点用随机策略进行游戏
反向传播:用结果更新整棵树
在推荐系统中,通常量化一个物品的收益率(或者说点击率)是使用点击数/展示数,例如点击为10,展示数为8,则估计的点击率为80%,在展示数达到10000后,其表现ctr是否还能达到80%呢? 显然是不可能的。而这就是统计学中的置信度问题,计算点击率的置信区间的方法也有很多,比如威尔逊置信空间
UCB算法步骤包括:首先对所有item的尝试一下,然后每次选择score值最大的那个:
该节点平均value值 (value / n) + sqrt(ln总次数 / 当前节点探索次数)
这个公式表明随着每个物品试验次数的增加,其置信区间就越窄,收益概率就越能确定。如果收益均值越大,则被选中的机会就越大(exploit),如果收益均值越小,其被选中的概率也就越少,同时哪些被选次数较少的item也会得到试验机会,起到了explore的作用。
选择一个节点,判断是否为叶节点,如果不是,当前节点为ucb值最大的子节点,继续选择。
然后判断该节点访问次数是否为0,如果不是,枚举所有的可能添加到树中,如果是,进行rollout
无限循环,直到达到游戏的结束,然后返回价值
每次会给父节点的探索次数 + 1
value也会累加
如果不是叶子节点,则求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)
当前节点的所有合法棋步全部模拟一次,计算出具体的估值
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
每个父节点都会加上子节点的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)
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
# 蒙特卡洛树搜索 分析
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)
蒙特卡洛树搜索选择出最优的节点,当做结果返回给网络模块
未完待续
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。