杭州建站模板搭建,wordpress底部音乐插件,太平洋电脑网站,56做视频网站感想#xff1a;电赛初赛控制类题还是蛮简单的#xff0c;别被五花八门的硬件搞懵了#xff08;决赛当我没说#xff09;。抓住核心#xff0c;理念都是通用的。我是计科专业的#xff0c;因此选择的控制类E题#xff0c;相对来说背的知识要少很多#xff0c;更考验智商…感想电赛初赛控制类题还是蛮简单的别被五花八门的硬件搞懵了决赛当我没说。抓住核心理念都是通用的。我是计科专业的因此选择的控制类E题相对来说背的知识要少很多更考验智商。其实电赛结果都不重要在电赛经历中对自己的磨练尤其是“所想即所得”的快感弥足珍贵。要不是参加电赛我都不敢想象自己做了一个人机对弈装置。通过电赛见到了更宽广的世界。
声明本文中绝大部分算法所有核心算法均是我个人想出来的部分细节由队友补充转载请私信严禁盗代码如果我发现谁盗我代码我直接全网曝光并且停更
前言我本人一向以天才自居算法也都是最简洁干练的那些艰深晦涩而复杂的算法往往是愚蠢的人写出很多人劝我不要把代码开源我偏要我看不惯CSDN的那些VIP专栏那是把智慧锁进了笼子里。文章格式就懒得调了。如果你们发现本文在逻辑上有缺失的部分欢迎私信我进行补充 正文 声明本文中绝大部分算法所有核心算法均是我个人想出来的部分细节由队友补充转载请私信严禁盗代码如果我发现谁盗我代码我直接全网曝光并且停更 三个核心算法1.棋子识别。2.棋盘方格匹配按键标签。3.对弈算法。 其他懒得写了。总结懒得总结了可以发现如果优化得当做电赛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 (sat1){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){key1disp[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){key2comp[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!0tem.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.htypedef 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.对弈算法。
基本核心算法启发式计算有效直线指有经过三个方格中心的直线且其上没有对方落子的组数按子数排序返回最大着法。 补丁按优先级排序
己方三点必胜对方二点必堵己方双重威胁对方双重威胁
注意以下代码为电赛现敲未经过优化可复用部分一大把当时图方便直接复制粘贴的我懒得改了。
// 根据当前棋谱生成棋盘
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题只需要几百行代码即可获得满分如果你写了几千行代码说明你智商有限还是转行搞其他题目吧谢谢如果我的智商故意冒犯了你请举报一下就说我太聪明了不谢
