设计一个中国象棋的人机博弈软件需要学习哪些东西?

设计一个中国象棋的人机博弈软件需要学习哪些东西?

你一个人搞比较头疼,做这个的一般是团队,目前武汉大学的刘博士做的不错,国内做这块的不到五家,哈工大的学生参与过几届比赛,水平不高。我这边有些资料,给你看看,希望对你有帮助。

你需要了解以下:

中国棋软的发展历程

拆解经典326

鲟鱼的发展历程

NNUE技术的应用

中国云库

中国象棋的基本逻辑

棋规如何植入

残局库的实现

显卡引擎GG的逻辑

谷歌zero的自我学习方案

1. 深学基本单元——感知机是一类人造神经元,在许多神经网络中,主要的神经元模型是sigmoid神经元。

2. 感知机如何工作?

3. 一个感知机通过一些二进制的输入x1,x2,...x1,x2,...,然后产生一个二进制的输出:

在上图中,感知机有三个输入x1,x2,x3x1,x2,x3,权重提供了一个简单的规则来计算输出,它用权重w1,w2...w1,w2..(上一层与下一层的每一个神经元之间均会有一个权重,后文会提及).来表示各个输入对输出的重要性。神经元的输出,要么是0要么是1,由某感知机的值是否小于或者大于某一阈值来决定。和权重一样,阈值(threshold)也是一个实数。输出结果用代数式表达即为

以上就是感知机的工作原理。

你可以认为感知机是一种通过权衡各个因素做出决定的设备。举个例子,假设周末就要来了,你们城市有一场奶酪节,你很喜欢奶酪,你正在犹豫要不要去参加,你可能通过权衡下面三个因素来做出你的决定:

1. 当天天气怎么样

2. 你的男朋友或者女朋友要不要一起去

3. 交通是否方便

我们可以通过对应的二进制变量x1,x2,x3x1,x2,x3来表示这三个因素。比如,x1=1表示天气很好,x1=0表示天气很差,同样x2=1表示女朋友想去,以此类推。

现在,假设你真的非常喜欢奶酪,以至于你无论你女朋友去不去,或者交通十分不便,你都很想去。但是可能因为你又非常非常讨厌恶劣天气导致你绝对不会参加。这时你可以使用感知机来模拟这种决策。因为天气对你的影响最大,你可以选择w1=6来表示天气的权重,w2=2,w3=2来表示其他的因素,w1的权重最大表示天气因素对你影响最大。最后假设你选择了5作为阈值,这样以来,你的感知机决策模型就建立好了。

显然,人类的决策模型不仅仅只有感知机。但是这个例子说明了感知机如何做出决定的。一个复杂的感知机网络可以做出更加精准的决定似乎是合理的:

在这个网络中,第一列感知机——我们称作第一层感知机,通过权衡输入用来做三个很简单的决定。那么第二层的感知机是干什么的呢?这些感知机每一个都通过权衡第一层输出的结果作为输入而做决定。这样以来第二层的感知机可以比第一层做出更加复杂和抽象的决策。更复杂的决策可以在第三层做出。通过这种方式,一个第一层的感知机网络可以进行十分复杂的决策。

顺便说一下,我们定义的一个感知机都只有一个输出,上图的多层感知机看起来一个感知机有很多个输出,其实它只是把同一个输出传递给不同的下一层感知机用来利用(但由于权重后一层接收到的输入均不相同)。

让我们简化一下感知机的描述方式,首先我们可以使用向量点积的方式代替∑jwjxj,即W⋅X=∑jwjxjW·X=∑jwjxj,其中W和XW和X分别是权重值和输入值所组成的向量。其次,我们可以把阈值threshold移到不等式的另一边,即b=−thresholdb=−threshold,其中b被称为感知机的偏差。通过偏差代替阈值,综上,感知机规则改写为:

你可以把偏差b看作衡量感知机输出1的难易程度。从生物学的角度来讲,偏差衡量一个感知机是否容易激活。如果偏差b是个很大的实数,那么该感知机就很容易输出1。显然,目前引入偏差让我们对感知机的描述只是产生了很小的改变,后面我们将会看到它导致的进一步简化。后文我们将不再使用阈值而是使用偏差。

前面已经说过感知机是一个权衡输入做决定的方法。感知机的另一种使用方法是计算我们通常认为是底层计算的基本逻辑函数,如AND、OR和NAND。比如,假设我们有一个感知机有两个输入,每一个的权重都是-2,偏差是3,下图是该感知机模型:

然后我们看到输入值为[0,0]的话,感知机输出值就为1,因为(−2)∗0+(−2)∗0+3=3(−2)∗0+(−2)∗0+3=3是正数。这里使用*表示乘法是显而易见的。同样无论输入[0,1]还是[1,0],最后产生的结果都是1,但是当输入[1,1]的时候产生的结果是0,因为计算出来的表达式为-1。其实我们的感知机在这里实现了一个NAND功能。

该例子说明了感知机可以用来计算简单的逻辑函数。事实上,我们可以使用感知机网络计算任何逻辑函数。因为任何逻辑计算都可以通过NAND组合而产生。比如,我们可以使用NAND门来构建一个含有两位的电路x1和x2x1和x2。这需要按位求和,x1⊕x2x1⊕x2,也需要在x1和x2x1和x2都为1时该位设为1,也就是做按位乘积x1x2x1x2:

为了得到等价的感知机网络,我们将所有的NAND门替换为拥有两个输入,输入权重均为-2,偏差全为3的感知机。下图是所得的网络。

需要注意的时,最左侧的感知机的输出被最下方的感知机作为输入使用了两次。前面的感知机模型的定义中并没有说是否允许一个输出被同一个感知机使用多次。事实上这并不重要。如果我们不想允许这种情况存在,我们可以简单的将两天直线合并,用一根权重为-4的线代替这两根权重为-2的线。然后上述感知机网络变为下面这个等价的网络,其中没有标记的输入权重仍是-2:

到目前为止,我都是把像x1,x2x1,x2这样的输入当作变量画在了网络的左侧,事实上,通常我们会画一个额外的感知机——输入层,对输入进行编码:

可以看到输入感知器有输出但没有输入.

但它实际上并不是一个没有输入的感知机。如果我们确实有一个没有输入的感知机,那么∑jwjxj的值一直都是0,因此感知机的输出就只和偏差b有关,这时感知机仅仅输出一个固定的值,而不是期望得到的值。我们最好把输入感知机看作是一个特殊的单元,用来简单的定义为了输出所需要的那些值x1,x2...x1,x2...

上述的例子论证了一个感知机网络可以用来模拟许多包含了NAND门的电路。因为NAND门是通用的计算方法,因此感知机也通用于计算。

以下是历届奥林匹克计算机软件大赛中国象棋

1989 第一届:特级大师(虞希舜)、象棋专家、ELP、XIAN[美]

1990 第二届:ELP(许舜欣、陈志昌、邓武尧)、南开大学程序(NKW?)

1991 第三届:SURPRISE(mrsj吴韧)

1992 第四届:SURPRISE(mrsj吴韧)、ELP

第五届 因参赛软件未达三个取消该项目(长达九年)

2001第六届:ELP(许舜欣、陈志昌、邓武尧)、象棋世家、ABYSS’99[加]

2002第七届:ELP(许舜欣、陈志昌、邓武尧)、象棋世家、XieXie[法]

2003年11月第八届 奥地利:纵马奔流、XieXie、ELP、千虑、Lock(象棋世家)

2004年7月 第九届 以色列:千虑、ELP

由于种种原因许多知名软件从未参加过比赛:比如将族、棋隐、七星大师、Saola等, 在同一时期它们的水平不见得低. 当然现在再拿出来也没有比较的意义了.

2005年第十届中国台湾:象棋奇兵、象棋世家、棋天大圣、天马行空、千虑、XieXie、ELP、象棋经略、元棋、深象、象眼、棋谋、神奇、Jade

2006年5月第11届 意大利都灵:棋天大圣 象棋世家 深象 谢谢大师 千虑

2006年8月 浪潮杯首届中国计算机博弈锦标赛 北京

(个人以为这是象棋软件的历史性转折,人机大战中棋天大圣两和特级大师许银川)

1.棋天大圣 (王骄)

2.象棋奇兵 (赵明阳)

3.象棋旋风(陈朝营)

4.天机 (张旭)

5.将神传说(雷春鸣)

2007年棋软比赛成绩:

1.象棋旋风(陈朝营)

2.天机 (郑旭)

3.棋天大圣 (王骄)

4.佳佳象棋 (李国来)

5.象棋奇兵(赵明阳)

2008年棋软比赛成绩:1 Intella 倚天象棋 陈朝营.韦余涛2 Cyclone 象棋旋风 张闽谭卓勋3 EThinker 天机 郑 旭4 Gagachess 佳佳象棋 李国来5 MonkeyKing 猴王 徐心和6 NEUChess 棋天大圣 王 骄7 3DChess 3D象棋 刘 进8 XQMASTER 象棋奇兵 赵明阳

2009年棋软比赛成绩:1.象棋名手 蒋志敏2.佳佳象棋 李国来3.陶情弈趣 谭卓勋.张闽(孤独)4.倚天象棋 韦余涛5.天 机 郑 旭6.新 奇 兵 王贤谷(赵明阳)

2010年棋软比赛成绩:

1.象棋旋风Tornado 陈朝营2.佳佳象棋Gaga chess 李国来3.象棋名手XQMS 蒋志敏.张闽4.先知象棋OracleX 张志福5.棋 弈Sunrise 北京理工大学6.哈工程 赵国东(哈工程)7.哈理工象棋 哈尔滨理工大学

推荐文献:Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm

神经网络与深度学习

Stockfish NNUE

Stockfish是一款开源国际象棋程序。由于最初的开发者中的两位分别来自挪威和意大利,为了纪念两国历史悠久的鳕鱼贸易,开发者将他们的程序命名为了Stockfish。在过去的十多年中,一众爱好者对其不断维护完善,使其成为了棋力最为顶尖的国象程序之一。Stockfish将传统计算机国际象棋技术发挥到了极致,包括但不限于alpha-beta搜索,各种剪枝技术,以及手动调整参数的估值函数等等。至少在2017年之前,Stockfish几乎稳坐各大计算机国象程序棋力排名榜第一名。然而2017年,Deep Mind发表了关于Alpha Zero的论文,并提出:以Monte-Calo Tree Search(MCTS)结合神经网络的方法照样可以达到甚至超越Stockfish现有的棋力。于是2018年,Leela Chess Zero(Lc0)横空出世。另一群爱好者依照Alpha Zero论文中的方法,经过近一年多的开发和参数训练,终于复现了Alpha Zero论文中的结果。截止到2019年底,在CCRL (Computer Chess Rating List)上,Lc0一度超越Stockfish,成为神经网络时代第一个依靠纯粹的强化学习的方法获得世界顶尖水平的国象程序。

知网也有几篇相关的论文,不过有点老,可以看看。下面补充一下GG:

象棋界面:可以加载引擎、连线游戏的软件。

免费界面如下

32位系统:兵河五四3.6,鲨鱼象棋,鹏飞象棋,新佳佳界面

64位系统:兵河五四4.1

象棋引擎:具有运算能力的程序。

免费引擎如下

32位系统:象棋巫师/象眼(棋力:☆)

旋风6.3破解版(棋力:★)

南澳1.6双核版(棋力:★☆)

名手326六核版(棋力:★★)

64位系统:三元加强版(棋力:★★☆)

国圣32u体验版(棋力:★★★)

佳佳象棋(棋力:★★★☆)

ggzero(棋力:★★★★★★)

64位系统的引擎均需要sse4.2指令集的支持,10年以前的老电脑无法使用

开局库:制作出来的棋谱,减轻引擎开局的运算压力,或设置飞刀陷阱

权重文件(network):相当于ggzero的学习文件,随着训练的不断进行棋力会不断提升

http://www.ttyes.com/ 中可以查看ggzero权重目前的棋力,elo越高,棋力越高。

常见显卡与运算性能得分图

zero无需开局库,开局能力强于其他CPU引擎。

目前通过MCTS算法改良,残局能力也有了大幅度提升,

审局常常比传统引擎更为准确。

但一些必杀的残局,弱卡仍还需要较长时间计算