§ ITPOW >> 文档 >> C#

一个简单的五子棋算法

作者: 来源: 日期:2010-4-16

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

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

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

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

禁手对执白同样成立。

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

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;  
        }  
    }  
}
相关文章