- 1nlp中文本预处理技术_自然语言处理 中文 预处理
- 2最新ChatGPT GPT-4 自然语言理解NLU与句词分类技术详解（附ipynb与python源码及视频讲解）——开源DataWhale发布入门ChatGPT技术新手从0到1必备使用指南手册（四）_gpt nlu
- 3【深入理解计算机网络】“数制”视频课程-王达-专题视频课程
- 4Oracle分组函数之ROLLUP、GROUPING用法_oracle rollup grouping
- 5vit-transformer模型结构及源码解读
- 6基于Bert和通用句子编码的Spark-NLP文本分类_agnews数据集下载
- 7准确率（Accuracy）、精确率(Precision)、召回率(Recall)、F值(F-Measure)、AUC、ROC的理解_准确率,精确率,召回率
- 8IDEA好用插件：MybatisX快速生成接口实体类mapper.xml映射文件_idea创建mapper映射文件
- 9HTML5+CSS3实现小米商城（有源码）_小米商城菜单html代码
- 10脉冲神经网络（Spiking Neural Network，SNN）概述
AI玩转重力四子棋_重力四子棋ai平台
赞
踩
AI玩转重力四子棋
导语
最近看到一个小游戏，感觉很有意思，想着如何让电脑学会跟人下。于是做了一些简单的探索，完成了基本的AI模拟，这里的算法是直接使用特征来进行差别。搜索深度也只做了2步，还可以做更深度的搜索，也可以使用深度模型来训练，就算是抛砖引玉吧。
版本历史
1.0.3 优化WEB界面，增加人机比分展示；
1.0.2 完成HTTP服务端包装，可通过网页实现对弈；
1.0.1 完成AI算法，可进行人机对弈；
1.0.0 完成重力四子棋基本框架，可进行命令行对弈；
先汇总一下相关资源：
-
重力四子棋在线游戏 http://connect4.hexi5.com/
-
重力四子棋源码：https://github.com/xmxoxo/connect4
重力四子棋介绍
-
重力四子棋共有7行6列
-
每次只能选择在一个列中下一个棋子；
-
由于重力作用，所下的棋子会下落到该列的最下方；
-
一方棋子在任意直线方向上连成4个棋子即获胜；
当然，根据这个规则还可以把游戏变得更复杂：
棋盘也可以变成更大，四子也可以变成N子；
甚至可以把二维变成三维：最强大脑里的立体重力四子棋，有兴趣的可以自行百度
如果对规则不是很了解的话，可以到马上试玩一下： 重力四子棋
重力四子棋的基本实现
首先是实现重力四子棋的基本方法，可以下棋，换游戏者，判断胜负等。
这些过程相对比较简单，重点的就说几个地方吧：
一是下棋：重力作用会让棋落到最下面。
这个的实现是基于原来的代码结构，使用了一个column的类来完成。其实也可以简化成使用numpy的判断。
二是判断胜负： 搜索所有的棋判断有没有连成4个。
搜索的时候是从上到下，从左到右，找到每一个棋子，
然后沿着：右，右下，下，左下，这四个方向去查找。
为什么是这四个方向呢，因为另外四个方向其实是对称的，已经包含在上面的方向里了。
只要在方向上能找到连续的另外三颗同色的棋子，就说明获胜了。
基本的实现过程可以看源码中的 Connect_N.ipynb
重力四子棋的AI模拟
整个AI模拟的思路过程也都写在了Connect_N.ipynb 文件中。
这里把思路重新理一下：
棋盘状态特征
棋盘状态特征的目的是针对当前棋盘状态，提取出棋子的特征值。
棋子的特征值可以分为针对游戏者双方分别给出特征值，提取的方法是相同的。
最终的特征为已方棋子特征加上对方棋子的特征,即：
[[已方特征],[对方特征]]
棋子特征
棋子特征主要是要能够描述棋子的好坏，棋子的发展变化情况，棋子离目标状态的远近。
这里参考围棋的思路，主要引入几个核心要素：棋串，棋长，真气，长气，气度等。
棋串
棋串是指一个或者多个在一条直线上的棋子连成的串;
棋串包括横向，竖向和斜向（正反）四个方向。
每个棋子可以包含在不同的棋串中。
棋串用chess表示
○○○○○○
○○▲○○○
○●●▲○○
- 1
- 2
- 3
上图中●方共有子串三个：
● 位置：((3,2))
● 位置：((3,3))
●● 位置：((3,2),(3,3))
- 1
- 2
- 3
▲方共有子串三个:
▲ 位置：((3,2))
▲ 位置：((3,3))
▲▲ 位置：((2,3),(3,4)) 斜线
- 1
- 2
- 3
棋长
棋长是指棋串的最大长度,是一个整数；
棋长用maxlen表示；
可以很容易推断出，对于N子棋来说：
- 当出现棋长为N的棋串表示已经胜利；
- 当前局面中最大的棋长为N-1
真气
真气是指棋串周边可以下棋的空位位置，位置包括斜方向，与围棋的气的计算相同。
真气的数量越多，表示棋串未来的发展变化程度越大。
棋串的真气数量用gas_count表示；
对于真气为0的棋串，已经没有发展的空间，可以不需要参与计算；
气度
棋串的每一个真气，有些真气是马上可以“落下棋”的位置，而有些是未来才能“落下棋”的位置；
气度就是要多少步才能“落下棋”到该位置，用一个整数来表示，0表示马上就可以落棋；
对于N子棋来说，气度的取值范围为0至N-1；
显然，气度为0的真气就是下一步要落子的位置。
长气
长气是指棋串的真气中，可以让棋长变大的真气；
长气的个数最小值为0，最大值为2；
必胜局面
显然可见，对于4子棋来说，如果出现：一个棋串长度为3，长气个数为2，长气的气度均为0，则为必胜棋。
如下图：
○○○○○○
○○○○○○
○○○○○○
○○○○○○
○○○○○○
○○▲▲▲○
○○●●●○
- 1
- 2
- 3
- 4
- 5
- 6
- 7
对于●方：
最大棋串的长度为3，真气个数为4，左右两边分别有一个长气，即长气个数为2，并且这两个长气的气度均为0。
此时无论对方下哪个位置，这两个位置二者必得其一，所以是必胜的局面。
必应局面
对于4子棋来说，如果最大棋串长度为3，长气个数为1，且长气的气度为0，则为必应局面，也就是必须抢占这个位置。
如下图：
○○○○○○
○○○○○○
○○○○○○
○○○○○○
○○○○○○
○○○▲▲▲
○○○●●●
- 1
- 2
- 3
- 4
- 5
- 6
- 7
对于●方：
最大棋串长度为3，长气个数为1，气度为0，也就是再下到这里就获胜了，所以是双方抢占的位置。
对于已方来说，叫获胜位；对于对方来说，叫必应位。
棋盘状态表示
棋盘状态使用各个棋串表示，搜索出当前棋盘下的所有棋串，去除掉包含的子串以及死串。
重点：使用棋串长度l，长气气度d1，长气气度d2 这三个值组成的特征数组表示一个棋串
例如：
[3,1,1] 必胜棋串
[3,0,1] 必应棋串
[3,2,2] 带禁入的棋串，
[2,0,2] 斜向有发展前途的棋串
- 1
- 2
- 3
- 4
使用以下公式来计算一个棋串的分值：
value = 10**(l+2) + 10**(l+1)/d1**3 + 10**(l+1)/d2**3 + 10**(l+1)/(d1*d2)**2 + 10**(l)/(d1+d2)**2
- 1
公式中，要排除掉d1,d2为0的情况，避免出现计算错误。
棋盘的总得分即为所有棋串的分值总和。
这样设计公式的原因是把棋串长度，气度1，气度2分别放在不同的位上进行区分；
当棋串长度从3变为4时，棋串得分立即从10万等级上长到100万等级，因此很容易判断是否获胜。
同时考虑了气度1、气度2为0；以及同时为1的情况，公式的设计可以实现同长度棋串的不同气度排序：
[x,1,1] > [x, 1, 2] > [x, 1, 3] > [x, 0,1] > [x, 0, 2]
- 1
棋串得分公式及验证
# 棋串得分计算公式 def chessvalue(l,d1,d2): if l<4 and d1==d2==0: return 0 value = 10**(l+2) k1 = d1*d2 k2 = d1+d2 v1 = 0 if d1==0 else 10**(l+1)/d1**3 v2 = 0 if d2==0 else 10**(l+1)/d2**3 value += v1+v2 if k1>0: value += (10**(l+1) / k1**1.5) if k2>0: value += (10**(l) / k2) #value *= 100 return int(value) testv = [[5,0,0], [4,1,1], [4,0,0], [4,0,1], [4,0,2], [3,1,1], [3,1,2], [3,1,3], [3,1,4], [3,0,1], [3,1,0], [3,2,2], [3,2,3], [3,2,4], [3,0,2], [3,0,3], [3,0,0], [2,1,1], [2,0,1], [2,1,0], [2,1,2], [2,1,3], [2,0,2], [2,0,3], [2,1,4], [2,0,0], [1,1,1], [1,0,1], [1,0,0], ] for x in testv: print('{0} ==> {1:>10,d}'.format(str(x), chessvalue(*x)))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
运行完的结果：
[5, 0, 0] ==> 10,000,000 [4, 1, 1] ==> 1,305,000 [4, 0, 0] ==> 1,000,000 [4, 0, 1] ==> 1,110,000 [4, 0, 2] ==> 1,017,500 [3, 1, 1] ==> 130,500 [3, 1, 2] ==> 114,083 [3, 1, 3] ==> 111,731 [3, 1, 4] ==> 110,981 [3, 0, 1] ==> 111,000 [3, 1, 0] ==> 111,000 [3, 2, 2] ==> 103,375 [3, 2, 3] ==> 102,098 [3, 2, 4] ==> 101,729 [3, 0, 2] ==> 101,750 [3, 0, 3] ==> 100,703 [3, 0, 0] ==> 0 [2, 1, 1] ==> 13,050 [2, 0, 1] ==> 11,100 [2, 1, 0] ==> 11,100 [2, 1, 2] ==> 11,408 [2, 1, 3] ==> 11,173 [2, 0, 2] ==> 10,175 [2, 0, 3] ==> 10,070 [2, 1, 4] ==> 11,098 [2, 0, 0] ==> 0 [1, 1, 1] ==> 1,305 [1, 0, 1] ==> 1,110 [1, 0, 0] ==> 0
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
对局面来进行评估
有了棋串的得分，把一个局面中所有的棋串得分加起来，就是当前局面的得分了。
代码如下：
def all_chess(self, board=None): '''盘面分析，获取所有的棋串，并计算得分''' #判断子串重复 check_repeat = lambda m,n: all( map(lambda x:x in n, m)) ret = [[],[]] # 每个点沿右，右下，下，左下4个方向最多走3步，每一步都必须与当前点同色，如果能走到3步则表示获胜 dire = [[0,1],[1,1],[1,0],[1,-1]] if board is None: bd = self.board else: bd = board for x in range(bd.shape[0]): for y in range(bd.shape[1]): po = bd[x,y] if po>0: #ret[po-1].append([(x,y)]) for d in dire: step=0 chess = [] #chess.append(po) chess.append((x,y)) xn,yn = x,y #----- 计算气度1:d1 d1 = 0 px, py = x-d[0],y-d[1] if 0<=px<bd.shape[0] and 0<=py<bd.shape[1]: if bd[px,py]==0: k = bd[:, py][::-1][:bd.shape[0]-px] d1 = len(list(filter(lambda x:x==0,k))) #----- #最大深入3级 for s in range(3): # 计算下一个点的位置 xn,yn = xn+d[0],yn+d[1] # 判断点是否在区域内 if 0<=xn<bd.shape[0] and 0<=yn<bd.shape[1]: if bd[xn,yn]==po: chess.append((xn,yn)) step += 1 else: break else: break #----- 计算气度2：d2 d2 = 0 #xn,yn = xn+d[0],yn+d[1] if 0<=xn<bd.shape[0] and 0<=yn<bd.shape[1]: if bd[xn,yn]==0: k = bd[:, yn][::-1][:bd.shape[0]-xn] d2 = len(list(filter(lambda x:x==0,k))) #----- # 记录棋串 #if step>0: # 判断是重重复 if not any(map(lambda x:check_repeat(chess,x[0]), ret[po-1])): value = chessvalue(len(chess),d1,d2) ret[po-1].append([chess,[len(chess), d1, d2],value]) # 记录棋串长度，气度1，气度2 # 棋串排序,按棋长 #mysort = lambda r: sorted(r,key=lambda x:-len(x[0])) # 棋串排序,按棋串得分 mysort = lambda r: sorted(r,key=lambda x:-x[-1]) ret = list(map(mysort,ret)) return ret
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
有了局面的分值，就可以进行评估了，这里来进行模拟一下：
board = Board(4) board.drop_disk(6) board.drop_disk(5) board.drop_disk(5) board.drop_disk(4) board.drop_disk(5) board.drop_disk(4) board.drop_disk(4) board.drop_disk(3) board.drop_disk(3) board.drop_disk(3) #board.drop_disk(3) board.display() ai = AI(board) allchess = ai.all_chess() #v = map(lambda y: sum(map(lambda x:x[-1], y)), allchess) v1, v2 = ai.score() print('棋盘状态:') print('玩家1 得分:{0:,d}'.format(v1)) ret = list(map(print,allchess[0])) print('-'*30) print('玩家2 得分:{0:,d}'.format(v2)) ret = list(map(print,allchess[1]))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
运行结果如下：
------------重力棋游戏------------- 玩家：● 电脑:▲ 1 2 3 4 5 6 ○○○○○○ ○○○○○○ ○○○○○○ ○○○○○○ ○○▲●●○ ○○●▲●○ ○○▲▲▲● 1 2 3 4 5 6 当前轮到: [●]玩家 棋盘状态: 玩家1 得分:145,325 [[(4, 3), (5, 4), (6, 5)], [3, 1, 0], 111000] [[(4, 3), (5, 2)], [2, 1, 1], 13050] [[(4, 4), (5, 4)], [2, 1, 0], 11100] [[(4, 3), (4, 4)], [2, 0, 2], 10175] ------------------------------ 玩家2 得分:212,413 [[(6, 2), (6, 3), (6, 4)], [3, 1, 0], 111000] [[(4, 2), (5, 3), (6, 4)], [3, 4, 0], 100406] [[(4, 2)], [1, 3, 0], 1007] [[(5, 3), (6, 3)], [2, 0, 0], 0] [[(5, 3), (6, 2)], [2, 0, 0], 0]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
AI棋步推荐
有了局面的分值，就可以计算出局面的分值变化了，最终的目标就是让下一步棋后，得到分值更大的局面。当然这里也可以判断分值超过百万就是获胜了。
AI就是去计算每一步棋下完后的局面得分，然后按分值的高低排序即可。
以下是下一步棋推荐的核心代码：
def nextstep(self, player): '''预测出下一步最好的棋应该下在哪里''' '''计算下一步可下棋的位置''' pos = np.where (self.board[0]==0)[0]+1 #print(pos) #模拟在某一列下一个棋 def dropstep(bd,col,player): bd = bd.copy() #print('-'*30) #print(bd) k = bd[:, col][::-1] row = bd.shape[0] - k.tolist().index(0) - 1 bd[row,col] = player #print('-'*30) #print('drop:',col) #print(bd) return bd # 当前得分 current_score = np.array(self.score()) #print('current_score:', current_score) #分别计算每一个可下位置下棋后的状态得分变化值 def nextscore(bd, current_score, player): nplayer = 1 if player==2 else 2 f_score = np.array([current_score] * bd.shape[1]) '''计算下一步可下棋的位置''' pos = np.where (self.board[0]==0)[0] for p in pos: #模拟下一步棋后的状态 nbd = dropstep(bd, p, player) # 计算状态及得分 v_chess = self.all_chess(board=nbd) v_score = list(map(lambda y: sum(map(lambda x:x[-1], y)), v_chess)) f_score[p] = v_score f_score -= current_score return f_score score_change = nextscore(self.board, current_score, player ) #print('score_change:', score_change) pp = [1,-2] if player == 2: pp = [-2, 1] score_change = score_change * pp # 得分变化计算方式：已方增加值值 - 对方增加值 t_score = score_change[:,0] - score_change[:,1] #print(t_score) # 排序 idx = np.array(t_score).argsort()[::-1] + 1 #print('sorted:', idx) nt = np.sort(t_score,axis=0)[::-1] #ns = np.sort(score_change,axis=0)[::-1] #nf = np.sort(f_score,axis=0)[::-1] rpos = list(zip(idx, nt.tolist())) #, ns.tolist(), nm.tolist() return rpos
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
针对上面的局面，让AI推荐一下：
recommand = ai.nextstep(1)
print(recommand)
print('-'*30)
recommand = ai.nextstep(2)
print(recommand)
- 1
- 2
- 3
- 4
- 5
运行结果如下；
[(3, 892909), (5, 198948), (4, 23813), (6, 23125), (1, 1110), (2, -123436)]
------------------------------
[(3, 210798), (5, 24983), (1, -1110), (6, -1850), (4, -10635), (2, -995407)]
- 1
- 2
- 3
可以看到，都是推荐下在第3列，后面的值是得分的变化值。
总结与后计
上周末跟儿子一起下这个重力四子棋，没想到连输了好几盘，答应他这周末搞出一个AI来跟他下，看来基本上是完成了。
整个过程中对于numpy、flask、session、ajax等的使用能力都有所提升，代码里也有一些小小的通用功能点实现，可以作为后续工程的参考。
例如：对array的各类旋转、切片操作；加载favicon.ico；记录人和AI的获胜得分比；
当然代码中还有很多可以优化的地方：
-
Column类其实并不需要，可以优化掉。
-
棋串的得分函数还存在优化的空间；
-
AI下一步棋推荐算法中，只计算了两步：自己下完，以及对手再下完后的局面。
这样其实并没有看到最后能否获胜。 -
下一步棋推荐算法中，使用的是循环，不方便指定“AI算力”。如果改成递归或者加上深度的判断，可以指定AI的智力程度。
-
对于这类游戏，还可以使用深度模型来训练，得到一个非常强大的对弈模型。
希望有兴趣的小伙伴们可以继续，做出更好的更强的AI。
- 不允许mysql ...
赞
踩
