五子棋毕业论文

19

{

return TRUE; } } }

以上四个判断看起来写的复杂，时间复杂度有些高，但是每一个都是很有限的判断，计算机执行起来的时间基本都是0ms。所以程序中也不用怎么优化。

4.2 计算机落子时的算法[6]

4.2.1 计算落子时的所有获胜可能性

该程序为玩家和电脑都设置了一个三维数组，用于储存落子时的所有获胜的可能情况。根据上面判断落子时是否五子连珠，所有的可能性有以下几种。水平方向上：11*15； 竖直方向上：11*15；左下方向上：11*11；右下方向上：11*11。故落子时所有的获胜可能有 15 * 11 * 2 + 11 * 11 * 2 = 572种。

有了这些获胜的可能性，就可以对棋盘上当前落子进行打分，即对每一个位置进行

分数计算，给出最有进攻优势或者防守力度的坐标值。那么任何一方都需要一个15*15*572的数组来记录每一个坐标处的获胜可能性。

五子棋是两方的对弈，因此需要计算出双方的落子得分。电脑的落子得分与玩家的

落子得分计算都是参考上面的规则。

另外，每次进入游戏时，所有的获胜可能都一样，需要在COneGame::Init中初始化一下，都是572种。

4.2.2 落子后计算得分

只要棋盘上有落子，都需要作如下处理：

? 如果当前位置可以落子，并且落子后无论在哪个方向上，只要有一个方向能获

20

胜，则将获胜可能性数组加1。（此时并未落子，只是计算每个坐标的得分。） ? 如果对方在此坐标有可能获胜，则将对方在此坐标的获胜可能性置为false，

并将对方此获胜组合添加棋子数置为-1（不可能靠此组合获胜）。 以玩家落子为例，代码为：

for ( i = 0; i < 572; i++ ) {

// 修改状态变化

if ( m_Plajer[stepPut.i][stepPut.j][i] &&

m_Win[0][i] != -1 )

m_Win[0][i]++;

if ( m_Computer[stepPut.i][stepPut.j][i] ) {

m_Computer[stepPut.i][stepPut.j][i] = false; m_Win[1][i] = -1; } }

4.2.3 查找棋盘上的空位置

在电脑每一次落子之前，都有扫描一下棋盘，找出空位置。程序中的SearchBlank就是负责该功能的。SearchBlank函数进行不重复的查找，对已查找过的坐标进行标记，以便返回。其代码如下：

bool COneGame::SearchBlank( int &i, int &j,

int nowTable[][15] ) {

int i, j;

for ( i = 0; i < 15; i++ ) {

for ( j = 0; j < 15; j++ )

21

{

if ( nowTable[i][j] == -1 && nowTable[i][j] != 2 ) {

i = i; j = j; return true; } } }

return false; }

4.2.4 为每一个可以落子的位置打分

对于玩家有利的位置，就是对计算机不利的位置，故玩家的分数设为负值，对计算机来说就是既考虑了进攻，又考虑了防守。这就是整个程序的核心算法。上面的SearchBlank函数找到空位后，需要对当前坐标的落子进行打分，这个分对于这个坐标来说，就是落子后该棋子放在坐标处的价值。

m_Plajer[stepPut.i][stepPut.j][i]表示该坐标处的分数，若是玩家走棋时的分数则设为相反数，若是电脑走棋的分数就设为本身。

4.2.5 防守策略

落子的考虑不单单要从进攻考虑，还要从防守考虑。这一细节的实现其实就是让计算机从玩家棋盘布局分析战况，然后找出对玩家最有利的落子位置。

4.2.6 选取最佳落子

在循环结束的时候，就可以根据攻、守两方面的打分综合地考虑落子位置了。代码如下：

22

if ( ctemp + pscore > cscore ) {

cscore = ctemp + pscore; besti = pi; bestj = pj; }