超現實數與博弈/博弈
假設我們有兩個玩家,分別稱為左玩家和右玩家,他們玩著具有以下屬性的遊戲
- 遊戲不涉及任何機會或運氣因素
- 雙方玩家對遊戲資訊完全瞭解
- 玩家輪流進行合法操作
- 遊戲不會無限期進行下去;每次合法操作都會使遊戲狀態更接近於一方或雙方玩家沒有合法操作的狀態
因此,圍棋就是這種遊戲,國際象棋或奧賽羅也是。但撲克則不是,因為它有運氣和隱藏資訊因素。足球也不是,因為足球也有運氣因素,並且遊戲程序並非輪流操作。
在遊戲的任何階段,我們可以認為遊戲狀態是由左玩家所有合法操作的集合(表示為 )和右玩家所有合法操作的集合(表示為 )決定的。左玩家的每次合法操作都會使遊戲狀態變得更簡單,右玩家也是如此。我們用 表示遊戲狀態。
多米諾遊戲就是這種遊戲的很好例子。遊戲從一些方形排列組合開始,這些方形在它們的邊上連線在一起。左玩家從集合中移除一個 2x1(豎直)矩形,右玩家移除一個 1x2(水平)矩形。第一個沒有合法操作的玩家輸掉遊戲。
考慮一個只包含一個方形或根本沒有方形的遊戲。顯然,兩個玩家都沒有合法操作,所以這個遊戲的狀態是 。這看起來眼熟嗎?沒錯,這就是超現實數 0。因此,這裡的 0 表示“先手必敗”;如果輪到你操作,你就會輸。如果我們從一個 2x1 的豎直方形開始會怎麼樣?在這種情況下,左玩家有一個合法操作,並且執行該操作會使遊戲狀態變為沒有人有合法操作的狀態。因此,左玩家的合法操作集是 。右玩家根本沒有合法操作,所以這個遊戲是 。這就是超現實數 1。
|
練習 1 證明對應於一個 1x2 水平矩形的遊戲等於超現實數 -1。 |
如果我們從三個以 L 形排列的方形開始,我們會得到什麼?每個玩家都有一個合法操作,這會使遊戲狀態變為沒有人有合法操作的狀態。因此,它等於 。我們在開始的第一天簡要地遇到了這個物件,並發現它不是有效的超現實數。然而,它是一個完全合法的遊戲,並且對應於“先手必勝”。
到目前為止,我們只考慮了玩家只有一個合法操作或根本沒有操作的情況。如果有選擇要做出怎麼辦?考慮一個長邊垂直的俄羅斯方塊 L 形。如果輪到左玩家操作,他可以選擇上面的兩個方形。這樣做很愚蠢,因為然後右玩家會選擇另外兩個方形並獲勝,但它仍然是一個合法操作;-1 是左玩家的選項之一。或者左玩家可以選擇角落。然後兩個玩家都沒有合法操作;0 是左玩家的另一個選項。如果輪到右玩家操作,她只能選擇下面的兩個方形,然後讓左玩家透過選擇另外兩個方形來獲勝。她的唯一選擇是 1,即左玩家獲勝。因此,這個遊戲對應於 。我們認識到這是超現實數 1/2。
|
練習 2 證明對應於一個 1x4 水平矩形的遊戲等於超現實數 -2。 |