高深的博弈论?不!这是中学生都能懂的游戏必胜策略!

作者: 张通

来源: 新东方智慧学堂

发布日期: 2021-11-26 12:52:13

本文讨论了动态博弈中的一类有趣的游戏策略——必胜/败策略,并通过具体游戏例子说明了如何构建这些策略。

首先,动态博弈是指参与人的行动有先后顺序,而且行动在后者可以观察到行动在先者的选择,并据此作出相应的选择。典型的例子是下棋(如象棋、围棋、跳棋等)。下棋有两个博弈参与者,一人一步,游戏规则和每一步的信息都是完全公开的,且无任何运气成分,游戏的所有可能局面有限且游戏规则已决定游戏会在有限步内结束。策梅洛定理告诉我们:这类游戏先行或后行方当中必有一方有必胜或必不败的策略。

下面简单证明策梅洛定理。为方便计,对游戏的所有可能状态染色,如果某一状态已经判定先手胜则该状态染黑,同理先手负则该状态染白。如果某一状态是先手方行动且它的所有后继状态都是白色,则这一状态染白。如果某一状态是先手方行动且存在它的某一个后继状态是黑色,则这一状态染黑。如果是后手方行动,同上。此局先手(红)下一步无论怎么走,后继状态都是白色(输)。

总结一下:没有平局,每个游戏局面要么是必胜态,要么是必败态;一个状态是必败态,当且仅当它的所有后继状态都是必胜态;一个状态是必胜态,当且仅当它的后继状态存在一个必败态。必胜策略的核心本质是:理清必胜态和必败态,并构造必胜态与必败态之间的状态转移。

下面选取一些著名游戏的例子来说明如何构建必胜/败策略。为了方便,去掉可能出现平局的游戏。

Bash Game有枚棋子甲乙轮流拿,每次只能拿枚,谁拿到最后一枚棋子算胜。若甲先拿,问:谁有必胜策略?当n=1时,甲(先手)必胜;当n=2时,甲(先手)不管拿几枚,乙(后手)都可以在下一次全拿完,即甲行动的所有后继状态都是乙必胜,所以甲(先手)必败;当n=3时,甲(先手)只要拿1枚后,就可以让乙先手并面临n=2的情形,即甲行动的某一个后继状态都是乙必败,所以甲(先手)必胜。

UUID: 1f752e3e-6742-4275-9e1e-4c946e1e35dc

原始文件名: /home/andie/dev/tudou/annot/AI语料库-20240917-V2/AI语料库/中科院物理所公众号-pdf2txt/2021/中科院物理所_2021-11-26_「转」高深的博弈论?不!这是中学生都能懂的游戏必胜策略!.txt

是否为广告: 否

处理费用: 0.0054 元