抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

博弈论

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

零和博弈

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

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

极大极小策略

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

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

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

假设各节点的价值如下

DearXuan

决策过程如下:

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

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

井字棋算法

棋局

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

TicTac.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/// <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;
}
}
}

回合

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

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

Node.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/// <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

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

下棋代码

Program.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
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("------------");
}
}

DearXuan

评论