老调重提,利用SDK实现智能五子棋

下载本文示例代码
下载源代码

　　网上有很多的实现五子棋的算法，如利用规则法，递归法，博弈树法来实现五子棋的，上次我写了一篇利用SDK实现迷宫算法的文章——“老调重提,利用 SDK 实现迷宫算法”，这次还是同样的题目，老调重提，我利用的是规则法来实现五子棋的智能。不过我个人认为还是博弈树法还是简洁。如果读者对博弈树有兴趣的，可以重读数据结构中的树结构的实现这一部分!

这是利用SDK实现的五子棋程序运行界面：



这里我讲出我实现的思路：
第一步，计算出一个棋盘的五子棋的所有胜利组合。
第二步，计算出玩家的下棋状态,电脑将会根据玩家的状态而采取进攻或防守。
第三步，根据第二步的运行情况,而出现三种结果,玩家获胜,电脑获胜,和局。
第一步，计算胜利的组合


　　从图中可以看出，只要五个棋子连续成一直线就可以胜利，这样我们就可以根据这样的规则计算出所有的胜利组合，利用组合运算可以算出一个10 * 10的棋盘的胜利组合可以有192种。即这样计算，每一行有十个格，计算出连续的五个格的组合，10个格中无论怎样已经有四个格连续的了，剩下的六个格中每一个都会是连续的组合，所以C6.1 = 6，共有6种胜利组合，10行共有 60 种胜利组合，10列中也会有 60 种胜利组合， 对角线则这样计算， 从正对角线开始， 其组合成直线的格可以有 10， 9， 8， 7， 6， 5， 剩下的不足五格，不可能构成胜利组合 C(10 - 4).1 = 6， C(9 - 4).1 = 5， C(8 - 4).1 = 4， C(7 - 4).1 = 3， C(6 - 4).1 = 2， C(5 - 5).1 = 1，由于对称，即对角线有 6 ( 5 4 3 2 1 ) * 2 = 36， 反对角线同样为 36。则所有的胜利组合为 36 * 2 60 * 2 = 192 种胜利组合，玩家和电脑的所有获胜都会在这些组合中。

//知道所有的胜利组合状态,我们可以定义一个数组记录这些组合.

BOOL	bArrPlayerWin[ 10 ][ 10 ][ 192 ] = { FALSE };

BOOL	bArrComWin[ 10 ][ 10 ][ 192 ] = { FALSE };

　　这是一个三维数组, 记录了在棋盘中所有的胜利组合.如玩家在棋盘 列1 行1的位置,则有三种胜利组合,如图：



　　可能为bArrPlayer[1][1][3] = TRUE，bArrPlayer[1][1][6] = TRUE，bArrPlayer[1][1][9] = TRUE如果电脑在标记为绿色的位置的地方放了棋子，则破坏了这种获胜组合，玩家不可能在这种组合中获胜，所以把其值设成 FALSE，则电脑可以不用在这儿再放置棋子了，同样，玩家可以破坏电脑的获胜组合。
　　计算所有的胜利的组合在 InitWinStatus()函数中，这些代码很简单，所以不讲解了，请读者自已理解这些代码!

void InitWinStatus()

{

	int nCount = 0;



	// Set the vertical combinations winning status.

	for ( int i = 0; i < 10; i   )

		for ( int j = 0; j < 6; j   )

		{

			for ( int k = 0; k < 5; k   )

			{

				bArrPlayerWin[ j   k ][ i ][ nCount ] = TRUE;

				bArrComWin[ j   k ][ i ][ nCount ] = TRUE;

			}



			nCount  ;

		}



	// Vertical has 60 winning status.

	assert( nCount == 60 );



	// Set the horizontal combinations winning status.

	for ( i = 0; i < 10; i   )

		for ( int j = 0; j < 6; j   )

		{

			for ( int k = 0; k < 5; k   )

			{

				bArrPlayerWin[ i ][ j   k ][ nCount ] = TRUE;

				bArrComWin[ i ][ j   k ][ nCount ] = TRUE;

			}



			nCount  ;

		}



	// Horizontal has 60 winning status

	assert( nCount == 120 );



	// Set the positive diagonal winning status.

	for ( i = 0; i < 6; i   )

		for ( int j = 0; j < 6; j   )

		{

			for ( int k = 0; k < 5; k   )

			{

				bArrPlayerWin[ j   k ][ i   k ][ nCount ] = TRUE;

				bArrComWin[ j   k ][ i   k ][ nCount ] = TRUE;

			}



			nCount  ;

		}



	// Positive diagonal has 36 winning status.

	assert( nCount == 156 );



	// Set the negative diagonal winning status.

	for ( i = 0; i < 6; i   )

		for ( int j = 9; j > 3; j-- )

		{

			for ( int k = 0; k < 5; k   )

			{

				bArrPlayerWin[ j - k ][ i   k ][ nCount ] = TRUE;

				bArrComWin[ j - k ][ i   k ][ nCount ] = TRUE;

			}



			nCount  ;

		}



	// Negative diagonal has 36 winning status.

	assert( nCount == 192 );



	// Who is the first ?

	if ( rand() % 2 == 0 )

		bPlayerDo = TRUE;

	else

		bComputerDo = TRUE;

}

　　第二步,电脑计算玩家下棋状态采取进攻或防守的策略,这是五子棋的关键所在,这儿给出实现的伪代码.

	// 计算玩家的状态.

	for ( int i = 0; i < 10; i   )

		for ( int j = 0; j < 10; j   )

			if ( nArrBoard[ i ][ j ] == NoBall )

			{

				// 利用一个变量记录该位置的分值.

				nArrPlayerGrades[ i ][ j ] = 0;

				for ( int k = 0; k < 192; k   )

					// 该位置是在获胜的组合中.

					if ( bArrPlayerWin[ i ][ j ][ k ] )

						switch( nArrWinner[ nPlayer ][ k ] )

						// 根据放在组合的棋子数计算分值.

						// 棋数越多,分值越高.

			}

	// 计算电脑的状态, 代码同上.

	.........



	// 判断情况

	if ( nArrComGrades[ i ][ j ] < nArrPlayerGrades[ i ][ j ] )

		// 该胜利组合中有可能输

		进攻;

	else

		防守;

第三步，在第二步中不停地进攻防守，则可以出现三种结果，电脑胜，玩家胜，或和局。

for ( int i = 0; i <= 1; i   )

	for ( int j = 0; j < 192; j   )

	{

		if ( nArrWinner[ i ][ j ] == 5 )

			if ( i == nPlayer )

			{

				bPlayerWin	= TRUE;

				bOver		= TRUE;

				break;

			}

			else

			{

				bComputerWin	= TRUE;

				bOver		= TRUE;

				break;

			}

			if ( bOver )

				break;

	}

　　遍历所有的胜利组合， 如果所属的组合已经有五颗棋子，有则游戏结束!这只是简单地说明我实现的过程，附件中附有五子棋的所有源代码，你自已修改这些代码，增加功能。

结语

　　从这里可以初步了解， AI的其本实现就是要将所有的情况计算出来， 再根据情况而采取相应
的措施。但是这里的实现只是限于简单的五子棋规则， 从而把其所有的胜利计算出来， 对于象棋，围棋等复杂的情况，我们还是需要用博弈树进行剪枝来找出所有的胜利组合。希望你会喜欢这个游戏!
　

下载本文示例代码

输入您的搜索字词 提交搜索表单