到了考试周了佯,可是偏偏这个时候迎来了很多很多的课程设计,幸好教授把C语言的课程设计提前发出了,不然都在最后几周,加上数据结构的课程设计就没有时间做这个啦~
刚开始打算做成UWP应用的,可是网上的教程都是C#,并且用C++做的话某些功能和C#不一样,所以就这样拖了好多周,省赛前一点儿也没有开始做,等到省赛结束之后,别人都差不多完成啦!而我才开始准备查找资料……
然而一周过去了,进度还是0%。噫,1%吧!
眼看就要开始验收了,算了,还是用最简单的 EasyX 做吧!以后的 C# 课程设计再考虑 UWP。
周一开始敲代码,整整一周的课余时间,都在努力做这个,现在想起来,那个时候真的好累唉,居然没有感觉到~😔
最初做这个游戏是因为想起来 秦时明月 中的 墨攻棋阵 ,也就是黑白棋,努力还原动漫中的场景,周末的时候终于完成了。
先附图:
怎么说千千也都是新手呢!感觉做的还算满意吧!
人机对战中有三种模式哦!
简单、中等、困难
那么,接下来,我们一起来看看黑白棋中的AI是如何实现的。
对于我们来说,下棋的时候总是想着如何才能对自己最有利,当前最优?还是全局最优?
如果我们往后几步考虑的话,那便是全局最优啦!那当我们只看眼下哪一个位置的落子对自己最有利,这样便是当前最优,也是局部最优。
在黑白棋中,我们同样可以采用这样的思想。
首先来看看简单AI,因为简单呗,所以它返回的仅仅只是当前的最优解,再怎么说也不能让它随机返回坐标对吧!
那局部最优解又是以什么为评测标准的呢?
嗯,我们采用的是能够转换对方棋子最多的位置,这个可不是行动力哦!
POINT2 Easy() //人机对战简单AI
{
POINT2 MAX; //定义以及初始化最优解
MAX.INIT(0, 0);
int maxx = 0;
for (int i = 0; i < SIZE; ++i)
for (int j = 0; j < SIZE; ++j)
{
if (expect[i][j] >= maxx) //寻找可以转化棋子最多的点作为最优解
{
maxx = expect[i][j];
MAX.INIT(i, j);
}
}
if (ESCEXIT)gameStart();
Sleep(800); //间歇
return MAX; //返回最优解
}
呐,expect中便是每个点可以转换对方棋子的个数,这个 AI 简单吧!😄
其他难度 AI:
既然是简单以上的难度,就不能再像那样简单啦!不然一个中等AI被简单AI击败多没意思,O(∩_∩)O哈哈~
首先,我们应该知道一个估值表的问题,在黑白棋中,不同位置都有不同位置的估值,虽然这样的估值表的用处并不是很大,但却在某些细节中表现出至关重要的作用。
黑白棋的棋盘默认是8*8的,总共64格。
从游戏规则我们可以看出来,角上的子很重要,因为这里不会被对方转换,角边上的点很危险,它给了对方直接进角的机会。
边上中间的四个点比较重要,只能从一个方向被翻转……等等。
根据这样的经验,我们大致可以得到以下的估值表:
|
A |
B |
C |
D |
E |
F |
G |
H |
1 |
90 |
-60 |
10 |
10 |
10 |
10 |
-60 |
90 |
2 |
-60 |
-80 |
5 |
5 |
5 |
5 |
-80 |
-60 |
3 |
10 |
5 |
1 |
1 |
1 |
1 |
5 |
10 |
4 |
10 |
5 |
1 |
1 |
1 |
1 |
5 |
10 |
5 |
10 |
5 |
1 |
1 |
1 |
1 |
5 |
10 |
6 |
10 |
5 |
1 |
1 |
1 |
1 |
5 |
10 |
7 |
-60 |
-80 |
5 |
5 |
5 |
5 |
-80 |
-60 |
8 |
90 |
-60 |
10 |
10 |
10 |
10 |
-60 |
90 |
有了这张表,AI 进行估值的时候就很简单了,不过仅凭这一点可不行哦!
黑白棋的AI中,我们要考虑的除了估值表,还有稳定子。
稳定子,即不能被转换的棋子,稳定子的数量在游戏中是变化的,比如,一方占据整整一条边,那么这一条边上的所有棋子都是稳定子。
行动力,某方当前可走位置的个数,因为在黑白棋的游戏规则中,每一步的走棋都要形成转换,否则不能走棋,既然这样的话,我们在AI中便要尽可能让自己的行动力最大,而对方行动力最小,也就是尽可能让双方行动力差最大,这样的话,很容易AI便可以把玩家逼上绝路,玩笑而已……
除了这两个还有余裕手和潜在行动力,虽然并不懂~
对电脑AI设定中,我们的原则是能走角就走角,不到万不得已的情况下不要走邻角点。
对其他情况下采用极大极小博弈树搜索:
这里假设AI的对手都是最聪明的,会选择最优解,即会选择对AI最不利的选择。
搜出来的结果集是AI方的结果,那么要选择最终得分最高的那个位置
搜出来的结果集是玩家方的结果,那么要选择最终得分最低的那个位置。
如下图
假设圆形代表的是AI节点,方形代表玩家节点。
对于A2和A3这两种选择,AI显然是选择A2得10分。对于A4和A4这两种选择,AI显然是选择A4得20分。
但是对于B1,B2来说,玩家如果下B2,使得AI可以得20分,下B1,使得AI只能得10分,那么玩家显然是下B1。
所以最终A1这一步,AI只能得10分。这就是极大极小算法。
然后就是α-β剪枝:
现在A2,A3已经选出最大值10,B1的得分是10分。
而对于B1,B2来说是要选最小值,既然B1的得分是10分,则B1,B2之间的最终结果是<=10的。
而A4的得分是20分,对于A4,A5来说是选择最大值得,即A4,A5之间的最终结果是>=20的,说明B2的最终结果是>=20的。
那么这种情况下肯定是选B1了,对于还没有搜索的A5节点来说,已经影响不到最终的选择结果了,所以就可以不用考虑了。
然后得分的计算:
这里每一步的得分,都是相对于AI来说的得分。
AI自己落子某一个位置,得一个正分,之后对手落子某一个位置,所得的分数对于AI来说就是一个负分(即玩家取得的优势,对于AI来说就是劣势)。
对于已经搜到最大深度的节点来说,它的得分就是这个位置的本身得分(因为后面已经不搜了)。
而对于中途节点来说,它的得分应该是这个位置的本身得分,加上下一步对方的选择结果的得分。这里不能只以最后一步的结果逆推的。
举个例子:
如上图的左右两种情况。
假设圆形代表的是AI节点,方形代表玩家节点。
其中分值表示的是节点自身落子该位置所获得的在估值表中的得分,玩家节点取负分。
如果只是用最深层的节点的得分,来计算最上层的节点的得分,那么按照上面极大极小算法,AI最后的得分:左边是10分,右边是5分。那么AI选择左边的10分这种情况。
但是却造成了中间过程中,玩家可以得到50分的这样一个相对来说是比较好的分值。
而AI应该不让玩家取得这样一个比较好的优势。
所以要综合前后对方的落子位置以及得分来考虑最终得分:
AI最后的得分:左边是-30分,右边是-15分。最终选择为右边,而不是左边。
极大极小搜索就是这样了,难度的抉择取决于搜索的深度,不过要保证的是不要超时哦!
接下来附上我的 墨攻棋阵 中的AI算法,估计只有一点点的沾边吧!
还有很多需要优化的地方惹😭
int difai(int x,int y,int mapnow[SIZE][SIZE],int expectnow[SIZE][SIZE],int depin,int depinmax) //极大极小搜索
{
if (depin >= depinmax)return 0; //递归出口
int maxx = -10005; //最大权值
POINT2 NOW;
int expectnow2[SIZE][SIZE] , mapnow2[SIZE][SIZE],mapnext[SIZE][SIZE],expectlast[SIZE][SIZE]; //定义临时数组
copymap(mapnow2, mapnow); //复制当前棋盘
mapnow2[x][y] = NOWCOLOR ? 1 : -1; //模拟在当前棋盘上下棋
int ME = MAPPOINTCOUNT[x][y] + expectnow[x][y]; //当前棋子权
NOW.INIT(x,y);
Change(NOW, mapnow2, false); //改变棋盘AI结束
int MAXEXPECT = 0, LINEEXPECT = 0, COUNT = 0;
for (int i = 0; i < SIZE; ++i)
for (int j = 0; j < SIZE; ++j)
{
expectnow2[i][j] = Judge(i, j, !NOWCOLOR, mapnow2);//预判对方是否可以走棋
if (expectnow2[i][j])
{
++MAXEXPECT;
if ((i == 0 && j == 0) || (i == 0 && j == SIZE - 1) || (i == SIZE - 1 && j == SIZE - 1) || (i == SIZE - 1 && j == 0))return -1800; //如果对方有占角的可能
if ((i < 2 && j < 2) || (i < 2 && SIZE - j - 1 < 2) || (SIZE - 1 - i < 2 && j < 2) || (SIZE - 1 - i < 2 && SIZE - 1 - j < 2))++LINEEXPECT;
}
}
if (LINEEXPECT * 10 > MAXEXPECT * 7)return 1400;//如果对方走到坏点状态较多 剪枝
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
if (expectnow2[i][j]) //如果对方可以走棋
{
int YOU = MAPPOINTCOUNT[i][j] + expectnow2[i][j];//当前权值
copymap(mapnext, mapnow2); //拷贝地图
mapnext[i][j] = (!NOWCOLOR) ? 1 : -1; //模拟对方走棋
NOW.INIT(i, j);
Change(NOW, mapnext, false); //改变棋盘
for (int k = 0; k < SIZE; k++)
for (int l = 0; l < SIZE; l++)
expectlast[k][l] = Judge(k, l, NOWCOLOR, mapnext); //寻找AI可行点
for (int k = 0; k < SIZE; k++)
for (int l = 0; l < SIZE;l++)
if (expectlast[k][l])
{
int nowm = ME - YOU + difai(k, l, mapnext, expectlast, depin + 1, depinmax);
maxx = maxx < nowm ? nowm : maxx;
}
}
return maxx;
}
有关黑白棋AI极大极小搜索的算法也就这些了,希望本文能对你有一点帮助。
另外,墨攻棋阵的项目源码在我的 GitHub 里面,欢迎大家 Fork ,发现 Bug 后不要忘记给我留言哦!😝
感谢大佬!学到了很多ヾ(^▽^*)))
哈哈,欢迎常来呀~
千千为什么联机不了啊求指点
咦,应该可以的呀~ 得在同一个局域网下面
牛
欢迎常来呀~
小伙纸,你让哥哥们压力好大
咦,千千只是一个人呀~
又要做课设了,我有点慌。。。
我也好多课程设计,数据库和java