一个简单可靠的五子棋算法

由于不是五手两打开局，所以执黑必胜，所以推荐执白

而且禁手只考虑了长连

五子棋理论上已经证明过如果没有任何规则，执黑先行的人如果每一步都应对得正确的话，是必胜的，也就是说，执黑因为有先手优势，每一步都有必胜的落子点，白棋不管怎么应对，结果都是很输的，所以为了抵消执黑的优势，在国际五子棋比赛里才规定了五手两打（上面打错了）和禁手的规则，

所谓的五手两打就是执黑和执白各走了二步后执黑连下两子让执白选择一个，去掉一个，然后继续，

还有三手交换，执黑和执白各走了一步后，执黑再走一步，如果执白这时发现开局对自己不利，可以要求互换，也就是执黑变执白，执白变执黑，

禁手就是不能下的点，连六、连七等都叫长连，比如执黑，也就是说下了这个子后，棋盘上连续的黑子超过了5个，那就不能下这点，三三禁手就是下了这点后棋盘上出现了两个（或更多）的活三（活三就是连续3个而且两头都是空格），四四禁手一样，就是连续4个子（不一定要两头都是空格）的情况出现了2个或以上

禁手对执白同样成立，

比赛可以规定有禁手和无禁手两种比赛规则

比如三三禁手：
      口
口黑黑X 口
       黑
    黑
   口

X处不能下

源代码及Demo下载

http://download.csdn.net/source/1896609

view plaincopy to clipboardprint?
using System;  
using System.Collections.Generic;  
using System.ComponentModel;  
using System.Data;  
using System.Drawing;  
using System.Text;  
using System.Windows.Forms;  
  
namespace wzq  
{  
    /// <summary>  
    /// Made by Wartim 1.0  
    /// </summary>  
    public partial class Form1 : Form  
    {  
        const int BORDER_LINES = 5; // >=5  
        const int DESK_LINES = 15;  
        const int TOTAL_LINES = DESK_LINES + BORDER_LINES * 2;  
        static int[,] Desk = new int[TOTAL_LINES, TOTAL_LINES];  
        static int SPACE = 0;  
        static int PLAYER = 1;  
        static int CPU  
        {  
            get  
            {  
                return 3 - PLAYER;  
            }  
        }  
        static int BORDER = 3;  
        PictureBox PB = new PictureBox();  
  
        public Form1()  
        {  
            InitializeComponent();  
  
            PB.Parent = this;  
            PB.Dock = DockStyle.Fill;  
            PB.MouseClick += new MouseEventHandler(PB_MouseClick);  
  
            this.MaximizeBox = false;  
            this.ClientSize = new Size(TOTAL_LINES * 10, TOTAL_LINES * 10);  
            this.FormBorderStyle = FormBorderStyle.FixedSingle;  
            this.StartPosition = FormStartPosition.CenterScreen;   
  
            Start();  
        }  
  
        void Start()  
        {  
            for (int i = 0; i < TOTAL_LINES; i++)  
                for (int j = 0; j < TOTAL_LINES; j++)  
                    if (i >= BORDER_LINES && i < BORDER_LINES + DESK_LINES  
                        && j >= BORDER_LINES && j < BORDER_LINES + DESK_LINES)  
                        Desk[i, j] = SPACE;  
                    else  
                        Desk[i, j] = BORDER;  
            Draw();  
  
            if (MessageBox.Show("执黑？", "开局", MessageBoxButtons.YesNo, MessageBoxIcon.Asterisk) == DialogResult.Yes)  
                PLAYER = 1;  
            else  
            {  
                Random R = new Random();  
  
                PLAYER = 2;  
                Desk[BORDER_LINES + DESK_LINES / 3 + R.Next(DESK_LINES / 3),  
                    BORDER_LINES + DESK_LINES / 3 + R.Next(DESK_LINES / 3)] = CPU;  
                Draw();  
            }  
        }  
  
        void PB_MouseClick(object sender, MouseEventArgs e)  
        {  
            int X = e.X / 10;  
            int Y = e.Y / 10;  
  
            if (X >= BORDER_LINES && X <= BORDER_LINES + DESK_LINES - 1  
                && Y >= BORDER_LINES && Y <= BORDER_LINES + DESK_LINES - 1)  
            {  
                if (Desk[X, Y] != SPACE)  
                    return;  
  
                Desk[X, Y] = PLAYER;  
                for (int k = 0; k < 8; k++)  
                {  
                    int Count = LineLength(GetCheckString(X, Y, k).Replace('X', 'P'), 'P');  
                    if (Count > 5)  
                    {  
                        Desk[X, Y] = SPACE;  
                        MessageBox.Show("禁手！");  
                        return;  
                    }  
                    if (Count == 5)  
                    {  
                        Draw();  
                        MessageBox.Show("你赢了");  
                        Start();  
                        return;  
                    }  
                }  
                Draw();  
  
                Compute();  
            }  
        }  
  
        void Draw()  
        {  
            if (PB.Image != null)  
                PB.Image.Dispose();  
            Bitmap Bmp = new Bitmap(this.ClientRectangle.Width, this.ClientRectangle.Height);  
            using (Graphics G = Graphics.FromImage(Bmp))  
            {  
                G.Clear(Color.LightGreen);  
  
                for (int i = 0; i < TOTAL_LINES; i++)  
                    for (int j = 0; j < TOTAL_LINES; j++)  
                        if (Desk[i, j] == SPACE )  
                        {  
                            G.DrawLine(Pens.Gray, i * 10, j * 10 + 5, i * 10 + 10, j * 10 + 5);  
                            G.DrawLine(Pens.Gray, i * 10 + 5, j * 10, i * 10 + 5, j * 10 + 10);  
                        }  
                        else if (Desk[i, j] != BORDER)  
                        {  
                            Color FillColor = Desk[i, j] == 1 ? Color.Black  : Color.White ;  
  
                            G.FillPie(new SolidBrush(FillColor), new Rectangle(i * 10, j * 10, 10, 10),0,360);  
                        }  
  
                PB.Image = Bmp;  
            }  
        }  
  
        void Compute()  
        {  
            double Max = 0;  
            int X = 0;  
            int Y = 0;  
            for (int i = BORDER_LINES; i <= BORDER_LINES + DESK_LINES - 1; i++)  
                for (int j = BORDER_LINES; j <= BORDER_LINES + DESK_LINES - 1; j++)  
                    if (Desk[i, j] == SPACE)  
                    {  
                        double Sum = 0;  
                        for (int k = 0; k < 8; k++)  
                        {  
                            Desk[i, j] = CPU;  
                            if (LineLength(GetCheckString(i, j, k).Replace('X', 'C'), 'C') == 5)  
                            {  
                                Draw();  
                                MessageBox.Show("你输了！");  
                                Start();  
                                return;  
                            }  
                            Desk[i, j] = SPACE;  
  
                            Sum += GetSource(GetCheckString(i, j, k));  
                        }  
                        if (Sum > Max)  
                        {  
                            Max = Sum;  
                            X = i;  
                            Y = j;  
                        }  
                    }  
  
            Desk[X, Y] = CPU;  
            Draw();  
        }  
  
        String GetCheckString(int i, int j, int Direct)  
        {  
            int StartX = 0;  
            int StartY = 0;  
            if (Direct == 0 || Direct == 4)  
                StartX = 0;  
            else if (Direct == 1 || Direct == 2 || Direct == 3)  
                StartX = 5;  
            else  
                StartX = -5;  
            if (Direct == 2 || Direct == 6)  
                StartY = 0;  
            else if (Direct == 3 || Direct == 4 || Direct == 5)  
                StartY = 5;  
            else  
                StartY = -5;  
  
            int XStep = -Math.Sign(StartX);  
            int YStep = -Math.Sign(StartY);  
            String S = String.Empty;  
            int X = i + StartX;  
            int Y = j + StartY;  
  
            for (int k = 0; k < 10 + 1; k++, X += XStep, Y += YStep)  
                if (X == i && Y == j)  
                    S += "X";  
                else if (Desk[X, Y] != 3)  
                    S += Desk[X, Y].ToString();  
              
            return S.Replace((Char)(PLAYER + '0'), 'P').Replace((Char)(CPU + '0'), 'C');  
        }  
  
        double GetSource(String CheckString)  
        {  
            double Source = 0;  
            String[][] CheckArea =  
            {  
                new String[]  
                {  
                    "XPPPP","PXPPP","PPXPP","PPPXP","PPPPX" // 玩家 连5  
                },  
                new String[]  
                {  
                    "0XCCC0","0CXCC0","0CCXC0","0CCCX0", // 连4全连通  
                },  
                new String[]  
                {  
                    "0XPPP0","0PXPP0","0PPXP0","0PPPX0", // 玩家 连4全连通  
                },  
                new String[]  
                {  
                    "XCCC0","CXCC0","CCXC0","CCCX0" // 连4半连通  
                },  
                new String[]  
                {  
                    "XPPP0","PXPP0","PPXP0","PPPX0" // 玩家 连4半连通  
                },  
                new String[]  
                {  
                    "X0CCC","C0XCC","C0CXC","C0CCX", // 连4  
                    "XC0CC","CX0CC","CC0XC","CC0CX",  
                    "XCC0C","CXC0C","CCX0C","CCC0X",  
                },  
                new String[]  
                {  
                    "X0PPP","P0XPP","P0PXP","P0PPX", // 玩家 连4  
                    "XP0PP","PX0PP","PP0XP","PP0PX",  
                    "XPP0P","PXP0P","PPX0P","PPP0X",  
                },  
                new String[]  
                {  
                    "0XCC0","0CXC0","0CCX0"  // 连3全连通  
                },  
                new String[]  
                {  
                    "0XPP0","0PXP0","0PPX0"  // 玩家 连3全连通  
                },  
                new String[]  
                {  
                    "0X0CC0","0CX0C0","0C0XC0","0CC0X0" // 连3  
                },  
                new String[]  
                {  
                    "0X0PP0","0PX0P0","0P0XP0","0PP0X0" // 玩家 连3  
                },  
                new String[]  
                {  
                    "0XC0","0CX0" // 连2全连通  
                },  
                new String[]  
                {  
                    "0XP0","0PX0" // 玩家 连2全连通  
                },  
                new String[]  
                {  
                    "0X0P0","0P0X0" // 连2  
                },  
                new String[]  
                {  
                    "0X0C0","0C0X0" // 玩家 连2  
                }  
            };  
            int CPUCount = LineLength(CheckString.Replace('X', 'C'), 'C');  
            int PLAYERCount = LineLength(CheckString, 'P');  
  
            if (CPUCount > 5 || PLAYERCount > 5)  
                return -1;  
            else if (CPUCount == 5)  
                return GetN(CheckArea.GetUpperBound(0) + 1) + 1;  
            else if (PLAYERCount == 5)  
                return GetN(CheckArea.GetUpperBound(0) + 1);  
            else  
            {  
                for (int i = 0; i <= CheckArea.GetUpperBound(0); i++)  
                    foreach (String S in CheckArea[i])  
                        if (CheckString.IndexOf(S) > 0)  
                        {  
                            Source += GetN(CheckArea.GetUpperBound(0) - i);  
                            break;  
                        }  
            }  
            for (int i = 0; i < CheckString.Length; i++)  
            {  
                int LineChar = CheckString[i];  
                Source += LineChar == 'C' ? 3 : LineChar == 'P' ? 2 : LineChar == '0' ? 1 : 0;  
            }  
            Source += CPUCount * 2 + PLAYERCount;  
            return Source;  
        }  
  
        double GetN(int M)  
        {  
            if (M == 0)  
                return 1000;  
            else  
                return GetN(M - 1) * 8 + 1;  
        }  
  
        int LineLength(String CheckString, Char LineChar)  
        {  
            int Max = 0;  
            int Count = 0;  
            for (int i = 0; i < CheckString.Length; i++)  
                if (CheckString[i] == LineChar)  
                    Count++;  
                else  
                {  
                    if (Count > Max)  
                        Max = Count;  
                    Count = 0;  
                }  
            if (Count > Max)  
                Max = Count;  
            return Max;  
        }  
    }  
}  

原文 http://blog.csdn.net/wartim/archive/2009/12/12/4993364.aspx

dm520

发表于 2009-12-16 09:23 dm520 阅读(356) 评论(0) 编辑收藏所属分类: 技术文章

常用链接

留言簿(2)

随笔分类(34)

随笔档案(38)

文章分类(45)

文章档案(83)

新闻分类(19)

新闻档案(20)

相册

收藏夹(2)

技术blog

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜