精华内容
下载资源
问答
  • 博弈

    2013-07-12 12:14:23
    博弈
    博弈
            说道博弈,首先必须说起nim游戏,nim游戏指的就是有3堆石子,现在alice和bob两个人轮流在这三堆石子中任意选择一堆石块扔掉至少一个石块,如果一个人不能进行操作那么就是定义为输。整个问题可以抽象成在一个DAG图上面,游戏中的每一个状态抽象成图中的一个点,进行一次操作相当于在图中沿着有向边进行一次移动,不能移动的一方就算是输。
            那么对于任意一个组合博弈游戏有什么解法呢,我们假设在博弈中的双方都是决定聪明的,所以如果存在必胜策略的话,那么alice一定会去选择这个必胜策略,如果一个人没有必胜策略,那么肯定就是必败态,所以我们这里对于每个状态分成两种状态,必败和必胜,当然这都是对于后手来说的,首先可以确定的就是没有出度的顶点就是 必败态,能够抵达必败态的均是必胜态,如果一个状态后继均是必败的话,那么他就是必胜态,这种方法看起来真的不错呢,只要得到这个DAG的拓扑次序,就可以递推出整个图的信息。
            但是当整个图的规模很大的时候呢,比如就像nim游戏怎么去求解呢,就要引入nim和的概念,nim和指的就是三堆石子数的异或和,有结论表明如果nim和为0,那么这个状态就是必败态,非零就是必胜态,是不是很神奇,这就要从异或的性质上去解释,将某一堆的石子减少到某一个数量对应的操作在相当于减少一个数字,很明显,最终状态异或是0,如果一个状态nim和是0,那么肯定有至少一种减少某一个数值的方法使得异或值变成0,并且如果nim和是0的话,显然所有操作方法的后继状态全部是非零的。所以异或值就等价于我们上面说的必胜必败态。
           虽然我们最开始介绍的第一种必胜必败理论能够很好的结论单个游戏中的胜负情况,但是如果是多个游戏的组合呢,状态数会大大增加,能不能像上面的nim和一样存在一种简便的方法呢,答案就是SG函数。
            SG函数就是的定义就是在一个DAG当中,如果当前状态是S,那么SG(S) = 所以后继状态中SG值中没有出现过的最小值,根据相似的定义,SG值为0 当且仅当该状态是必败态。SG函数强大的地方就在于在多个组合游戏当中,整体的SG值等于每个独立游戏的SG的异或和。
            关于证明并不是特别懂,大致的证明和我们的nim和的证明很类似,相当于任意一个SG异或和为零的状态的所有后继都是必胜态,任意一个必胜态总存在至少一个后继是必败态。前面的这些是一些最基本的理论知识。
            关于博弈的题目,白爷给出了六字真言,“找规律背结论”。

            一些基础的题目类型就是给出一些操作,我们对于整个DAG进行SG值得打表。
            cf上某题,题号不记得,给出一个正方形的边长,现在alice和bob轮流在图中放圆,圆形的半径也已经知道,alice先放,问alice是的胜负。如果alice能够放置第一个圆,那么alice就是必胜,否则必败,因为alice将第一个圆放置在正方形的中间,接下去alice就照着bob放置的放对称的圆就可以。

            hdu 3863
    No Gambling永远是先手必胜,因为这个游戏和博弈还是有一点差距,你刚开始先放置一个最自己必定是肯定有优势的,所以如果这样第二个人存在必胜策略的话,先手肯定可以把这个方法拿来用,反证法,说明先手必胜。

            hdu 1525
    Euclid's Game这道题很巧妙,刚开始不知道数据范围搞搞看,发现数据其实很大,后来发现如果当大数比小数大于等于两倍的时候,那么假设直接对大数取模是必胜态,那么就直接选,如果是必败态,那么我们就选到大数比小数大又不足两倍的情况,将必败留给对手。所以当大数大于两倍小数就是必胜态,其他情况是唯一后继的情况,直接递推。

            hdu 1527 取石子游戏 直接就是威佐夫博奕,威佐夫博奕指的就是在两堆中,可以有两种操作,一种是在一堆中取走一些石子,另外一种就是在两堆中取走想通数量的石子,那么直接有规律,第K个必败状态就是ai = k*( (1+sqrt(5))/2) 向下取整,bi = ai+k.

           另外一类博弈,在一个无向图当中,我们任选一个起点,然后从这个
    起点开始沿着无向边走,走过的点不能重复访问,无法走动的那个判负。在这类博弈中,利用图的匹配来解决,求出这个图的每个联通分量的匹配,如果一个联通分量不是完美匹配,那么我们就选择未盖点作为起点,那么后手必将进入一个新的匹配内,我们就可以行走这个匹配,必胜,否则的话就是存在增广路,和我们的最大匹配不符。
            这个问题适用于一般图,当然也适用于二部图,如果限制了起点,做法稍微需要变通一下,先求出除起点外的最大匹配数,再求出包括的起点的匹配数,如果不等,等价于存在从起点开始的增广路,那么先手必胜,一直走下去,一定能找到一个增广路。


            树上删边的博弈,给一棵树,可以删去一条边,树下面的部分自动脱落,最后一次操作的人获胜,问胜负状态。同样可以用sg函数来解释,定义叶子节点的sg值为0,如果增加一条边,那么sg函数加1,如果一棵树由几个子树组成,那么就是他们的异或值(这里其实跟nim游戏是一样的),所以树的sg值定义为所有孩子的异或值加1的异或值。

            ANTI-SG,跟普通组合游戏的规则相同,唯一不同的是定义无法进行操作的那个人 定义为获胜。解法:定义所有终态的SG值是0,其他求法都和普通的SG求法相同。先手获胜当且仅当(1)游戏的SG值不为0并且游戏中某一单一游戏的SG值大于1。 (2)游戏的SG函数为0并且游戏中没有单一游戏的SG值大于1.
    展开全文
  • 博弈博弈博弈博弈博弈博弈博弈博弈博弈博弈博弈博弈博弈博弈博弈
  • 还在四处寻找有关于智猪博弈——博弈案例讲解吗?整理发布的这一款智猪博弈——博弈案例讲解定...该文档为智猪博弈——博弈案例讲解,是一份很不错的参考资料,具有较高参考价值,感兴趣的可以下载看看
  • 博弈博弈

    千次阅读 2020-03-26 14:51:36
    博弈 目标:使参与博弈的一方获胜

    博弈与博弈树

    博弈

    博弈双方根据事先制定的规则,轮流交替在对应的棋局上做出自己的选择,然后根据规则判定那一方获胜。

    博弈树(一种特殊的与或树)

    在这里插入图片描述

    • 目标:将当前棋局作为根节点,选出最有利于自己获胜的一步棋
    • 结构
      • 节点:每一个节点代表一种棋局,总共有两种情况,一种是敌方走过,轮到我走;另外一种是我方走过,敌方进行选择。

      • 交替出现的与或节点:双方轮流走步,轮流扩展自己的节点

      • 终叶节点:

        • 我方获胜,节点可解
        • 敌方获胜,节点不可解
      • 根节点:敌方刚走过的棋局,我方根据该棋局做出自己的判断

      • 根节点的字节点:我方根据敌方走过的棋局,可以做出的选择

    • 估价函数:将胜利的判定条件作为可视化,可比较的数字,通过比较估价函数值,来确定当前步是否是最有力的步骤
      • 终叶节点的估价函数:通过终叶棋局的直接计算获得
      • 父节点:
        • 子节点是或连接:选取子节点中估价函数最大的得分作为父节点的估价函数值
        • 子节点是与连接:选取子节点中估价函数最小的得分作为父节点的估价函数值

    搜索方法——man-min搜索

    • 基本思想:自下而上逐层回溯评估。——因为底层的终叶节点代表着棋局的最终输赢,所以要从结局开始追溯,判定某一步走的结果是输是赢。
    • 与节点的子节点选择最小值最为父节点的值——敌方有若干种可能,只要有一种可能,在同等的情况下,敌方也一定会赢,所以,父节点一定是最小值。
    • 或节点的子节点选择最大值作为父节点的值——我方有若干种走法,凡是我方一定选择胜率最高的步子。
    图例

    在这里插入图片描述
    有当前棋局出发,根据步数4的要求,延展出对应的与或图
    在这里插入图片描述
    然后根据对应的传递规则,从下往上进行推导,直到倒数第二层,选择出胜率最高的步数。

    展开全文
  • 零和博弈、正和博弈和负和博弈

    万次阅读 2019-12-05 11:18:44
    零和博弈、正和博弈和负和博弈: 零和博弈是指双方在博弈时,在严格的竞争条件下,一方获得利益的同时必然意味着另一方遭受损失,双方受益加和为0。 负和博弈是指双方在博弈中由于不可调节的冲突和矛盾,有损双方的...

    零和博弈、正和博弈和负和博弈:
    零和博弈是指双方在博弈时,在严格的竞争条件下,一方获得利益的同时必然意味着另一方遭受损失,双方受益加和为0。
    负和博弈是指双方在博弈中由于不可调节的冲突和矛盾,有损双方的利益,导致两败俱伤的场面。
    正和博弈是指博弈双方的利益都有所增加,双赢局面。
    例子:
    夫妻二人要看电视,可是丈夫看体育,如果当晚丈夫能看到体育节目,得分为1,不能得分为0;妻子看肥皂剧,如果当晚妻子能看到肥皂剧,得分为1,不能得分为0。
    若双方采用石头剪刀布决定电视权,则一方可以得到满足,另一方不能,则1+(-1)=0,可以看出此时是零和博弈
    若双方因抢夺遥控器发生争吵,甚至拔掉电源等情况造成双方都不能达到满足,即-1+(-1)=-2,此时为负和博弈
    若双方都很包容,双方约定轮流看电视,双方各看一个小时自己喜爱的节目,此时达到双赢局面,1+1=2,此时为正和博弈

    展开全文
  • 博弈

    万次阅读 多人点赞 2019-10-13 16:28:32
    本文为个人学习博弈树的过程,非常感谢张少宏老师课上精彩的讲解! 博弈树的搜索 博弈树定义: 一类特殊的与或图 (本次讨论的博弈树都是“与或图”) 应用范围: 下棋、故障诊断、风险投资 基本搜索策略: 极小极大...

    博弈树的搜索

    博弈树定义:
    一类特殊的与或图
    (本次讨论的博弈树都是“与或图”)

    应用范围:
    下棋、故障诊断、风险投资

    基本搜索策略:
    极小极大搜索(min-max)

    优化的搜索方法:
    α-β剪枝搜索
    (剪枝)
    (搜索与生成同时进行)

    了解背景:

    (完全博弈问题)博弈问题

    特点:
    双人对弈:轮流下,一人走一步。
    信息完备:双方看到的信息一样
    零和:双方利益冲突,对一方有利则对另一方不利。一般对节点N取一个估价函数f(N),一共两类节点:
    ——叫Max的极大节点追求最大化,有选择时肯定选值最大的;
    ——叫Min的极小节点追求最小化,有选择时肯定选值最小的。

    例子1:下棋

    两位选手对垒,轮流走步。这时每一方不仅知道对方过去已经走过的棋步,而且还能估计出对方未来可能的走步。对弈的结果是一方赢(另一方则输),或者双方和局。如象棋,围棋,五子棋,…

    例子2:选包拿钱

    假设有两个钱包,每个钱包都放2张钱,第一个放了0.5元和100元,第二个放了2元和10元, Max和Min两个人是仇敌。现在Max负责挑出一个包,Min负责从Max选的包里选一张小的钱给Max。
    因为Max想让自己的钱越多越好而Min不想让Max钱多,所以Min会选一张相对最小的钱给Max。也即,Max想获得最大利益,而Min只是想承受最小的对手变强程度。在这种情况下Max应该选择包2,Min会给他2元。如果Max选择了包1 ,Min只会给他选0.5元。
    图1
    完全信息博弈抽象出任务原型:
    给出(或逐步生成)一个博弈树,求出在指定搜索深度(层数)下的最佳路径和相应估价分数。比如下象棋,Max先走一步,Min再走一步,再轮到Max走,这时Max遇到的各个局面可以估分,再倒推回去Max的第一步应该选择走哪步最佳
    基本搜索策略:极小极大搜索(min-max)
    为了提高极小极大搜索方法的速度,所以采用剪枝,最主要的是α-β剪枝

    不完全信息博弈情况:
    大部分纸牌游戏(如斗地主、拖拉机)
    大部分即时策略游戏(如红警、星际、帝国)
    ——需要探路(即信息不对等)
    ——游戏还受手速(APM)影响

    但是博弈问题常常不能简单穷举,以中国相亲为例:
    ——一盘棋平均走50步,总状态数约为10的161次方。假如一毫微秒走一步,约需10的145次方。
    ——结论:不可能穷举

    极小极大搜索方法:

    极小极大搜索方法是博弈树搜索的基本方法 。
    首先假定,有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时,表示棋局对我方有利,对对方不利。当评价函数小于0时,表示棋局对我方不利,对对方有利。
    方法过程:
    1、当轮到我方走棋时,首先按照一定的搜索深度生成出给定深度d以内的所有状态,计算所有叶节点的评价函数值。然后从d-1层节点开始逆向计算:
    2、对于我方要走的节点(用MAX标记,称为极大节点)取其子节点中的最大值为该节点的值(因为我方总是选择对我方有利的棋)。
    3、对于对方要走的节点(用MIN标记,称为极小节点)取其子节点中的最小值为该节点的值(对方总是选择对我方不利的棋)。
    4、一直到计算出根节点的值为止。获得根节点取值的那一分枝,即为所选择的最佳走步。
    图2 极小极大搜索
    因此,极小极大过程是一种假定对手每次回应都正确的情况下,如何从中找出对我方最有利的走步的搜索方法。
    值得注意的是,不管设定的搜索深度是多少层,经过一次搜索以后,只决定了我方一步棋的走法。等到对方回应一步棋之后,需要在新的棋局下重新进行搜索,来决定下一步棋如何走。

    对于静态估计函数f(x)
    一般规定有利于MAX的势态,f§取正值,有利于MIN的势态,f§取负值,势均力敌的势态,f§取0值。若f§=+∞,则表示MAX赢,若f§=-∞,则表示MIN赢。下面的讨论规定:顶节点深度d=0,MAX代表程序方,MIN代表对手方,MAX先走。
    当用端节点的静态估计函数f(p)求倒推值时,两位选手应采取不同的策略,从下往上逐层交替使用极小和极大的选值方法,故称极小极大过程。

    个人总结:
    极小极大搜索——从一个原始状态节点,根据估值函数,对后面出现的可能状态进行估值,在一定深度内通过一个路径选择方式(max层节点从子节点选择最大的值,min层节点从子节点总选择最小的值),选择出最优的路径(该路径为到达最优值所在节点路径)。

    α-β剪枝搜索过程:

    能否在搜索深度不变的情况下,利用已有的搜索信息减少生成的节点数呢?
    MIN-MAX过程是把搜索树的生成和格局估值这两个过程分开来进行,即先生成全部搜索树,然后再进行端节点静态估值和倒推值计算,这显然会导致低效率。
    实际上把生成和倒推估值结合起来进行,再根据一定的条件判定,有可能尽早修剪掉一些无用的分枝,同样可获得类似的效果,这就是α-β过程的基本思想。

    注意: α-β剪枝搜索和生成扩展子节点是同步的。其得到的最优解结果与Min-Max过程一致
    Min-Max过程和α-β剪枝搜索的结果都受生成/搜索策略顺序有关(比如选择广度优先或者深度优先,结果可能不一样)

    简单例子:

    图3 极小极大搜索方法
    由图3可知,对于min-max搜索,得到的最优路径为A1-A11。max得分为3

    图4 α-β剪枝方法
    而图4是通过α-β剪枝方法得到的,同样得到最优路径为A1-A11。max得分为3。

    例子2:

    对该搜索树进行左边深度优先α-β剪枝搜索

    图5 例子2
    左边为原搜索树,右边为α-β剪枝搜索
    ——极小值节点I的N子树被剪枝了( α剪枝)
    ——极大值节点G的L子树被剪枝了(β剪枝)

    α-β搜索方法定义:
    Max节点的下界为α,即Max确保能获得的最小得益。初始化为-inf。
    Min节点的上界为β,即Min付出的上界代价保障。初始化为+inf。
    对于节点N的估计函数值f(N),初始化α =-inf ≤ f(N) ≤ β=+inf
    若 α ≤ β则N有解。若 α > β 则N无解(为什么无解?因为对于上一层,min/max层不会选择该路径的节点了,故而可以放弃搜索),该节点N的其他未访问子树会被剪枝
    如图中节点I,从左子树DBE可以获得下界α=3,并传送到右边的极小节点I,此时I的子节点M给了个上界β=1。所以α=3> β=1,下界α大于上界β ,无解。

    在这里插入图片描述
    理解:
    极大节点N,从一个子树获得的α值和β值,可以传送给其子节点
    极大节点N 的α值只可能越改越大,否则极大节点N可以还选择原有α值
    极小节点M的β值只可能越改越小,否则极小节点M可以还选择原有β值
    从单边子节点往父节点推,极大值父节点只更改α值,极小值父节点只更改β值。

    在这里插入图片描述
    α剪枝(发生在极小层节点,如图中的节点I)
    (1)α剪枝:若任一极小值层节点的β值小于或等于它任一先辈极大值层节点的α值,即α(先辈层)≥β(后继层),则可中止该极小值层中这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个β值。
    从一个子树获得的极大节点的α值,可以传送给该节点的其他子树,从而选择α剪枝机会(课本说法,和“先辈”节点α值比较,是和所有先辈节点比较,而不是仅仅和父节点比较)。
    从单边子节点往父节点推,极大值父节点只更改α值,极小值父节点只更改β值

    注意看极小节点I:
    极大节点A从左子树获得α值3,从而可以把α=3传播给右子树,在极小节点I点由于子节点M值为1从而可以确认β=1,此时α=3> β=1,从而I的其他节点可以被α剪枝, I点的β=1。

    在这里插入图片描述
    β剪枝(发生在极大层节点,如图中的节点G)
    (2)β剪枝:若任一极大值层节点的α值大于或等于它任一先辈极小值层节点的β值,即α(后继层)≥β(先辈层),则可以中止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的最终倒推值就确定为这个α值。
    从一个子树获得的极小节点的β值,可以传送给该节点的其他子节点,从而选择β剪枝机会(课本说法,和“先辈”节点β值比较,是和所有先辈节点比较,而不是仅仅和父节点比较)。
    从单边子节点往父节点推,极大值父节点只更改α值,极小值父节点只更改β值

    注意看极大节点G:
    极小节点C通过部分计算(A左子树和F子树)获得α=3和β=5 ,从而可以把α=3和β=5传播给极大节点G,在极大节点G点由于子节点K值为6从而可以确认α=6 ,从而G点此时α=6> β=5,从而G的其他节点可以被β剪枝,G点的α=6 。

    祭出终极例子3:
    在这里插入图片描述

    α-β搜索方法总结:

    1、α-β剪枝后选得的最好优先走步,其结果与不剪枝的MINIMAX方法所得完全相同,因而α-β过程具有较高的效率。
    2、α-β剪枝最理想的情况是,Min节点先扩展最低估值子节点,Max节点先扩展最大估值节点。(这个策略可以用于启发式α-β剪枝搜索)

    思考问题:为什么所有α-β剪枝搜索例子都是用深度优先策略?
    因为深度优先更有机会发生剪枝。

    展开全文
  • 成功创业不仅需要能吃苦、能勤奋,还需要拥有良好规划、正确方法,而这些智猪博弈-博弈案例讲解都能给予...该文档为智猪博弈-博弈案例讲解,是一份很不错的参考资料,具有较高参考价值,感兴趣的可以下载看看
  • 配套笔记!值得期待!本课程介绍了博弈论的基本概念、完全信息静态博弈、完全信息动态博弈、不完全信息静态博弈、不完全信息动态博弈、合作博弈以及演化博弈
  • 1 序贯博弈与重复博弈 序惯博弈(sequential game):参与人在前一个决 策点的选择决定随后的子博弈的结构,因此, 从后一个决策点开始的子博弈不同于从前一个 决策点开始的子博弈,或者说,同样结构的子 ...
  • 博弈算法ppt

    2019-02-22 00:36:56
    acm/oi博弈算法的入门讲义,从nim博弈入手,介绍博弈树与sg函数等基本概念,而后介绍了各种nim博弈的变种以及翻硬币类的博弈题目
  • 博弈
  • 这几天看一些crowdsourcing的经典文章,发现经常初选game theory,之前看过一段时间但是没好好整理,重新整理一发 Non-cooperative Game 非合作博弈是指一种参与者...负和博弈和零和博弈统称为非合作博弈,正和博弈亦...
  • 博弈论之威佐夫博弈

    千次阅读 多人点赞 2018-04-17 22:19:37
    威佐夫博弈(Wythoff's game)是指的这样一个问题:有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。 我们用(a[k],b...
  • 博弈论】博弈论基础知识

    万次阅读 多人点赞 2019-05-26 16:49:07
    本学期选了博弈论的通识课,现将其基础知识点总结一下: 1.博弈论(Game Theory):博弈论也称游戏论、对策论,是研究相互依赖、相互影响的决策主体的理性决策行为以及这些决策的均衡结果的理论。 2.博弈论的基本构成...
  • Stackelberg博弈

    千次阅读 2020-03-30 15:13:09
    Stackelberg最早来源于...在Stackelberg安全博弈中领导者首先确定自身的混合策略,跟随者通过观察得到领导者的策略信息,然后选择能够最大化自身收益的策略进行博弈,根据策略执行动作跳转到下一状态。 Stackelb...
  • 该算法使用线性规划模型(使用优化工具箱)在混合策略中检测鞍点或寻找解决方案。 还分析了存在无用策略的博弈矩阵并返回最优值。
  • 博弈

    2021-02-21 13:58:56
    说到博弈论,他的官方解释就是:博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。 博弈论很多种类,一般训练中会遇到的有几种,巴什博弈,威佐夫博弈,尼姆博弈,斐波那契博弈。 下面分开进行对...
  • 博弈论诡计

    2018-04-25 22:51:44
    博弈论诡计:介绍博弈论的一些有趣的案例来加深对博弈论的理解
  • 贝叶斯博弈

    2012-07-16 16:23:35
    贝叶斯博弈

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,280
精华内容 29,312
关键字:

博弈