算法人工智能与机器学习人工智能时代(AI)

强化学习在成语接龙比赛中的应用

2018-11-06  本文已影响52人  LucienCho

题目:

裁判任意给出一个成语,比赛双方在有限的时间里轮流进行成语对答,要求:
1. 成语的首字要与上一个成语的尾字同声同调;
2. 当前比赛出现的所有成语不能再次出现;
3. 必须为四字成语

分析:

看到这个题目,笔者本能的想法是用现成代码跑一跑。但是在git上搜不到能赢得比赛的成语接龙代码,大多数代码只是实现了成语接龙的功能,随机找出符合规则的成语,不足以想赢得比赛,所以打算自己尝试。

重新分析一遍规则吧!若不考虑对手失误,说出重复成语或非四字成语的情况,也不考虑对手的知识量比你大,掌握了一些你词表里没有的成语,只考虑依靠算法获胜的话,则可以理解为这是一道典型的博弈问题。你获胜条件就是在规定时间内,你说出一个成语,你的对手并没有可用的成语,让首字与其同声同调。

思路:

尝试用强化学习的Q-learning解决。

Q-learning核心思想就是在某个状态s下,经过某个动作a,使当前状态更新到下一个状态\tilde{s},记录状态-动作对为Q(s, a),通过定义这个过程中的奖励R(s,a)和观察下一个状态下所有可能动作的Q(\tilde{s}, \tilde{a})的最大值,来更新Q表。经过多个episodes的训练,最终得到整张参数表Q,公式如下:

Q(s,a)\leftarrow Q(s,a)+\alpha [R(s,a)+\gamma{\max}_\tilde{a}Q(\tilde{s},\tilde{a})-Q(s,a) ]

在预测某一个状态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比赛,先手的胜率在九成以上。

上一篇下一篇

猜你喜欢

热点阅读