博弈论
博弈论是现代数学的一个分支,是用于研究竞争现象的数学工具.博弈策略是一套考虑到所有可能的情况而做出的行动.博弈论在人工智能方面有极大的价值.
零和博弈
在零和博弈,双方的总利益为0,其中一方为了自己利益最大化,必须损失另一方的利益.正如棋局中,一方赢了,则另一方必定输了,则利益之和为 1+(-1)=0
这就要求,任意一方都要使自己利益最大化,同时使对方利益最小化.因此在决策时,不能只考虑自己的最大利益,还需要考虑对方做出的对自己最不利的选择
极大极小策略
极大极小方法是分析零和博弈问题时的一种策略,在对局制游戏中,每个参与者都会做出对自己最有利,同时也是对对方最不利的选择.
在下棋时,每一个棋盘布局都可以表示为一个节点,相邻的节点形成多叉树.每种布局都会对一方有利而对另一方不利,称节点的有利程度为价值.
假设人类与计算机进行对决,并假设人类绝对聪明,那么在人类的回合,他会选择对计算机最不利的棋局,也就是价值最低的节点.而计算机则会选择对自己价值最高的节点.
假设各节点的价值如下
决策过程如下：
- 计算机选择对自己有利的节点：10→17
- 人类选择对计算机不利的节点：17→8
- 计算机选择对自己有利的节点：8→11
- 人类……
称这种在最大和最小值之间不断切换的决策过程为极大极小策略
这是一种保守策略,因为计算机不会尝试冒险,它会假设人类每次都做出对自己最不利的选择,从而保证自己最后得到节点价值不至于太低
井字棋算法
棋局
用TicTac类表示棋局,用数组保存棋子
TicTac.cs1
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
|
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;
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;
}
public bool DropDown(int i, int j, int player)
{
if (chess[i, j] == Player.Non)
{
chess[i, j] = player;
num++;
return true;
}
return false;
}
public bool PickUp(int i, int j)
{
if (chess[i, j] != Player.Non)
{
chess[i, j] = Player.Non;
num--;
return true;
}
return false;
}
public int GetWinner()
{
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.cs1
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
|
public class Node
{
public TicTac ticTac;
private int? value = null;
public List<Node> childNodes = null;
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();
}
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.cs1
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("------------");
}
}
|
