博弈论
博弈论是现代数学的一个分支，是用于研究竞争现象的数学工具。博弈策略是一套考虑到所有可能的情况而做出的行动。博弈论在人工智能方面有极大的价值。
零和博弈
在零和博弈，双方的总利益为0，其中一方为了自己利益最大化，必须损失另一方的利益。正如棋局中，一方赢了，则另一方必定输了，则利益之和为 1 (-1)=0
这就要求，任意一方都要使自己利益最大化，同时使对方利益最小化。因此在决策时，不能只考虑自己的最大利益，还需要考虑对方做出的对自己最不利的选择
极大极小策略
极大极小方法是分析零和博弈问题时的一种策略，在对局制游戏中，每个参与者都会做出对自己最有利，同时也是对对方最不利的选择。
在下棋时，每一个棋盘布局都可以表示为一个节点，相邻的节点形成多叉树。每种布局都会对一方有利而对另一方不利，称节点的有利程度为价值。
假设人类与计算机进行对决，并假设人类绝对聪明，那么在人类的回合，他会选择对计算机最不利的棋局，也就是价值最低的节点。而计算机则会选择对自己价值最高的节点。
假设各节点的价值如下
决策过程如下：
- 计算机选择对自己有利的节点：10→17
- 人类选择对计算机不利的节点：17→8
- 计算机选择对自己有利的节点：8→11
- 人类…… 称这种在最大和最小值之间不断切换的决策过程为极大极小策略
这是一种保守策略，因为计算机不会尝试冒险，它会假设人类每次都做出对自己最不利的选择，从而保证自己最后得到节点价值不至于太低
井字棋算法
棋局
用TicTac类表示棋局，用数组保存棋子
代码语言：javascript复制/// <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;
}
}
}回合
用节点表示一个回合，节点包括棋局，价值，子节点，棋手，落子位置
其中子节点包含了当前回合后所有可能的情况，棋手是当前回合轮到的棋手，落子位置是上一回合的棋手下的最后一步棋位置
代码语言：javascript复制/// <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
如果游戏尚未结束，则在棋局上所有空位置落子，并得到所有可能的子节点。如果当前棋手是人类，则该节点的价值是子节点的价值的最小值，因为人类会做出对计算机最不利的选择。如果当前棋手是电脑，则该节点的价值是子节点的价值的最大值，因为电脑会做出对自己最有利的选择。
下棋代码
代码语言：javascript复制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("------------");
}
}
