强化学习实践(一):Tic-Tac-Toe


为了对强化学习的基本概念有一个直观的认识,《Reinforcement Learning: An Introduction》第一章给出了一个简单的例子:Tic-Tac-Toe游戏.

游戏规则

游戏的规则很简单, 两位玩家在 3x3 的棋盘上轮流下棋, 一位打 X, 另一位打 O, 若棋盘的任意一行、任意一列、正反对角线上有三个相同的棋, 则执该棋的玩家获胜. 若棋盘下满仍没有决出胜负, 则平局.

Tic-Tac-Toe示例


我们尝试使用强化学习的方法来训练一个Agent, 使其能够在该游戏上表现出色(即Agent在任何情况下都不会输, 最多平局).

由于没有外部经验, 因此我们需要同时训练两个Agent进行上万轮的对弈来寻找最优策略.

注:下面的代码只给出部分关键实现过程, 完整代码见:tic_tac_toe.py.

版权归 @Shangtong Zhang 等人所有, 仅添加中文注释便于理解.


状态

强化学习一个重要的概念就是——状态(State).

状态是指Agent在一个特定时刻从环境中所感知的信号.

Tic-Tac-Toe游戏中, 状态即为 3*3 棋盘的布局.

定义一个State类用来表示状态.

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
class State:
def __init__(self):
'''状态初始化
棋盘使用 n * n 的数组进行表示
棋盘中的数字: 1代表先手, -1代表后手下, 0代表该位置无棋子

'''

# 该状态的数组表示
self.data = np.zeros((BOARD_ROWS, BOARD_COLS))
# 该状态下的胜利者
self.winner = None
# 该状态的哈希值表示
self.state_hash = None
# 该状态是否为终结状态
self.end = None

def hash(self):
'''计算状态的哈希值表示

Returns
-------
int
状态的哈希值表示
'''
pass

def is_end(self):
'''判断当前状态是否为终结状态.
如果为终结状态, 同时判断胜利者是谁

Returns
-------
bool
当前状态是否为终结状态
'''
pass


def next_state(self, i, j, symbol):
'''计算当前状态的后继状态

Parameters
----------
i : int
下一步动作的行坐标
j : int
下一步动作的列坐标
symbol : int
动作的执行者(1代表先手, -1代表后手)

Returns
-------
State
下一步棋盘的状态
'''
pass

def print_state(self):
'''打印状态信息

'''
pass

根据游戏规则我们知道, 每个格子仅有三种状态, 即先手(1), 后手(-1), 空(0), 那么该游戏的状态数上限仅有 $3^9=19683$ 个.

因此, 我们可以预处理出所有合法的棋盘状态, 供后面强化学习算法使用.

1
all_states = get_all_states()

AgentPlayer相关

定义一个AgentPlayer类用来表示强化学习中和环境进行交互的智能体.

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
class AgentPlayer:

def __init__(self, step_size=0.1, epsilon=0.1):
'''Agent初始化

Parameters
----------
step_size : float, optional
更新步长
epsilon : float, optional
探索概率

'''

# 值函数
self.value = dict()
# 值函数更新步长
self.step_size = step_size
# Agent探索概率
self.epsilon = epsilon
# Agent在一轮游戏中经历的所有状态
self.states = []
# 记录每个状态是否采取贪心策略
self.greedy = []

def reset(self):
'''重置Agent的状态, 开启新一轮游戏

'''
pass

def set_state(self, state):
'''将当前棋盘状态加到Agent的状态列表

Parameters
----------
state : State
当前棋盘的状态

'''
pass

def set_symbol(self, symbol):
'''根据先后手, 初始化Agent的值函数

Parameters
----------
symbol : int
先手还是后手

'''
pass

def backup(self):
'''值函数迭代

'''
pass

def act(self):
'''根据状态采取动作

Returns
-------
list
采取的动作
'''
pass

def save_policy(self):
'''保存策略

'''
pass

def load_policy(self):
'''加载策略

'''
pass

在AgentPlayer类中, 我们重点关注 set_symbol, backup, act 三个函数.

奖励

Agent每次与环境进行交互的时候, 都会得到一个反馈信号称之为奖励(Reward).

Agent的目标是最大化游戏过程中的奖励总和.

Tic-Tac-Toe 游戏中, 由于只有在游戏结束的时候才知道胜负, 故没有给出每一步显式的奖励, 而是直接评估状态的值函数(Value Function).

根据我们的先验知识, 可以对不同的状态设置不同的初始值函数.

对于导致游戏结束的终结状态, 可分为胜利/平局/失败三种情况, 相应的值函数为1.0/0.5/0.0.

而对于非终结状态, 可以简单地将状态的值函数设为0.5, 代表无法判断胜负.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def set_symbol(self, symbol):
'''根据先后手, 初始化Agent的值函数

Parameters
----------
symbol : int
先手还是后手

'''

self.symbol = symbol
for state_hash in all_states.keys():
(state, is_end) = all_states[state_hash]
if is_end: # 终结状态
if state.winner == self.symbol: # 获胜
self.value[state_hash] = 1.0
elif state.winner == 0: # 平局
self.value[state_hash] = 0.5
else: # 失败
self.value[state_hash] = 0
else: # 非终结状态
self.value[state_hash] = 0.5

值函数迭代

使用时序差分学习(Temporal-Difference Learning)方法进行值函数的更新:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def backup(self):
'''值函数迭代

'''

# 获取状态的哈希值表示
self.states = [state.hash() for state in self.states]

# 逆序遍历所有的状态, 并进行值函数的更新
for i in reversed(range(len(self.states) - 1)):
state = self.states[i]
# TD误差 = V(s_{t + 1}) - V(s_{t})
td_error = self.greedy[i] * (self.value[self.states[i + 1]] - self.value[state])
# TD-Learning(时序差分学习)更新公式
self.value[state] += self.step_size * td_error

动作

采用 $\epsilon$-greedy 的贪心策略选择动作, 即有 $1 - \epsilon$ 的概率选择后继状态值函数最大的动作, 有 $\epsilon$ 概率进行随机选择动作.

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
def act(self):
'''根据状态采取动作

Returns
-------
list
采取的动作
'''

# 获取当前状态
state = self.states[-1]
# 下一步所有可能的状态
next_states = []
# 下一步所有可能的位置
next_positions = []
for i in range(BOARD_ROWS):
for j in range(BOARD_COLS):
# 当前棋盘位置上无棋子
if state.data[i, j] == 0:
# 可行的位置
next_positions.append([i, j])
# 可行的状态
next_states.append(state.next_state(i, j, self.symbol).hash())

# 有epsilon概率采取随机动作
if np.random.rand() < self.epsilon:
action = next_positions[np.random.randint(len(next_positions))]
action.append(self.symbol)
self.greedy[-1] = False
return action

values = []
# 遍历下一步所有可能的状态和位置
for state_hash, pos in zip(next_states, next_positions):
# 获取对应状态的值函数
values.append((self.value[state_hash], pos))
# 如果有多个状态的值函数相同,且都是最高的,shuffle则起到在这些状态中随机选择的作用
np.random.shuffle(values)
# 按值函数从大到小排序
values.sort(key=lambda x: x[0], reverse=True)
# 选取最优动作
action = values[0][1]
action.append(self.symbol)
return action

HumanPlayer相关

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
class HumanPlayer:
def __init__(self, **kwargs):
self.symbol = None
self.keys = ['q', 'w', 'e', 'a', 's', 'd', 'z', 'x', 'c']
self.state = None
return

def reset(self):
return

def set_state(self, state):
self.state = state

def set_symbol(self, symbol):
self.symbol = symbol
return

def backup(self, _):
return

def act(self):
self.state.print_state()
key = input("Input your position:")
data = self.keys.index(key)
i = data // int(BOARD_COLS)
j = data % BOARD_COLS
return [i, j, self.symbol]

Agent训练

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
def train(epochs, print_every_n=500):
'''对Agent进行训练

Parameters
----------
epochs : int
训练轮数
print_every_n : int, optional
每多少轮输出训练信息

'''

# 定义两个Agent
player1 = AgentPlayer(epsilon=0.01)
player2 = AgentPlayer(epsilon=0.01)
# 定义判决器
game = Game(player1, player2)
# 先手赢的次数
player1_win = 0.0
# 后手赢的次数
player2_win = 0.0
for i in range(1, epochs + 1):
# 新的一轮游戏
game.reset()
winner = game.play(print_state=False)
if winner == 1:
player1_win += 1
if winner == -1:
player2_win += 1
# 打印各自的胜率
if i % print_every_n == 0:
print('Epoch %d, player 1 winrate: %.02f, player 2 winrate: %.02f' % (i, player1_win / i, player2_win / i))
# 在每轮游戏结束后,对Agent进行学习
player1.backup()
player2.backup()
# 保存训练好的策略
player1.save_policy()
player2.save_policy()

Agent对弈

经过充分的训练后, 两个Agent对弈的胜率应该都为0%. 即任何局面都只能打成平手, 没有一方可以胜过另一方.

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
def compete(turns):
'''将训练好的两个Agent进行对弈

Parameters
----------
turns : int
对弈轮数

'''

# 对弈的时候不进行动作的探索, 故epsilon设为0.
player1 = AgentPlayer(epsilon=0)
player2 = AgentPlayer(epsilon=0)
game = Game(player1, player2)
player1.load_policy()
player2.load_policy()
player1_win = 0.0
player2_win = 0.0
for _ in range(0, turns):
game.reset()
winner = game.play()
if winner == 1:
player1_win += 1
if winner == -1:
player2_win += 1
print('%d turns, player 1 win %.02f, player 2 win %.02f' % (turns, player1_win / turns, player2_win / turns))

Human v.s. Agent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def play():
'''人类玩家和Agent进行对弈

'''

while True:
player1 = HumanPlayer()
player2 = AgentPlayer(epsilon=0)
game = Game(player1, player2)
player2.load_policy()
winner = game.play()
if winner == player2.symbol:
print("失败!")
elif winner == player1.symbol:
print("胜利!")
else:
print("平局!")