2024全国大学生电子设计大赛全国初赛 E题 三子棋游戏装置 一等奖满分最简方案

感想：电赛初赛控制类题还是蛮简单的，别被五花八门的硬件搞懵了（决赛当我没说）。抓住核心，理念都是通用的。我是计科专业的，因此选择的控制类E题，相对来说背的知识要少很多，更考验智商。其实电赛结果都不重要，在电赛经历中对自己的磨练，尤其是“所想即所得”的快感弥足珍贵。要不是参加电赛，我都不敢想象自己做了一个人机对弈装置。通过电赛，见到了更宽广的世界。

声明：本文中绝大部分算法（所有核心算法）均是我个人想出来的，部分细节由队友补充，转载请私信！严禁盗代码！如果我发现谁盗我代码我直接全网曝光并且停更！

前言：我本人一向以天才自居，算法也都是最简洁干练的（那些艰深晦涩而复杂的算法往往是愚蠢的人写出），很多人劝我不要把代码开源，我偏要，我看不惯CSDN的那些VIP专栏，那是把智慧锁进了笼子里。文章格式就懒得调了。如果你们发现本文在逻辑上有缺失的部分，欢迎私信我进行补充！

三个核心算法：

1.棋子识别。

通过识别棋盘方格，计算差分列表，得出棋盘状态变化情况，根据黑棋先行的规则确定棋谱并保存。由于扰动的存在，实际每帧中方格的位置都会变化，因此通过计算汉明距离来匹配方格（待匹配方格与base(全局静态变量，初始九宫格)中九个方格进行比较）。理想情况汉明距离为一个方格，我取一半(当然也可以取1/3)。

// 计算两个点之间的距离
double distance(position p1, position p2)
{return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}// 寻找A中满足条件的点，并返回满足条件的点的个数
int find_points(position A[], int sizeA, position B[], int sizeB, position result[])
{int i, j;double threshold;int result_count = 0;threshold = g_min_distance;// 遍历A中的点，判断是否满足条件for (i = 0; i < sizeA; ++i){int satisfies = 1;for (j = 0; j < sizeB; ++j){if (distance(A[i], B[j]) <= threshold){satisfies = 0;}}if (satisfies){result[result_count++] = A[i];}}return result_count;
}double hamming(void)
{ // 计算汉明距离double min_distance = 99999;int i, j;g_min_distance = 99999;for (i = 0; i < 9; ++i){for (j = i + 1; j < 9; ++j){double d = distance(g_base[i], g_base[j]);if (d < min_distance){min_distance = d;}}}g_min_distance = min_distance / 2;return min_distance;
}position bind(u8 key)
{return g_base[key - 1];
}u8 label_1(position pos)
{int i;position tem;for (i = 1; i < 10; i++){tem = bind(i);if (distance(pos, tem) < g_min_distance){return i;}}return 0;
}position findpawns(position *fields, u8 lens)
{int result_count;int i;int j;int k;int h;position result[MAX_POINTS];position result2[MAX_POINTS];u8 disp[9] = {0};u8 comp[9] = {0};u8 compcnt = 0;static position PreResult[MAX_POINTS];static u8 PreResultCnt = 0;u8 key1;u8 key2;u8 sat;position a;if (lens == prefield_len) // 悔棋判定{for (j = 0; j < lens; j++){disp[j] = label_1(fields[j]);}for (k = 1; k < 10; k++){	sat = 1;for (h = 0; h < g_u8BordCnt; h++){		if (k == g_u8Bord[h]){sat = 0;}}if (sat==1){comp[compcnt] = k;compcnt++;}}for (j = 0; j < lens; j++){sat = 1;for (k = 0; k < lens; k++){if (disp[j] == comp[k]){sat = 0;}}if (sat == 1){key1=disp[j];}}for (j = 0; j < lens; j++){sat = 1;for (k = 0; k < lens; k++){if (comp[j] == disp[k]){sat = 0;}}if (sat == 1){key2=comp[j];}}//move(key2,key1) 此处代码省略a.x = 0;a.y = 0;return a;}prefield_len = lens;result_count = find_points(g_base, 9, fields, lens, result);if (PreResultCnt != 0){find_points(result, result_count, PreResult, PreResultCnt, result2);}for (i = 0; i < result_count; i++){PreResult[i].x = result[i].x;PreResult[i].y = result[i].y;}if (PreResultCnt != 0){PreResultCnt = result_count;return result2[0];}else{PreResultCnt = result_count;return result[0];}
}u8 SetLog(position *fields, u8 fieldlens)
{ // 记录棋谱position tem =findpawns(fields, fieldlens);if (tem.x!=0&&tem.y!=0){g_u8Bord[g_u8BordCnt] = label_1(tem);g_u8BordCnt++;return 1;}return 0;}u8 FillFileds(void)
{position fileds[MAX_POINTS];u8 u8FiledLen = 0;int i;for (i = 0; i < MAX_POINTS; i++){if (g_PointPosition[i].x != 0 && g_PointPosition[i].y != 0){u8FiledLen++;fileds[i].x = g_PointPosition[i].x;fileds[i].y = g_PointPosition[i].y;}else{fileds[i].x = 0;fileds[i].y = 0;}}return SetLog(fileds, u8FiledLen);
}

Q:为什么不直接识别棋子而要识别方格？
A:识别棋子方案复杂，且OpenMV无库函数支持（只有下限阈值）。
Q:差分列表是什么意思？
A:首先识别空白方格列表（棋子所在方格低于find_blob阈值）,第一次与base作差求出棋子所占空格列表（数组），与pre作差求出当前走法。

2.棋盘方格匹配按键标签。

由于实际中无法做到完全棋盘正置，故不需要区分是否旋转（不旋转默认为右转）。对于当前棋盘，利用一个布尔变量区分左转或者右转，用九个点（用（x,y）坐标形式表示一点）组成的一维数组表示各方格位置。对于右转的情况，先取y坐标最小的点，作为该组中的直线基准，然后取y坐标次小的（要求该点与本组基准点构成的直线斜率正负符号为b，如果斜率无法计算即直线垂直不符合要求），然后取y坐标次次小的（要求该点与本组基准点构成的直线斜率正负符号为b，如果斜率无法计算即直线垂直不符合要求），此三点为一组，分别标号1、2、3，对于剩下的点继续该操作分组，组内各点标号递增，如第二组内三点标号分别为4、5、6.最后按照标号大小顺序依次输出对应的点坐标。左转类似。这样可以保证坐标系和棋盘相对位置在旋转后不变，方格的顺序也不发生改变。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct
{double x;double y;
} position;typedef struct
{int x;int y;int label;
} Point;position g_base[MAX_POINTS];
bool rt = 0;
// 比较函数，用于qsort按y坐标排序
int compare(const void *a, const void *b)
{Point *pointA = (Point *)a;Point *pointB = (Point *)b;if (pointA->y != pointB->y){return pointA->y - pointB->y;}else{if (rt == 0) // 1return pointA->x - pointB->x;elsereturn pointB->x - pointA->x;}
}// 判断两点间的斜率符号是否与布尔变量b相符
bool isValidSlope(Point base, Point next, bool b)
{int dx = next.x - base.x;int dy = next.y - base.y;bool slopeSign;if (dx == 0){return false; // 垂直线不符合要求}slopeSign = (dy > 0) == (dx > 0);return slopeSign == b;
}void groupPoints(Point *points, int size)
{int label = 1;int i;qsort(points, size, sizeof(Point), compare);for (i = 0; i < size; i++){int count = 1; // 找俩点Point base = points[i];int n;if (points[i].label != 0){continue;}// 选择基准点points[i].label = label++;for (n = 0; n < size && count < 3; n++){if (points[n].label == 0){if (isValidSlope(base, points[n], rt)){points[n].label = label++;count++;}}}}
}void SortPoint()
{int i, j;j = 1;for (i = 0; i < 9;){if (g_PointPosition[i].label == j){g_base[j - 1].x = g_PointPosition[i].x;g_base[j - 1].y = g_PointPosition[i].y;j++;if (j > 9){break;}else{i = 0;continue;}}else{i++;}}hamming();
}void Label(bool b)
{rt = b;groupPoints(g_PointPosition, 9);SortPoint();
}

3.对弈算法。

基本核心算法：启发式，计算有效直线（指有经过三个方格中心的直线且其上没有对方落子）的组数（按子数排序），返回最大着法。
补丁（按优先级排序）：

1. 己方三点必胜
2. 对方二点必堵
3. 己方双重威胁
4. 对方双重威胁

注意：以下代码为电赛现敲，未经过优化，可复用部分一大把（当时图方便直接复制粘贴的），我懒得改了。

// 根据当前棋谱生成棋盘
void generate_board(int board[9], int moves[], int move_count)
{int i;for (i = 0; i < 9; i++){board[i] = EMPTY;}for (i = 0; i < move_count; i++){board[moves[i] - 1] = (i % 2 == 0) ? BLACK : WHITE;}
}// 判断是否有赢家
int check_winner(int board[9])
{int i;int win_positions[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, // 行{0, 3, 6},{1, 4, 7},{2, 5, 8}, // 列{0, 4, 8},{2, 4, 6} // 对角线};for (i = 0; i < 8; i++){int a = win_positions[i][0];int b = win_positions[i][1];int c = win_positions[i][2];if (board[a] == board[b] && board[b] == board[c] && board[a] != EMPTY){return board[a];}}return EMPTY;
}// 计算在给定位置下棋后的最长同线长度和组数
void evaluate_position(int board[9], int player, int pos, int *max_length, int *num_groups)
{int i;int j;int lines[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, // 行{0, 3, 6},{1, 4, 7},{2, 5, 8}, // 列{0, 4, 8},{2, 4, 6} // 对角线};*max_length = 0;*num_groups = 0;for (i = 0; i < 8; i++){int length = 0;int valid_group = 1;for (j = 0; j < 3; j++){int index = lines[i][j];if (index == pos || board[index] == player){length++;}else if (board[index] != EMPTY){valid_group = 0;break;}}if (valid_group){if (length > *max_length){*max_length = length;*num_groups = 1;}else if (length == *max_length){(*num_groups)++;}}}
}// 检查是否有获胜的走法
int find_winning_move(int board[9], int player)
{int i;int j;int lines[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, // 行{0, 3, 6},{1, 4, 7},{2, 5, 8}, // 列{0, 4, 8},{2, 4, 6} // 对角线};for (i = 0; i < 8; i++){int count = 0;int empty_pos = -1;for (j = 0; j < 3; j++){int index = lines[i][j];if (board[index] == player){count++;}else if (board[index] == EMPTY){empty_pos = index;}else{count = 0;break;}}if (count == 2 && empty_pos != -1){return empty_pos;}}return -1;
}// 检查是否有阻止对方获胜的走法
int find_blocking_move(int board[9], int player)
{int opponent = (player == BLACK) ? WHITE : BLACK;return find_winning_move(board, opponent);
}// 检查是否存在某个位置，如果让对方在该位置下子，会使对方在两个有效直线上都有两个子的情况
int find_double_threat_move(int board[9], int player)
{int i;int j;int k;int opponent = (player == BLACK) ? WHITE : BLACK;int lines[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, // 行{0, 3, 6},{1, 4, 7},{2, 5, 8}, // 列{0, 4, 8},{2, 4, 6} // 对角线};for (i = 0; i < 9; i++){if (board[i] == EMPTY){int threat_count = 0;for (j = 0; j < 8; j++){int count = 0;int empty_count = 0;for (k = 0; k < 3; k++){int index = lines[j][k];if (board[index] == opponent || index == i){count++;}else if (board[index] == EMPTY){empty_count++;}}if (count == 2 && empty_count == 1){threat_count++;}if (threat_count >= 2){return i;}}}}return -1;
}// 主策略函数
void next_move_strategy(int moves[], int move_count, int result[])
{int i;int board[9];int move;int winner;int current_player;generate_board(board, moves, move_count);// 检查当前棋局是否已经有赢家winner = check_winner(board);if (winner != EMPTY){for (i = 0; i < move_count; i++){result[i] = moves[i];}MyWin = winner;return;}current_player = (move_count % 2 == 0) ? BLACK : WHITE;// 检查是否有获胜的走法move = find_winning_move(board, current_player);if (move == -1){// 检查是否有阻止对方获胜的走法move = find_blocking_move(board, current_player);}if (move == -1){// 检查是否有使己方形成双重威胁的走法int op;op = (move_count % 2 == 0) ? WHITE : BLACK;move = find_double_threat_move(board, op);}if (move == -1){// 检查是否有使对方形成双重威胁的走法move = find_double_threat_move(board, current_player);}if (move == -1){// 否则，选择最佳的一般走法int best_move = -1;int best_length = -1;int best_num_groups = -1;for (i = 0; i < 9; i++){if (board[i] == EMPTY){int max_length, num_groups;evaluate_position(board, current_player, i, &max_length, &num_groups);if (max_length > best_length || (max_length == best_length && num_groups > best_num_groups)){best_length = max_length;best_num_groups = num_groups;best_move = i;}}}move = best_move;}// 生成新的棋谱for (i = 0; i < move_count; i++){result[i] = moves[i];}result[move_count] = move + 1; // 位置从1到9
}

其他：懒得写了。

总结：懒得总结了，可以发现，如果优化得当，做电赛E题只需要几百行代码即可获得满分，如果你写了几千行代码，说明你智商有限，还是转行搞其他题目吧，谢谢！如果我的智商故意冒犯了你，请举报一下，就说我太聪明了，不谢！