0. 引子
OK。这回我们换了个模型，从单纯的与或树搜索法换到了强化学习的方法。我之前从来没有研究过强化学习的具体模型，这次正好学习一下。强化学习模拟的是智能体与环境中的交互，通过设立奖励/惩罚函数欲求使结果最优化。Q-Learning是强化学习中，相对简单的一个方法。
Q-Learning的具体信息，请参考强化学习入门笔记——Q-learning从理论到实践。
1. 奖励函数的设定
奖励函数和上一章提到的利益函数不一样，前者考虑操作带来的优劣，后者考虑整体地图的优劣。
人也是智能体，可以根据我们自己玩2048的体验，来设定奖励函数：
- 输掉游戏，非常不爽，给-400点奖励。
- 合并两个单元格，比较开心，给$log_2(V)$点奖励，其中，$V$是合并前单元格的值。没有合并单元格，有点不爽，给-1点奖励。
- 赢得游戏，非常开心，给400点奖励。
2. 具体的算法
我根据这张图实现Q-Learning算法：
其中，$\epsilon$为探索系数，表示随机采取动作的概率；$1-\epsilon$就是采取贪心策略的概率，贪心策略就是指，从已经探索出来的所有$Q(s,a)$中，选取奖励最大的动作；$\alpha$是一个参数；$s$代表状态，也就是当前地图；$a$是采取的动作；所谓$\hat{Q}(s,a)$就表示在$s$状态下，采取$a$动作的奖励值；$\gamma$也是一个超参数。
设置超参数
所谓超参数(Hyperparameter)，就是一些不随训练改变的参数，比如总的训练次数，训练batch大小，都属于超参数。
我的超参数设置如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| random.seed(42)
map_size = 4
epsilon = 0.42
update_step = 0.42
memory_size = 5000000
q_pointer = 0
operations = ['LEFT', 'RIGHT', 'UP', 'DOWN', 'GREEDY']
episode = 200
reward_discount = 0.9
...
class Strategy(object):
def __init__(self, state, movement=None, reward=0):
self.state = state
self.movement = movement
self.reward = reward
q_table: list[Strategy] = []
|
其中：
map_size，地图的长和宽的值。epsilon，采取随机动作的概率，1-epsilon就表示采取贪心策略的概率。update_step，更新步长。memory_size，最多能存放多少个训练出来的$Q(s,a)$。q_pointer，指向q_table的指针，代表当前最新更新的是哪一个元素。后者是存放$Q(s,a)$的列表。episode，一共训练多少次。reward_discount，即上面提到的$\gamma$，一个超参数。Strategy，记录$Q(s,a)$的类。
学习
按照上面的伪代码，容易实现出学习的函数框架:
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
| def Learn():
global episode, update_step, reward_discount
for i in range(episode):
original_map = [[0 for i in range(map_size)] for j in range(map_size)]
game.GenerateTwo(original_map)
game.GenerateTwo(original_map)
node = Strategy(original_map, 0)
state = node.state.copy()
reward = 0
curr_Q = 0
print("Starting episode: " + str(i))
while not game.GameFailed(state) and not game.GameSuccess(state):
operation = GetOperation()
if operation == 'GREEDY':
operation = Greedy(state)
state, reward = GetStatusAndReward(state, operation)
game.GenerateTwo(state)
curr_Q = curr_Q + update_step * (reward + reward_discount * GetMaxQByStrategy(Strategy(state, operation)) - curr_Q)
UpdateQTable(Strategy(state, operation, reward))
game.ShowMap(state)
print("Current Reward: " + str(reward))
|
获取行动方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| def GetOperation():
rand_num = random.uniform(0, 100)
if rand_num < epsilon * 100:
rand_num = random.randint(0, 3)
return operations[rand_num]
else :
return 'GREEDY'
def Greedy(state):
temp_operation = 'LEFT'
temp_max_reward = -sys.maxsize
for i in range(len(q_table)):
if q_table[i].state == state:
if q_table[i].reward > temp_max_reward:
temp_max_reward = q_table[i].reward
temp_operation = q_table[i].movement
else:
continue
return temp_operation
|
奖励的计算
可以通过分数的增量来模拟合并单元格带来的奖励：获取分数的增量，之后取以2为底的对数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| def GetStatusAndReward(original_map, operation):
map = original_map.copy()
bonus = 0
delta = 0
if operation == 'LEFT':
map, neo_bonus = game.MoveLeft(map, bonus)
delta = neo_bonus - bonus
elif operation == 'RIGHT':
map, neo_bonus = game.MoveRight(map, bonus)
delta = neo_bonus - bonus
elif operation == 'UP':
map, neo_bonus = game.MoveUp(map, bonus)
delta = neo_bonus - bonus
elif operation == 'DOWN':
map, neo_bonus = game.MoveDown(map, bonus)
delta = neo_bonus - bonus
if game.GameFailed(map):
return map, 400
if game.GameSuccess(map):
return map, 400
if delta == 0:
return map, 1
else:
return map, math.log2(delta)
|
3. 测试
测试的结果用如下判据表示：将每次最终态的最大值块值加起来，除以总的训练次数。
最终训练结果也蛮难看：
- 200次-86.8
- 400次-88.4
- 2000次-94.544
发现结果都差不多，2048-RLRepo的统计结果如下：
Q-Learning
- 1 minute of training
- Average Max Tile: 115.2
- Reached 2048: 0
- 1 hour of training
- Average Max Tile: 137.8
- Reached 2048: 0
- 1 day of training
- Insufficient storage and computing power
