AlphaGo特別篇｜完全公開信息類遊戲之最佳策略

1996年，那是一個歷史性的時刻。許海峰和他的團隊帶領他們研發的人工智慧機器人Deep Blue，在國際象棋比賽中戰勝了人類。

令人驚嘆的是，數十年後，圍棋，這個人類一直認為無法被超越的領域，也再次被人工智慧所征服。

為什麼人工智慧能在這兩個領域涉足，並能戰勝萬物之靈的人類呢？這期我們就為大家揭開這個謎團。

從本質上來講，國際象棋和圍棋都屬於完全公開信息類的遊戲。這類遊戲的特點是：在遊戲任何時刻，只有一個玩家能行動，並且他知悉到該時刻為止所有玩家採取過的行動。

對於任何一個完全公開信息類的遊戲，我們都可以用一個樹狀圖來描述它的整個遊戲過程。這裡舉個很簡單的例子：假設現在有一個服務方要提供某項收費服務，也有一位顧客在考慮是否購買這項服務，雙方正在博弈。如果我們把這個博弈看作是一場他們共同參與的遊戲，便可用下方樹狀圖來描述這個遊戲自始至終的全部過程。

從圖中我們可以看出，遊戲先由服務方決定服務質量。然後，顧客根據該服務質量來決定是否購買此項服務。如果我們把服務分為高質量服務和低質量服務兩種，同時顧客只能選擇購買或不購買，那麼該遊戲就會有4種可能的結果。而雙方對於每一種結果，都有自己的滿意度。

我們姑且設定滿意度的範圍是從0到3。0代表很不滿意，1代表一般，2代表較滿意，3代表非常滿意。那麼我們便可以量化服務方和顧客對每一種結果的滿意度：

1）服務方提供低質量服務，顧客選擇購買。

由於提供低質量服務的成本低，卻換來了收益，服務方的滿意度是最高的，為3。對於顧客來說，他花了錢，卻買到了低質量服務，所以滿意度是最低的，為0。

2）服務方提供低質量服務，顧客選擇不購買。

由於提供低質量服務的成本低，同時無收益，服務方的滿意度一般，為1。對於顧客來說，他沒花錢，也沒獲得服務，所以滿意度一般，為1。

3）服務方提供高質量服務，顧客選擇不購買。

由於提供高質量服務的成本高，卻無收益，服務方的滿意度是最低的，為0。對於顧客來說，他沒花錢，也沒獲得服務，所以滿意度一般，為1。

4）服務方提供高質量服務，顧客選擇購買。

由於提供高質量服務的成本高，卻也獲得了收益，服務方的滿意度較高，為2。對於顧客來說，他花錢，買到了高質量服務，所以滿意度較高，為2。

當我們通過上述分析對這場遊戲有了清晰的認識後，便可以從結果倒推來確定雙方在理性條件下所作出的選擇。

由於最終做決定的是顧客，如果知道服務方提供的是高質量服務後，他就必然選擇購買，因為這樣帶來的滿意度是2，高於不購買的所帶來的1的滿意度。如果服務方提供的是低質量服務，顧客就應該選擇不購買，因為這樣帶來的滿意度是1，高於購買所帶來的0的滿意度。

對於服務方來說，當他預測了顧客會做出以上判斷後，便會在一開始選擇提供高質量服務，因為「提供高質量服務＋購買」給服務方帶來的滿意度為2，高於「提供低質量服務＋不購買」所帶來的1的滿意度。

因此，遊戲雙方的最佳策略為：

服務方：提供高質量服務。

顧客：購買高質量服務，不購買低質量服務。

從上述例子我們知道：對於完全公開信息類的遊戲中的玩家來說，如果他能知道遊戲所有可能的結果，並對每一個結果計算出自己的滿意度，便可通過理性分析，得出自己所應該採取的最佳策略。既然圍棋屬於完全公開信息類的遊戲，那麼圍棋的選手便可從棋局的結果倒推，通過理性分析掌握最佳策略。只要計算出最佳策略，並按照這個最佳策略去下棋，便可確保自己的勝利。然而，據估算，圍棋可能的結果約有250的150次方種，不僅人類無法實現這個目的，就連計算機也基本不可能具備這樣的能力。

那麼，以4:1完敗李世石的AlphaGo究竟是如何做到的呢？TA的「大腦」中到底藏了些什麼？

請看下期：《人工智慧 | AlphaGo的「大腦」中到底藏了些什麼？》。

Reference:

1) David Silver, Aja Huang, Mastering the game of Go with deep neural networks and tree search, Nature 529, 484-489.

2) Theodore L. Turocy, Bernhard von Stengel, Game Theory, CDAM Research Report LSE-CDAM-2001-09.

歡迎關注eigenPhys亦知物理微信公眾號，您可通過搜索「eigenPhys」找到我們。我們將為您定期分享物理學的美，將理性的浪漫撒向人間。