你好！



我们正处于圣彼得堡HSE的应用数学和信息学本科学习的第一年。在使用C ++进行一个学期团队项目的工作中，我们决定用机器人编写计算机版本的Intellector-在带有特殊图形的六角板上的国际象棋游戏。



在本文中，我们将讨论游戏的发展方式，如何驯服六角形板，如何在命令行上绘制以及如何制作几乎无法击败的机器人。







我们的团队有3个人：Yura Khudyakov，Valera Golovin，Misha Savrasov。对于我们每个人来说，这是第一个团队项目，因此在工作过程中，我们不仅写了专家文章，而且学会了在团队中工作并使用版本控制系统（在我们的情况下为git）。该项目有很多奇怪的地方，特别是自行车-有很多可以使用的现成好的解决方案。但是，我们项目的目标是获得经验，因此我们自己发明和实施了很多东西。

什么是智力？

首先，值得解释一下我们编写了哪种游戏。



游戏“ Intellector”最近已经出现并且仍在流行。首届公开锦标赛于今年在圣彼得堡举行。





智力专家与国际象棋在领域结构，规则和一套棋子上有所不同。但是，许多元素都很相似：例如，游戏中有一个Progressor角色，它扮演Pawn的角色。她只能向前走，到达极限时可以变成另一个身材。



这里的国王是一个称为“智者”的人物。游戏的目的是减少该片段，而不是对其进行核对（尽管这几乎是同一件事）。



游戏机制的差异源于该领域的具体情况。智力场是对称的，这使它与国际象棋在其王室和皇后区之间有明显的区别。



要理解本文，不需要了解规则和游戏能力。

通用架构

我们在应用程序中想要什么？

为了使游戏正常运行，您需要实现其主要组件：游戏逻辑。它包括一个董事会模型和移动规则。另外，为方便起见，值得保留移动历史并执行撤消/重做。



该板需要显示并允许用户玩。这是由游戏的图形组件-界面完成的。用户友好的界面应具有菜单和设置。



毕竟，您需要一个对手来比赛。我们决定为此目的制造一个机器人，以便玩家可以与计算机竞争。在这种情况下，漫游器的复杂度应该是可调整的。

申请方案：

1. 游戏逻辑
   • 六角板模型
     
     存储为六边形单元的二维阵列
   • 棋子的移动规则
     
     检查棋子的可接受性，获取棋子的所有可用棋子，以及球员的棋盘
   • 移动历史记录
     
     撤消并重做移动
2. 接口
   
   计划的2个接口：ncurses和Qt。项目中仅实现了ncurses，有关详细信息，请参见“接口”部分。
   • 显示
     
     字段在控制台中渲染和更新字段
   • 使用键盘键移动光标，无需鼠标即可播放
   • 显示移动的文本历史记录
   • 显示主菜单
3. 机器人
   • 随机机器人
   • 贪婪的机器人
   • Alpha-beta机器人经过
     
     优化，可以迭代所有动作

怎么做？

下图描述了一个非常简化的应用程序体系结构：





游戏部分负责所有游戏逻辑并存储棋盘。



当使用计算机打开游戏时，游戏与Bot



Controller中的机器人进行交互，从游戏中获取有关游戏的数据，并将其传输到界面上以显示给玩家。该接口依次将用户交互的结果通过控制器返回给游戏。



当有多个接口时，控制器形式的中间链接会派上用场（最初我们计划制作2个接口：控制台和图形接口）。他们都通过控制器以统一的方式与游戏进行通信，而不是每个人都以不同的方式进行游戏。

技术细节

游戏模型

六角板

考虑上图中的“游戏”部分。它必须存储棋盘并处理所有游戏逻辑。



为了更好地理解，您可以阅读我们从中获得此想法的文章。



我们将整个电路板存储在一个二维单元格数组中，其元素由一对坐标索引，(w,h)如下图所示。这样选择坐标似乎是很自然的，但是对于描述图形的移动是不方便的（例如，观察沿对角线移动时坐标如何变化）。





^{单元格沿水平轴w和垂直轴的坐标h}



为了方便描述图形的移动，我们将使用三维坐标。让我们选择一些单元格作为带有坐标的参考单元格{0,0,0}（为方便起见，它将与(0, 0)数组的单元格重合）。





^{单元相对于中心单元的三维坐标，坐标为，{0,0,0}}



沿对角线“从右至左，从下至上”x的位移由坐标表示，从底部至顶部的位移由坐标表示，y沿对角线的“从左至右，从下至上”位移由坐标表示z。移动到相邻单元格时，相应的坐标将改变一个。因此，如上图所示，每个单元格都接收三个坐标。



在这种情况下，单元编号不明确。例如，如果我们从具有坐标的中心单元格中{0,0,0}向左下移然后向上移动，我们将获得该单元格的坐标{0,1,-1}。但是，{1,0,0}如果您直接从中央单元格进入同一单元格，则具有坐标，如上图所示。





^{用于指定单元格坐标的另一个选项{1,0,0}。}



在“左-下”-“上”-“右下”循环中遍历任何像元会将我们带到同一个像元，但是将向量添加到其坐标{-1,1,-1}，其坐标之和等于-1。在脑海中以相同或相反的方向多次进行这样的行走，我们可以将任何单元格的坐标更改为等价的坐标，它们之间的差值将与矢量成比例{-1,1,-1}。为了消除歧义，在每个等价类中，我们选择一个三坐标系作为代表，其总和等于零。这种坐标选择是唯一的（证明！）。



让我们进一步描述该类中从二维坐标转换为三维坐标，反之亦然的算法Position。

Position(int w, int h) //    
        : x_{-w/2 — w % 2 - h}
        , y_{w % 2 + 2 * h}
        , z_{w / 2 — h} {
}

int posW() const { //       
    return -x_ + z_;
}

int posH() const { //       
    return (x_ + z_ — (x_ + z_)%2) / 2 + y_;
}

请注意，构造函数产生的坐标(x,y,z)加起来为零。在这种情况下，对于任何一组坐标，坐标(x,y,z)到的转换都(w,h)可以正确进行（总和不必为零）。



我们如何找到所有这些公式？通过科学的戳方法：通过分析二维坐标之一1（构造函数）和相反方向（方法）移动时三维坐标的变化。



使用三维坐标，我们可以轻松地检查单元格是否共线。例如，要检查两个像元在同一对角线上z，您需要找到一个连接这些像元的向量，并检查其等价类是否包含以下形式的向量：{0, 0, z}... Z可以是任何数字-此数字给出单元格之间的距离。实现对移动进行正确性检查并找到所有可用于移动的单元格将非常简单。



在代表板的二维数组中，我们将存储有关图形位置的信息。在每个单元格中，如果有一个棋子，我们将存储其类型和颜色。



在board类的实现中，我们仅将片段的类型存储在单元格中。我们需要一个可以在板上找到所有可能动作的类，并检查动作的正确性。

拼凑而成

我们已经FigureMoveValidator为每个图类型创建了一个具有6个继承者的类（如果在每种方法中都为图类型创建了切换条件，则可以没有继承者。）类的构造函数有2个参数：位置和板参考。在课堂上还有两种方法allMoves和checkMove。



让我们考虑一下方法allMoves。为了找到所有的移动，让我们组成一个可能的位移矢量数组并进行遍历。对于移动了一步的棋子，我们需要检查是否没有跳下棋盘，也没有进入棋子所在的单元。对于沿直线移动多个像元的图形，在前一个条件通过时添加一个移动矢量。



现在checkMove...我们记得我们知道如何检查数字是否在同一直线上。如果我们检查这条线上没有其他零件，则可以得到现成的Dominator（车模）的方法。如果碎片位于一条直线上，那么我们可以找到它们之间的距离，并获得渐进者（兵），防御者（像国王一样行走），情报（国王，只能割伤）和解放者（可以穿越一个单元格到达任何一个单元）的方法侧）。仍然有一个侵略者（一头大象的类似物），他从当前方向的六个方向对角移动到牢房（从牢房{0, 0, 0}到{0, 1, 1}，到{0, 2, 2}，等等：请参见下图中的灰色牢房）。对于此图，您可以尝试将一个坐标置零，并检查其余2个坐标的绝对值是否相等（由于三维坐标）。





^{侵略者可能采取的行动}



现在，我们需要弄清楚如何应对这些行动。让我们创建一个Move类，该类将存储移动的所有必要信息。我们决定存储2个位置和4个部件：部件从其移动的位置，部件的位置以及有关在每个单元格中站立的部件以及应用移动后将站立的部件的信息。这将使实现移动历史记录系统和移动回滚变得容易。

接口

建筑

该应用程序是在ncurses控制台库中编写的（这是它的教程）。该库允许您在控制台中创建伪图形。例如，Midnight Commander和Nano就是基于它的。



这个选择似乎很奇怪：还有许多其他的库，它们更漂亮，更方便并且可以跨平台使用。与此相关的是，我们最初计划创建2个界面：控制台和图形界面。在交付项目时，我们没有设法编写2个接口，而是在控制台版本中添加了更多功能。尽管从体系结构上讲，该应用程序仍被设计用于不同的接口。



有2个主要实体：显示和控制器...视图向玩家显示图片，控制器在不同视图和内部游戏模型之间进行调解。



显示屏处理所有用户交互：光标位置和移动，形状选择，可用字段突出显示，游戏完成等。影响电路板的动作涉及控制器，并向模型发送/从模型接收必要的信息。



显示屏会创建自己的电路板版本，但需要其他参数，例如光标的位置和单元格的颜色。这些参数不能添加到主模型中，因为不同的映射需要不同的参数。例如，在控制台界面中，您需要存储光标的位置，而不是在图形界面中，因为图形的选择和移动是用鼠标完成的。



如果玩家想知道可用于移动的字段，则会发生以下情况：

1. 播放器将光标移到图形字段并按空格键
2. 具有形状的字段标记为已选中
3. 接口是指selectCell控制器上的方法
4. 方法selectCell是指allFigureMoves模型的方法
5. allFigureMoves创建FigureMoveValidator计算所有可用动作的
6. allFigureMoves 找到的转移回到控制器
7. 控制器将它们传递给接口
8. 界面将重绘字段，突出显示可用字段

^{光标在面板的中间：淡蓝色的正方形上。在将其移动到该位置之前，用户选择了一个形状。可用的移动以绿色突出显示，并且所选单元格本身为紫色。}

如何画田野？

控制台界面在带有文本行的矩形窗口中呈现。如果将符号放在正确的位置并给它们上色，则会得到图片：





^{（Evil Pacman，用字母“ o”绘制）} ncurses中的



一个函数move(int y, int x)更改当前位置，该函数addch(chtype c)添加一个字符并将当前位置1右移（x —> x+1）。



可以将复杂的图片存储为二维数组，并逐行显示：当行结束时，将当前位置移动到下一行的开头。其原理与打字机非常相似。



如果终端支持颜色和其他文本属性，则在用户计算机上，我们游戏中的字段将被着色。



Ncurses允许开发人员在将文本输出到控制台时更改文本的属性（颜色，粗体，闪烁）。为此，请编写代码：

attron( *attributes* );
addch(c);
attroff( *attributes* );

每个符号都有其自己的颜色和背景颜色。现代游戏机最多支持256种颜色，因此您必须使用有限的设置：就颜色设计而言，这是非常可悲的。



输出的图像可以存储在代码中（就像我们最初所做的一样），也可以将它们存储在单独的文件中，并在程序启动时从中读取。为此，我们提出了自己的文件格式*.btn。



它存储游戏将读取和显示的文本图像。例如，形状或题词“白胜” /“黑胜”或菜单按钮。在这种情况下，有时您可能需要透明性以便不覆盖先前绘制的内容。为此，您可以在第一行#和“透明”符号列表之后添加一个哈希，这些哈希将在输出中被忽略。



例如，假设我们在屏幕上绘制了3个矩形：





将以下文件中的矩形添加到中心：

#C
AAAAAAAAA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
AAAAAAAAA

我们得到以下图片：





^{（为清楚起见，以黄色突出显示）}



此格式在开发菜单时特别有用。

菜单

游戏还具有一个包含设置的菜单，该菜单在游戏开始之前和结束之后绘制。



从文件中读取菜单按钮*.btn。这些按钮应具有大而优美的文字。我们不知道如何使用ASCII字符进行精美绘制，但是figlet（一种用于显示不同字体的ASCII文本的实用程序）可以：





这些按钮将框起从文件读取的标签：





然后将它们居中并顺序输出：





在某些菜单中，您可能会失败，例如，调整漫游器的复杂程度和颜色：





设计菜单系统最有趣的部分是将其元素组合到一个系统中。这是通过系统的一个独立元素（称为多路复用器）完成的。该名称受终端多路复用器的启发。



多路复用器接受用户按下的键，并将其发送到所有当前显示的菜单。每个菜单自行决定如何使用该键：忽略或以某种方式处理。处理菜单的结果返回到多路复用器，由多路复用器决定下一步要执行的操作：关闭菜单，创建新菜单，更改设置，关闭应用程序...



事实证明，这种方法很方便，但总的来说可能还不够：2个不同的菜单可以对同一个键做出反应，用户应该可以选择对哪个菜单做出反应。解决方案是使用特殊的键盘快捷键，使您可以在不同的菜单之间切换。例如，如在tmux中。但这是多余的，不是必需的。

机器人

如上所述，我们的游戏有一个机器人。我们试图使它对于初学者和有经验的玩家都变得有趣。



在描述机器人之前，我想谈谈一些实现细节。我们为每种形状分配了一些权重。它越大，这个数字就越有价值。我们使用公式（白块的权重之和）-（黑块的权重之和）来确定板上的位置。使White最大化此表达式，使Black最小化是有利的。



完整计算整个动作树是一项艰巨的任务，因此，我们仅计算了前几个动作（展望未来，事实证明，要计算出6个动作）。我们将董事会中处于一定深度的所有状态视为遍历树的叶子。



游戏中有三种不同类型的机器人：

• RandomBot — . .
• GreedyBot — «» , , .
• AlphaBetaBot — , - .

当我们开始进行优化实验时，我们意识到我们不能没有对该机器人的单元测试，因此我们为AlphaBetaBot“ a”创建了一个孪生兄弟，我们将其命名为OptimizedAlphaBetaBot。我们在上测试了所有用于优化的想法OptimizedAlphaBetaBot，而单元测试则有助于确保两个孪生兄弟找到相同的有用举动。通过在板上生成随机模式，RandomBot为我们很好地服务。要做到这一点，就足以要求RandomBot双方走几十遍。



总共OptimizedAlphaBetaBot 实现了3个主要的优化（此处按实用程序的降序排列）：

• 使用回滚。经过优化后，不再需要多次复制电路板来进行移动。
• FigureKeeper, , . std::vector .
• std::unordered_map Zobrish hashing.

除了主要的优化之外，还有一些较小的优化。例如，如果在排序之前您考虑了一定的移动来计算板上所有位置的值，那么您就不再需要对复杂的对象进行排序Move，而只需int对。



最初，计划实施几套评估功能：例如，一个被敌人威胁的人物的估计费用为一半。但是事实证明，该机器人玩起来很“干净”，丢了几块，所以事实证明，简单的操作更有效。



但是，该僵尸程序体系结构仍支持添加新的评估功能。为此，您只需要定义三件事：

1. 如果需要为给定的图形排列“从头开始”计算成本，则该函数
2. Delta函数，该函数应快速重新计算给定移动的成本。
3. 自定义类的构造函数的一组函数的编号FunctionSet。

您可以开启机器人大战，并观察整个过程。





^{由2个具有相同难度的机器人组成的游戏（可能达到6级中的第4级）。光标在整个游戏的区域中心}

结论

我们已经实现了一种类似于国际象棋的游戏，但是具有不同的规则和不同寻常的棋盘。我们的实现有扩展的空间。Intellector本身也在不断发展和变化：最近对规则进行了更新，我们的应用程序尚未支持该规则。例如，现在您无法在前2圈内越过中心线。



另外，我们最初计划了各种功能，但是在项目开始时还没有时间实施。例如，在这个应用程序中，我真的很想看一个网络游戏。同样，例如，在Qt上，一个不错的跨平台界面也不会受到损害。



也许全部或部分将在不久的将来出现。在此之前，感谢您的阅读！



Github仓库