隨著程式語言的進步，從以前的組合語言到現今的高度抽象化的程式語言，造就了越來越複雜的軟體系統，因此我們亟需要自動化的方法來幫助我們分析這樣的軟體系統。軟體系統其中的一支系統，反應系統（Reactive System），由於必須和環境不斷的互動，因此環境的不確定性使得反應系統的行為更加的難以分析與預測。而賽局理論恰巧是探討兩個以上行為決策者的學科，所以直覺上賽局理論很適合拿來做這種系統的分析。

賽局理論自從在二十世紀初開始有系統的研究以來，已經在生物學，經濟學，國際關係，政治學，軍事理論等許多領域越來越受到重視並且有了很廣泛的應用，而且賽局理論也漸漸的被應用在計算機科學中的許多領域，如人工智慧（Artificial Intelligence ）、分散式系統（Distributed System）、反應系統（Reactive system）、最佳化求解（Optimization）和模型檢驗（Model checking）等問題。在本文中，我們將介紹數種用來分析反應系統的賽局，和它們所適用的情境。

在計算機科學裡，我們可以用圖形（Graph）的方式來表示一個系統。在圖上，節點（vertex）代表系統的狀態，邊（edge）代表了從一個狀態到另一個狀態的轉換。而用來表示反應系統時，節點可以更進一步的區分為系統的節點以及環境的節點，因此從系統的節點連出去的邊就代表了受控制的行為，系統可以藉由選擇其中一個邊，而明確的知道系統的下一個狀態；而從環境的節點連出去的邊，代表不受控制的行為，所以在環境做出選擇之前，並無法知道下一個系統狀態是什麼。

正規上來說，我們會定義一個雙人玩的賽局圖（Game graph）G＝（V1, V2, E1, E2）來模型化一個反應系統。在 G中V1代表玩家1的節點，V2代表玩家2的節點，

E1：V1×V2是從V1節點到V2節點的邊，代表受玩家1所控制的選擇，E2：V2×V1是從V2節點到V1節點的邊，代表不受玩家1所控制的選擇。由於反應系統是不斷的和環境做互動，所以系統和環境之間形成的賽局，都是沒有結束的賽局，也就是說V1和V2中的節點，一定至少會有一個向外的邊。除了提供賽局圖來當作賽局的比賽場所之外，賽局中還必須定義了怎樣子叫做贏了一場賽局，也就是說每一個賽局都必須定義他的求解概念（solution concept）。注意：以下所介紹的賽局，皆為完全資訊並且是回合制的賽局。

《圖一　 有限圖上的一個賽局》

為了能更簡潔的介紹各種賽局，我們先定義了以下幾個術語：

接下來我們將介紹幾種常見的賽局，和它們的求解概念。

無可避免型（Inevitable Condition）

這類的求解概念，在找尋是否存在一個玩家1的策略，不管玩家2怎麼做，玩家1都可以到達系統中的某些狀態。這類的賽局，在偵測死結（deadlock），無作用的程式碼（dead code）等等，都非常的有用。屬於這一類的賽局有：

可到達賽局（Reachability game）

可到達賽局定義為RGame＝(G, v0, R)，v0V1∪V2代表賽局的起始點；RV1∪V2代表某些特定的節點，只要玩家1可以引導比賽進入R的其中一個節點，玩家1就算贏了這一場比賽。在文獻上，可到達賽局具有兩個非常漂亮的性質：

重複型（Recurrence Condition）

這類的求解概念，在找尋是否存在一個玩家1的策略，不管玩家2怎麼做，玩家1都可以不斷的重覆某些狀態。這類的賽局，在偵測系統是否保有公平性（Fairness）的特質時非常的有用，譬如作業系統的排程等等。屬於這一類的賽局有：

Buchi賽局（Buchi game）

Buchi賽局定義為BGame＝（G, v0, F），v0V1∪V2代表賽局的起始點，FV1∪V2代表某些特定的節點，只要在比賽裡，F其中至少一個節點無限次的出現在比賽中，那麼玩家1就算贏了這一場賽局，否則就算玩家2贏了這一場賽局。

同樣的在文獻上也證明了Buchi賽局擁有確定性和存在無記憶策略的性質。

對稱性賽局（Parity game）

對稱性賽局定義為PGame＝（G, v0, p），v0V1∪V2代表賽局的起始點；p是優先權函數，給每一個節點都指派一個優先權，正規地來說，p：V1∪V2→[d], d  N。在對稱性賽局中，只要在比賽中，無限次出現的優先權中，最小的數字是偶數的話，就代表了玩家1贏得這一場比賽，如果是奇數的話，那就是玩家2贏得這一場比賽。

同樣的在文獻上也證明了對稱性賽局擁有確定性和存在無記憶策略的性質。

權重型（Weighted Condition）

這類的賽局追求的不在是誰勝誰負，而是盡可能的最大化自己的利益，最小化對方的所得。通常在各個狀態或是狀態轉換時，都需要消耗一定量的系統資源，因此這類的求解概念，常被用來分析一個系統是否能夠對資源做有效的配置，譬如嵌入式系統功率的消耗和網路路由器的緩衝區大小等等。屬於這一類的賽局有：

平均收益賽局（Mean payoff game）

平均收益賽局定義為MGame＝（G, v0, r），v0 V1∪V2代表賽局的起始點；r是報酬函數，給每一個節點都指派一個報酬，正規地來說，r：V1∪V2→R。在一場比賽中，玩家1會獲得在比賽中每一手節點的平均報酬，而玩家1所獲得的即是玩家2所失去的，因此再平均收益賽局裡，玩家1的目標是提高平均收益，而玩家2的目標是降低平均收益。

在平均收益賽局裡，確定性是定義為存在一個數字C，使得玩家1最少都還有C的平均報酬，並且玩家2最多就只輸C這麼多的平均報酬。

同樣的在文獻上也證明了平均收益賽局擁有確定性和存在無記憶策略的性質。

涵蓋率賽局（Coverage game）

涵蓋率賽局定義為CGame＝（G, v0, r），v0 V1∪V2代表賽局的起始點；r是涵蓋率的映射函數，給每一個節點都指派一個涵蓋率，正規地來說，r：V1∪V2→R。在一場比賽中，玩家1所獲得的涵蓋率是在比賽中所有節點的涵蓋率總合，而玩家2所獲得的涵蓋率即是圖上所有節點涵蓋率的總和扣掉玩家1所得到的涵蓋率。因此再涵蓋率賽局裡，玩家1的目標是提高比賽中總共可以涵蓋的涵蓋率，而玩家2的目標是避免涵蓋率的增加。

在文獻上已經證實了涵蓋率賽局中，求取玩家1所能夠獲得的最大的涵蓋率是屬於PSPACE-complete的問題。這種賽局，非常適合用來產生測試計劃，和作為測試案例品質的指標。

混合型

綜合其他類型特色的賽局，就形成了混合型的賽局，這類的賽局，通常都比較複雜，也需要更多的計算，但好處是可以更精準的分析出一個系統是否能夠同時滿足多種需求。屬於這一類的賽局有：

平均收益對稱賽局（Mean-payoff parity game）

平均收益對稱賽局定義為MPGame＝（G, v0, p, r），v0 V1∪V2代表賽局的起始點；p是優先權函數，給每一個節點都指派一個優先權，正規地來說，p：V1∪V2→[d], d  N；r是報酬函數，給每一個節點都指派一個報酬，正規地來說，r：V1∪V2→R。在一場比賽中，如果無限次出現的優先權中，最小的數字是偶數的話，那玩家1可以獲得在比賽中每一手節點的平均報酬，否則玩家1的平均報酬將是負的無限大；而玩家1所獲得的即是玩家2所失去的，因此再平均收益對稱賽局裡，玩家1的目標同樣是提高平均收益，而玩家2的目標同樣也是降低平均收益。

《圖二　平均收益對稱賽局》

以圖二為例，如果玩家1的策略為當節點1被拜訪過的次數mod k為0的話，就選擇節點3作為下一步，否則就選擇節點2作為下一步。如此一來，無限次出現的優先權為偶數，故玩家1可以贏得{(k-1)×10+2}/k的平均收益。

在文獻上，平均收益對稱賽局已經被證明擁有確定性的性質，但是只存在需要無限記憶空間的最佳化策略。

結語

本文整理了數種文獻上曾經探討過的賽局和它們所要解決的問題，並且指出各種賽局在軟體系統的分析上可能的應用，顯示出賽局理論在計算機科學中漸漸地引起注意，扮演舉足輕重的角色。

---作者王凡為美國德州大學奧斯汀校區計算機科學博士，現任台灣大學電機與電子工程研究所教授；吳榮軒為國立台灣大學電機工程碩士，現為台灣大學電機工程研究所博士班學生---

＜參考資料：

[1] Automata, Logics, and Infinite Games：A Guide to Current Research

Gradel Erich, Thomas Wolfgang and Wilke Thomas, LNCS, Vol.?2500, 2002.

[2] Mean-Payoff Parity Games

K. Chatterjee, T. A. Henzinger and M. Jurdzinski

, LICS 2005.＞