C# 五子棋及其算法实现

[ 38964 / 455 / 58 ]

前一段时间某个公司给我出了一道作业题,当然,只有做完了这个题目才能够有基本的实习机会,这个题目就是五子棋了。五子棋说起来简单,也比较简单,毕竟现在网上已经有非常成熟的算法了,而如果说五子棋考人面试的话,应该还算是有一定的难度的(虽然思路不是特别难),当然,我在做这个题目的时候,还是发现了很多问题。在博客园上找了一个五子棋的实现,我写的算法基本和他差不多,不过我的AI总没有他那么高,我这就是简单的实现了一下,如下图所示。

C# 五子棋及其算法实现_11148

在做五子棋这个程序的时候,首先确定一些基本功能,这些功能包括如下。

玩家能够快速开始游戏。
玩家能够更换身份(更换黑棋和白棋)。
玩家能够退出游戏。
其中,玩家能够快速开始游戏,需要考虑玩家当前的身份。例如当玩家为黑棋的时候(玩家先走棋),单击【快速游戏】时玩家能够开始下棋,另外,当玩家为白棋的时候(电脑先走棋),单击【快速游戏】时计算机首先下棋。不仅如此,玩家能够快速更换身份。更换身份后玩家能够进行不同的棋子的选择,从而和电脑进行博弈。
如果玩家希望退出时,可以单击【退出】进行系统退出。

OK,了解了基本的功能后,主要就是算法问题了,这里主要有几个类,这几个类分别为Stones(控制棋子),Boards(控制棋盘以及逻辑),PC(电脑AI的实现),Rules(五子棋规则的实现)。首先也是最重要的,就是Boards类,该类一开始首先需要绘制一个棋盘在窗体中。棋盘是绘制上去的,在Paint方法中实现,示例代码如下所示。
  1. private void Form1_Paint(object sender, PaintEventArgs e)   
  2. {   
  3.     bd.DrawBoard();   
  4. }
复制代码
上述代码使用了Boards的bd类进行棋盘的创建,这里可以看看该类的实现。
  1. public void DrawBoard()   
  2. {   
  3.     Assembly myAssembly = Assembly.GetExecutingAssembly();   
  4.     Stream myStream = myAssembly.GetManifestResourceStream("FiveStone.board.png");   
  5.     Bitmap bt = new Bitmap(myStream);   
  6.     myStream.Close();   
  7.     mg.DrawImage(bt, 20, 20, bt.Width, bt.Height);   
  8.  
  9.     for (int i = 0; i < 15; i++)   
  10.     {   
  11.         for (int j = 0; j < 15; j++)   
  12.         {   
  13.             if (board[i, j] == 0)   
  14.             {   
  15.                 stone.DrawStone(i, j, true);   
  16.             }   
  17.             if (board[i, j] == 1)   
  18.             {   
  19.                 stone.DrawStone(i, j, false);   
  20.             }   
  21.         }   
  22.     }   
  23. }
复制代码
由于我们的棋盘是15*15的,那么该函数会在每次重绘的时候进行棋盘中的棋子的绘画。那么棋子怎么表示呢,这里就用-1,0,1进行表示,其中0是白子,而1是黑子,那么-1当然就是没子了,该函数会在每次重绘时进行绘制,从而呈现棋盘上的内容。

在上述代码中,使用了Stones的stone对象,该类的实现如下所示。
  1. public class Stones   
  2. {   
  3.     private Graphics mg;   
  4.     private Bitmap bs;   
  5.     private Bitmap ws;   
  6.  
  7.     public Stones(Graphics g)   
  8.     {   
  9.         Assembly myAssembly = Assembly.GetExecutingAssembly();   
  10.         Stream bStream = myAssembly.GetManifestResourceStream("FiveStone.black.png");   
  11.         Stream wStream = myAssembly.GetManifestResourceStream("FiveStone.white.png");   
  12.         bs = new Bitmap(bStream);   
  13.         ws = new Bitmap(wStream);   
  14.         bStream.Close();   
  15.         wStream.Close();   
  16.         mg = g;   
  17.     }   
  18.  
  19.     public void DrawStone(int x, int y, bool flag)   
  20.     {   
  21.         if (flag)   
  22.         {   
  23.             mg.DrawImage(bs, x * 40 + 20, y * 40 + 23, bs.Width, bs.Height);   
  24.         }   
  25.         else 
  26.         {   
  27.             mg.DrawImage(ws, x * 40 + 20, y * 40 + 23, bs.Width, bs.Height);   
  28.         }   
  29.     }   
  30. }
复制代码
代码不做过多的解释,这里的高手一定都知道了,这些内容可以在源代码中下载。OK,在了解了基本的绘制棋盘以及绘制棋子(还有棋子状态的描述),那么就应该描述AI了。AI部分的实现,我从网上看到的资料,大多都是用权值进行描述,当然,这个方法虽然最笨也是最容易实现的。当人下子的时候(通过ON_MONTHDOWN方法),可以在相应的数组空间中进行赋值,例如如果人下的是白子,那么相应的数组位置的值应该等于0,反之等于1。那么当人下子了之后,计算机如何知道该怎么下子呢,计算机当然不知道什么是”双三,”冲四,这里必须通过数学的方法进行实现,(可能网上说的不太清除,我详细的讲一下,也会自己进行记录)如下图所示。

C# 五子棋及其算法实现_11149

如上图所示,当我们首先在中间下了一个黑子(这里是计算机先下,方便说明,因为如果我先下的话,那么计算机很快就下子了。。),那么计算机就应该计算哪里才是最好的地方,当然,这里只有一个子,计算机的计算就可以随便计算,当然,也有一定的规律性。计算机可能在上图中的1、2、3或者周边的其他地方下子,但是为什么要选这个地方下子?计算机就要找到最好的地方,怎么找最好的地方,就是要找到胜利的”可能性,既然知道计算机要找到可能性,那么怎么找可能性?如下图所示。

C# 五子棋及其算法实现_11150

如上图所示,在最上面一行,其中是一个连子的可能性。其中占用五个子,那么在最上面一行的可能性有11种(自己数,上图中是一种可能性,依次右移,有11种),这里有15行,那么就是11*15种可能性。同理,从上到下的可能性也是11*15种可能性,而侧边(即左上右下,右上左下的方向),也具有可能性,上图中也描述了,这个可能性希望大家能够自己数一数。

OK,知道了可能性以后,就需要了解计算机怎么判断落子点,上图中在中间下了一个白子,既然下了一个白子,那么周边也是有可能性的。注意,计算机会通过可能性计算你下子周边的可能性,例如上面下了一个白子,周边的连子(即能够形成5个子连子的可能性),都是有的,并且应该相等。当然,在初期,这个相等的值比较多。然后里该位置越远,可能性就越少,计算机就越不会在那个位置下子,例如左下角,大家都知道中间这个点和左下角这个点练成五子的可能性为0,这里计算机也认为为0,那么就不会在这个地方下子,同样,下了多步后,可能性也会被重新计算,如下图所示。

C# 五子棋及其算法实现_11151

当下了多步之后,例如上面,计算机马上要赢了,那么计算的话,第5个子的位置的权值应该是最高的,即10000,这里可以随意定,越高越好。而其他周边的地方,赢的可能性可能会少一些,可能就是500,同理,在右下边两个黑子那里,由于还是两个黑子,没有构成猥亵,计算机也会认定具备较少的权值,则计算机会下权值最高的点(如果人不堵这个位置),如果人堵了这个点,那么计算就就会继续找权值最高的点(当然,这个时候权值就可能不是上图中所描述的了)。

既然了解了基本原理之后,那么如何计算权值?权值的计算方法比较容易,即从上、下、左上右下、右上左下四个方向寻找连子,如果连子有1个,即可赋值权值100,依次增高,如果连子有4个,那么就应该有最高的权值,即10000。值得注意的是,权值不仅仅包括一个方向,例如”双三或”冲四,在一个点中的不同方向都有多个子的时候,应该加上所有方向的权值。

在计算中,首先需要计算整个棋盘的权值,示例代码如下所示。
  1. public void Down(int[,] board)   
  2. {   
  3.     int[,] q = new int[15, 15];   
  4.     for (int i = 0; i < 15; i++)   
  5.     {   
  6.         for (int j = 0; j < 15; j++)   
  7.         {   
  8.             if (board[i, j] != -1)//如果这个位置没有子的话   
  9.             {   
  10.                 q[i, j] = -1;//权值为-1即可咯   
  11.             }   
  12.             else 
  13.             {   
  14.                 q[i, j] = FindQz(i, j, board);//找权值   
  15.             }   
  16.         }   
  17.     }   
  18.     ForMax(q);   
  19. }
复制代码
上述代码使用了FindQz方法寻找权值,示例代码如下所示。
  1. public int FindQz(int x,int y,int[,] board)   
  2. {   
  3.     int qz = 0;   
  4.     int w1 = 10000000;   
  5.     int w2 = 50000;   
  6.     int w3 = 10000;   
  7.     int w4 = 5000;   
  8.     int w5 = 1000;   
  9.     int w6 = 500;   
  10.     int w7 = 100;   
  11.     int w8 = 50;   
  12.     int w9 = -100000000;   
  13.     int[] move = new int[4];   
  14.     if (mifis)   
  15.     {   
  16.         board[x, y] = 0;   
  17.     }   
  18.     else 
  19.     {   
  20.         board[x, y] = 1;   
  21.     }   
  22.     move[0] = Rules.X1(x, y, board);   
  23.     move[1] = Rules.X2(x, y, board);   
  24.     move[2] = Rules.X3(x, y, board);   
  25.     move[3] = Rules.X4(x, y, board);   
  26.     if (x == 7 && y == 7)   
  27.     {   
  28.         qz += 1;   
  29.     }   
  30.  
  31.     for (int i = 0; i < 4; i++)   
  32.     {   
  33.         if (Abs(move) == 5)   
  34.         {   
  35.             qz += w1;   
  36.         }   
  37.         else if (move == 4)   
  38.         {   
  39.             qz += w3;   
  40.         }   
  41.         else if (move == 3)   
  42.         {   
  43.             qz += w5;   
  44.         }   
  45.         else if (move == 2)   
  46.         {   
  47.             qz += w7;   
  48.         }   
  49.  
  50.         if (mifis)   
  51.         {   
  52.             if (Rules.Fails(move, board[x, y]))   
  53.             {   
  54.                 qz += w9;   
  55.             }   
  56.         }   
  57.     }   
  58.  
  59.     if (mifis)   
  60.     {   
  61.         board[x, y] = 1;   
  62.     }   
  63.     else 
  64.     {   
  65.         board[x, y] = 0;   
  66.     }   
  67.  
  68.     move[0] = Rules.X1(x, y, board);   
  69.     move[1] = Rules.X2(x, y, board);   
  70.     move[2] = Rules.X3(x, y, board);   
  71.     move[3] = Rules.X4(x, y, board);   
  72.  
  73.     for (int i = 0; i < 4; i++)   
  74.     {   
  75.         if (Abs(move) == 5)   
  76.         {   
  77.             qz += w2;   
  78.         }   
  79.         else if (move == 4)   
  80.         {   
  81.             qz += w4;   
  82.         }   
  83.         else if (move == 3)   
  84.         {   
  85.             qz += w6;   
  86.         }   
  87.         else if (move == 2)   
  88.         {   
  89.             qz += w8;   
  90.         }   
  91.     }   
  92.     board[x, y] = -1;   
  93.     return qz;   
  94. }
复制代码
上述代码就不详细解释了,如果有不会的朋友可以逐步运行并查看局部变量的值。其中,Rules中包括计算四个方向的连子的方法,其中一个方法的代码如下所示。
  1. //左右方向   
  2. public static int X1(int x, int y, int[,] board)   
  3. {   
  4.     int flag=0;   
  5.     int count=1;   
  6.     int i = x + 1;   
  7.     while(i<15)   
  8.     {   
  9.         if (board[x, y] == board[i, y])   
  10.         {   
  11.             count++;   
  12.             i++;   
  13.         }   
  14.         else 
  15.         {   
  16.             break;   
  17.         }   
  18.     }   
  19.  
  20.     if (i == 15)   
  21.     {   
  22.         flag++;   
  23.     }   
  24.     else 
  25.     {   
  26.         if (board[i, y] != -1)   
  27.         {   
  28.             flag++;   
  29.         }   
  30.     }   
  31.  
  32.     i = x - 1;   
  33.     while (i > 0)   
  34.     {   
  35.         if (board[x, y] == board[i, y])   
  36.         {   
  37.             count++;   
  38.             i--;   
  39.         }   
  40.         else 
  41.         {   
  42.             break;   
  43.         }   
  44.     }   
  45.  
  46.     if (i == -1)   
  47.     {   
  48.         flag++;   
  49.     }   
  50.     else 
  51.     {   
  52.         if (board[i, y] != -1)   
  53.         {   
  54.             flag++;   
  55.         }   
  56.     }   
  57.  
  58.     if (flag == 2)   
  59.     {   
  60.         return -count;   
  61.     }   
  62.     else 
  63.     {   
  64.         if (flag == 1 && count == 3)   
  65.         {   
  66.             return -count;   
  67.         }   
  68.         else 
  69.         {   
  70.             return count;   
  71.         }   
  72.     }   
  73. }
复制代码
需要找四个方向,就需要四个方法进行权值的计算,同样在代码中可以看到,这里就不重复张贴。计算了整个棋盘的的权值之后,还需要找到最大的权值点,示例代码如下所示。
  1. public void ForMax(int[,] q)   
  2. {   
  3.     int max=0;   
  4.     for (int i = 0; i < 15; i++)   
  5.     {   
  6.         for (int j = 0; j < 15; j++)   
  7.         {   
  8.             if (q[i, j] > max)   
  9.             {   
  10.                 X = i;   
  11.                 Y = j;   
  12.                 max = q[i, j];   
  13.             }   
  14.         }   
  15.     }   
  16. }
复制代码
找到了最大的权值后,计算机就知道在该点是最好的下子点,即如果计算机在这个位置下子,那么玩家的胜利率就会降低。OK,既然了解了基本的算法及其思路之后,大家应该会写了,这里我归纳一下我做的时候遇到的一些难点。

绘制的时候描点非常难,主要是鼠标点在棋盘中,那个棋子是不是下在那个位置,有可能有点点误差就会下偏,这里要看精确度。

算法实现的时候,进行移动,判断的时候需要不少变量,特别是人机交换的时候,让计算机知道自己下子的类型。

当然,这个算法还是基本能够完成所需要的任务的了。但是这个算法还是有误差的,如下图所示。

C# 五子棋及其算法实现_11152

当下子,快胜利时,有可能双三,那么计算机可能在计算权值的时候,会遇到以上的情况,即都是10000,那么计算机可能会找到一个位置(可能是随机,看具体怎样实现)进行下子,但是这个点并不是制胜点。如上图,这里就可能需要再次比较相同的最大权值的部分进行分析。

另外,在计算权值的时候,可以使用矩阵转置,稀疏矩阵进行描述,这里就不再详细的编写算法了。最后说一句,由于是面试题,所以不能够使用现有的类进行实现,这里我手动实现了一个堆栈和一些方法,具体可以参考代码。

源码下载:
附件: 亲,您没有权限下载或查看附件喔:-) 试试登录注册吧!
TOP

回复 1# cobra 的帖子

谢谢,非常感谢!
TOP

学习一下
TOP

回复 1# cobra 的帖子

学习下
TOP

好东西 ,呵呵
TOP

谢谢,非常感谢
TOP

ding~~ding~~
TOP

mark下
TOP

回复,下载
TOP

棋盘图片怎么能的啊
TOP