超现实数与博弈/博弈

简介

假设我们有两个玩家，分别称为左玩家和右玩家，他们玩着具有以下属性的游戏

游戏不涉及任何机会或运气因素
双方玩家对游戏信息完全了解
玩家轮流进行合法操作
游戏不会无限期进行下去；每次合法操作都会使游戏状态更接近于一方或双方玩家没有合法操作的状态

因此，围棋就是这种游戏，国际象棋或奥赛罗也是。但扑克则不是，因为它有运气和隐藏信息因素。足球也不是，因为足球也有运气因素，并且游戏进程并非轮流操作。

在游戏的任何阶段，我们可以认为游戏状态是由左玩家所有合法操作的集合（表示为 $L$ ）和右玩家所有合法操作的集合（表示为 $R$ ）决定的。左玩家的每次合法操作都会使游戏状态变得更简单，右玩家也是如此。我们用 $\{L|R\}$ 表示游戏状态。

多米诺游戏

多米诺游戏就是这种游戏的很好例子。游戏从一些方形排列组合开始，这些方形在它们的边上连接在一起。左玩家从集合中移除一个 2x1（竖直）矩形，右玩家移除一个 1x2（水平）矩形。第一个没有合法操作的玩家输掉游戏。

考虑一个只包含一个方形或根本没有方形的游戏。显然，两个玩家都没有合法操作，所以这个游戏的状态是 $\{\varnothing |\varnothing \}$ 。这看起来眼熟吗？没错，这就是超现实数 0。因此，这里的 0 表示“先手必败”；如果轮到你操作，你就会输。如果我们从一个 2x1 的竖直方形开始会怎么样？在这种情况下，左玩家有一个合法操作，并且执行该操作会使游戏状态变为没有人有合法操作的状态。因此，左玩家的合法操作集是 $\{0\}$ 。右玩家根本没有合法操作，所以这个游戏是 $\{0|\varnothing \}$ 。这就是超现实数 1。

练习 1

证明对应于一个 1x2 水平矩形的游戏等于超现实数 -1。

如果我们从三个以 L 形排列的方形开始，我们会得到什么？每个玩家都有一个合法操作，这会使游戏状态变为没有人有合法操作的状态。因此，它等于 $*:=\{0|0\}$ 。我们在开始的第一天简要地遇到了这个对象，并发现它不是有效的超现实数。然而，它是一个完全合法的游戏，并且对应于“先手必胜”。

到目前为止，我们只考虑了玩家只有一个合法操作或根本没有操作的情况。如果有选择要做出怎么办？考虑一个长边垂直的俄罗斯方块 L 形。如果轮到左玩家操作，他可以选择上面的两个方形。这样做很愚蠢，因为然后右玩家会选择另外两个方形并获胜，但它仍然是一个合法操作；-1 是左玩家的选项之一。或者左玩家可以选择角落。然后两个玩家都没有合法操作；0 是左玩家的另一个选项。如果轮到右玩家操作，她只能选择下面的两个方形，然后让左玩家通过选择另外两个方形来获胜。她的唯一选择是 1，即左玩家获胜。因此，这个游戏对应于 $\{-1,0|1\}$ 。我们认识到这是超现实数 1/2。

练习 2

证明对应于一个 1x4 水平矩形的游戏等于超现实数 -2。