前言:
前几天在 csdn 下载资源的时候才发现自己 csdn 有近 200 的下载积分,看了看共享的资源,哈哈 ... 7年前写的五子棋游戏很受欢迎。
下载地址:新手入门五子棋游戏 刚入行的时候写的,采用的 "权值" 计算法。
在这个 AI 的浪尖风口上,借助我对游戏领域的热爱,在工作余外的时间唤起了我的想法,学习 AI 实现一个五子棋机器人。
一、五子棋介绍
种类及区别
先说说五子棋吧,通常大家玩的五子棋分为带禁手和不带禁手两个版本,
(前者称之为连珠
Renju,后者一般称之为五子棋
Gomoku)
然而无论哪一个版本,先手黑棋均必胜。
(所谓黑必胜
的意思是,只要黑棋按照一定的方式下,白棋选择棋盘上的任何一个点都不可能赢棋。)
(禁手规则增加程序复杂度,暂不考虑加入)
这里只说结果,至于为什么参考文末资料:
1992年Victor Allis通过编程证明不带禁手的五子棋,黑必胜。
2001年Janos Wagner第一次证明的带禁手的五子棋,也是黑必胜。
先手优势及棋谱介绍
黑棋的优势到底有多大呢?在26个职业开局里,已经发现有19个是黑棋必胜的(一打必胜)。
因此为了进一步削弱黑棋的优势,国际上推出五手两打
的规则。
(就是黑棋的第三步需要下两个点,但由白棋挑选让其下较弱的哪一个)
可是人们发现黑棋带禁手依然是必胜。
从实践的角度来讲,网上是可以搜索地毯谱
的,一般在几百兆左右,可以用renlib
软件打开,
所谓地毯谱的意思就是黑棋会指定下法,但白棋每一步都可以选择棋盘任意位置,最后黑棋必胜。也就是说,只要按照此棋谱下棋,五子棋世界冠军都一定会输给你。
( 目前花月、浦月、云月、雨月、峡月、溪月、金星、水月、寒星、明星、岚月、新月、名月,山月,残月都是五手两打
必胜)
那么正式的比赛是怎么玩的呢?
现在的正式比赛通常会常用三手交换
、五手两打
这些复杂的规则来平衡比赛,但这些规则的各个分支也是逐渐被人破解,
五子棋的比赛已经很大程度不是在考验自己的临场发挥,而是考验选手对于少量黑白平衡 分支的记忆情况。
广义的五子棋
不带禁手的五子棋是属于一类更为普遍的 m,n,k游戏 的一种特例,既 15,15,5。
m,n,k游戏是指m行n列,轮流下子,连成k个算赢。这个在数学中专门的研究如果在最理想下法(Perfect Play)
的情况下有什么样不同的结果,
比如标准的三连棋(Tic-tac-toe)是3,3,3是一个平局,同样只有六路棋盘的五子棋也是平局,当然上面我们已经说明了15,15,5是先手必胜,
还有研究发现11,11,5也是先手必胜。m,n,k游戏只有先手必胜和平局两种结果。由于每下一个子都一定会对下子一方那一方有优势,
所以可以通过反证法证明m,n,k游戏里不可能有后手胜利的情况。如果后手有胜利的方法,
那么先手可以提前借鉴(Strategy stealing)
过来实现必胜。
参考来自:Csdoker's Blog
二、人工智能介绍
先看图,来自:《Google TensorFlow 深度学习架构》
AlphaGo 的介绍跳过、说说我们中国阿里巴巴的 "鲁班" 号称每秒能够做 8000 张海报的 AI + Design 设计师。
其实也是机器学习在图像领域的应用,通过循环训练的方式。
在回来说本文的重点 "人机博弈" ,AlphaGo 主要是由三个部分组成:
蒙特卡罗数搜索(Monte Carlo tree search MCTS)
估值网络(value network)
走棋网络(policy network)
核心就是估值和走棋,故名思议。
通过在大量人类围棋高手对弈的棋谱获取的训练数据,走棋网络能够预测 57% 人类围棋高手的下一步;
但是通过这个还远远不足以战胜人类冠军,就融入了估值网络,就是给当前的棋盘,判断每个棋位输赢的概率;
据说 AlphaGo 团队将进入游戏领域的研究,星际争霸2;
三、实现思路
开发语言:HTML5、JS (轻)
绘制棋盘、胜负判断规则、界面操作功能,这些比较基础的内容暂时不考虑;
采用一个三维数据来定义棋盘内容:
var _chessPieces = new Array();
_chessPieces[16][16][1] = -1; // [16][16] 棋盘大小:15 * 15,[1] 黑白棋子 (-1 没有棋子,0 白色棋子,1 黑色棋子)