跳棋游戏第三阶段实验报告¶
一、小组分工¶
周小琳 ： 代码编译调试，ui文件编辑，添加AI模式按钮，查看任意玩家历史路径的服务端完善， 以及小组作业的上传。
杨爽 ： 第三阶段AI实现代码编写，代码调试，编写额外任务，写实验报告
赵铎淞：搜集图片素材，游戏试玩反馈，搜集跳棋的攻略，提供AI方向思路参考，游戏页面美化
二、AI算法思路分析¶
1、用户操作¶
这一阶段要求能够让用户在AI模式和自己下棋之间切换，所以我们在棋盘上面添加了一个AI模式的按钮，轮到某个 用户走棋的时候，他可以自己走，也可以按下AI模式的按钮，然后相应的AI算法会代替其决策。
（改正： 一开始我对于要求“让用户能够在AI模式和自己下棋之间来回切换”理解的是每一步都要用户决定是不是要自己下，自己下的话就点击AI的按钮，但是联机展示以后，实际要求可能并不是这个意思，所以后来这里改成了，点击一下AI模式的按钮，后面轮到该用户的每一步，都是AI来下，直到用户再一次点击AI模式的按钮为止）
2、方法选择¶
一般这类问题可以考虑几个方向：深度学习，随机化的算法和搜索。
用C++写深度学习的模型会比较麻烦，而且大概率效果不好，所以就不考虑这个方法。
如果用类似爬山，模拟退火这一类随机化的算法的话，我们也同样是需要一个棋盘格局的评分函数，但是对于每一步走棋的决策，显然我们并不需要用这一类算法来寻找评分函数最大的那一种格局，或许可以用来找到走几步之后一个比较有利的格局，但是格局涉及到对方的行棋方法，查找这样的格局似乎也没什么意义。所以这一类算法在此处并不适用。
所以我决定还是采用比较传统的搜索的方法，尽可能多搜几步，从而选择一个比较有利于后面局势发展的解。
三、代码框架设计¶
1、评分函数¶
显然搜索是不可能搜索到棋局的结束为止的，所以我们要对棋局中任何可能出现的格局设置一个合理的评分函数。
每一个player有一个dis[player]作为当前玩家的评分值，代表的是player这个玩家距离终点的距离。假如当前用于AI决策的玩家是player1，另外两个玩家是player2和player3，那么当前格局的评分函数就为dis[player2] + dis[player3] - 3 * dis[player1]。其中，3是我加上去的一个权重（这个权重可以根据情况调整），代表相比对手距离终点的距离，AI决策方玩家距离终点的距离会更加重要。显然这个评分函数的值越高，代表对AI决策方的玩家越有利。
其中，dis[player]的具体计算方式如下：首先我们考虑玩家对角的位置，终点共有4个位置，可以划分成4层，我们从小层往大层找，找到一个没有被当前玩家占据的位置的一层，将这一层的位置作为当前的终点目标，然后找到当前玩家的每一个棋子，计算这个棋子距离目标层上最近的一个点的距离（这里的距离指的是，如果只采用平移的走法，那么两个点之间需要走多少步），然后累加所有棋子得到的距离，就是dis[player]。
其中，评分函数和相关辅助函数的代码和注释如下所示：
int Widget :: AI_dis(int x, int y, int tx, int ty)
{
// 此处的距离函数，我们假设只采用平移的方法，需要移动多少步才能到达，距离就是多少
int stepy = (abs(ty - y) / _edge);
int stepx = (abs(tx - x) - stepy * half_edge) / (half_edge * 2);
return (stepx + stepy);
}
int Widget :: AI_corner_dis(int _player, int x, int y) // 找到当前点到对角的距离
{
// 首先找到对角的玩家在画面上显示的坐标
int anti = Coordinate_pos[corner[_player]];
// 然后分层看是否有空余的位置
int min_dis= int_limits;
for (int i = 0; i <= 3; i++)
{
int startj;
if (i == 0) startj = 0; else startj = level_sep[i-1] - 1;
bool flag = 1;
for (int j = startj; j <= level_sep[i]; j++)
{
int cy = level[anti][j];
int tx = Coordinate[anti][cy].x; int ty = Coordinate[anti][cy].y;
if (AI_mark[tx][ty] == coordinate_mark && AI_occupied[tx][ty] == _player) // 如果对方的这个位置已经我方的棋子占据
{
// 排除就是当前棋子的情况
if (x == tx && y == ty)
{
flag = 0; min_dis= 0;
break;
}
continue;
}
else
{
flag = 0;
int cur_dis = AI_dis(x, y, tx, ty);
if (cur_dis < min_dis) min_dis = cur_dis; // 否则求到这个空白点的距离
}
}
if (!flag) break; // 如果这一层有空位置，那么就返回到这一层的空着的位置的距离的最小值。
}
return min_dis;
}
int Widget :: AI_assess(int _player, int search_step, int search_limit) //评估当前局面的有利程度，给出一个函数
{
// 这里需要结合决策方和对抗方的综合情况来进行评判
// 每一方都用距离函数来衡量，即所有棋子距离对角点的斜坐标上的距离之和，显然这个值越小越好
int value = 0;
for (int i = 1; i <= 6; i++)
if (ishere[i] && !judgement[i]) // 如果当前玩家还在房间里面，并且AI决策之前还没有胜利，那么就参与到这个局势的评分里面
{
int size = chess_array[i].size();
int sum = 0;
for (int j = 0; j < size; j++)
{
sum+= AI_corner_dis(i, chess_array[i][j].first, chess_array[i][j].second);
}
// 我们可以通过更改这个评估函数来调整决策的偏重点
// 比如我会认为让自己获胜会比让别人不利更重要
// 于是我会调整我自己的sum的值更大一些的权重
if (i == _player)
value = value - sum * 3;
else value = value + sum;
}
// 如果在到达步数限制之前就进入到评估函数，代表决策方在较短的步数内就获得了胜利，显然是一个比较好的决策，我们需要加上额外的权重
// 这里相关的参数可以调整
if (search_step <= search_limit)
value += extra_score * (search_limit - search_step + 1);
return value;
}
2、搜索设计¶
然后就是考虑怎么搜索的问题。
我们可以在响应时间能接受的范围内尽可能的多搜，然后通过实验确定了搜索的层数；然后对于给定深度的格局给出一个评分函数来判断当前格局的好坏，用第一步选择的每个分支下面的格局评分的平均值作为这一步选择的分值。
在搜索树上的每一层，我们会找出当前玩家的每一个棋子所有可以到达的位置，然后对这些位置进行剪枝（因为我们假设所有的玩家都会理智进行决策，比较离谱的行棋就直接不选择，所以只保留比较有利的行棋位置，也就相当于在联机对抗中假设其他组的AI每一步决策都会比较优，这个假设目前看来是比较合理的），循环这些可能进行选择，递归进入下一层，直到到达搜索层数的限制或者是被决策的玩家已经获胜，然后我们对当前的局面进行评分并保存下来这个评分，回溯。
下面是主要实现这个递归过程的代码，注释如下所示：
void Widget :: AI_dfs(QVector<int>& evaluate_p, int _player, int now_player, int dep,int limit, int win_state)
{
if (if_repeated[hash_value] == hash_mark) return;
// 如果是之前已经存在的格局或者是已经决策过的格局，那么就不再进行搜索
if_repeated[hash_value] = hash_mark;
if (judgeWin(_player) || dep > limit)
// 如果用来决策的这一方已经获得胜利，那么就没有继续搜索下去的必要了
// 如果超过了步数的限制那么也要直接结束
{
evaluate_p.append(AI_assess(_player, dep, limit)); // 评估当前局面，并加入分数
return;
}
//同时我们需要判断当前玩家是不是一个新增的获胜者，如果是的话，那么此轮需要轮空
if (judgeWin(now_player))
{
int new_win_state = win_state + (1 << (now_player - 1));
AI_dfs(evaluate_p, _player, next_player(now_player, new_win_state), dep, limit, new_win_state);
return;
}
// 否则我们来对当前玩家的行棋进行选择，这里采用的是AI_choose里面相同的决策方法
int size = chess_array[now_player].size();
// 首先排序一下，按照距离从远到近
for (int i = 0; i < size - 1; i++)
{
for (int j = i + 1; j < size; j++)
if (backwards(now_player, chess_array[now_player][i].first, chess_array[now_player][i].second, chess_array[now_player][j].first, chess_array[now_player][j].second))
{
int t = chess_array[now_player][i].first; chess_array[now_player][i].first = chess_array[now_player][j].first; chess_array[now_player][j].first = t;
t = chess_array[now_player][i].second; chess_array[now_player][i].second = chess_array[now_player][j].second; chess_array[now_player][j].second = t;
}
}
QVector<QPair<int,int>> select_p; // 存储选择走棋的位置
QVector<QPair<int,int>> target_p; // 存储选择目标的位置
// 下面找到所有可行的行棋方案
select_count++;
for (int i = 0; i < size; i++)
{
int x = chess_array[now_player][i].first;
int y = chess_array[now_player][i].second;
QPair<int,int> now_pair(x,y);
QVector<QPair<int,int>> target = search(x,y);
int t_size = target.size();
int target_num = 0;
int target_point_x[10];
int target_point_y[10];
int target_point_dis[10];
for (int j = 0; j < t_size; j++)
{
if (target[j].first == x && target[j].second == y) continue;
if ((!backwards(now_player, x, y, target[j].first, target[j].second)) && ifselected[target[j].first][target[j].second] != select_count)
{
if (target_num < select_limit) // 还没满，那么就直接加进去
{
target_point_x[target_num] = target[j].first;
target_point_y[target_num] = target[j].second;
target_point_dis[target_num] = AI_corner_dis(now_player, target[j].first, target[j].second);
target_num++;
}
else // 否则和已经选择的点进行比较，看能否取代距离顶点最远的那一个
{
int temp_max = -2147483648;
for (int k = 0; k < target_num; k++)
if (target_point_dis[k] > temp_max) temp_max = target_point_dis[k];
int cur_dis = AI_corner_dis(now_player, target[j].first, target[j].second);
if (cur_dis < temp_max) // 如果可以取代最远的那一个，那么就取代
{
for (int k = 0; k <target_num; k++)
if (target_point_dis[k] == temp_max) // 找到距离最远的那一个
{
target_point_x[k] = target[j].first;
target_point_y[k] = target[j].second;
target_point_dis[k] = cur_dis;
break;
}
}
}
}
}
// 然后我们要把当前棋子选中的目标点，标注为已选，并且加入到select的里面
for (int j = 0; j < target_num; j++)
{
ifselected[target_point_x[j]][target_point_y[j]] = select_count;
select_p.append(now_pair);
QPair<int,int> t2(target_point_x[j],target_point_y[j]);
target_p.append(t2);
}
}
size = select_p.size();
for (int i = 0; i < size; i++)
{
int x = select_p[i].first; int y = select_p[i].second;
int tx = target_p[i].first; int ty = target_p[i].second;
AI_update(_player,x,y,tx,ty); //假设按照这样进行选择
AI_dfs(evaluate_p, _player, next_player(now_player,win_state), dep + 1, limit, win_state);
AI_update(_player, tx,ty,x,y); //undo
}
}
3、搜索剪枝与优化¶
这里最主要的剪枝和优化的思想是贪心，去除掉一些基本上不够优的决策，从而减小搜索的规模。
（1） 哈希去重：在搜索的过程中，为了避免搜索重复的格局从而导致时间的浪费，这里利用了字符串哈希的思想，将棋盘的每一个格子标号，一个玩家的棋子排布对应就可以得到一个哈希值，然后将参与玩家的哈希值再一次拼接就可以得到整个格局的哈希值。然后用map映射存 储哈希值(ps: 为了避免关键词冲突也可以使用孪生素数来进行双哈希)，如下所示是哈希值得到的预处理的代码和详细注释：
hash_value = 0; // 棋盘的hash值
coordinate_mark++;
for (int i = 1; i <= 6; i++) // i代表每一个玩家，遍历每一个玩家的所有棋子，计算哈希值
{
int size = chess_array[i].size();
hash_value_player[i] = 0;
for (int j = 0; j < size; j++)
{
int x = chess_array[i][j].first; int y = chess_array[i][j].second;
//表示这个位置有棋子
AI_mark[x][y] = coordinate_mark;
AI_occupied[x][y] = i;
//每个玩家各自的has值
hash_value_player[i] = (hash_value_player[i] + base_pow[AI_pos[x][y]]) % mod_p;
}
// 每个玩家得到各自的hash值以后，我们还需要按照玩家的顺序进行整合，得到一个总体的棋盘的hash值
hash_value = (hash_value + hash_value_player[i] * base_player[i])% mod_p;
}
//保存下当前格局的hash值
hash_mark++;
if_repeated[hash_value] = hash_mark;
// AI部分对于参与决策时候的格局和AI给出的决策后的格局保证不会有重复的出现
hash_history[hash_value] = 1;
（2）禁止向远离对角顶点的位置跳跃： 设置一个函数判断行棋之后的位置是不是比原来的位置更远，是的话就抛弃这种选择，被抛弃的选择放到备选的决策里面
（3）在决策之前将该玩家的棋子按照距离终点从远到近进行排序，然后按照这个顺序进行决策。如果有两个棋子能够同时跳到某一个候选的位置，那么只保留在距离终点比较远的那个棋子到这个位置的决策，因为我们不希望落在后面的棋子一直在后面，所以这样才会有一个整体上往前跳的效果。
（4）对于每一个棋子，只保留有限数量的候选目标位置：候选的位置如果太多，搜索的复杂度会过高，所以我们只在其中贪心地选择若干个离终点距离最近的候选位置，剩下的候选位置放到备选的决策里面。
（5）关于连跳的处理：按照规则连跳是可以在跳跃的任何一步停下来的，但是这里贪心地没有保存下中间的这些点，而只是保存下了最后能跳到的最远的那个位置。（其实这个优化是比较存疑的，因为由于有（4）的剪枝，所以每一层会搜索的数量是有上限可以计算的，并不需要这个条件来节省时间，而且从理论上讲，并不是连跳跳到尽可能远的地方才是好的选择，所以我有做过实验，让不加这个条件的AI和加了这个条件的AI进行对抗，结果是加了这个条件的AI的领先的优势挺明显的，所以最终就保留了这一段）
（6）关于备选决策的处理：如果通过上面的条件过滤，只剩下备选的决策，那么 此时循环所有备选的方案，然后对于每一个方案，尝试走这一步，然后对当前局面给出评分，选择评分最大的那个备选决策作为最终的决策。
（7）然后递归往深处搜索的时候，要循环每一个玩家的所有可能选择，但是我们并不搜索所有的可能，而是基于其他玩家都是比较理智比较优的决策的前提，只保留这些树上的分支，然后往下搜索。这样的假设是比较符合目前的实际情况的，并且可以有效减少搜索的规模。
4、接口说明¶
首先是AI决策的函数主体，代码和详细注释如下所示：
void Widget :: AI_choose(int _player,int& source_x, int& source_y, int& terminal_x, int& terminal_y)
{
hash_value = 0; // 棋盘的hash值，定义在累里面
coordinate_mark++;
for (int i = 1; i <= 6; i++) // i代表每一个玩家，遍历每一个玩家的所有棋子，计算哈希值
{
int size = chess_array[i].size();
hash_value_player[i] = 0;
for (int j = 0; j < size; j++)
{
int x = chess_array[i][j].first; int y = chess_array[i][j].second;
//表示这个位置有棋子
AI_mark[x][y] = coordinate_mark;
AI_occupied[x][y] = i;
//每个玩家各自的has值
hash_value_player[i] = (hash_value_player[i] + base_pow[AI_pos[x][y]]) % mod_p;
}
// 每个玩家得到各自的hash值以后，我们还需要按照玩家的顺序进行整合，得到一个总体的棋盘的hash值
hash_value = (hash_value + hash_value_player[i] * base_player[i])% mod_p;
}
//保存下当前格局的hash值
hash_mark++;
if_repeated[hash_value] = hash_mark;
// AI部分对于参与决策时候的格局和AI给出的决策后的格局保证不会有重复的出现
hash_history[hash_value] = 1;
QVector<QPair<int,int>> select_p; // 存储选择走棋的位置
QVector<QPair<int,int>> target_p; // 存储选择目标的位置
// 备选的一些行棋方案
QVector<QPair<int,int>> can_select_p;
QVector<QPair<int,int>> can_target_p;
int size = chess_array[_player].size();
// 这里首先将目前玩家拥有的棋子进行排序，距离对角顶点比较远的棋子排在前面，具有对跳跃到的目标的优先选择权
//因为我们希望滞后的棋子能够尽快走到靠前的位置
for (int i = 0; i < size - 1; i++)
{
for (int j = i + 1; j < size; j++)
if (backwards(_player, chess_array[_player][i].first, chess_array[_player][i].second, chess_array[_player][j].first, chess_array[_player][j].second))
{
int t = chess_array[_player][i].first; chess_array[_player][i].first = chess_array[_player][j].first; chess_array[_player][j].first = t;
t = chess_array[_player][i].second; chess_array[_player][i].second = chess_array[_player][j].second; chess_array[_player][j].second = t;
}
}
for (int i = 0; i < size; i++)
select_count++; // 给前面选择过的目标点打上标签，保证一个目标点不会有两个棋子跳到它
for (int i = 0; i < size; i++)
{
int x = chess_array[_player][i].first;
int y = chess_array[_player][i].second;
QPair<int,int> now_pair(x,y);
QVector<QPair<int,int>> target = search(x,y);
int t_size = target.size();
int target_num = 0;
int target_point_x[10];
int target_point_y[10];
int target_point_dis[10];
// 这里首先做一遍筛选，往后走的点不要，前面已经选中的可能的目标点不要，在这之中选出距离顶点坐标最近的几个点
for (int j = 0; j < t_size; j++)
{
if (target[j].first == x && target[j].second == y) continue;
if ((!backwards(_player, x, y, target[j].first, target[j].second)) && ifselected[target[j].first][target[j].second] != select_count)
{
int temp_hash = hash_update(_player, x, y , target[j].first, target[j].second);
if (!hash_history[temp_hash]) // 判断该决策是否会造成重复的格局，是的话就不选
{
if (target_num < select_limit) // 还没满，那么就直接加进去
{
target_point_x[target_num] = target[j].first;
target_point_y[target_num] = target[j].second;
target_point_dis[target_num] = AI_corner_dis(_player, target[j].first, target[j].second);
target_num++;
}
else // 否则和已经选择的几个点进行比较，看能否取代距离顶点最远的那一个
{
int temp_max = -2147483648;
for (int k = 0; k < target_num; k++)
if (target_point_dis[k] > temp_max) temp_max = target_point_dis[k];
int cur_dis = AI_corner_dis(_player, target[j].first, target[j].second);
if (cur_dis < temp_max) // 如果可以取代最远的那一个，那么就取代
{
for (int k = 0; k <target_num; k++)
if (target_point_dis[k] == temp_max) // 找到距离最远的那一个
{
target_point_x[k] = target[j].first;
target_point_y[k] = target[j].second;
target_point_dis[k] = cur_dis;
break;
}
}
}
}
}
else // 否则的话依然要加入到备选的里面
{
// 如果会造成重复的格局，那么备选也是不加入的
int temp_hash = hash_update(_player, x, y , target[j].first, target[j].second);
if (!hash_history[temp_hash])
{
can_select_p.append(now_pair);
can_target_p.append(target[j]);
}
}
}
// 然后我们要把当前棋子选中的目标点，标注为已选，并且加入到select的里面
for (int j = 0; j < target_num; j++)
{
qDebug() << target_point_x[j] << " " << target_point_y[j] ;
ifselected[target_point_x[j]][target_point_y[j]] = select_count;
select_p.append(now_pair);
QPair<int,int> t2(target_point_x[j],target_point_y[j]);
target_p.append(t2);
}
}
// 根据不同的模式设置搜索后继步数的限制
int step_limit;
if (type == 2) step_limit = 4; else step_limit = 3;
size = select_p.size();
if (size == 0) // 无处可走
{
source_x = -1; source_y = -1;
terminal_x = -1; terminal_y = -1;
//注意这里也不一定是真正的无处可走，而是在启发式的决策下没有相应符合要求的行棋策略
// 这个时候，如果备选行棋方案里面，存在选择，那么就在备选的方案中选择一个评分函数比较高的决策作为此次AI的决策
int n = can_select_p.size();
if (!n) return;
int max_score = -2147483648;
for (int i = 0; i < n; i++)
{
int x = can_select_p[i].first; int y = can_select_p[i].second;
int tx = can_target_p[i].first; int ty = can_target_p[i].second;
AI_update(_player, x, y, tx, ty);
int temp_score = AI_assess(_player, 0, 0); // 表示这一步走棋后的局势评分
AI_update(_player, tx, ty, x, y);
if (temp_score > max_score)
{
max_score = temp_score;
source_x = x; source_y = y;
terminal_x = tx; terminal_y = ty; // 记录这一步的行棋方案
}
}
int temp_hash = hash_update(_player, source_x, source_y, terminal_x, terminal_y);
hash_history[temp_hash] = 1; // 将已经决策过的hash值标记为1，避免陷入循环
// 找到评分最大的返回即可
return;
}
// 当前的胜负状态
// 二进制压位，作为状态传送
int win_state = 0;
for (int i = 1; i <= 6; i++)
{
win_state+=judgement[i] * (1 << (i - 1));
}
QVector <int> Min;
QVector <double> Avg;
// 下面循环所有走棋的选择
for (int i = 0; i < size; i++)
{
int x = select_p[i].first; int y = select_p[i].second;
int tx = target_p[i].first; int ty = target_p[i].second;
AI_update(_player,x,y,tx,ty); //假设按照这样进行选择
//这里有可能会需要使用更大的整数类型
QVector <int> evaluate_p; // 得到后继状态的评分函数值的集合
AI_dfs(evaluate_p, _player, next_player(_player,win_state), 1, step_limit, win_state);
AI_update(_player, tx,ty,x,y); //undo
int e_size = evaluate_p.size();
int now_min = int_limits;
double total = 0; // 分别求得这些局面的评分函数的平均值和最小值
for (int j = 0; j < e_size; j++)
{
if (evaluate_p[j] < now_min) now_min = evaluate_p[j];
total = total + (double)evaluate_p[j];
}
double now_avg = total/(double)e_size;
Min.append(now_min);
Avg.append(now_avg);
}
// 现在我们可以结合上面两个指标来选择一个最优的解
// 在假设对手是最优决策的情况下，我们应该选择最小值最大的那个
// 在假设对手是随机选择的情况下，我们应该选择平均值最大的那个
// 这里我们先选择采用平均值的决策
int now_max = 0;
for (int i = 0; i < size; i++)
if (Avg[i] > Avg[now_max]) now_max = i;
//做出选择
source_x = select_p[now_max].first; source_y = select_p[now_max].second;
terminal_x = target_p[now_max].first; terminal_y = target_p[now_max].second;
// 将这个决策后的hash值记录下来，后面不能再重复这个选择
int temp_hash = hash_update(_player, source_x, source_y, terminal_x, terminal_y);
hash_history[temp_hash] = 1;
}
按下AI模式的按钮后，响应的槽函数的代码和详细注释如下所示：
void Widget :: on_AIButton_clicked()// 点一次开启，再点一次关闭
{
if (AI_on) // 如果此时AI模式是开启的
{
// 需要关闭AI模式
AI_on = 0;
this -> control = this -> temp_control; // 将控制权返还给玩家
}
else // 如果此时AI模式是关闭的
{
// 需要开启AI模式
AI_on = 1;
this -> temp_control = this -> control; // 将当前控制权信息存储起来
this -> control = -1; // 禁止玩家自行下棋
AI_move(); // 调用AI进行行走
}
}
其中调用Ai决策的函数接口如下：
void Widget :: AI_move()
{
if (this -> temp_control != player) return; //不是当前玩家的轮次的时候禁止下棋
int source_x, source_y, terminal_x, terminal_y;
AI_choose(player,source_x,source_y,terminal_x, terminal_y); // 获得对应的行棋方案
if (source_x == -1 && source_y == -1 && terminal_x == -1 && terminal_y == -1) // 这种情况代表AI找不到任何决策
{
// it is not supposed to happen
return;
}
int cx = get_Coordinatex(g[source_x][source_y]); int cy = get_Coordinatey(g[source_x][source_y]);
this -> select = Coordinate[cx][cy].chess;
int cx2 = get_Coordinatex(g[terminal_x][terminal_y]); int cy2 = get_Coordinatey(g[terminal_x][terminal_y]);
Coordinate_struct* ptr = &Coordinate[cx2][cy2];
bool canmove = isLegalMove(select, ptr);
// 在发送signal_move之前要确保已经保存好了行棋的路径, 这里借助一下isLegalMove的函数来获取一下路径
emit signal_move(); // 发送信号给客户端请求移动
//由于自己将不再接收到move up的信号，所以会自行行棋
if (canmove)
{
QString my_trail = getTrail();
this -> setmove(player, my_trail);
}
//恢复配置
this->select = nullptr;
}
四、额外任务¶
三个额外任务都已经完成，下面是具体实现的方法
1、旋转视角¶
旋转视角的主要思路是考虑如果某一个玩家在视角的底部，那么需要从原来的位置顺时针旋转多少个60度，然后用一个数组记录下这个数字，然后编写旋转坐标的函数代码和注释如下所示：
int Widget :: rotate_x (int x, int y) // 将玩家1朝上情况的坐标转换成画面展现的时候的坐标
{
for (int i = 1; i <= temp_bias[player]; i++) // 代表当前玩家在正下方的时候需要旋转几个60度
{
int tx = x + y; int ty = -x;
x = tx; y = ty;
}
return x;
}
int Widget :: rotate_y (int x, int y)
{
for (int i = 1; i <= temp_bias[player]; i++) // 代表当前玩家在正下方的时候需要旋转几个60度
{
int tx = x + y; int ty = -x;
x = tx; y = ty;
}
return y;
}
int Widget :: re_rotate_x (int x, int y) // 将画面展示时候的坐标转换成玩家1朝上情况下的坐标
{
// 转回去本应该是逆时针的旋转
// 但是这里可以等价于顺时针旋转互补的度数
int rotate_times = (6 - temp_bias[player]) % 6; // 注意360度的时候就直接不转，节省时间
for (int i = 1; i <= rotate_times; i++)
{
int tx = x + y; int ty = -x;
x = tx; y = ty;
}
return x;
}
int Widget :: re_rotate_y (int x, int y)
{
// 转回去本应该是逆时针的旋转
// 但是这里可以等价于顺时针旋转互补的度数
int rotate_times = (6 - temp_bias[player]) % 6;
for (int i = 1; i <= rotate_times; i++)
{
int tx = x + y; int ty = -x;
x = tx; y = ty;
}
return y;
}
计算要旋转多少个60度的代码和注释如下所示：
//这是正常视角的时候顺时针方向对应的每一个玩家
int temp_pos[10];
temp_pos[1] = 1; temp_pos[2] = 3; temp_pos[3] = 5;
temp_pos[4] = 2; temp_pos[5] = 4; temp_pos[6] = 6;
// temp_bias[i]代表i号玩家在正下方的时候应该顺时针转动多少个位置
// for (int i = 1; i <= 6; i++) temp_bias[i] = 0; // 这样设置就可以取消旋转的效果
temp_bias[2] = 0; temp_bias[5] = 1; temp_bias[3] = 2;
temp_bias[1] = 3; temp_bias[6] = 4; temp_bias[4] = 5;
// 下面根据当前的玩家来确定每个玩家在展示的时候对应的位置
// 获取Coordinate_pos的值，对应表示每个玩家在展示画面的时候应该对应Coordinate的哪一个横坐标
// re_Coordinate_pos则应该是一个反向的函数，表示这个坐标下对应展现的是哪一个玩家的棋子
temp = 0;
for (int i = 1 + temp_bias[player]; i <= 6; i++)
{
temp++;
Coordinate_pos[temp_pos[temp]] = temp_pos[i];
re_Coordinate_pos[temp_pos[i]] = temp_pos[temp];
}
for (int i = 1; i <= temp_bias[player]; i++)
{
temp++;
Coordinate_pos[temp_pos[temp]] = temp_pos[i];
re_Coordinate_pos[temp_pos[i]] = temp_pos[temp];
}
由此可见，任意的视角转换只要调整这里的参数就可以了，实现起来十分简单。
2、展现行棋的路径¶
（注意：这里在联机展示之后做了调整，之前显示路径的方法是在跳过的位置上面显示一个灰色的棋子，但是助教认为这种方法显示路径不够清晰，所以这里改成了动画的效果）
首先我们将服务端传送进来的路径的字符串进行解析，然后根据视角旋转坐标，再转换成实际对应的直角坐标，得到一系列路径上的点的坐标，然后我们根据这些坐标， 利用QPropertyAnimation实现两两点之间的平移的动画效果，然后按照顺序加入到一个串行动画组里面，实现连续的路径展示，主要代码和注释如下所示：
void Widget :: showTrail()
{
// 串行执行的动画组
QSequentialAnimationGroup *group = new QSequentialAnimationGroup(this);
int a_count = 0;
for (int i = 0; i < s_trail_num - 1; i++)
{
// 下面展现两个点之间的平移效果
animation[a_count] = new QPropertyAnimation(select, "pos");
animation[a_count]->setDuration(300);
animation[a_count]->setStartValue(QPoint(s_Trail_x[i] - chess_bias, s_Trail_y[i] - chess_bias));
animation[a_count]->setEndValue(QPoint(s_Trail_x[i+1] - chess_bias, s_Trail_y[i+1] - chess_bias));
group->addAnimation(animation[a_count]); // 将当前动画片段添加到动画组中
a_count++;
if (i != (s_trail_num - 2)) // 如果还是中间点
{
// 下面添加一个停顿，这样视觉效果会更加清晰一些
animation[a_count] = new QPropertyAnimation(select, "pos");
animation[a_count]->setDuration(100);
animation[a_count]->setStartValue(QPoint(s_Trail_x[i+1] - chess_bias, s_Trail_y[i+1] - chess_bias));
animation[a_count]->setEndValue(QPoint(s_Trail_x[i+1] - chess_bias, s_Trail_y[i+1] - chess_bias));
// 这里移动的起始和终点是一样的，实际上展现出来的效果就是在这个中间点上停留了0.1秒
group->addAnimation(animation[a_count]); // 将当前动画片段添加到动画组中
a_count++;
}
}
group->start(QAbstractAnimation::DeleteWhenStopped); // 执行动画组中的所有片段
connect(group, &QSequentialAnimationGroup::finished, this, &Widget::endShowTrail);
}
3、允许玩家查看任意一个玩家的上一步的行棋路径¶
这个小任务可以调用上面一个小任务里面的函数接口来实现，我们只需要添加一些客户端和服务端的之间的传输的命令来协同完成即可。
首先我们需要修改networkdata.h里面的一部分代码如下所示：
enum class OPCODE : int {
JOIN_ROOM_OP = 200000,
JOIN_ROOM_REPLY_OP,
LEAVE_ROOM_OP,
CLOSE_ROOM_OP,
PLAYER_READY_OP,
START_GAME_OP,
START_TURN_OP,
MOVE_OP,
END_TURN_OP,
END_GAME_OP,
ERROR_OP,
CHECK_OP, // 新加
DISPLAY_OP // 新加
};
这里添加了CHECK_OP和DISPLAY_OP
当某一个客户端向服务端发送CHECK_OP的时候，代表这个客户端的玩家请求查看某一个玩家的行棋的历史路径，data1是被查看的玩家的昵称。
当某一个客户端接受到CHECK_OP的时候，这个客户端被要求发送该玩家上一次行棋的历史路径给服务端，发送的数据命令为DISPLAY_OP，其中data1是行棋路径压缩而成的字符串。
当某一个客户端接受到DISPLAY_OP的时候，这个客户端被要求展现这个data1里面的存储的路径，即当前客户端要求查看的路径。
相应地，当服务端收到CHECK_OP的时候，应该发送一条CHECK_OP的指令给data1里面存储的昵称对应的玩家所在的客户端，然后接受这个客户端发送来的DISPLAY_OP，然后将这一条DISPLAY_OP转发给之前发送CHECK_OP的客户端，从而实现该客户端的玩家查看任意一个玩家上一次历史路径的要求。
客户端中相应的代码和详细注释如下所示：
/*客户端接受到对应的指令*/
else if (data.op == OPCODE :: CHECK_OP)
{
// 这个来自服务端的请求，收到的客户端要求给出上一次行棋的历史路径发送给服务端
QString str;
//获取行棋的路径
str = winArray -> getTrail();
// 发送display_op的请求, data1表示行棋的路径
NetworkData sendata = NetworkData(OPCODE ::DISPLAY_OP,str,"");
this -> socket->send(sendata);
}
else if (data.op == OPCODE :: DISPLAY_OP)
{
winArray -> displaypatch(data.data1); // 接收到的路径之后调用接口展示
}
/*客户端发送相应的指令*/
void Room :: try_check_trail() // 发出查看历史路径的请求
{
NetworkData sendata = NetworkData(OPCODE ::CHECK_OP,winArray -> checkplayer,"");
this -> socket->send(sendata);
}
最终展现出来的效果就是会把被查看玩家的上一次行棋的路径重新动画演示一遍。
五、遇到的问题以及解决方法和思考¶
1、一开始的AI会在接近终点的时候会出现在某两个位置反复横跳的情况。
这是因为虽然我们用哈希解决了搜索过程中重复格局的问题，但是对于已经决策过的格局，我们并没有保存下其哈希值，所以导致这种情况可能会发生。
与此同时，这也说明我们一开始的评分函数存在问题，才会让反复横跳的这两个位置在评分函数看来没有区别，从而走不到终点。
这是因为一开始的距离函数，我们是用棋子到对角顶点的位置的距离来表示的，这样显然会在对角顶点被占据的时候显得不合理，因为此时棋子不应该再将对角顶点作为最后的目标，而是对角里面的其他终点位置。
所以我们最后将距离函数改成了上面所说的那样，并且保存下决策后的格局的哈希值，从而不可能出现来回横跳的情况。
改进以后，问题得到了解决，并且AI的决策也由于评分函数的优化而得到了改善。
2、AI模式来回切换的要求理解有些偏差，联机展示之后已经进行了修改，只是设计上想法不太一样，但是技术实现上没有什么问题。
3、在联机展示的时候助教认为路径展示的效果不够清晰，现在已经改成了动画演示路径。
4、关于AI决策是否优的问题：其实关于AI决策是否优是一个比较复杂的问题。
-
首先从理论上来讲：这里面有些东西一开始的时候只能从直觉上设置，但是很难说明是否合理。就比如这里的评估函数的计算方法能否很好地体现这个格局的好坏程度；再比如评估函数里面有一些我自己设置的参数（比如extrascore，再比如给自己一方的评估总和加上的权重为3），这些参数的大小设置是否合理；再比如我把第一步决策后面的所有分支的格局的评估值取平均值作为这一步决策的评分是否合理。考虑到这样的种种因素，这样搜索后面可能出现格局的做法能否优化决策是存疑的。因为搜索的目的是为了更好地预见后面的局势（否则直接枚举所有决策比较它的评分函数的做法就退化成了单纯的贪心），但是由于上面提出的这些问题，搜索能否准确地预测某一步决策后面的局势发展是不确定的。而且从实际运行的角度来看，能够搜索的深度并不大，且经过我们实验，即使是卡着时间限制搜索地尽量深一点，也很有限（因为这里是指数增长的时间），而且结合前面的分析，搜索越深未必就更好地预见了以后的局势。
-
其次从实际评估上来讲：我们也可以从结果的角度来衡量AI的好坏。首先我们让组员和AI进行了比赛，然后AI均获得胜利。其次可以做的就是和其他小组联机对抗，从而对自己AI的策略进行调整，但是协调其他小组一起调整代码没有足够时间和条件，只能在联机展示前一天进行了几轮对抗，观测了一下结果：对决中双人模式都取得了胜利，三人模式中没有明显的优势（这可能是因为根据不同的模式需要设置不一样的参数，目前的参数可能比较适合双人模式）。然后当我们对某些条件的设置不知该如何取舍的时候，我们选择了让两种不同的设置的AI进行对抗，然后保留胜利的那一方的方案。显然，我们也可以通过这样的方法，调整不同的参数值进行对抗，保留获得胜利的一方的设置，从而达到参数调优的效果（但是我们没有足够的时间进行反复的实验，在这里特别说明，给出继续优化的方向）
六、代码运行截图¶
首先是开局时候的画面，可以看到视角旋转的效果，还有允许查看每个玩家历史路径的按钮。
下面是AI托管过程中的一些运行截图。
