这类游戏,例如围棋,象棋之类。
我不太懂博弈论,自己大概想了下,是否在给定规则(假设没有和局),自己和对手在给定无限计算速度和存储的情况下,最终的结果是不是就是根据规则和先手顺序唯一的决定的?
就是说,给定规则,先手不是必败就是必胜?
以下是我的想法:
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)