人工智能基础-极大极小策略

DearXuan

发布于 2022-01-19 18:53:39

6010

发布于 2022-01-19 18:53:39

文章被收录于专栏：DearXuan的博客文章DearXuan的博客文章

博弈论

博弈论是现代数学的一个分支，是用于研究竞争现象的数学工具。博弈策略是一套考虑到所有可能的情况而做出的行动。博弈论在人工智能方面有极大的价值。

零和博弈

在零和博弈，双方的总利益为0，其中一方为了自己利益最大化，必须损失另一方的利益。正如棋局中，一方赢了，则另一方必定输了，则利益之和为 1+(-1)=0

这就要求，任意一方都要使自己利益最大化，同时使对方利益最小化。因此在决策时，不能只考虑自己的最大利益，还需要考虑对方做出的对自己最不利的选择

极大极小策略

极大极小方法是分析零和博弈问题时的一种策略，在对局制游戏中，每个参与者都会做出对自己最有利，同时也是对对方最不利的选择。

在下棋时，每一个棋盘布局都可以表示为一个节点，相邻的节点形成多叉树。每种布局都会对一方有利而对另一方不利，称节点的有利程度为价值。

假设人类与计算机进行对决，并假设人类绝对聪明，那么在人类的回合，他会选择对计算机最不利的棋局，也就是价值最低的节点。而计算机则会选择对自己价值最高的节点。

假设各节点的价值如下

决策过程如下：

计算机选择对自己有利的节点：10→17
人类选择对计算机不利的节点：17→8
计算机选择对自己有利的节点：8→11
人类…… 称这种在最大和最小值之间不断切换的决策过程为极大极小策略

这是一种保守策略，因为计算机不会尝试冒险，它会假设人类每次都做出对自己最不利的选择，从而保证自己最后得到节点价值不至于太低

井字棋算法

棋局

用TicTac类表示棋局，用数组保存棋子

/// <summary>
/// 棋子
/// </summary>
public static class Player
{
    public const int Non = 0;
    public const int Computer = 1;
    public const int Human = -1;
}
public class TicTac
{
    public int num { get; set; }= 0;
    
    /// <summary>
    /// 棋盘布局
    /// </summary>
    public int[,] chess { get; } = new int[,]
    {
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 0}
    };
    public TicTac(){}
 
    public TicTac(TicTac copyFrom)
    {
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                chess[i, j] = copyFrom.chess[i, j];
            }
        }
        num = copyFrom.num;
    }
 
    /// <summary>
    /// 放下棋子
    /// </summary>
    /// <param name="i">位置</param>
    /// <param name="j">位置</param>
    /// <param name="player">棋手</param>
    /// <returns>结果</returns>
    public bool DropDown(int i, int j, int player)
    {
        if (chess[i, j] == Player.Non)
        {
            chess[i, j] = player;
            num++;
            return true;
        }
        return false;
    }
 
    /// <summary>
    /// 拿起棋子
    /// </summary>
    /// <param name="i">位置</param>
    /// <param name="j">位置</param>
    /// <returns>结果</returns>
    public bool PickUp(int i, int j)
    {
        if (chess[i, j] != Player.Non)
        {
            chess[i, j] = Player.Non;
            num--;
            return true;
        }
        return false;
    }
 
    /// <summary>
    /// 返回获胜者
    /// </summary>
    /// <returns>获胜者</returns>
    public int GetWinner()
    {
        //检查胜者只需要判断三格数字之和是否为 ±3
        //检查行
        if (Math.Abs(chess[0, 0] + chess[1, 0] + chess[2, 0]) == 3) return chess[0, 0];
        if (Math.Abs(chess[0, 1] + chess[1, 1] + chess[2, 1]) == 3) return chess[0, 1];
        if (Math.Abs(chess[0, 2] + chess[1, 2] + chess[2, 2]) == 3) return chess[0, 2];
        //检查列
        if (Math.Abs(chess[0, 0] + chess[0, 1] + chess[0, 2]) == 3) return chess[0, 0];
        if (Math.Abs(chess[1, 0] + chess[1, 1] + chess[1, 2]) == 3) return chess[1, 0];
        if (Math.Abs(chess[2, 0] + chess[2, 1] + chess[2, 2]) == 3) return chess[2, 0];
        //检查对角线
        if (Math.Abs(chess[0, 0] + chess[1, 1] + chess[2, 2]) == 3) return chess[0, 0];
        if (Math.Abs(chess[0, 2] + chess[1, 1] + chess[2, 0]) == 3) return chess[0, 2];
        //没有胜者
        return Player.Non;
    }
 
    public bool isEnd()
    {
        if (GetWinner() != Player.Non || num == 9)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

回合

用节点表示一个回合，节点包括棋局，价值，子节点，棋手，落子位置

其中子节点包含了当前回合后所有可能的情况，棋手是当前回合轮到的棋手，落子位置是上一回合的棋手下的最后一步棋位置

/// <summary>
/// 节点类
/// </summary>
public class Node
{
    /// <summary>
    /// 棋局
    /// </summary>
    public TicTac ticTac;
 
    /// <summary>
    /// 价值
    /// </summary>
    private int? value = null;
 
    /// <summary>
    /// 子节点
    /// </summary>
    public List<Node> childNodes = null;
 
    /// <summary>
    /// 棋手
    /// </summary>
    public int player = Player.Non;
 
    public Point lastDrop = null;
    
    private Node(){}
 
    public Node(TicTac ticTac, int player)
    {
        Debug.Assert(player == Player.Computer || player == Player.Human);
        this.ticTac = new TicTac(ticTac);
        this.player = player;
        GetValue();
    }
 
    public Node(Node lastNode, Point drop)
    {
        this.ticTac = new TicTac(lastNode.ticTac);
        this.player = -lastNode.player;
        this.lastDrop = drop;
        ticTac.DropDown(drop.i, drop.j, lastNode.player);
        GetValue();
    }
    
    /// <summary>
    /// 计算当前节点的价值
    /// 如果棋手是电脑，则返回子节点的最大价值
    /// 如何棋手是人类，则返回子节点的最小价值
    /// </summary>
    public int GetValue()
    {
        //已经计算过价值
        if (value != null) return (int) value;
        //胜负已分
        int winner = ticTac.GetWinner();
        if (winner != Player.Non)
        {
            value = winner == Player.Computer ? 10 : -10;
            return (int) value;
        }
        //棋盘已满
        if (ticTac.num == 9)
        {
            value = 0;
            return (int) value;
        }
        //子节点没有初始化，构造子节点
        if (childNodes == null)
        {
            childNodes = new List<Node>();
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (ticTac.chess[i, j] == Player.Non)
                    {
                        Node child = new Node(this, new Point(i, j));
                        childNodes.Add(child);
                    }
                }
            }
        }
        if (player == Player.Computer)
        {
            //当前棋手是电脑，返回最大价值
            int maxValue = Int32.MinValue;
            //从子节点的最小价值里查找最大值
            foreach (Node item in childNodes)
            {
                if (item.GetValue() > maxValue)
                {
                    maxValue = item.GetValue();
                }
            }
            value = maxValue;
        }
        else
        {
            int minValue = Int32.MaxValue;
            foreach (Node item in childNodes)
            {
                if (item.GetValue() < minValue)
                {
                    minValue = item.GetValue();
                }
            }
            value = minValue;
        }
        return (int) value;
    }
 
    public Node SearchChildByPoint(int i, int j)
    {
        foreach (Node item in childNodes)
        {
            if (item.lastDrop.i == i && item.lastDrop.j == j) return item;
        }
        return null;
    }
}

棋局价值

对于一种棋局，如果游戏已经结束，那么根据获胜者来计算价值。如果获胜者为电脑，则价值为10；如果获胜者为人类，则价值为-10；如果平局，则价值为0

如果游戏尚未结束，则在棋局上所有空位置落子，并得到所有可能的子节点。如果当前棋手是人类，则该节点的价值是子节点的价值的最小值，因为人类会做出对计算机最不利的选择。如果当前棋手是电脑，则该节点的价值是子节点的价值的最大值，因为电脑会做出对自己最有利的选择。

下棋代码

public class Point
{
    public int i { get; set; }
    public int j { get; set; }
 
    public Point(int i, int j)
    {
        this.i = i;
        this.j = j;
    }
}
 
class Program
{
    private const string space = " ";
    private static Node node;
    static void Main(string[] args)
    {
        Play();
    }
 
    static void Play()
    {
        Console.Write("先手方为(1:电脑, 0:人类):");
        int start = int.Parse(Console.ReadLine());
        //初始化头节点
        Console.WriteLine("正在初始化...");
        node = new Node(new TicTac(), start == 1 ? Player.Computer : Player.Human);
        Console.WriteLine("初始化结束...");
        Point drop = null;
        while (!node.ticTac.isEnd())
        {
            if (node.player == Player.Computer)
            {
                drop = WaitComputerDrop();
            }
            else
            {
                drop = WaitHumanDrop();
            }
            Drop(drop.i, drop.j);
        }
        Console.WriteLine("游戏结束，比赛结果");
        switch (node.ticTac.GetWinner())
        {
            case Player.Computer:
                Console.WriteLine("电脑获胜!");
                break;
            case Player.Human:
                Console.WriteLine("人类获胜!");
                break;
            case Player.Non:
                Console.WriteLine("平局!");
                break;
        }
    }
 
    static void PrintTicTac()
    {
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                string s;
                switch (node.ticTac.chess[i, j])
                {
                    case Player.Computer:
                        s = "0";
                        break;
                    case Player.Human:
                        s = "1";
                        break;
                    default:
                        s = "x";
                        break;
                }
                Console.Write(s + space);
            }
            Console.WriteLine();
        }
    }
 
    static Point WaitHumanDrop()
    {
        Console.WriteLine("请输入落子位置[1~3,1~3],例如: 2,3");
        string line = Console.ReadLine();
        string[] s = line.Split(",");
        Point p = new Point(int.Parse(s[0]) - 1, int.Parse(s[1]) - 1);
        return p;
    }
 
    static Point WaitComputerDrop()
    {
        Node maxNode = null;
        int MaxValue = Int32.MinValue;
        foreach (Node item in node.childNodes)
        {
            if (item.GetValue() > MaxValue)
            {
                maxNode = item;
                MaxValue = item.GetValue();
            }
        }
        return new Point(maxNode.lastDrop.i, maxNode.lastDrop.j);
    }
 
    static void Drop(int i, int j)
    {
        Console.WriteLine("------------");
        Console.Write("棋手:" + (node.player == Player.Computer ? "电脑" : "人类") + ",");
        node = node.SearchChildByPoint(i, j);
        Console.WriteLine("落子点:(" + (i+1) + "," + (j+1) + ")");
        PrintTicTac();
        Console.WriteLine("------------");
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021年11月13日，如有侵权请联系 cloudcommunity@tencent.com 删除

计算机

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

计算机

登录后参与评论

0 条评论

热度