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

2018-05-17 15:58:00 +08:00
 ballshapesdsd
这类游戏,例如围棋,象棋之类。

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

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

以下是我的想法:
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)
741 次点击
所在节点    问与答
2 条回复
ballshapesdsd
2018-05-17 16:01:03 +08:00
顺便说一句,现有围棋贴目是不是可以根据这个来调整。。。设置为先手必败和先手必胜的分界点。。。
ballshapesdsd
2018-05-17 16:01:24 +08:00
@ballshapesdsd #1 当然这是不可能做到的。。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/455651

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX