题目:
裁判任意给出一个成语，比赛双方在有限的时间里轮流进行成语对答，要求:
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比赛，先手的胜率在九成以上。
