如何正确的猜拳:反事实遗憾最小化算法

反事实遗憾算法是一种自我演绎的AI模型。本质是两个AI代理人互相对抗,从头开始学习游戏。事实上在多数情况下,这是一个代理人进行自我对抗,所以它的学习速度会翻倍(重点注意,尽管它本身是和自己玩,但实际上它并没有足够聪明到站在对手的位置理解它上一步的行为。)

与许多最近在AI研究中的重大突破(如AlphaGo)不同,CFR不依赖于神经网络计算概率或特定举措的价值。取代通过自我对局数百万甚至上亿的的方法,它从总结每个操作对特定位置加以考虑的遗憾总量着手。

这个算法令人兴奋的是,随着游戏的进行它将越来越接近游戏的最佳策略,即纳什均衡。它已经在许多游戏和领域证明了自己,最有趣的是扑克特别是无限德州扑克。这是我们目前拥有的最好的扑克AI算法。

遗憾匹配

遗憾匹配(RM)是一种寻找最大限度地减少对游戏每个步骤决策遗憾的算法。顾名思义,它从过去的行为学习告知未来决策,通过赞同它后悔以前没有采取的行为。

在这个模式中,既有积极的遗憾和消极的遗憾。当消极遗憾被你定义成你期望的情况:在特别得情况下采取特别行动的遗憾。这意味着如果在这种情况下没有选择这个行为,代理人会做得更好。

积极的遗憾也定义成你期望的: 这是一种代理人可以跟踪导致积极结果的行为的机制。(我个人认为应该被称为别的东西,但这无所谓。)

在代理人在自我对抗的每场游戏后,最新游戏中遇到的负面和积极的遗憾都被添加到所有其他盘游戏中的总结里,并且计算出新的策略。

简而言之,通过概率,它偏好采取过去产生的积极成果的行动并避免采取导致负面结果的行为。

与其他的学习机制一样人类也有遗憾学习机制—我们尝试做一些事情,如果失败并引起消极的情绪反应,我们会记下这种遗憾,并让自己再次尝试。以“Scissors-Paper-Rock(SPR)”游戏为例(就是猜拳),如果我们在对手出布的时候出了石头,我们就后悔没有出剪子。

这种模式在零和游戏中向靠拢纳什均衡,对于那些不熟悉博弈论的人来说,游戏中每个代理人的赢或输完全可以由其他代理人的赢或输来平衡。例如,剪刀,石头,布,是零和游戏。当你打败你的对手时,你赢了+1,他们输了-1,和为零。

猜拳

在这里,我们将猜拳(SPR)标准化作为一种存在纳什均衡的标准的零和的双人游戏。虽然这句话包含了很多信息,但我们将其分解成组件。首先,SPR可以定义为元组< N,A,u >,正式称为规格化形式:

  • N = 1,… .n代表n个玩家的有限集合。在猜拳中,一般是N={1,2}
  • S是一个有限动作的组。这里每个玩家都有相同的动作选择,所以S ={ S,P,R }

是所有玩家同时行动的所有可能组合。即,A = {(R,R),……,(S,P)},并且每个组合被称为动作剖析。

U是一个函数映射,将每个玩家的每个行动的数据储存成一个效果或者回报的矢量。

  • U是每个动作简档映射到向量为每个玩家公用事业/回报的功能。例如,(R,P)=(-1,1)意味着如果玩家1出了石头给玩家2的布(即输了),玩家1的奖励为-1。因此,我们可以为玩家1定义一个效用矩阵如下:

此外,我们也可以定义策略σᵢ(s)作为玩家ᵢ选择动作s∈S的概率。当玩家使用遗憾匹配来更新自己的战略,σᵢ(s)预支成正比的累积遗憾。请注意,每个效用向量的和都为0,因此我们将其称为零和博弈。在任何双人零和博弈中,当两个玩家都坚持遗憾匹配时,他们的平均策略收敛于纳什均衡,即两者都能够最大化自己预期的效用:

但现在已经有足够的数学抽象了。我们言归正传,在实践中了解一些关于遗憾匹配实际工作的具体原理。在本教程中,我们将编写一个实现RM算法完猜拳游戏的简单程序。我们假设读者有Python编程语言的基础知识,最好是接触过Numpy。

我们首先导入本程序所需的模块。

from __future__import division
from randomimport random
import numpy as np
import pandas as pd

然后我们定义猜拳游戏的基本参数。“utilities”是上述效用函数,用于确定行动剖析的实用值。按惯例,我们定义行的玩家是玩家1,列的玩家是玩家2.因此,为了查询给定动作剖析(s1 = Rock,s2 = Paper)的玩家1的实用值,我们调用utilities.loc['ROCK', 'PAPER']

class RPS:
    actions= ['ROCK','PAPER','SCISSORS']
    n_actions= 3
    utilities= pd.DataFrame([
        # ROCK  PAPER  SCISSORS
        [0,   -1,   1],# ROCK
        [1,    0,  -1],# PAPER
        [-1,    1,   0] # SCISSORS
    ], columns=actions, index=actions)

每个玩家负责维护自己的策略和遗憾的统计。目前,我们只提出一个类框架,但稍后会回到实现细节。有几个变量需要解释:

  • 策略:对应于σ(s),策略向量,表示当前采取行动的概率。
  • 策略总计:

是从游戏开始到现在策略向量的总和。

  • Regret_sum:是每次迭代的遗憾矢量的总和。
  • avg_strategy:归一化策略总和。
class Player:
    def __init__(self, name):
        self.strategy,self.avg_strategy,\
        self.strategy_sum,self.regret_sum= np.zeros((4, RPS.n_actions))
        self.name= name

    def __repr__(self):
        return self.name

    def update_strategy(self):
        """
        set the preference (strategy) of choosing an action to be proportional to positive regrets
        e.g, a strategy that prefers PAPER can be [0.2, 0.6, 0.2]
        """
        self.strategy= np.copy(self.regret_sum)
        self.strategy[self.strategy <0]= 0  # reset negative regrets to zero

        summation= sum(self.strategy)
        if summation >0:
            # normalise
            self.strategy/= summation
        else:
            # uniform distribution to reduce exploitability
            self.strategy= np.repeat(1 / RPS.n_actions, RPS.n_actions)

        self.strategy_sum+= self.strategy

    def regret(self, my_action, opp_action):
        """
        we here define the regret of not having chosen an action as the difference between the utility of that action
        and the utility of the action we actually chose, with respect to the fixed choices of the other player.
        compute the regret and add it to regret sum.
        """
        result= RPS.utilities.loc[my_action, opp_action]
        facts= RPS.utilities.loc[:, opp_action].values
        regret= facts- result
        self.regret_sum+= regret

    def action(self, use_avg=False):
        """
        select an action according to strategy probabilities
        """
        strategy= self.avg_strategyif use_avgelse self.strategy
        return np.random.choice(RPS.actions, p=strategy)

    def learn_avg_strategy(self):
        # averaged strategy converges to Nash Equilibrium
        summation= sum(self.strategy_sum)
        if summation >0:
            self.avg_strategy= self.strategy_sum/ summation
        else:
            self.avg_strategy= np.repeat(1/RPS.n_actions, RPS.n_actions)

游戏/环境的定义 我们有两名玩家Alasdair和Calum,除非明确指定max_game,否则玩1000局。“play_regret_matching”函数充分描述了原始遗憾匹配的过程:

1.从累积遗憾计算遗憾匹配策略剖析。

2.根据策略剖析选择每个玩家操作情况

3.计算玩家遗憾并添加到玩家累积的遗憾中。

class Game:
    def __init__(self, max_game=10000):
        self.p1= Player('Alasdair')
        self.p2= Player('Calum')
        self.max_game= max_game

    def winner(self, a1, a2):
        result= RPS.utilities.loc[a1, a2]
        if result== 1:    return self.p1
        elif result== -1: return self.p2
        else:              return 'Draw'

    def play(self, avg_regret_matching=False):
        def play_regret_matching():
            for iin xrange(0,self.max_game):
                self.p1.update_strategy()
                self.p2.update_strategy()
                a1= self.p1.action()
                a2= self.p2.action()
                self.p1.regret(a1, a2)
                self.p2.regret(a2, a1)

                winner= self.winner(a1, a2)
                num_wins[winner]+= 1

        def play_avg_regret_matching():
            for iin xrange(0,self.max_game):
                a1= self.p1.action(use_avg=True)
                a2= self.p2.action(use_avg=True)
                winner= self.winner(a1, a2)
                num_wins[winner]+= 1

        num_wins= {
            self.p1:0,
            self.p2:0,
            'Draw':0
        }

        play_regret_matching()if not avg_regret_matchingelse play_avg_regret_matching()
        print num_wins

    def conclude(self):
        """
        let two players conclude the average strategy from the previous strategy stats
        """
        self.p1.learn_avg_strategy()
        self.p2.learn_avg_strategy()

现在让我们实现未完成的玩家类,从“regret”和“action”函数开始。考虑到行动剖析(Rock,Paper),不采取行动相应的遗憾基本上是行动与对手行为之间的效用差异,即(Rock = -1,Scissor = 1,Paper = 0),剪刀被明确的舍弃了。

class Player:
    # ....
    def regret(self, my_action, opp_action):
        """
        We here define the regret of not having chosen an action as the difference between the utility of that action and the utility of the action we actually chose, with respect to the fixed choices of the other player. Compute the regret and add it to regret sum.
        """
        result= RPS.utilities.loc[my_action, opp_action]
        facts= RPS.utilities.loc[:, opp_action].values
        regret= facts- result
        self.regret_sum+= regret

    def action(self, use_avg=False):
        """
        select an action according to strategy probabilities
        """
        strategy= self.avg_strategyif use_avgelse self.strategy
        return np.random.choice(RPS.actions, p=strategy) # p refers to 'probability'

“update_strategy”函数与遗憾匹配算法的核心思想一致:“选择与过去没有选择的积极后悔成正比的行为”,因此策略实际上是积极的遗憾归一化。然而,请注意,当没有积极的遗憾(也就是,说上一场比赛是完美的)时,我们采取随机策略,尽可能地减少暴露采取行动的偏见,因为这种偏见可以被对手利用。

class Player:
    # ....
    def update_strategy(self):
        """
        Set the preference (strategy) of choosing an action to be proportional to positive regrets. e.g, a strategy that prefers PAPER can be [0.2, 0.6, 0.2]
        """
        self.strategy= np.copy(self.regret_sum)
        self.strategy[self.strategy <0]= 0  # reset negative regrets to zero

        summation= sum(self.strategy)
        if summation >0:
            # normalise
            self.strategy/= summation
        else:
            # uniform distribution to reduce exploitability
            self.strategy= np.repeat(1 / RPS.n_actions, RPS.n_actions)

        self.strategy_sum+= self.strategy

    def learn_avg_strategy(self):
        # averaged strategy converges to Nash Equilibrium
        summation= sum(self.strategy_sum)
        if summation >0:
            self.avg_strategy= self.strategy_sum/ summation
        else:
            self.avg_strategy= np.repeat(1/RPS.n_actions, RPS.n_actions)

现在我们可以开始运行了!尝试多次运行后你可能会发现:单纯的遗憾匹配并不总是产生均匀分布的赢家数,反而平均后悔遗憾匹配可以产生。如果你在单纯的遗憾匹配的在每个中间迭代打印“num_wins”,不甚至看到优胜者定期在p1和p2之间产生。这是由于简单遗憾匹配的可利用性。想象你知道对手喜欢出剪刀,你可能会在接下来的几个回合中偏向出石头,并且需要一段时间后悔自己的偏见。

然而,平均的结果是在SPR中随机选择一个完美的策略。这是对对手采取的任何固定策略的最佳反应,在每个动作选择中都没有留下可利用的信息。

if __name__== '__main__':
    game= Game()
    print '==== Use simple regret-matching strategy === '
    game.play()
    print '==== Use averaged regret-matching strategy === '
    game.conclude()
    game.play(avg_regret_matching=True)

完整的源代码可从以下网址获得:

https://gist.github.com/namoshizun/7a3b820b013f8e367e84c70b45af7c34

原文发布于微信公众号 - ATYUN订阅号(atyun_com)

原文发表时间:2017-09-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

机器之心「GMIS 2017」嘉宾揭秘:LSTM之父Jürgen Schmidhuber

2017 全球机器智能峰会(GMIS 2017),让我们近距离接触「LSTM 之父」Jürgen Schmidhuber。 2017 全球机器智能峰会(GMIS...

2768
来自专栏黄成甲

怎样成为解决问题的高手(连载四)

在上一篇我们讲了系统思维——透过框架来理解世界的思维方式。这一篇我们继续学习构建框架:自下而上提炼框架。在介绍自下而上提炼框架前,我先补充一些基础、常用的思考工...

752
来自专栏Java学习网

一个32岁入门的70后程序员给我的启示

一个32岁入门的70后程序员给我的启示 大家好,我是帅气小伙,今天为大家带来一个非常励志,让我反思的故事。今天为大家讲的是我父亲是如何用行动教会我成为程序员的。...

2709
来自专栏飞总聊IT

人工“智能”与图灵机

人工“智能”与图灵机 ? 今天白天有两件事情,第一是我看到了一篇知乎神文,讨论比图灵机更强悍的计算模型。第二是朋友圈讨论群都在刷亚马逊机器学习年会和微软bui...

33213
来自专栏人工智能头条

ELM:为深度学习提供理论支持, 将勾连生物学习

1213
来自专栏大数据

纳米白与Pandas

温井很久没有来更新,感谢小伙伴幕黑君积极推送文章,希望大家喜欢。 温井消失的理由,说来很不好意思。 一是后来意识到上一篇中提到的后台留言的粉丝,其实是给幕黑君留...

16310
来自专栏大数据文摘

脑洞|手绘从零维到十维空间

21310
来自专栏大数据文摘

[独家]MIT课程笔记:数据可视化会撒谎

2458
来自专栏量子位

AI研发新药真有那么神?可能哈佛、斯坦福和阿斯利康实验室都在吹牛

安妮 李林 编译自 Medium 量子位 出品 | 公众号 QbitAI ? 近年来,向往着用AI研发新药的美好愿景,巨头纷纷投下了重注。 制药巨头赛诺菲和AI...

3377
来自专栏java思维导图

一个32岁入门的70后程序员给我的启示

大家好,今天为大家带来一个非常励志,让我反思的故事。今天为大家讲的是我父亲是如何用行动教会我成为程序员的。 岁月的锤炼   圆口接口的键盘,2003 年的 ? ...

2986

扫描关注云+社区