Mathematica工具箱：ChessY-生成、可视化和分析位置象棋图的软件

SoftwareX 9（2019）39ChessY：用于生成、可视化和分析位置象棋图的Mathematica工具箱米歇尔·鲁伊-莉莉丝Unité de Neurosciences，Information et Complexité（UNIC），CNRS，1 Ave de la Terrasse，91198 Gif-sur-Yvette，Francear t i cl e i nf o文章历史记录：接收9八月2018收到修订版2018年12月17日接受2018年12月17日保留字：象棋PGN parser图论博弈论Mathematicaa b st ra ct国际象棋游戏无疑是历史上最受欢迎的双人战略棋盘游戏之一，休闲玩家和竞争着名的专业人士都喜欢，并在各种领域中作为原型研究课题虽然在大量不同的平台上有大量的解析器可以用来处理在线数据库中提供的国际象棋比赛记录，但令人惊讶的是，MathematicaChessY试图填补这一空白，通过提供一套简单的工具来处理便携式游戏记法（PGN）国际象棋记录及其转换为位置国际象棋图，从而为使用Mathematica在强大的图论范围内系统分析国际象棋游戏打开了大门。©2018作者由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v1.0用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX_2018_142法律代码许可证BSD-2-Clause使用的代码版本控制系统无Wolfram Mathematica使用的软件代码语言、工具和服务编译要求、操作环境依赖性Mathematica v10. 0或更高版本如果可用，链接到开发人员文档/手册http://mrudolphlilith.github.io/publications/Peer-ReviewedArticles/A38/A38.html问题支持电子邮件rudolph@unic.cnrs-gif.fr1. 动机和意义国际象棋有64个方格，6种类型的32颗棋子，棋子在方格之间的离散移动受到严格限制，可以说是简单的规则集，国际象棋无疑可以被视为图论中网络的经典例子[1]。尽管许多与国际象棋相关的问题及其解决方案，例如骑士巡回赛问题参见[2，3]），然而，对在图论背景下记录了几十年的国际象棋比赛的可用数据集的系统分析仍然很少并且主要限于可视化各种国际象棋策略和搜索算法（例如，见[4]，见[5]，见[6]。一个原因阻碍了国际象棋游戏的全面图论分析当然是与解析在线PGN（便携式游戏符号）数据库相关的固有困难。PGN电子邮件地址：rudolph@unic.cnrs-gif.fr。网址：http://mrudolphlilith.github.io。https://doi.org/10.1016/j.softx.2018.12.004国际象棋记录使用由国际象棋联合会（FIDE）标准化的标准代数表示法（SAN），通过指定棋子的类型和目标方格来编码棋局中的位置变化。然而，这样的紧凑表示受到潜在的模糊性的影响，例如，多个块可以到达给定的目标正方形，这需要复杂的并且通常在计算上要求苛刻的解析算法以便完全解析。尽管各种编程语言的开源和专有解析器以及国际象棋游戏引擎都很容易获得（参见[6]最近的全面评论），但这些引擎只专注于使用评估函数评估游戏位置，与Shannon最初提出的类似[7]，并通过搜索可用国际象棋游戏的庞大数据库来选择有利的移动此外，许多这些解析器和引擎的API仅提供对给定位置的棋子的全部可能移动的有限访问，从而使得国际象棋图的构造困难且依赖。另一个也许是更重要的原因限制了更广泛的在图论文献中，国际象棋游戏的曝光是2352-7110/©2018作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx40M. 鲁比-莉莉丝/SoftwareX 9（2019）39P NE源目标目标源=PPPEN′′E----N ENE= −=关于 我们关于 我们{E E}∈{}{}--联系我们∈{}{}111222位置象棋图形的特殊构成棋盘上的每个方格对应于一个图节点，并且占据棋盘上方格的棋子可以合法执行的所有潜在移动包括这些节点之间的边的集合，如图11所示。1.一、然而，位置象棋图的定义构成偏离了无权无向关系图，即简单图，这在经典和应用图论中最突出的特征（参见[8]关于该主题的综合最近介绍）。实际上，大多数可用于分析真实世界网络的软件包仅配备用于处理简单图，其中包括通常需要手动更改核心数据和过程结构的国际象棋图。ChessY提供了一套基本的工具来解析、验证和可视化可用的PGN象棋比赛记录，以及构建、操作和分析象棋图。因此，ChessY为使用计算机代数环境Mathematica[9]作为强大的探索引擎对国际象棋游戏进行系统和深入的研究打开了大门。然而不幸的是，尽管国际象棋作为一个最突出的棋盘游戏的历史作用，据作者所知，没有包或工具箱尚未提供在Mathematica中，用于解析可用的PGN记录和从这些记录构建国际象棋图，从而使ChessY成为第一次彻底尝试，使用这个强大的平台上提供的图论和代数工具，为国际象棋游戏的更系统分析打开了大门。ChessY已经成功地用于研究大师和计算机玩家之间的国际象棋游戏，旨在识别和表征人类玩家和计算机国际象棋算法的游戏中采用的策略方法[10]。这项研究发现，对于特级大师和电脑玩家来说，保留更多和更高价值的棋子，同时保持与棋盘上方块的高潜在连接，是获胜策略的一个组成部分。然而，一个电脑玩家平均来说比一个特级大师更能利用这种僵化的有了这些发现，ChessY可能有助于在图论背景下刺激对国际象棋这一有趣游戏的进一步研究，并有助于描绘在人类玩家中观察到的战略和决策细微差别，以便潜在地纳入国际象棋游戏引擎。2. 软件描述ChessY是一个用Mathematica语言编写的高级函数和数据结构的小集合，用于生成，可视化和分析位置象棋图。国际象棋位置及其相关的图形可以手动构建，也可以通过解析可用的PGN国际象棋比赛记录来构建所有生成的数据对象都以易于访问的多维列表的形式提供，因此在Mathematica环境中，在ChessY提供的功能核心之外，可以随时进行进一步的操作。2.1. 软件构架ChessY是围绕三种主要类型的数据对象构建的，即象棋位置、节点和边。虽然position对象包含棋子列表、它们在棋盘上的位置以及表征给定位置的补充信息，但节点和边分别是一维和二维列表，唯一地描述与给定位置相关联的位置象棋图：P={info，{{i1，p1}，{i2，p2}，. . . }}、N= {s1，s2，. . . }的情况下，E={{i，i，s i}，{i，i，s i}，. . . }的情况下，i表示唯一的方格或节点标识符，其范围从1到64，从棋盘上的左下角的a1方格开始，到右上角（h8方格）结束，p是包含颜色（w和b分别表示白子和黑子）和类型（K、Q、R、B、N和P分别表示王、后、车、象、马和卒）的棋子标识符，并且s是节点状态，例如s1或s1分别表示被白色或黑色棋子占据的方格，或s0表示未被占据的方格。最后，info表示一个简单的关联列表，其中包含关于可能的附带移动的目标节点、易位移动的可能性ChessY使用这些信息来处理完整的国际象棋比赛记录，并在比赛期间构建与每个位置相关联的有效国际象棋图。上述数据对象由生成国际象棋位置和国际象棋图形的函数以及ChessY以下列表提供了ChessY中可用函数的概述。生成国际象棋位置：getPositionFromPieceFileRank[p1，p2，. . . ]getPositionFromPieceNode[p1，p2，. . . ]getPositionsFromGamePGN[m1，m2，. . . ]的一种用于生成棋位的函数，在棋盘上放置单个棋子，或者通过解析有效的这里，pw，b K，Q，R，B，N，P a，. . . ，h1，. . .，8是通过颜色、类型、文件和等级来标识件放置的4个字符串，p′w，b K，Q，R，B，N，P1，. . . 64是通过颜色、类型和节点ID标识棋子放置的字符串，并且m是单个国际象棋的PGN格式的字符串动生成棋盘图：getNodesFromPosition[P]getEdgesFromPosition[]给定一个棋位 ，这些功能提供了完整的一组节点和边，通过返回，一个长度为64的一维列表，包含所有节点状态和所有加权边的二维列表。象棋图形的可视化：showChessPosition[P]showPositionalChessGraph[，]用于生成显示国际象棋位置的图形对象的函数问题P在一个经典的，棋子在棋盘上的风格，和一个国际象棋图与节点N和边缘E，分别。animateChessPositions[{m1，m2，. . . }，{P1，P1，. . . }]animatePositionalChessGraphs[N1，N2，. . . 、一，二，. . ]函数返回交互式动画图形对象，显示多个国际象棋移动mi和位置Pi，或分别由其节点i和边i定义的多个这些函数用于动画完整的国际象棋比赛。象棋图分析：getNumberOfNodes[N]getNumberOfEdges[]函数返回一个列表，其中包含特定类型、颜色或在给定节点状态N中被占用，以及给定边列表E的边的数量E。getAdjacencyMatrix[E]返回象棋图的邻接矩阵的函数M. 鲁比-莉莉丝/SoftwareX 9（2019）3941×NENE→→N E=N EN P= − =====-= −Fig. 1. 由ChessY生成的国际象棋位置及其相关位置国际象棋图形的示例（示例1）。左侧面板以经典格式可视化国际象棋位置，中间和右侧面板分别显示了具有8 8和线性节点布局的位置国际象棋图。线性布局中拱形边的高度表示源节点和目标节点之间的棋盘（Chebyshev）距离。图中的位置是1972年第八届世界锦标赛第三轮斯帕斯基（白色）和菲舍尔（黑色）之间的第11步（黑色）。getConnectedness[E]函数返回象棋图的连通性，定义为边数E与具有相同节点数的全连通图中的边数之比getControl[N，E]getMobility[N，E]getDominance[，]函数，给定一个位置象棋图，以及分别返回控制、移动性和支配性，其中控制被定义为唯一未占用节点和由处于给定状态的节点作为目标的对手所占用的节点的分数，移动性被定义为唯一未占用节点和由处于给定状态的节点作为目标的对手所占用的节点的分数，支配性被定义为唯一未占用节点、处于给定状态的源节点和由对手所占用的目标节点的分数。getAverageNodeReach[ ，]的情况下，函数返回边所指向的唯一节点的数目从处于给定状态的节点发出，由处于该状态的节点的总数归一化。getOffensiveness[N，E]getDefensiveness[，]函数，给定一个位置象棋图，和分别返回给定状态中以相反状态（进攻性）中的被攻击节点为目标的节点的数量和给定状态中向相同状态（防御性）中的节点产生潜在边的节点的数量2.2. 软件功能ChessY从这些记录构造位置象棋图开始于将象棋记录中常用的文件秩平方标识fr转换为数字节点标识。fieri∈ [ 1，64]使用函数i（f，r）=8< $（r−1）+（f−1）+1，其中板. . ，h8。 每个节点i可以有三种状态s i之一，这取决于相应的正方形是被白色或黑色块占据（分别为s i1和s i1），还是空的（s i 0）。然后，每个被占用的节点i 对于潜在的捕获移动，除了在途中，目标的状态节点是sj si。 对于易位移动，存在两个源节点和目标节点，s i1s i2和s j1s j20，而对于所有其他合法移动，包括顺路和非捕获提升，s j0。特殊的移动（王车易位和过路）需要一个较早的游戏位置的减少记录，由协会列表信息进行， P.最后，如果一个给定的位置产生一个边到一个节点在状态si和占用的国王（检查），那么从节点发出的潜在的边缘在同一状态si的集合仅限于元素，删除这个节点作为潜在的目标在下一个位置。如果这个集合是空的，给定的图标志着一场国际象棋比赛的结束（将死）。这样，实现了表示给定象棋位置生成的位置象棋图由其节点N和相关边E完全描述，并且与手动或通过解析有效PGN游戏记录获得的位置P一起，可用于使用ChessY中提供的工具或嵌入平台Mathematica的探索潜力进行可视化 和 分 析 。 具 体 来 说 ， ChessY 的 getEdgesFromPosition 和getAdjacencyMatrix函数（参见第2. 1节）返回的边列表E和邻接矩阵aij2.3. 绩效评价为了评估ChessY的性能，在OSX 10.11（El Capitan）上运行的2013 型号Mac Pro （3.5 GHz 6-Core Intel Xeon E5 ，64 GB1866 MHz DDR3 ECC）上分析了包含2000条国际象棋比赛记录的PGN数据库。 用于解析单个PGN国际象棋游戏记录并生成相关联的游戏位置（函数getPositionFromGamePGN）的平均CPU时间为1.95秒，标准差（SD）为0.77秒，用于在平均游戏期间为每个位置构建位置国际象棋图（函数getNodesFromPosition和get-EdgesFromPosition ） 的CPU时间为 6.03 秒 （ SD 为 2.34秒）。最大的误差是这些评估是国际象棋游戏固有变异性的直接结果，在调查的样本数据集中，平均位置数为74（SD为40）最后，在生成节点和边之后使用第2.1节中列出的完整分析函数集对游戏期间生成的位置象棋图进行分析，平均CPU时间仅为0.41 s（SD为0.19 s），这是位置象棋图非常小的直接结果（64个节点和平均1.5%的稀疏42M. 鲁比-莉莉丝/SoftwareX 9（2019）39图二. 在实施例2中获得的1972年第8届世界锦标赛期间Spassky（白人）和Fischer（黑人）之间的完整比赛结果的可视化。示出的是总连通性，其被定义为实际边和可能边的数量之间的比率，控制，其被定义为唯一未占用节点和被给定颜色状态中的节点作为目标的对手所占用的节点的分数，以及防御性，其被定义为给定颜色状态中的节点的数量，其向相同状态中的节点产生潜在边，白棋和黑棋在比赛中的位置。3. 说明性实例例1. 为了说明ChessY的使用，第一个例子展示了在第八届世界锦标赛（1972年7月16日，雷克雅未克）期间Spassky（白）和Fischer（黑）之间的第三轮臭名昭著的位置23（移动11，黑）的国际象棋图的生成，其输出如图1所示。position = position 23 SpasskyFischer 1972; （ * 在ChessY.m中定义 *）nodes=getNodesFromPosition[position];edges =getEdgesFromPosition[position]; g1= showChessPosition[position];G2=showPositionalChessGraph[nodes，edges];g3 = showPositionalChessGraph[nodes，edges，NodeLayout->“LinearV”，EdgeLayout->“Chessboard”，ShowFrame->True];GraphicsGrid[{{g1，g2，g3}}]实施例2. 在第二个例子中，处理了Spassky和Fischer之间的完全博弈。在从PGN游戏记录中提取出有序的移动列表之后，通过解析所有移动来生成有效国际象棋位置的列表，并且生成与每个位置相关联的节点和边的列表。最后，位置，节点和边缘数据对象被用来分析游戏图形理论上，特别是连接性，控制和防御性的白色和黑色件评估作为一个功能的层在游戏中。该分析的结果如图所示。 二、（*.加载PGN文件并提取移 动列表.* ）（* 获取游戏位置、节点和边的列表*）positions = getPositionsFromGamePGN[moves];For[i=1，i=Length[positions]，i++，nodes =Append[nodes，getNodesFromPosition[positions[[i];edges =Append[edges，getEdgesFromPosition[positions[[i]];（* 分析游戏的所有位置 *）对于[i=1，i=Length[positions]，i++，numberOfEdges [numberOfEdges [[i]]，State];co=int [i，i，i，i];C为Append[c，getControl[nodes[[i]]，edges[[i];d = Append[d，getDefensiveness[nodes[[i]，[[i] nums];];（*. 显示结果. * ）的文件4. 影响尽管国际象棋的有限和离散的时空构成可以被看作是图论中网络的一个典型例子，但到目前为止，在图论的强大范围内对大量可用的国际象棋比赛记录的系统研究仍然很少，这主要是由于与从PGN比赛记录构建国际象棋图相关的固有困难，以及位置国际象棋图的特殊性质ChessY工具箱试图弥合这一差距，它提供了一组基本的数据对象和函数，用于有效解析PGN记录，并使用Mathematica构建与这些记录相关的位置象棋图。计算机代数环境Mathematica被选中是因为它的探索性，沙箱般的性质允许ChessY中提供的工具的简单扩展，以及通过使用其数值和代数功能进一步检查国际象棋图形的几乎无限据我们所知，ChessY是第一次认真尝试为Mathematica中的国际象棋图形的构建、可视化和分析提供一组连贯的函数和数据结构，并且已经成功地用于分析大师和计算机玩家之间的国际象棋游戏，旨在识别和表征人类和计算机玩家使用的策略方法[10]。ChessY的目标是为在图论背景下研究国际象棋游戏的研究人员提供一个易于使用和可扩展的工具箱，从而通过使国际象棋游戏记录可用于网络分析的数学领域，促进对与这种intrigu- ingboardgame内在相关的动态复杂性随着Math-ematica作为嵌入平台的选择，ChessY将有望激发人们考虑研究国际象棋游戏的新方法，而不仅仅是数值分析，而是更正式的代数和算子图论途径。最后，通过打开系统图论研究的大门，ChessY可能会使我们更接近理解战略思维和决策核心的齿轮过程的雄心勃勃的目标，以及更像人类的计算机国际象棋M. 鲁比-莉莉丝/SoftwareX 9（2019）3943超越线性评价函数的算法或复杂决策树中的复杂自适应搜索，形成大多数当代国际象棋程序的概念基础。5. 结论软件包ChessY提供了一套易于访问且连贯的函数和数据结构，用于解析国际象棋比赛的PGN记录，以及Mathematica环境下位置象棋图的构建、可视化和分析[9]。再加上后者的无限探索潜力，ChessY是一个在图论的强大限制内对国际象棋游戏进行系统的数值和形式代数研究的场所。致谢作者希望感谢奥黛丽·赫本·勒恩对本文提出的宝贵意见和启发性的讨论。此外，作者还要感谢JAG Willow、CO Cain、S Hower和LSDee对本研究的宝贵贡献。研究部分由CNRS支持。利益冲突我们希望确认，本出版物不存在已知的利益冲突，并且本工作没有可能影响其结果的重大财务支持引用[1]沃特金斯JJ首页>外文书>人文>心理励志> Across the Board：The Mathematicsof Chessboard Problems 北京：清华大学出版社.[2]Benjamin A，Chartrand G，Zhang P.《图论的时尚世界》。普林斯顿大学出版社;2015.[3]约翰逊·K关于m × n象棋图的控制链。（硕士论文），默里州立大学;2018年。[4]陆文良，王永生，林文春.国际象棋进化可视化。IEEE Trans VisComputGraphics2014;20：702-13.[5]世界国际象棋联合会。Fédération Internationale des Échecs，FIDE，Hand-book. http://www.fide.com/fide/handbook.html? id=207& view=article.[6]利维DNL。计算机国际象棋纲要。Springer; 2009.[7]香农角为计算机编程下棋。Phil Mag1950;41：256-75.[8]纽曼MEJ。网络：介绍。牛津大学Press; 2010.[9] Wolfram Mathematica沃尔夫勒姆研究公司2016年。[10]鲁珀特-莉莉丝·M下一盘漂亮的象棋怎么样？IEEE Transactions onGames2018.提交出版。