强化学习在成语接龙比赛中的应用
题目:
裁判任意给出一个成语,比赛双方在有限的时间里轮流进行成语对答,要求:
1. 成语的首字要与上一个成语的尾字同声同调;
2. 当前比赛出现的所有成语不能再次出现;
3. 必须为四字成语
分析:
看到这个题目,笔者本能的想法是用现成代码跑一跑。但是在git上搜不到能赢得比赛的成语接龙代码,大多数代码只是实现了成语接龙的功能,随机找出符合规则的成语,不足以想赢得比赛,所以打算自己尝试。
重新分析一遍规则吧!若不考虑对手失误,说出重复成语或非四字成语的情况,也不考虑对手的知识量比你大,掌握了一些你词表里没有的成语,只考虑依靠算法获胜的话,则可以理解为这是一道典型的博弈问题。你获胜条件就是在规定时间内,你说出一个成语,你的对手并没有可用的成语,让首字与其同声同调。
思路:
尝试用强化学习的Q-learning解决。
Q-learning核心思想就是在某个状态下,经过某个动作,使当前状态更新到下一个状态,记录状态-动作对为,通过定义这个过程中的奖励和观察下一个状态下所有可能动作的的最大值,来更新表。经过多个episodes的训练,最终得到整张参数表,公式如下:
在预测某一个状态s_k下应采取的动作时,只要求出Q(s_k)中所有可能actions的argmax即可。
成语接龙比赛的关键点在于reward表的定义和变化。一开始reward表中奖励较高(reward=50)的是那些尾字拼音独一无二不可接的成语。但在比赛过程中,若某个首字拼音唯一的成语说完后,可能会有一些成语变成尾字拼音不可接,那么这些成语的reward将瞬间变大(从-1变为50)。因此在说出每一轮成语时,有一定的概率要对reward表中的某些值进行更新。
做法:
第一部分:设置参数(学习率lr、衰减值gamma)、第一轮比赛开始前重置Q表、每次比赛前重置成语与拼音映射关系和R矩阵。idioms_dict的key是每一个成语,value是(首字拼音, 尾字拼音);piny2id和id2piny是拼音索引;piny2idiom是拼音与成语的映射关系。
class Clever(object):
def __init__(self, name, is_train=True):
self.name = name
self.idioms_dict = {}
self.piny2id = {}
self.id2piny = {}
self.piny2idiom = {}
self.lose = '{} lose!'.format(name)
self.gamma = 0.9
self.lr = 0.5
self.r_matrix = None
self.reset()
self.q_table = self.build_q_table()
if not is_train:
model = np.load(MODEL)
self.q_table = np.array(model['q_table'])
def build_q_table(self):
""" 用0初始化Q表"""
vocab_size = len(self.piny2id)
return np.array([[0] * vocab_size] * vocab_size)
def build_r_matrix(self):
"""一轮比赛未开始时,需要重置R矩阵"""
vocab_size = len(self.piny2id)
matrix = np.array([[-1] * vocab_size] * vocab_size)
for idiom, (f_piny, l_piny) in self.idioms_dict.items():
score = 0
if l_piny not in self.piny2idiom:
score = 50
matrix[self.piny2id[f_piny]][self.piny2id[l_piny]] = score
return matrix
def reset(self):
"""重置比赛,建立成语到拼音的映射关系,重置R矩阵"""
vocab = load_vocab(VOCAB)
for n, (piny, _) in enumerate(vocab):
self.piny2id[piny] = n
self.id2piny[n] = piny
data = load_data(DATA)
for idiom, f_piny, l_piny in data:
self.idioms_dict[idiom] = (f_piny, l_piny)
if f_piny in self.piny2idiom:
self.piny2idiom[f_piny] += [idiom]
else:
self.piny2idiom[f_piny] = [idiom]
self.r_matrix = self.build_r_matrix()
第二部分:裁判以任意成语开始比赛,并且在每一次接龙,出现的成语不能重复出现(包括对手说的和裁判说的)。
def start(self, idiom):
""" 裁判给出第一个成语"""
f_piny, l_piny = get_pinyin(idiom, None)
self.pop(f_piny, idiom)
def pop(self, f_piny, idiom):
"""在映射关系中删除成语和相应拼音"""
if f_piny in self.piny2idiom:
self.piny2idiom[f_piny] = [i for i in self.piny2idiom[f_piny] if i != idiom]
if idiom in self.idioms_dict:
self.idioms_dict.pop(idiom)
第三部分:训练部分随机对出符合条件的成语,更新Q表,最终保存模型。
def random_play(self, idiom):
"""随机对出符合条件的成语"""
f_piny, l_piny = get_pinyin(idiom, None)
self.pop(f_piny, idiom)
idioms = self.piny2idiom.get(l_piny, None)
if not idioms:
return
picked = random.choice(idioms)
return picked
def play(self, idiom):
"""Q learning训练部分"""
picked = self.random_play(idiom)
if picked is None:
return
f_piny, l_piny = get_pinyin(picked, None)
for idiom, (f_piny, l_piny) in self.idioms_dict.items():
score = 0
if l_piny not in self.piny2idiom:
score = 50
self.r_matrix[self.piny2id[f_piny]][self.piny2id[l_piny]] = score
s = self.piny2id[f_piny]
a = self.piny2id[l_piny]
new_q = 100
if l_piny in self.piny2idiom:
new_idioms = self.piny2idiom[l_piny]
new_q = []
for new_idiom in new_idioms:
new_f_piny, new_l_piny = get_pinyin(new_idiom)
new_q.append(self.q_table[self.piny2id[new_f_piny], self.piny2id[new_l_piny]])
self.q_table[s, a] = self.q_table[s, a] + self.lr * (
self.r_matrix[s, a] + self.gamma * np.max(new_q) - self.q_table[s, a])
return picked
def save(self):
"""存储Q表"""
np.savez(MODEL, q_table=self.q_table)
第四部分:推理部分从Q表中找出每一步得分最高的成语作为输出。
def real_play(self, idiom):
"""Q learning推理部分"""
f_piny, l_piny = get_pinyin(idiom, None)
self.pop(f_piny, idiom)
idioms = self.piny2idiom.get(l_piny, None)
if not idioms:
return
q_max = -1
selected = None
for idiom in idioms:
f_piny, l_piny = get_pinyin(idiom, None)
s = self.piny2id[f_piny]
a = self.piny2id[l_piny]
q = self.q_table[s, a]
if q > q_max:
q_max = q
selected = idiom
return selected
实际效果
在训练阶段,获胜概率在五成左右,因为没用到Q表。预测阶段的对手有随机选手rand和另一个强化选手rl。在训练1000场比赛后,与rand比赛的胜率接近100%,而与和自己一样的rl比赛,先手的胜率在九成以上。