V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
ballshapesdsd
V2EX  ›  问与答

有限二人零和回合制游戏的问题

  •  
  •   ballshapesdsd · 2018-05-17 15:58:00 +08:00 · 734 次点击
    这是一个创建于 2372 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这类游戏,例如围棋,象棋之类。

    我不太懂博弈论,自己大概想了下,是否在给定规则(假设没有和局),自己和对手在给定无限计算速度和存储的情况下,最终的结果是不是就是根据规则和先手顺序唯一的决定的?

    就是说,给定规则,先手不是必败就是必胜?

    以下是我的想法:
    1 假设博弈树最大 n 层,每层一个节点的分支最大 m 个,如果有的分支不到 n 层就结束了,可以看做虚拟地延伸到最后一层,只不过结果在很早就不再变化了。
    2 在最后一层,所有节点都是终局,即不是黑棋赢就是白棋赢(以围棋为例)
    3 根据 minmax 反向传播,如果 n-1 层是黑棋走,那么黑棋在每个节点上挑选对自己最有利的选择,如果这个节点下的所有子节点都是白棋赢,那么即使选择了最优行动,那么仍然是白棋赢;如果这个节点任何一个子节点是黑棋胜,那么可以认为通过最优的选择,这个节点( n-1 层)是黑棋胜
    4 重复 3 的步骤传播到 n-2 层。。。直到第一层,这个单一的初始节点仍然是决定性的,不是必败就是必胜(假设对局双方绝对理性)。

    举个例子,街边的象棋残局,基本都是先手必败(这种情况分支已经很少了,摆摊的人已经完全研究透了);井字棋等等。

    如果考虑和局的话,同样最好情况下先手有三种可能,必败,必和或者必胜。

    以下是我的问题:
    如果这个命题成立,那么象棋,围棋这类游戏实际上是建立在不完全理性的基础上的,即如果完全理性的情况下先手必败,那么先手的胜利实际上是建立在对手犯错的情况下的。考虑 alphazero 的胜率估计,如果最理想的情况下在任何节点,胜率估计应该不是 0%就是 100%,那么实际上 alphazero 通过深度学习的算法,mcts 等等估计出来的胜率,有什么意义?怎样理解这个胜率比较好?是否可以这样理解,由于无法穷举所有可能,这个胜率估计实际上是对当前节点必胜的一个置信度估计?


    -----------
    好吧,刚查了一下这个叫做 Zermelo's theorem (game theory)。。。

    https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory)
    2 条回复    2018-05-17 16:01:24 +08:00
    ballshapesdsd
        1
    ballshapesdsd  
    OP
       2018-05-17 16:01:03 +08:00
    顺便说一句,现有围棋贴目是不是可以根据这个来调整。。。设置为先手必败和先手必胜的分界点。。。
    ballshapesdsd
        2
    ballshapesdsd  
    OP
       2018-05-17 16:01:24 +08:00
    @ballshapesdsd #1 当然这是不可能做到的。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5601 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 03:35 · PVG 11:35 · LAX 19:35 · JFK 22:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.