【人物】

深入模仿遊戲，淺談涂林測試

張貼日期：Mar 18, 2015 10:3:58 AM

作者：彭俊文（一個小小留學生）

機器會思考嗎?

I propose to consider the question "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." -- Alan Turing《Computing Machinery and Intelligence》

電影《模仿遊戲 The Imitation Game》的主角電腦之父艾倫涂林非常大膽地以這句話做為其論文《計算機器與智能 Computing Machinery and Intelligence》第一個章節《The Imitation Game》的開頭。這句話不只開創了人工智能的概念，更是現代電腦科學的基石。

(在此向各位迷妹致歉，本篇文章並無深入討論飾演涂林的男主角 BC 班奈迪克康柏拜區)

BUT！如何定義「思考」，是一個哲學問題。

涂林並不想陷入哲學爭辯的泥淖，所以他隨後馬上指出「機器是否會思考」這樣的問題是一個危險的切入方向，他提出了另一個問題取而代之:

「機器可不可以做跟我們一樣的事情？」

這句話就如同那些常常貼在 T 字路口的警語：「不是路到盡頭了，是該轉彎了」，轉了彎遇到的是康莊大道。涂林以此問題當作出發點，發明了涂林測試 (Turing Test)，一直到今天，涂林測試仍然是用來判定人工智能的重要基礎。接下來，我將用一個簡單的小遊戲，帶領各位讀者深入《模仿遊戲 The Imitation Game》最重要的概念－涂林測試。

涂林測試 (Turing Test)

首先，這個遊戲總共有三個人參加，一個男人、一個女人和一位詢問者。遊戲開始前，男人跟女人分別走入一個密室，詢問者並不知道他們分別走入哪間房間。

詢問者 的任務是分辨出哪間房間藏著女人，哪間房間藏著男人；

女人的任務是協助詢問者猜出正確的答案；

男人的任務是干擾詢問者 (像不像是那些總是喜歡在網路遊戲中男扮女裝的人妖!@#$%!$%)。

詢問者會與兩方對話，但對話方法被限定 只能有文字的交流，不能有任何的聲音、影像或感情，所以他們可透過像是鍵盤與螢幕來對話。每當詢問者將一個問題丟給男方和女方時，他們就會依據他們的被指派的任務來回答問題。

每次問答結束後，詢問者要做一次判斷，如果他的判斷一直 無法有效的猜到男生女生分別在哪個房間，那我們就將它 視為男生假扮女生成功，反之就是失敗。

如果將以上情境用於判斷一台機器是否具有人工智慧，人類就是女人、機器就是男人。如果這台機器能成功的騙過詢問者，那我們就說這是一台可以模仿人類的電腦，他可以做我們可以做的事情。

涂林測試的中心思想就是，只要我猜不到，那他就是對的。

這樣的說法或許太過粗糙了，更精確地來說，涂林測試的哲學有以下兩點：

一、「事物的本質並不重要，重要的是他能不能扮演他應該扮演的角色」；

二、機率的應用「能成功扮演人類的意思指的是測試人員猜對的機會大概就是 1/2」。下面將舉的兩個例子，不能完全說是涂林測試的推廣，他們各有其淵源，但是我們可以看到涂林測試的思考哲學，被廣泛的應用在當代電腦科學中。

1. Zero Knowledge Proof (零知識證明)

在 1985 年，由三位電腦科學家（Shafi Goldwasser, Silvio Micali, and Charles Rackoff）第一次提出零知識證明，它是一個用來向他人證明我有某樣東西，但是不讓別人看到這東西本體的方法。打個比方，就是魯蛇要怎麼讓大家相信他有女朋友，但是又不告訴大家他女朋友是誰一樣。這樣的哲學思考其實就是涂林測試（女朋友的本質不重要，重要的是我能不能說服大家我有女朋友）。

我們將引用一位歐洲密碼學家 Jean-Jacques Quisquater 發表的科普文章《如何向你的孩子解釋零知識證明》 (How to Explain Zero-Knowledge Protocols to Your Children) 中的一個故事來解釋。

在一個環形山洞的中央有一道門可以從兩邊打開 (如下圖)，但是這道門需要一串四位數字的密碼才能打開。Alice (女生)宣稱她擁有這組密碼，但是她又不想告訴大家這組密碼是什麼。此時來了一個無聊的男生 Bob 希望 Alice 能證明她擁有這組密碼 (不知道為何所有的密碼故事都是由 Alice 和 Bob 當主角)。他們想到了零知識證明可以用來解決這樣的問題。首先，Bob 先站在山洞外面等待，Alice 進入山洞裏面隨機的選擇由 A 或 B 進入洞穴中。

假設 Alice 選了 B 並走進去之後，Bob 就會走入山洞內，並且隨機指定一個出口要求 Alice 從那個出口出來。如果Bob 要求從 B 出來，那 Alice 可以不用使用密碼就出來了，但如果 Bob 指定 A 出口，那 Alice 就需要使用密碼打開門，然後從 A 出口出來。

所以每進行一次這樣的測試 Alice 就有 1/2 的機會使用到這組密碼，所以一次成功的測試會保證 Alice 擁有這組密碼的機率為 1/2，連續兩次成功則表示 Alice 擁有密碼的機率提高為1-(1/2)²= 75%，...，10 次成功的測試則保證 Alice 擁有密碼的機率為 1-(1/2)¹⁰，已經超過 99.9%。所以當測試過足夠多次後，我們有很高的信心拍胸脯掛保證Alice 擁有這組密碼，即使我們從來沒有真正看過這組密碼。

零知識證明最常被使用來當作授權協定的基本架構。例如有一家公司規定某金額以上的金流進出需要董事長的授權，董事長這時候可能是在夏威夷的某個海島上度假，所以只能透過網路。一方面，董事長需要一把鑰匙(密碼)來進行授權，另一方面，鑰匙又儘可能不要暴露在網路世界中，減少被複製的機會，因此，最好的方法就是採用零知識證明來向員工證明，我擁有鑰匙，我是董事長，我授權了你的行為。

2. 隨機的 0 與 1 (pseudorandom generator)

在網路世界隨機產生 0 與 1 ，也是一個重要的事情，隨機數最常被用在需要隨機分配的地方(例如網路遊戲 WOW 分房機制)，它同時也是加密系統中的一個重要起始值。但是電腦所有的動作都是依照某個程式在運行，(愛因斯坦曾經說過一句經典名言: 「上帝不擲骰子!」，後來，事實證明，上帝不只擲骰子，還把骰子擲到我們看不見的地方去。這裡我要說的是，「其實電腦才不擲骰子!」)，所以沒有真正的隨機。

那如何製造出一段隨機的 0,1 數列，可它事實上又不是隨機的呢？製造方法有很多種，而涂林測試的哲學給了我們一個好的方法來判斷數列是否為隨機。「一個數列是不是隨機的？」我們模仿涂林換個問法「一個數列是不是可以產生隨機的效果？」

回憶一下涂林的中心思想是什麼？

只要猜不到就是對的!!!

所以如果一段機器產生的 0 和 1 數列我們無法有效的猜到下一個是 0 或 1，或者說猜對的機率大概就 1/2 的話，我們就可以說這個數列是隨機的，即使產生這個數列的函數是一個再簡單不過的函數。

隨機數的問題起源要比涂林測試早很多，但是一直要到更近代，約二十世紀末，人們才有好的數學定義來描述隨機數列，而定義的方式就如同涂林繞過定義「思考」一樣，密碼學家選擇不定義何謂「隨機」，但我們說一個東西是隨機的意思是它能做到跟隨機一樣的效果。

從上面這些例子中，我們其實可以發現，機率論在現代密碼學(加密法與授權)與通訊協定中扮演重要的角色，常常用來對某個系統進行安全分析。假設我們要對車子進行安全測試，代數與數論就是這台車子的設計圖，涂林測試或其他電腦科學的方法就是安全測試法，而機率論就是最後在計算這台車子到底有多安全的工具。

部分圖片取自Zero Knowledge Proof, Wikipedia, http://en.wikipedia.org/wiki/Zero-knowledge_proof.