第1页 / 共21页
第2页 / 共21页
第3页 / 共21页
第4页 / 共21页
第5页 / 共21页
第6页 / 共21页
第7页 / 共21页
第8页 / 共21页
Blokus （角斗士）解题报告含代码.doc
Blokus 作业解题报告
一、解题思路：Blokus 的关键在于角的把握，把可以防止己方方块的点成为扩展点，
则己方占据的扩展点越多，敌方占据的扩展点越少，那么己方优势就越大。所以我把扩展点
的个数的多少作为取胜的关键。
主要以算分儿为主要手段，枚举每一种放法，达到最大的分数那一种作为最终的放法。
算分儿的规则如下：
1、由于最终得分是由放置方块儿的大小（即所含小单元的个数）决定的，所以放置方
块儿所含单元的数目是分数的重要组成部分，给分时为单元数目×8
2、计算己方放置方块儿后增加的扩展点，分数记为增加的扩展点数×9，这里之所以给
的分数高，是因为在后期，更多的扩展点要比一、两个单元更为重要
3、计算敌方因我方放置方块儿而减少的扩展点，分数记为减少的扩展点×1，这里之所
以给的分数少，是因为角斗士是以进攻渗透为主，防守是很难坚固其它三方的攻击的。
4、其它的分数。分为前期和后期。
①前期主要是想中间渗透，谁能抢占中场，谁就能称王，在向中间渗透的过程中，当然
会生成很多可用的扩展点，将来可以作为占据本方角落的扩展点。分数计算是：
放置方块儿前到中心点的距离 — 放置方块儿后到中心点的距离。（为一个负数，因为离中
心越近越好）
②后期主要是争取更多的扩展点，并尽量在同时压制敌方，不让敌方进入本方的角落，
占据本方的空间。当然，能渗透进地方区域是更好的。分数计算为：
放置方块儿后到角落的距离 — 放置方块儿前到角落的距离。
PS：之所以将这两个区分开，是因为前期如果也用后期的算法，那么不一定是向中心发
展，而可能严边沿发展，而且不好区分前期后期。假如后期用前期的算法，也是不合适的，
因为后期中区肯定很满，而边角应该还是有空隙的，而且渗透也是越深越好。
二、函数列表（只列出自己写的和改动的函数）
①int ownnumber()计算自己代号的函数，1——(0,0)，2——(0,19)，3——(19,19)，
4——(19,0)
②bool ok(int i,int j,int color)判断该点是否有邻近的同色点，i、j 分别为点的
横纵坐标，color 为己方的代号，分别判断上下左右有没有本方的点，有则返回 ture，全部
都没有返回 false。(若达到边界视为没有同色点)
③void availabledot()计算目前扩展点的个数，枚举每一个放置任何颜色单元的点，
看它四个角是否有同色点，找到以后看这个角上的点是否有临近的同色点，（调用 ok 函数）
如果没有，那么就是新的扩展点，本方的扩展点个数放入 Mypoint（全局变量），敌方（不
区分其它三方）存入 Otherpoint（全局变量）。
④double getgrade(int x,int y,int i,int d)计算方块儿 i 以 d 方式放置于(x,y)时
的分数。（不含其它分数）分数计算方法前边已经提到，返回之所以是 double 是因为后边
的距离可能不为整数。
⑤void deletesingle(board & cur, int x, int y,int i, int d); 将以 d 方式放置
的方块儿 i 从(x,y)取下，基本照抄 putsingle 函数的内容，除了填入数字的改动。
⑥double middle();计算目前本方单元中到中心最近的单元到中心的距离。搜索整个棋
盘，计算每个本方单元到中心的距离，得到最大距离。
⑦double extendplace();计算目前本方单元中到本方出生点最近的单元到出生点的距
离。搜索整个棋盘，计算每个本方单元到出生点的距离，得到最大距离。
⑧void putminefirst(board & cur)放置第一个方块儿，每个出生点有须先设定的固定
的方法，不进行计算。
⑨void putmine(board & cur)枚举每种可能的放置方法然后算分儿，然后把放上的方
块儿拿下，如此循环往复，最后放上最佳方案的方块儿。
三、总结和不足
本次大作业程序写的不是很精致，前两次提交的时候比较紧张，都有明显的错误，最终
改的结果还算在意料之中，写的时候大概是想到了上学期五子棋用的算分儿方法，觉得是写
AI 的好方法，便继续沿用，在实际中也有不错的效果。但是 blokus 的特殊情况还是比较多
的，比如说从两个对顶的敌方方块儿中利用角斗士这个“角”的特性穿过去，这是敌方无法
防守的，这一点的考虑还不是很到位。
关于算法的时间、空间复杂度问题没有进行细致的讨论，利用了一些简单的剪枝来降低
时间复杂度，但是总体上还是以枚举为主，这在一定程度上也是别无选择的方法。
总之，本次大作业算是基本按要求完成，有收获也有不足，都是一种锻炼。
四、附录（源代码）
/*
*/
<>
Sample Program of Team Game -- Blokus
Written by Zhong Cheng, Mar.22nd, 2009
#include
#include
#include
using namespace std;
int Mypoint=0, Otherpoint=0;
bool startstage=true;
struct
{
int x;
int y;
int i;
int d;
}choosepoint;
const int
Length = 19,
//游戏棋盘的规模（[0..19]*[0..19]）。
Piecesize = 4,
//方块的规模（[0..4]*[0..4]）。
Piecenum = 20,
//方块的个数（编号依次为, 1, ... , 20）。
Blankcolour = 4;
//游戏棋盘上空白格子的颜色。
int Mycolour = 5;
//自己方块的颜色。
const double
Ironsize[Piecenum + 1] =
//方块的大小，即每个方块的分值。
{
};
1, 2, 3, 4, 5, 3, 4,
5, 5, 4, 5, 4, 5, 5,
5, 5, 5, 4, 5, 5, 5
struct board {
int
};
b[Length + 1][Length + 1];
//游戏棋盘。其[i][j]分量的值，表示第i行、第j列的格子的颜色。
//本程序中的其它“坐标”[x][y]，也都表示第x行、第y列。
struct piece {
int
};
p[Piecesize + 1][Piecesize + 1];
//方块，其分量的值为或，表示该格子是否被占。
const piece
Iron[Piecenum + 1] =
//游戏描述中给出的种方块。
{
//No.0
{
{1, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.1
{
{1, 1, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.2
{
{1, 1, 1, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.3
{
{1, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.4
{
{1, 1, 1, 1, 1,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.5
{
{1, 1, 0, 0, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.6
{
{1, 1, 0, 0, 0,
1, 1, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.7
{
{1, 1, 0, 0, 0,
1, 1, 0, 0, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.8
{
{1, 1, 0, 0, 0,
0, 1, 1, 0, 0,
0, 0, 1, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.9
{
{1, 1, 0, 0, 0,
1, 0, 0, 0, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.10
{
{1, 1, 0, 0, 0,
1, 0, 0, 0, 0,
1, 0, 0, 0, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.11
{
{1, 0, 0, 0, 0,
1, 1, 0, 0, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.12
{
{1, 0, 0, 0, 0,
1, 1, 0, 0, 0,
1, 0, 0, 0, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.13
{
{1, 1, 0, 0, 0,
1, 0, 0, 0, 0,
1, 1, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.14
{
{0, 1, 0, 0, 0,
1, 1, 1, 0, 0,
0, 1, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.15
{
{1, 0, 0, 0, 0,
1, 1, 1, 0, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.16
{
{1, 1, 1, 0, 0,
1, 0, 0, 0, 0,
1, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.17
{
{0, 1, 1, 0, 0,
1, 1, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.18
{
{0, 1, 1, 0, 0,
1, 1, 0, 0, 0,
0, 1, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.19
{
{0, 1, 1, 0, 0,
0, 1, 0, 0, 0,
1, 1, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
},
//No.20
{0, 1, 1, 1, 0,
1, 1, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0}
{
}
};
board
cur;
//当前的游戏棋盘。
piece
diamond[Piecenum + 1][8];
//其[i][d]分量，表示第i种方块经第d种方式旋转后，得到的方块。
bool
int
bool
used[Piecenum + 1];
//其[i]分量表示第i个方块是否已被使用。
fx, fy;
//第一个方块必须覆盖的格子坐标。
meetend;
//是否收到[end]指令。
void turn(int d, piece oir, piece & res);
//方块oir经第d种方式旋转后，得到方块res。
void forge();
//生成diamond数组。
void clean(board & cur);
//初始化游戏棋盘。
void start(board & cur);
//执行[start]指令。
bool putable(board cur, int x, int y, int i, int d);
//判断以(x, y)为左上角坐标的第i种方块，经第d种方式旋转后得到的方块，能否被放置在
//当前棋盘上。
bool putablefirst(int x, int y, int i, int d);
//判断以(x, y)为左上角坐标的第i种方块，经第d种方式旋转后得到的方块，能否作为第一
//个方块，被放置在棋盘上。
void putsingle(board & cur, int x, int y, int p, int i, int d);
//将以(x, y)为左上角坐标的第i种方块，经第d种方式旋转后得到的方块，以颜色p放置在
//棋盘上。
void putothers(board & cur);
//执行[put]指令——根据输入的其他玩家所放置的方块，更新游戏棋盘各个格子的颜色。
void putmine(board & cur);
//依次选择（枚举）方块的种类、旋转方式、位置，直至其能够放置在当前棋盘上为止，并
//输出结果。
void putminefirst(board & cur);
//依次选择（枚举）第一个方块的种类、旋转方式、位置，直至其能够放置在当前棋盘上为
//止，并输出结果。
int ownnumber();//计算自己代号的函数，——(0,0)，——(0,19)，——(19,19)，——(19,0)
void availabledot();//计算目前扩展点的个数
double middle();//计算到中心的距离
void deletesingle(board & cur, int x, int y,int i, int d);//移除方块儿
double getgrade(int x,int y,int i,int d);//计算分数
double extendplace();//计算到出生点的距离
int main()
{
forge();
start(cur);
//初始化游戏棋盘，并生成游戏所需方块。
putothers(cur);
putminefirst(cur);
//放置第一个方块。
meetend = false;
for (;;) {
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
