# DataStructureAndAlgorithm_Chess

**Repository Path**: dancehole/chess

## Basic Information

- **Project Name**: DataStructureAndAlgorithm_Chess
- **Description**: 数据结构与算法大作业：三角网格五子棋
Git link was set as "chess";
Here is “Data Structure and Algorithm" Course Assignment: Trigonometric Network Gomoku Code Sharing Repository;
- **Primary Language**: C++
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 3
- **Forks**: 0
- **Created**: 2023-05-24
- **Last Updated**: 2025-03-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README


<h1 align="center">TriangleChess</h1>

<p align="center">
    <strong>简体中文</strong> | <s><a href="readme_en.md">English</a></s>
</p>

<p align="center">
  数据结构与算法课程设计大作业
    <br>
  三角网络五子棋（C++实现）
    <br>
    <strong>注意：本版本测试存在许多bug，请慎用</strong>
</p>
---

<div align="center">
    <a href ="https://dancehole.gitee.io/"><img src="https://img.shields.io/badge/Blog-dancehole-orange?style=flat&logo=microdotblog&logoColor=white&labelColor=blue"></a>
    <a href ="https://gitee.com/dancehole"><img src="https://img.shields.io/badge/Gitee-dancehole-orange?style=flat&logo=gitee&logoColor=red&labelColor=white"></a>
    <a href ="https://github.com/dancehole"><img src="https://img.shields.io/badge/Github-dancehole-orange?style=flat&logo=github&logoColor=white&labelColor=grey"></a>
</div>

<div align="center">
    <a href ="https://www.apache.org/licenses/LICENSE-2.0.html"><img src="https://img.shields.io/badge/license-Apache--2.0-yellow"></a>
    <a><img src="https://img.shields.io/badge/Repo_type-Tiny_C++_Game-blue"></a>
    <a><img src="https://img.shields.io/badge/Status-Finish-Chartreuse"></a>
    <a href="https://gitee.com/dancehole/chess/releases/tag/V1.0.0"><img src="https://img.shields.io/badge/Download-available-Chartreuse"></a>
    <a href="https://gitee.com/dancehole/chess/releases/tag/V1.0.0"><img src="https://img.shields.io/badge/Release-available-Chartreuse"></a>
</div>

---

> 2025/03/29 更新：目前web端已经适配，支持在线对战&人机对战，请访问[在线地址：https://dancehole.cn/chess/](https://dancehole.cn/chess/)

| 运行截图1                                                    | 运行截图2                                                    |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| <img src="https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess1.png" alt="image-20240203125830964"  /> | ![image-20240203125912606](https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess2.png) |
| web版截图1                                                   | web版截图2                                                   |
| <img src="https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess3.png"/> |                                                              |



## 📝 目录

- [发行版/demo下载](#demo)
- [项目简介](#description)
- [软件架构](#structure)
- [运行环境](#environment)
- [编译运行](#setup)
- [运行截图&bug反馈](#bug)
- [Contributing]()



## 💿发行版下载 <a name = "demo"></a>

**[点我下载最新版本](https://gitee.com/dancehole/chess/releases/tag/V1.0.0)**

- [Gitee Release](https://gitee.com/dancehole/chess/releases/tag/V1.0.0)
- <s>[Github Release]()</s>
- [Download Source Code](https://gitee.com/dancehole/chess/releases/tag/V1.0.0)
- [在线游玩地址：https://dancehole.cn/chess/](https://dancehole.cn/chess/)

**下载说明：**

- 建议直接下载exe文件
- Zip内含资源文件，可供开发使用

**版本说明：**

- 仅支持Windows(项目编译为.exe文件)，其他系统可以通过二进制翻译运行。
- 版本号V1.0.0，**经测试存在许多bug，谨慎参考**
- 最后版本更新时间2023.5（课程截止）



## 项目简介<a name = "description"></a>

**数据结构大作业简介**

### 1. 背景知识

众所周知，有一种国际知名的棋类游戏叫做**五子棋**，黑白双方通过相互堵截对方棋子同时，在或横或竖或斜组成五子直线相连来获取优胜。简述五子棋的规则和特点：五子棋一般使用横竖支线交叉的15×15的方格网络的棋盘，棋子放置在横竖线的交叉点上，故棋盘中总共有225个落子点。通常由黑方先行且可以落子到棋盘中任意位置，黑子落子后交由白方落子且同样白方可以落子到任意位置。黑白交替执行，直到一方先或横或竖或斜组成了五子相连直线即获得游戏胜利。实际游戏中，黑棋（先手）有着较大的优势，因此在国际比赛中会设置一些禁手。**本大作业不需要考虑禁手**。

相较于围棋来说，五子棋缩减了围堵的难度和胜负的判断，整体游戏规则简单，上手容易，棋盘的变化也远没有围棋那么复杂，十分适合拿来作为我们大作业的课题。但是，我们要做的并不是普通的五子棋。众所周知，五子棋的代码在网络上存在大量可用版本，那么能否设计一个让同学们有着一定自主发挥空间，又不是太难的五子棋大作业？

当然是可以的，我们可以设计如下图2所示的**三角网络五子棋**。如图2所示，新式的三角网络五子棋当中，棋盘由三条斜线交叉得到，棋子落子在三条线共同的交叉点上。此外，在三角网络五子棋当中，获胜条件仅判断线上是否组成了五子直线相连，将原来方格网络中8方向减少了6方向，实际上降低了五子棋规则的难度，使得这种改编意外地适合用来作为同学们的大作业。此外，因为棋子能够延申的方向减少了，实际上降低了围堵的难度，因此减低了黑棋的先手优势，但同时也增加了双方获胜的难度，可能会**比较容易出现平局的情况。**

<img src="https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess4.png" alt="image-20240203123946424" style="zoom:50%;" />

三角网络五子棋示意图

三角网络五子棋详细规则如下所述，其中绝大部分规则和方格网络五子棋规则基本一样，其中不同的地方将加粗表示：

1. 通过观察可得方格网络棋盘其实是由共心的7层正方形构成，且每层正方形上由8×L个落子点，L为层数，共计1+8+16+24+32+40+48+56=225个落子点。同理，如图3，设置三角网络棋盘为共心的7层六边形构成，每层六边形上由6×L个落子点构成，共计1+6+12+18+24+30+36+42=169个落子点，其中三方向的直线各有15条，共计45条直线。

<img src="https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess5.png" alt="image-20240203124056214" style="zoom:50%;" />

三角网络五子棋棋盘示例

2. 黑棋先行，白棋后行，黑白棋交替进行。落子只能落在未有落子的三条线的共同交叉点上。
3. 当一方在率先组成了五子相连直线，则该方胜利，游戏结束。**在三角网络五子当中只需要考虑连线方向，而不需要考虑未有连线的任意斜方向**。
4. 当无其他可落子之处，且仍未有一方组成五子直线相连，则平局，游戏结束。



### 2. 题目设定

**大作业的课题：实现上述三角网络五子棋的对战逻辑，以及进一步实现人机对战功能**。

此处将详细说明大作业中的各个部分的提示和细节要求。

1. **使用合理的数据结构表现三角网络棋盘上的落子状态**

如上文背景中所述，需要保存的数据主要是169个交叉点的落子情况，以及169个交叉点之间基于45条直线的邻接逻辑情况。因此，候选方案有多种，下面提示一种方案：

（1）   构建一个169个节点的顺序存储空间，并另外使用45组顺序表来来串联169个节点，存储节点之间的邻接关系。为了避免混乱且方便查找，可以给三个方向的每条线都进行编号，并在每个节点存储该节点所在的直线。节点和线的定义可以参考下述代码。

```c++
class GomokuNode {
	int status;
	int Line_x, Line_y, Line_z;
}
typedef GomokuNode* GomokuLine[15];

```

其中记录落子位置状况的169个数据构成了五子棋的棋盘状态，用status进行表示。落子位置之间的连线固定不变且只用来处理胜利判断，并不需要记录为棋盘状态。

2. **设计算法实现落子后的胜利判断**

简而言之，以落子点为中心向3个方向遍历，看看能否找出相连的5个棋子，如果能则获胜，反之，落子结束，交由对方落子。落子的函数可以设计为int move(pos, color),表示棋盘的pos位置放置color颜色的棋子，落子之后在函数内部进行胜利与否的判断，如果胜利则可以返回1代表当前执棋者获胜，返回0则继续游戏。

3. **设计三角网络的人工智能**

棋类的游戏过程本质上便是回溯树的构建、剪枝以及探索过程。如图4所示，如俗话所说的“走一步看十步”，棋类游戏的过程便是通过“预判对方”“预判对方的预判”“预判对方预判己方预判的预判”“……”来执行回溯树的搜索过程，最终采取己方收益最大化的行动。

其中，单次的预判可以简单描述为下述过程：

a)  模拟己方落子；

b)  模拟对方落子；

c)  重复a)和b)两个步骤n次；

d)  计算当次模拟的收益；

e)  变化模拟的落子状况，重复a),b),c)和d)四个步骤；

f)  在所有的模拟情况中，选出收益最大的一条路径，执行己方的落子。

![image-20240203124631151](https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess6.png)

<center>回溯树的构建</center>

人类智能在上述过程中，能够通过经验和学习对a)和b)步骤中模拟的落子进行筛选（即对回溯树进行剪枝）来加快回溯树的探索过程以及回溯树的探索深度。近年来的人工智能才刚能通过深度学习方法实现这种剪枝操作

其中，决定当前该在某处落子的依据为当前落子的收益，其中，收益可以通过该步落子所能到达的最终状态（即叶子结点），从下到上对各个中间状态来进行评估和计算。例如，下图所示为黑子落子时的回溯树，并根据最终状态黑子和白子获胜的可能性最终推算当前局面下落子的位置。注意，**能在下一步阻止对方获胜的落子位置应该将收益拉到最高，而存在多个能够阻止对方获胜的落子点位时，则可以同样基于回溯树判断更佳的落子点位。**

![image-20240203124718058](https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess7.png)

<center>通过当前局面所能得到的黑子最终胜率来选择落子路径</center>

**实现可人机对战的三角网络五子棋游戏**

假设玩家执黑子，则游戏过程可以简单整理下述状况：

（1）  初始化棋盘；

（2）  黑子尝试落子，判断是否可以落子，不能则游戏平局结束；

（3）  黑子落子，判断黑子是否获胜，黑子获胜则游戏结束；

（4）  白子尝试落子，判断是否可以落子，不能则游戏平局结束；

（5）  白子落子，判断白子是否获胜，白子获胜则游戏结束；

（6）  重复步骤（2）至（5）。



### 3. 作业要求

1. 尽可能多的使用本学期《数据结构和算法》的知识和技能来解决以上问题。

2. 从实际耗时和人工智能的效果用户使用的角度出发，**可以适当降低回溯树深度并采用诸如“当前活气口数量”“活气落子数量”等方式评价棋盘优劣势**。

3. 代码过程中可以设置棋盘规模变量n，从n=2逐步调整n=7来进行人机对战回溯树的调试工作。



## 软件架构<a name = "structure"></a>

软件架构说明：

本项目UI基于easyx图形库，基于c++（环境VS2022）编写。

项目架构如下：

![image-20230526232901818](https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess8.png)

- main.cpp：主函数入口文件
- logic.cpp/logic.h：逻辑文件
- ui.cpp/ui.h：界面文件
- ai.cpp/ai.h：ai落子算法文件
- global.h：全局头文件，存储所有结构体定义，库函数声明



## 运行环境<a name = "environment"></a>

1. [VisualStudio2022](https://visualstudio.microsoft.com/zh-hans/vs/)
2. [Easyx图形库]([EasyX Graphics Library for C++](https://easyx.cn/))



## 开发人员教程说明

相关文档：

<s>[如何优雅的进行多文件编程](./docs/优雅的多文件编程.md)</s>

[如何优雅的使用git协作](https://gitee.com/dancehole/code-labs/blob/master/Git/%E5%A6%82%E4%BD%95%E4%BC%98%E9%9B%85%E7%9A%84%E7%BB%99%E8%87%AA%E5%B7%B1%E7%9A%84%E4%BB%A3%E7%A0%81%E4%B8%8A%E4%BA%91.md)

<s>[项目说明文档](./docs/ProjReadme.md)</s>

## 编译运行<a name = "setup"></a>






## 实现思路

### 2.1 结构体声明

为了使全代码解耦合，方便团队协作，易修改性和方便代码重构，在此定义多个结构体，分别确定多个常用变量的数值，方便修改。

```c++
/*
* global.h
* 全局头文件
* 存放公共头文件，公共结构体
*/

#include<easyx.h>
#include <graphics.h>
#include <conio.h>
#include<iostream>
#include<stdio.h>

//数学常量
struct CConstVal
{
    const double PI = 3.1415926;
    const double SQRT3 = tan(60 * 3.1415926 / 180);     //根号三
};

//逻辑棋子
struct ChessPoint
{
    int line1;      //k=tan60°
    int line2;      //k=tan-60°
    int line3;      //竖直的线
    int status; //-+1为占用，0为空闲
};

//物理坐标(已弃用)
struct CPosition
{
    int x, y;       //物理屏幕的像素点x，y
};

//物理坐标
struct CPoint
{
    int x;
    int y;
};

//设置信息
struct SettingsVal
{
    int BlackWhiteFlag;
    int x;
    int y;
    CPoint midPoint;
    int sideLength;
    int circleSize;
};

//游戏进行时信息
struct RunningGameValue {
    int totalchess;     //合计落子数
    int board[15][15][15];
    int winflag;
};

//调试信息，现可弃用
struct DebugValue
{
    int shortDelaytime;
    int longDelaytime;
};

//棋子权重
struct ChessPriority
{
    ChessPoint point;
    int priority;
};
```



### 2.2 前期设计思路



#### 2.2.1 项目架构选型，开发环境选取。

开发环境影响了开发的难度，上限，实现效果与具体功能的实现。对此，经过研究探讨，确定以下可能的选型：

1. 方案一：使用虚幻引擎制作。以虚幻4（UE4）为例，虚幻引擎在制作2D-3D动态界面，单位素材的导入、制作与使用具有巨大优势，对于实现下棋界面的3D效果，游戏渲染效果等都有不错的优势。基于C++开发结合图形界面也能使我们相对熟悉。缺点是因其功能太过强大，实现一个功能与开发过程相对复杂。

   <img src="https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess9.png" alt="image-20230615004318637" style="zoom: 50%;" />

   <img src="https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess10.png" alt="image-20230615004440713" style="zoom: 33%;" />

   图：使用虚幻4制作五子棋示例,及实现效果

2. 方案二：使用Unity制作

   Unity使用C#开发，是当前最流行的小游戏引擎之一，有着完善的物理引擎库，xxx

3. 方案三：使用VS-c-easyx制作

​		由于在大一时积累相关经验，easyx的使用具有天然优势。

图：大一作业

4. 方案四：使用原生C（windows.h）制作

无opengl的封装，可移植性差。

经过对比探讨，最终确定使用方案三。



#### 2.2.3 棋盘构建思路

纯数学逻辑

为做到棋盘绘制与相关参数解耦合（方便修改），需要精确的数学分析。

由此确定如下：

<img src="https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess11.png" alt="image-20230615095357466" style="zoom:33%;" />

假设界面长度为x，宽度为y，则确定中心点坐标midPoint($\frac{x}{2}$,$\frac{y}{2}$)，如图所示

<img src="https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess12.png" alt="image-20230615095541148" style="zoom: 33%;" />

其次在尝试后，选择更换逻辑坐标。更换逻辑坐标为midPoint，方便绘图。假设最小的三角形半径为r（最小同心圆半径）

绘棋盘思路：先画七个同心六边形，然后通过循环连接各个六边形的线

所以我们需要计算出每个同心六边形的点，我们以最上方点设立下标“0“。有：

六边形各顺位点，顺位index
$$
A_x=x+r*sin(60*index*Pi)
$$

$$
A_y=t+r*cos(60*index*Pi)
$$



​	



#### 2.2.4 建立棋盘映射

自行阅读代码

#### 2.2.5 胜负判断

自行阅读代码

#### 2.2.6 棋盘架构优化

自行阅读代码



## 运行效果及Bug反馈<a name = "bug"></a>

### 运行截图

![image-20240203125912606](https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess1.png)

![image-20240203125844855](https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess13.png)

![image-20240203125912606](https://raw.githubusercontent.com/dancehole/image/main/danceholeLabs/project-gitee-chess2.png)



### bug反馈

- **赛博落子【严重bug】**：当落子不精确时，鼠标坐标会映射到一个虚拟的不存在无法被绘制的点。这本质上是因为数据结构定义了超过169个点（实际上定义了$10^3$个点，分别为三条直线的交点）。显然此架构是因为布线设计问题。**在落子精确时不会出现bug**
- 无胜利反馈。胜利后不会弹出标识，返回菜单等。



## 🙇‍ 贡献 参与我们<a name = "contributing"></a>

欢迎您参与贡献，我们鼓励开发者以各种方式参与文档反馈和贡献。

您可以对现有文档进行评价、简单更改、反馈文档质量问题、贡献您的原创内容，详细请参考[贡献文档]()。



## ☎️ 联系我们/作者<a name = "contacting"></a>

- <s>官方Q群：</s>

- 联系邮箱：1391755954@qq.com
- 个人网站：https://www.dancehole.top(随时停止维护)



## 👍 支持与致谢<a name = "contacting"></a>

- 团队成员：刘星晨（组长），谢垚璐，岑雄杰，陈一文，林俊彦，储涛，邓仕昊。

| Nickname昵称   | Contribution贡献                                             |
| -------------- | ------------------------------------------------------------ |
| Dancehole      | 仓库管理员                                                   |
| 刘星晨         | 组长，负责统筹规划项目，组织成员，项目测试。兼任UI设计       |
| 陈一文         | 副组长，和组长一起进行ppt和视频制作。兼任后期优化            |
| 林俊彦，储涛   | 负责回溯树的构建与ai落子的实现                               |
| 谢垚璐         | UI设计（开始界面，xxx）                                      |
| 岑雄杰，邓仕昊 | 负责项目前期工作（棋盘选型，ui工具选型，棋盘绘制，物理棋盘与逻辑映射建立，胜负判断，实现对战逻辑） |

**2023-5 物联网数据结构大作业项目地址**

**当前进度：作业已截止，文档及部分代码未完成（博弈树未构建）**