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

作者：在线问答5 | 2024-08-21 01:10:45

踩

简单的电赛

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

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

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

正文

- 声明：本文中绝大部分算法（所有核心算法）均是我个人想出来的，部分细节由队友补充，转载请私信！严禁盗代码！如果我发现谁盗我代码我直接全网曝光并且停更！
三个核心算法：
其他：懒得写了。
总结：懒得总结了，可以发现，如果优化得当，做电赛E题只需要几百行代码即可获得满分，如果你写了几千行代码，说明你智商有限，还是转行搞其他题目吧，谢谢！如果我的智商故意冒犯了你，请举报一下，就说我太聪明了，不谢！

三个核心算法：

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217

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) // 1
      return pointA->x - pointB->x;
    else
      return 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();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

3.对弈算法。

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

己方三点必胜
对方二点必堵
己方双重威胁
对方双重威胁

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

// 根据当前棋谱生成棋盘
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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265

其他：懒得写了。

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/1009219

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