数学建模里有一道找必胜策略的题,做着做着,就有一个疑惑,像五子棋,围棋这种棋,是不是要么是甲有必胜策略,要么就是乙有必胜策略?
吃饭的时候想到这个问题,和同学讨论,,同学不同意,然而直觉告诉我肯定是这样,如何证明?
证明也不复杂。
造一棵树,每长出一层要么是甲做了决策,要么是乙做了决策。由于棋盘大小是有限的,所以这棵树一定具有限大小。
每一个叶子节点要么是甲胜,要么是乙胜,是游戏的终局。
进行一个标注过程,从下至上,使得根节点也标注上甲胜或乙胜。
标注策略如下:
如果所有子节点都是甲胜,父节点就是甲胜。
如果所有子节点都是乙胜,父节点就是乙胜。
如果子节点既有甲胜也有乙胜,那么子到父的决定是谁做出的,父节点就是谁胜。