第二天:防守,堵堵堵
为了提高对五子棋游戏的感性认识,我又在网上找了几个写的很好的五子棋游戏,与电脑进行了若干次对弈。作为一个门外汉,防守总是最好的选择。那么在什么条件下防守,在什么位置防守,这些位置如何确定……在这一系列的问题的驱动下,我开始学习模拟对象的AI部分。
首先我选择了总是防守,所以在这一天,我的第一个问题解决了。那么在什么位置放手呢?
之前定义了棋盘用points[i][j]表示,那么最直观的想法是看看棋盘上的棋子,可是棋盘既有白子又有黑子,还有空位。怎么判断呢?好吧,从AI的角度出发,他现在要做的事情是:在当前棋盘状态选择一个合法位置——空位,然后在该位置出招。那么既然是在空位置出招,那么是不是评估棋盘上的空位置来指导出招就可以了?
作为门外汉我现在能够想到的就这么多了,好吧先不管3721,走起。
如何评估棋盘上的空位?
为了大家看起来方便,我先展示一个7*7的棋盘,示意一下。人先执黑,电脑后手执白,现在轮到电脑出招。棋盘如下
1234567
10000000
20000000
30021000
40001000
50000000
60000000
70000000
那么有子周围的空位置中,(2,4)向下看有一个2连,在(5,4)向上看有一个2连,在其他位置看到的都是1连。好了,从防守的角度出发,现在最危险的位置是(2,4)和(5,4)。通过这次观察,我们可以得到一种评估方法,那就是枚举棋盘上的每个空位,然后统计其8个方向上,相同颜色的棋子连成一线的棋子的个数。
为什么是8个方向?
因为空位填上子后,可能将以前的阴线(可能连成一线的线)变成阳线(已经连成一线的线)。因此,我们要在空位置上向八个方向都看看,看看这个位置能够连成多少条阳线,如果连成的阳线越多,阳线中棋子的数目越多,那么这个空位的威胁就越大。
定义int qiju[16][16][8][2]表示棋盘某个位置某个方向某种颜色的棋子连成一线的棋子的个数
定义int a1[16][16], a2[16][16]表示棋盘上某空位的评分。
如何评分呢?我们先考虑一线式的吧,就是横、竖、左斜、右斜这四种。定义int t1 = qiju[i][j][k][0]+qiju[i][j][k+4][0]表示,涵盖了空位在某一方向上一侧或两侧连成一线的棋子数目。
if t1 >= 4 a1[i][j] += 10000000;
if t1 == 3 a1[i][j] += 100000;
if t1 == 2 a1[i][j] += 1000;
if t1 == 1 a1[i][j] += 10;
同理可以计算a2。
好了在a1和a2中找到最大值的位置,如果人执黑,那么AI就用a1的最大值的位置作为落子的位置,如果AI执黑,那么AI就用a2的最大值的位置作为落子的位置。AI就可以成功的封堵住对自己威胁最大的位置,完成防守。
可是AI只会防守怎么行,好吧,那么我们只能重新考虑第一个问题将AI定义为攻守兼备,在什么条件下进攻呢,欲知后事如何,且听下回分解。
--------------------分割线--------------------
AI的代码如下,
void CWuZiQi::AI_1( const int points[16][16], bool first, int oldp[16][16], int newp[16][16], int *nx, int *ny ) { int i, j; int x, y; int x1 = 0, x2 = 0, y1 = 0, y2 = 0; int qiju[16][16][8][2]; int a1[16][16], a2[16][16]; // current state quick save for ( i = 1; i <= 15; i++ ) for ( j = 1; j <= 15; j++ ) { oldp[i][j] = points[i][j]; newp[i][j] = points[i][j]; } FillMatrix( qiju, 0 ); FillMatrix( a1, 0 ); FillMatrix( a2, 0 ); HowManyInLine( oldp, qiju ); ValueTheChessboardNaive( oldp, qiju, a1, a2 ); //rintMatrix( qiju ); //PrintMatrix( oldp ); /****************算出分数最高的空位,填写坐标*********************/ for( i = 1; i <= 15; i++ ) for( j = 1; j <= 15; j++ ) { if( a1[x1][y1] < a1[i][j] ) {x1 = i; y1 = j;} // black } for( i = 1; i <= 15; i++ ) for( j = 1; j <= 15; j++ ) { if( a2[x2][y2] < a2[i][j] ) {x2 = i; y2 = j;} // white } if ( first ) { x = x2; y = y2; newp[x][y] = 1; } else { x = x1; y = y1; newp[x][y] = 2; } *nx = x; *ny = y; }
统计函数如下,
void CWuZiQi::HowManyInLine( const int oldp[16][16], int qiju[16][16][8][2] ) { int i, j, k, t, cnt; int tx, ty; int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}; int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; /****************为双方填写棋型表************/ for ( i = 1; i <= 15; i++ ) // col for ( j = 1; j <= 15; j++ ) // row if ( oldp[i][j] == 0 ) { for ( k = 0; k < 8; k++ ) // direction { // black cnt = 0; tx = i; ty = j; for ( t = 0; t < 5; t++ ) { tx += dx[k]; ty += dy[k]; if ( tx > 15 || tx < 1 || ty > 15 || ty < 1 ) break; if( oldp[tx][ty] == 1 ) cnt++; else break; } qiju[i][j][k][0] = cnt; // white cnt = 0; tx = i; ty = j; for ( t = 0; t < 5; t++ ) { tx += dx[k]; ty += dy[k]; if ( tx > 15 || tx < 1 || ty > 15 || ty < 1 ) break; if( oldp[tx][ty] == 2 ) cnt++; else break; } qiju[i][j][k][1] = cnt; } } }
最最原始的、Naive阴线评估函数如下
void CWuZiQi::ValueTheChessboardNaive( const int points[16][16], int qiju[16][16][8][2], int a1[16][16], int a2[16][16] ) { int i, j, k; int win; /******************根据评分规则对每一个空格评分***************/ for ( i = 1; i <= 15; i++ ) // col for ( j = 1; j <= 15; j++ ) // row { if ( points[i][j] == 0 ) { win = 0; for ( k = 0; k < 4; k++ ) // direction { if ( qiju[i][j][k][0] + qiju[i][j][k+4][0] >= 4 ) win += 10000; else if ( qiju[i][j][k][0] + qiju[i][j][k+4][0] == 3 ) win += 1000; else if ( qiju[i][j][k][0] + qiju[i][j][k+4][0] == 2 ) win += 100; else if ( qiju[i][j][k][0] + qiju[i][j][k+4][0] == 1 ) win += 10; } a1[i][j] = win; // black win = 0; for ( k = 0; k < 4; k++ ) // direction { if ( qiju[i][j][k][1] + qiju[i][j][k+4][1] >= 4 ) win += 10000; else if ( qiju[i][j][k][1] + qiju[i][j][k+4][1] == 3 ) win += 1000; else if ( qiju[i][j][k][1] + qiju[i][j][k+4][1] == 2 ) win += 100; else if ( qiju[i][j][k][1] + qiju[i][j][k+4][1] == 1 ) win += 10; } a2[i][j] = win; // white } } }