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

文章目录
  1. 1. 游戏规则
  2. 2. 状态
  3. 3. AgentPlayer相关
    1. 3.1. 奖励
    2. 3.2. 值函数迭代
    3. 3.3. 动作
  4. 4. HumanPlayer相关
  5. 5. Agent训练
  6. 6. Agent对弈
  7. 7. Human v.s. Agent

为了对强化学习的基本概念有一个直观的认识,《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("平局!")
分享到 评论