• 五子棋简单AI算法（C#版）

    前言：

    本文只提供AI算法，不提供棋盘，因为棋盘不是我写的，不好拿出来分享，望谅解。

    AI水平说明：

    当前AI只能计算当前局面下最优的一步，没有深度，水平一般的普通人很轻易就会被其击败，但是有很大的升级空间，可以以此为基础再行添加算法添加深度，以及剪枝等算法。

    程序运行图片：黑方为AI，我是白色（我是不是太菜了。。）

    AI得分说明：

    当前AI为黑色时水平较高，为白色时需要修改得分表，得分表会影响AI的决策，得分可以自行修改，此得分表并非最佳得分表，但是经过我的测试貌似还可以。ps：这是AI的核心非常重要

    得分表如下：

    1. using System;
    2. using System.Collections;
    3. using System.Collections.Generic;
    4. using System.Linq;
    5. using System.Text;
    6. using System.Threading.Tasks;
    7.  
    8. namespace 五子棋
    9. {
    10.     public static class ChessValueUtil
    11.     {
    12.         
    13.         public static Hashtable blackTable = new Hashtable(); //创建一个HashTable实例
    14.         public static Hashtable whiteTable = new Hashtable(); 
    15.         //五子棋棋形，最长为7，最短为4（有些棋形必须将空位包含进去）
    16.         public static Hashtable getBlackTable()
    17.         {
    18.             return blackTable;
    19.         }
    20.         public static Hashtable getWhiteTable()
    21.         {
    22.             return whiteTable;
    23.         }
    24.         /**
    25.          *   *:表示黑子
    26.          *   -:表示空位
    27.          *   o:表示白子
    28.          */
    29.         static ChessValueUtil(){
    30.         //还要设置防守方的数值，防止被gank掉
    31.         //右边Add的whiteTable值，是防守分数，这样Ai就不会一味的猛冲
    32.  
    33.         //左边：黑方Ai的棋子判断                      右边：Ai结束后，玩家可能的棋子判断
    34.         blackTable.Add("*****",  100000);//连五
    35.         /*                                 */whiteTable.Add("ooooo",  90000);
    36.         blackTable.Add("-****-",  5000);//活四
    37.         /*                                 */whiteTable.Add("-oooo-",  4500);
    38.         blackTable.Add("*-***",  700);//冲四  1
    39.         /*                                 */whiteTable.Add("o-ooo",  200);
    40.         blackTable.Add("***-*",  700);//冲四  1  反向
    41.         /*                                 */whiteTable.Add("ooo-o",  200);
    42.         blackTable.Add("-****o",  900);//冲四  2
    43.         /*                                 */whiteTable.Add("-oooo*",  250);
    44.         blackTable.Add("o****-",  900);//冲四  2  反向
    45.         /*                                 */whiteTable.Add("*oooo-",  250);
    46.         blackTable.Add("**-**",  700);//冲四   3
    47.         /*                                 */whiteTable.Add("oo-oo", 200);
    48.         blackTable.Add("-***-",  600);//活三   1
    49.         /*                                 */whiteTable.Add("-ooo-",  150);
    50.         blackTable.Add("-*-**-",  150);//活三  2
    51.         /*                                 */whiteTable.Add("-o-oo-",  50);
    52.         blackTable.Add("-**-*-",  150);//活三  2   反向
    53.         /*                                 */whiteTable.Add("-oo-o-",  50);
    54.         blackTable.Add("--***o",  120);//眠三  1
    55.         /*                                 */whiteTable.Add("--ooo*",  30);
    56.         blackTable.Add("o***--",  120);//眠三  1  反向
    57.         /*                                 */whiteTable.Add("*ooo--",  30);
    58.         blackTable.Add("-*-**o",  80);//眠三   2
    59.         /*                                 */whiteTable.Add("-o-oo*",  15);
    60.         blackTable.Add("o**-*-",  80);//眠三   2  反向
    61.         /*                                 */whiteTable.Add("*oo-o-",  15);
    62.         blackTable.Add("-**-*o",  60);//眠三   3
    63.         /*                                 */whiteTable.Add("-oo-o*",  10);
    64.         blackTable.Add("o*-**-",  60);//眠三   3   反向
    65.         /*                                 */whiteTable.Add("*o-oo-",  10);
    66.         blackTable.Add("*--**",  60);//眠三   4
    67.         /*                                 */whiteTable.Add("o--oo",  10);
    68.         blackTable.Add("**--*",  60);//眠三   4   反向
    69.         /*                                 */whiteTable.Add("oo--o",  10);
    70.         blackTable.Add("*-*-*",  60);//眠三   5
    71.         /*                                 */whiteTable.Add("o-o-o",  10);
    72.         blackTable.Add("o-***-o",  60);//眠三   6
    73.         /*                                 */whiteTable.Add("*-ooo-*",  2);
    74.         blackTable.Add("--**--",  50);//活二  1
    75.         /*                                 */whiteTable.Add("--oo--",  2);
    76.         blackTable.Add("-*-*-",  20);//活二   2
    77.         /*                                 */whiteTable.Add("-o-o-",  2);
    78.         blackTable.Add("*--*",  20);//活二   3
    79.         /*                                 */whiteTable.Add("o--o",  2);
    80.         blackTable.Add("---**o",  10);//眠二  1
    81.         /*                                 */whiteTable.Add("---oo*",  1);
    82.         blackTable.Add("o**---",  10);//眠二  1   反向
    83.         /*                                 */whiteTable.Add("*oo---",  1);
    84.         blackTable.Add("--*-*o",  10);//眠二  2
    85.         /*                                 */whiteTable.Add("--o-o*",  1 );
    86.         blackTable.Add("o*-*--",  10);//眠二  2   反向
    87.         /*                                 */whiteTable.Add("*o-o--",  1);
    88.         blackTable.Add("-*--*o",  10);//眠二  3
    89.         /*                                 */whiteTable.Add("-o--o*",  1);
    90.         blackTable.Add("o*--*-",  10);//眠二  3   反向
    91.         /*                                 */whiteTable.Add("*o--o-",  1);
    92.         blackTable.Add("*---*",  10);//眠二  4
    93.         /*                                 */whiteTable.Add("o---o",  1);
    94.         
    95.     }
    96. }
    97. }

     AI算法思路讲解：

    首先我们需要知道输入和输出，给输入当前棋盘的二维数组，从而让他返回落点坐标。落点坐标有x，y两个值，我们可以先创建一个点的结构体，包括点信息，和当前点的分值：

    public struct Point
            {
                public int value;
                public int x;
                public int y;

            }

     二维数组中存储的是数字，而我们得分表中用的字符串，所以我们需要一个转换的方法，传入棋盘中某一条链，返回该链字符串形式：

    public static string ChessChainTostring(int[] CheckChain)
            {
                string pool = "";
                foreach (int chessColor in CheckChain)
                {
                    if (chessColor == 0)
                    {
                        pool += "-";
                    }
                    else if (chessColor == 1)
                    {
                        pool += "*";
                    }
                    else if (chessColor == 2)
                    {
                        pool += "o";
                    }
                    else
                    {
                        //放入一个hash表中不存在的字符
                        //这样后面算权值的时候就不会把它加进去了
                        pool += "#";
                    }
                }
                return pool;
            }

     核心思想:

    此处为我自己的思考方式，因为我实在是搞懂别人是怎么算的，思路很可能不一样，但是我的思路很简单，代码也少，但是运算量很大，如果你很有兴趣可以自己试着优化。

    最后一步肯定是依次计算棋盘中每一个点的分值，并从中选取得分最高的点返回（如果得分相同按理来说应该写个方法随机返回，我这里没写，默认返回第一个）

    int[,] map = new int[len, len];
                for (int i = 0; i < len; i++)
                {
                    for (int j = 0; j < len; j++)
                    {
                        if (ChessBoard[i, j] == 0)
                        {
                            map[i,j]=getScore(ChessBoard, i, j);
                            if (map[i, j] > max)
                            {
                                max = map[i, j];
                                point.value = max;
                                point.x = i;
                                point.y = j;
                            }
                        }
                    }
                }

    计算分值思路：

    假设在当前点下棋，拿到当前点位置横竖撇奈四条线上所有链条，转化为字符串并与得分表中的字符串进行比对，如果包含得分表中字符串就加上相应的分数，四条链每一条都要进行判断，最后得到在当前点落点的分值。

    假设当前点不下棋，通过同样方式计算得到原本该点四条链上的分值。

    落点的分值-不落点的分值=当前点的得分

    当前点得分有两种，因为我们有两个得分表（一黑一白），一种是进攻分，一种是防守分，都要进行计算，算出当前点的进攻分和防守分的总和，在减去两种原始得分，才能得出走该点真实分值。

    算完后不要忘记将棋盘还原。

    public static int getScore(int[,] ChessBoard, int x, int y)
            {
                int oldBlackValue=getValue(ChessBoard, x, y,1);
                int oldWhiteValue = getValue(ChessBoard, x, y, 2);
                ChessBoard[x, y] = 1;
                int atkValue=getValue(ChessBoard, x, y,1);
                ChessBoard[x, y] = 2;
                int defValue= getValue(ChessBoard, x, y,2);
                int score = atkValue + defValue - oldBlackValue- oldWhiteValue;

                //复原棋盘
                ChessBoard[x, y] = 0;
                return score;
            }

    public static int getValue(int[,] ChessBoard,int x,int y,int color)
            {
                int value = 0;
                ArrayList Chains=getChains(ChessBoard, x, y);
                foreach (int[] chain in Chains)
                {
                    string str=ChessChainTostring(chain);
                    Hashtable table;
                    if (color == 1)
                    {
                        table = ChessValueUtil.getBlackTable();
                    }
                    else
                    {
                        table = ChessValueUtil.getWhiteTable();
                    }
                    ICollection keys = table.Keys;
                    
                    foreach (string key in keys)
                    {
                        for (int i = 0; i < str.Length - key.Length+1; i++)
                        {
                            if (str.Substring(i, key.Length) == key)
                            {
                                value += (int)table[key];
                            }
                        }
                    }
                }
                return value;
            }

     public static ArrayList getChains(int[,] ChessBoard,int x,int y)
            {
                
                int len = 15;
                
                ArrayList Chains = new ArrayList();
                //横
                int[] heng = new int[len];
                for (int i = 0; i < len; i++)
                {
                    heng[i]=ChessBoard[i, y];
                }
                Chains.Add(heng);
                //竖
                int[] shu = new int[len];
                for (int i = 0; i < len; i++)
                {
                    shu[i] = ChessBoard[x, i];
                }
                Chains.Add(shu);
                //撇,x+,y-
                int[] pie = new int[len];
                int tmpX = x;
                int tmpY = y;
                while (tmpX > 0 && tmpY < len - 1)
                {
                    tmpX--;
                    tmpY++;
                }
                int k = 0;
                while (tmpX <= len - 1 && tmpY >= 0)
                {
                    pie[k++] = ChessBoard[tmpX, tmpY];
                    tmpX++;
                    tmpY--;
                }
                if (k < len)
                {
                    pie[k] = -1;
                }
                
                Chains.Add(pie);
                //捺
                int[] nai= new int[len];
                tmpX = x;
                tmpY = y;
                while (tmpX > 0 && tmpY>0)
                {
                    tmpX--;
                    tmpY--;
                }
                k = 0;
                while (tmpX <= len - 1 && tmpY <= len - 1)
                {
                    nai[k++] = ChessBoard[tmpX, tmpY];
                    tmpX++;
                    tmpY++;
                }
                if (k < len)
                {
                    nai[k] = -1;
                }
                Chains.Add(nai);
                return Chains;
            }

     这段代码判断当前棋盘为空时直接返回中间点坐标，其实最好还是不要写在AI里，因为每次都要循环一遍棋盘，最好是写在外面：

    int flag = 0;
                for (int i = 0; i < len; i++)
                {
                    for (int j = 0; j < len; j++)
                    {
                        
                        if (ChessBoard[i, j] != 0)
                        {
                            flag = 1;
                            break;

                        }
                        if (flag == 1)
                        {
                            break;
                        }
                    }
                }
                if (flag == 0)
                {
                    point.value = 0;
                    point.x = 7;
                    point.y = 7;
                    return point;
                }

    完整代码（代码写的很垃圾，见谅）：

    1. using System;
    2. using System.Collections;
    3. using System.Collections.Generic;
    4. using System.Linq;
    5. using System.Text;
    6. using System.Threading.Tasks;
    7. using System.Windows.Forms;
    8.  
    9. namespace 五子棋
    10. {
    11.     static class ChessUtil
    12.     {
    13.         public struct Point
    14.         {
    15.             public int value;
    16.             public int x;
    17.             public int y;
    18.  
    19.         }
    20.         /**
    21.         * 将棋子的颜色序列转换为字符序列
    22.         * 这样才能放入hashtable中进行比较
    23.         */
    24.         /**
    25.          *   *:表示黑子
    26.          *   -:表示空位
    27.          *   o:表示白子
    28.          */
    29.         public static string ChessChainTostring(int[] CheckChain)
    30.         {
    31.             string pool = "";
    32.             foreach (int chessColor in CheckChain)
    33.             {
    34.                 if (chessColor == 0)
    35.                 {
    36.                     pool += "-";
    37.                 }
    38.                 else if (chessColor == 1)
    39.                 {
    40.                     pool += "*";
    41.                 }
    42.                 else if (chessColor == 2)
    43.                 {
    44.                     pool += "o";
    45.                 }
    46.                 else
    47.                 {
    48.                     //放入一个hash表中不存在的字符
    49.                     //这样后面算权值的时候就不会把它加进去了
    50.                     pool += "#";
    51.                 }
    52.             }
    53.             return pool;
    54.         }
    55.         public static ArrayList getChains(int[,] ChessBoard,int x,int y)
    56.         {
    57.             
    58.             int len = 15;
    59.             
    60.             ArrayList Chains = new ArrayList();
    61.             //横
    62.             int[] heng = new int[len];
    63.             for (int i = 0; i < len; i++)
    64.             {
    65.                 heng[i]=ChessBoard[i, y];
    66.             }
    67.             Chains.Add(heng);
    68.             //竖
    69.             int[] shu = new int[len];
    70.             for (int i = 0; i < len; i++)
    71.             {
    72.                 shu[i] = ChessBoard[x, i];
    73.             }
    74.             Chains.Add(shu);
    75.             //撇,x+,y-
    76.             int[] pie = new int[len];
    77.             int tmpX = x;
    78.             int tmpY = y;
    79.             while (tmpX > 0 && tmpY < len - 1)
    80.             {
    81.                 tmpX--;
    82.                 tmpY++;
    83.             }
    84.             int k = 0;
    85.             while (tmpX <= len - 1 && tmpY >= 0)
    86.             {
    87.                 pie[k++] = ChessBoard[tmpX, tmpY];
    88.                 tmpX++;
    89.                 tmpY--;
    90.             }
    91.             if (k < len)
    92.             {
    93.                 pie[k] = -1;
    94.             }
    95.             
    96.             Chains.Add(pie);
    97.             //捺
    98.             int[] nai= new int[len];
    99.             tmpX = x;
    100.             tmpY = y;
    101.             while (tmpX > 0 && tmpY>0)
    102.             {
    103.                 tmpX--;
    104.                 tmpY--;
    105.             }
    106.             k = 0;
    107.             while (tmpX <= len - 1 && tmpY <= len - 1)
    108.             {
    109.                 nai[k++] = ChessBoard[tmpX, tmpY];
    110.                 tmpX++;
    111.                 tmpY++;
    112.             }
    113.             if (k < len)
    114.             {
    115.                 nai[k] = -1;
    116.             }
    117.             Chains.Add(nai);
    118.             return Chains;
    119.         }
    120.         public static int getValue(int[,] ChessBoard,int x,int y,int color)
    121.         {
    122.             int value = 0;
    123.             ArrayList Chains=getChains(ChessBoard, x, y);
    124.             foreach (int[] chain in Chains)
    125.             {
    126.                 string str=ChessChainTostring(chain);
    127.                 Hashtable table;
    128.                 if (color == 1)
    129.                 {
    130.                     table = ChessValueUtil.getBlackTable();
    131.                 }
    132.                 else
    133.                 {
    134.                     table = ChessValueUtil.getWhiteTable();
    135.                 }
    136.                 ICollection keys = table.Keys;
    137.                 
    138.                 foreach (string key in keys)
    139.                 {
    140.                     for (int i = 0; i < str.Length - key.Length+1; i++)
    141.                     {
    142.                         if (str.Substring(i, key.Length) == key)
    143.                         {
    144.                             value += (int)table[key];
    145.                         }
    146.                     }
    147.                 }
    148.             }
    149.             return value;
    150.         }
    151.         public static int getScore(int[,] ChessBoard, int x, int y)
    152.         {
    153.             int oldBlackValue=getValue(ChessBoard, x, y,1);
    154.             int oldWhiteValue = getValue(ChessBoard, x, y, 2);
    155.             ChessBoard[x, y] = 1;
    156.             int atkValue=getValue(ChessBoard, x, y,1);
    157.             ChessBoard[x, y] = 2;
    158.             int defValue= getValue(ChessBoard, x, y,2);
    159.             int score = atkValue + defValue - oldBlackValue- oldWhiteValue;
    160.             ChessBoard[x, y] = 0;
    161.             return score;
    162.         }
    163.         public static Point getScoreMap(int[,] ChessBoard)
    164.         {
    165.             Point point;
    166.             int max = 0;
    167.             point.value = 0;
    168.             point.x = 0;
    169.             point.y = 0;
    170.             int len = 15;
    171.             int flag = 0;
    172.             for (int i = 0; i < len; i++)
    173.             {
    174.                 for (int j = 0; j < len; j++)
    175.                 {
    176.                     
    177.                     if (ChessBoard[i, j] != 0)
    178.                     {
    179.                         flag = 1;
    180.                         break;
    181.  
    182.                     }
    183.                     if (flag == 1)
    184.                     {
    185.                         break;
    186.                     }
    187.                 }
    188.             }
    189.             if (flag == 0)
    190.             {
    191.                 point.value = 0;
    192.                 point.x = 7;
    193.                 point.y = 7;
    194.                 return point;
    195.             }
    196.             int[,] map = new int[len, len];
    197.             for (int i = 0; i < len; i++)
    198.             {
    199.                 for (int j = 0; j < len; j++)
    200.                 {
    201.                     if (ChessBoard[i, j] == 0)
    202.                     {
    203.                         map[i,j]=getScore(ChessBoard, i, j);
    204.                         if (map[i, j] > max)
    205.                         {
    206.                             max = map[i, j];
    207.                             point.value = max;
    208.                             point.x = i;
    209.                             point.y = j;
    210.                         }
    211.                     }
    212.                 }
    213.             }
    214.             return point;
    215.         }
    216.     }
    217.     
    218. }

    最后一个方法本来是计算当所有点坐标的分值图，从而进行二次甚至是三次递归的，但是因为是简单AI，所以算一次就返回吧，其实有些运算都是可以避免的，比如如果某点附近5步之内没有点，其实可以直接跳过的，但是我没进行优化，所以运算量是相当大了，大家自己试着优化吧。

    如果是白棋的话，翻转一下棋盘传进去，就能获得一个偏向进攻的白棋，但是可能会出现某些问题，还有就是传入的棋盘最好是备份的，尽量不要把原本的棋盘传进去，就这样吧。

    如果你找到了更好的计算当前点分数的方法，请务必给我留言，感激不尽！

  • 相关阅读:
    基于FPGA的Hamiton方程--辛几何算法实现（全网唯一）
    QT：画一个简单的时钟（坐标系移动、坐标系旋转、保存坐标系、恢复坐标系）
    Java 面试真题
    Leetcode_48:旋转图像
    NBT：快准全！geNomad——宏病毒组鉴定新工具
    IO流的讲解（3）
    数学小抄:线性回归与协方差
    使用.NET源生成器(SG)实现一个自动注入的生成器
    统计遗传学：第四章，GWAS分析
    微信小程序使用 scss
  • 原文地址：https://blog.csdn.net/Starry_error/article/details/125498493