[音樂播放] 演講嘉賓：歡迎回來，大家好。 這是CS50。 而今天，我們有很多的 有趣的東西可談。 不過，首先我要提醒 你的一些管理的事情。 本週是測驗之一，星期三 或為耶魯部 在週二和週四，週四。 有測驗點評 今晚在耶魯大學，下午5:30到7:00。 在哈佛，他們1昨天錄製。 每個人都可以觀看，網上。 此外，本週末或下週初， 我們有我們的最後CS50講座。 [呻吟]我知道。 它來了這麼快。 耶魯大學的學生將有一個活 講座在這裡的法學院 觀眾席上週五。 會有蛋糕。 哈佛的學生將有 桑德斯在最後一節課，週一。 也會有蛋糕。 此外，本週上週五，對於那些 你們誰是來紐黑文， 我們有CS50世博會。 我們有超過30 不同的組註冊 告訴你一切 從自主帆船， 該識別系統 數碼人像，計算機 音樂和電腦製作音樂。 所以，請加入我們的行列。 我認為這將是一個偉大的時刻。 但是，今天我們去 繼續談論AI， 關於人工智能。 和的事情之一 我們要拿到今天 是如何的想法 使用人工智能來解決問題。 現在，一如既往，讓我們開始 簡單的東西。 我們要開始 一個簡單的想法。 這就是使用搜索。 所以，想像一分鐘，我 有我需要執行的任務。 我想有該任務 通過一些軟件代理的自動化。 想像一下，我想訂一套 從航班，讓我們說，波士頓 到舊金山。 我可以通過我可以使用 精彩的在線搜索之一 工具，這是要幹什麼 基本相同的過程，我們是 要穿行今天。 但是，如果你沒有這種 工具，你會怎麼辦？ 好了，你可以看看和 看，說，我在波士頓。 哪些航班可以給我嗎？ 現在，也許我有三個 可能的航班從波士頓 將適合的時間 當我需要離開。 我能飛芝加哥。 或者，我可以飛到邁阿密。 或者，我可以飛到紐約。 然後，我可以看看每個 這些目的地城市之一 想想什麼位置 我可能達到 從每次個別城市。 因此，也許從芝加哥，我可以得到 直飛舊金山。 這是非常好的。 或者，我可以得到一個飛往丹佛的航班。 現在，也許該航班到舊金山 是一個完美的解決方案，對我來說， 但也許不會。 也許我尋找的東西 這是一個有點便宜 或者我的日程表更好一點。 因此，我可以尋找其他什麼 可能性可能是在那裡。 所以，我可以看看丹佛。 而從丹佛，好吧，也許 我可以得到一個飛行奧斯汀。 而從奧斯汀，也許我可以得到一個 飛往鳳凰城，從鳳凰城 到舊金山。 現在，我還沒有完成。 因為也許有一個 從紐約直達航班 到舊金山，非常適合我。 或者，也許有來自邁阿密的航班 通過丹佛，這是一個便宜很多。 所以，我還是得去。 我仍然要看看所有這些 我還沒有進行調查的城市。 我要徹底檢查所有的 我可能有機會。 因此，從紐約，也許我可以得到一個 飛往納什維爾，並從納什維爾 奧斯汀。 然後，我知道我在哪裡。 然後我知道，從奧斯汀，我可以 飛往鳳凰城，從鳳凰城 到舊金山。 如果我先飛到邁阿密，不過， 也許我可以從邁阿密的航班 納什維爾，或從邁阿密到奧斯汀。 現在我已經嘗試了所有 的可能性。 我已經建立了這個圖， 我顯示了所有可能的途徑 我也許可以採取。 當我們表示這些 那樣的問題， 我們不會代表 他們明確地為這個圖， 因為該圖沒有表示 在這裡，我們已經走了的歷史。 知道我的飛 鳳凰城到舊金山 不告訴我，我是否通過來 納什維爾，或通過丹佛，或通過邁阿密。 因此，我會做的是 我要這個同樣的問題， 我將它表示為一棵樹。 並在樹的根，在 頂，我會把我開始的地方， 波士頓。 並在波士頓，我將看看 所有的可能位置 我可以前往。 那麼，在這種情況下，我有三個， 芝加哥，紐約和邁阿密。 然後，我將探討各 這些孩子在樹上。 從芝加哥，我看到了 我有兩個航班。 我可以直接飛到 舊金山或丹佛。 現在舊金山，這就是我的目標。 這是我的目標。 這將是這棵樹的葉子。 也就是說，我永遠不會去 舊金山後的地方。 從丹佛，不過， 我可以從丹佛飛 奧斯汀，奧斯汀鳳凰， 從鳳凰城到舊金山。 而現在再說一次，我已經到了一個葉。 我可以再回到下一個 城市，我還沒有充分開發。 這將是紐約，去 備份到我的樹的頂端， 下來到紐約。 從紐約，我可以飛 納什維爾，從納什維爾到奧斯汀， 從奧斯汀到鳳凰，和 從鳳凰城到舊金山。 最後，一個城市我 還沒有看呢，邁阿密。 那麼，從邁阿密我說我有兩個 可能性，納什維爾和奧斯汀。 如果我飛到納什維爾，那麼好吧我飛 從納什維爾，奧斯汀，鳳凰， 到舊金山。 如果我飛到奧斯汀，我飛奧斯汀， 鳳凰城，舊金山。 現在我有一棵樹。 這是一個完整的樹。 這是所有的可能性， 所有我可以採取的路徑。 也就是說，如果我開始在 樹的頂部根 我再往之一 葉，它告訴我，不僅 在這裡我要 最終，舊金山， 但它告訴我的路線 我需要到那裡。 現在，這些哪一個是最好的？ 好了，一無所知 問題還沒有告訴我 其中哪些是最好的解決方案。 也許我關心最關心 我有多少時間是在空氣中， 或距離是我飛。 在這種情況下，芝加哥聖 舊金山可能是最短的數 在航空里程。 也許我在乎成本。 我們都知道直達航班 通常更昂貴。 所以，如果我拿這個，也許 一種倒退路線 通過邁阿密，納什維爾， 奧斯汀，鳳凰，也許那時 我得到一個較低的價格。 但我可以優化任何 我關心的標準。 誰擁有最好的 飛機上的Wi-Fi無線，或 機場擁有最好的食物。 而且每個可能 給我一個不同的解決方案 我看到的是最好的。 這些種類的問題， 我們要去哪裡 打造出了這棵樹 可能性，然後 看看每那些 各個路徑，並檢查 其中那些滿足了 一個標準對我們來說， 我們將調用 這些搜索問題。 我們有很多的 算法，其中一些 我們已經看到，去 探索那些樹。 我們能做到這一點的方式，我 只是做了一個深度優先搜索， 下降盡可能我們可以直到我們 打葉，然後再回來了， 而要正確回落。 或者，我們可以做什麼 所謂廣度優先搜索。 我們可以擴大一切 在頂部，然後 一切一行 下方的是，然後 一切下方的一行。 這些搜索樹 是十分重要的AI。 但他們並沒有完全得到 它的權利所有的時間。 事實上，在很多情況下 我們真正關心的， 我們要建立一棵樹， 但我們實際上並不 去決定一切的。 這些都是所謂的情況下， 對抗性搜索，也被稱為 如何寫玩遊戲 系統和得到報酬。 但這些都是種 系統在哪裡 可能會選擇當我去從 波士頓，我去旁邊哪個城市。 但在那之後，別人可能會 使在哪裡我飛行的決定。 因此，要建立這些 種結構，我們 將不得不採取一種 不同的方法吧。 我們不打算要能夠 只是通過搜索樹 了，因為我們沒有 一個是在控制 其中每個決策點的。 因此，讓我們想像一下一個簡單的 遊戲像井字棋。 我可以從一個 完全空白板。 而在井字棋， x被打首發。 所以，我能想到的一切 可能的行動是X可以使。 如果我是一個打 在X，這是偉大的。 我有九個可能 移動，我可以做到的。 我可以把一個X中的任何一個 這些九個位置。 然後從每次的，我 可以想像接下來會發生什麼。 那麼，在這種情況下，其他 玩家將獲得轉一轉。 Ø將獲得轉一轉。 和從每次的，有 將八個不同的地方 其中O可能將他們的標誌。 比方說，我決定，我是 打算把一個X在中心。 這似乎總是喜歡 良好的開放性舉措。 我可以看看下面的是， 八種可能的舉動，Ö使。 現在，如果我打X，這是美妙的。 我可以選擇哪一個我 去，一個在中間。 但是，現在O與其選擇。 而且我沒有控制 在這一決定。 但是從每次的 可能的倉板， 還有接著又 設置的可能性。 當說到做到 我重新開機，我就 來挑，說，好， 如果可移動到了，好了， 中間點在左邊，然後 我有一組的可能性 在那裡我可以把我的下一步行動。 從這些，我可以考慮全部 他們下方的可能性。 然後與O將得到 在那些選擇。 而且我可以繼續建設這個 樹，直到我到了點 在這裡無論是有人 贏得game--那 得到了被認為是一個葉node-- 或董事會完全充滿 也沒有人贏了。 而這也將是一個葉節點。 這將是一個平局。 但棘手的事情與這 如果這只是一個常規的搜索 的問題，我能 比方說，好了，X應該去這裡。 可是啊應該走的路那邊。 然後X應該走在這裡。 然後與O應該走的路那邊。 然後X可以得到三個 在一排，我贏了。 而本場比賽將超過 在五個動作，三對我來說， 二為我的對手。 但我並不總是得到選擇。 因此，不是，我們是 不得不做 是我們將有 有一個新的戰略。 而戰略 玩遊戲的算法經常使用 是所謂極小。 的中心思想 極小的是，我們 會挑，讓移動 我們的對手可能出現的最壞集 的動作，他們可以做到的。 它沒有我好 選擇一個移動的地方 我也許能取勝後 即，因為我的對手不是 要給我這樣的機會。 他們會選擇一些 可怕的結局對我來說。 所以我打算讓 移動，迫使我的對手 做一些事情對我來說更好。 好吧。 讓我們來看看這發揮出來。 因此，這裡是我們的偽代碼算法。 我們將產生 整個遊戲樹。 我們要打造 整個結構。 然後我們會去。 和在最底層，在每個 終端節點，在各葉片的， 我們將評估如何 可貴的是，在我身上？ 而我們要的價值的東西， 是為我好為陽性。 事情是不是為我好 將不太積極的，或零， 甚至為負。 因此，井字棋，也許 一場勝利對我來說是很好的。 這是一個。 而領帶是零。 而東西是一個損失 我，也許這是一個消極的。 所有的事情是更好的 這對我來說，得分越高 它接收。 從這些可能性在 底部，然後我們會篩選向上。 而當這是我選擇的機會 在一組備選的， 我會選擇一個的 拿到了最高分。 每當這是我的 反對者轉而選擇， 我認為他們將 選擇一個得分最低。 如果我做這一切的方式 到樹的頂部， 我已經選擇了一條路，讓 我說，我能得到最好的結果， 假設我的對手 使所有正確的行動。 好吧，讓我們看看 這個動作的第一。 然後我們將實際 看看它的代碼。 所以，想像一下我這棵大樹。 現在我不玩井字棋。 我想給你 東西一點點更豐富。 所以，我有一些遊戲， 有許多不同的分數 我可以有結尾。 所以我建立這個完整的樹。 而且我可以先移動。 我在樹的根。 我能選擇that--所以我得到 跨越該第一節點最大化。 然後我的對手隨便去哪兒。 然後，我現在能去一次。 這樣下來在底部，我有一組 可能性，我可以選擇， 遊戲中不同的終端狀態。 如果我在那很沮喪 最左邊的角落， 我看到，我有一個選擇 八，七，和一個兩者之間， 好了，我是一個得到選擇。 所以我要選擇 這其中的佼佼者。 我要選擇的八個。 所以，我知道，如果我 下來到這一點， 我就可以拿到8分。 如果我最終的下一個點 並且，在接下來的節點， 九，一，或六，好了，我 要選擇最好的那些。 我會選擇九。 如果我有之間的選擇 2，和四，和一， 我會選擇四，最高的。 現在，如果我看水平 上面說，我的對手 是一個得到做出這樣的選擇。 所以，我的對手到達 選擇，我想給他 的事情是怎麼回事 讓他八點， 還是我給他的東西，是 打算給他9分， 或東西是怎麼回事 給他四點？ 而我的對手，是 理性的，是怎麼回事 要選擇那些最小的， 是要選擇四個。 我能做到這一點 整個樹。 我可以去到 中間套三。 我可以進行選擇 一，三，五。 我能選擇。 所以，我選擇了五。 我可以選擇三種，九兩。 我能選擇，所以我選擇的九個。 六，五或二，我選擇。 我能選擇的六個。 在該水平之上，誰可以選擇呢？ 誰可以選擇呢？ 另外一個人，我的對手。 因此，他們選擇5個， 九，六，哪一個？ 聽眾：五。 演講嘉賓：他們選擇的五個。 他們能選擇的最低。 然後最後一個， 選擇一個，兩個或三個。 我能選擇，所以我選擇三種。 九，七，或兩個，我選擇九歲。 而11，六，或四個，我選擇11。 我的對手則選擇三， 9，或11，選擇最小。 他給了我三個。 然後最後在頂部 樹，我可以重新選擇。 而我得到之間做出選擇 四，五，或三。 所以，我把五。 如果我控制一切，我會 採取了導致11的路徑。 但我不明白做出這樣的選擇。 如果我走這條路。 我的對手會強迫我進入 這導致了三個選擇。 所以，我能做的最好的是 採取這一中間分支， 做出這樣的選擇這是最終 要帶領我到五點。 這就是極小呢。 好吧。 讓我們來看看這個。 因此，這裡的CS50 IDE是一個程序， 實現極小玩井字棋。 我們要打造 向上的表示。 我們將有兩個opponent-- 或者兩個球員，我們的電腦 播放器和一個人的球員。 玩家頭號將被打 在O.那將是機器的球員。 他們得到第二招。 而其他的球員，我們的 人類的球員，將是X. 而為了讓我的生活 一點簡單的，我要去 標記該玩家負值。 所以我只能乘 由負一換 之間的一個播放器和其他。 好吧，讓我們來看看 我們實際上是要幹什麼。 我們要確定我們的董事會。 這將是，嗯，我們要去 以允許它有三個由三個， 或者，我們甚至可以玩 五經五天或七天 七井字棋，如果你想 像的基礎上，一些尺寸D. 並且我們將有一對夫婦 輔助函數 那會做這樣的事情 初始化screen--還是遺憾， 初始化我們的變量，清除 屏幕上，繪製電路板在屏幕上， 一個檢查板 看是否 有一個贏家，一個 解析通過命令行， 只是助陣，一個讀取 輸入，以及一個函數調用極小。 這就是一個 我們最關心的。 但是，讓我們先來看看主。 我們做什麼？ 好了，我們要 分析我們的命令行， 只是讀，看看 維板，我們希望有。 我們將初始化我們的董事會。 然後，我們會輸入一個 野生大循環，反复 接受移動直到遊戲 贏了，或者有沒有向左移動。 每次我們去通過 循環中，我們將清除屏幕。 我們要開董事會在屏幕上。 我們是那種故意 這些抽象走為子程序， 所以，我們不必過於擔心 他們是如何發生的細節。 你必須在代碼後的今天。 如果你想看看通過 並找出，你可以看到他們所有。 但是，我們會得出一個板在屏幕上。 然後我們會檢查並 看，我們有一個贏家？ 曾有人贏了這場比賽？ 如果他們有，我們將打印 出了勝利的消息。 並且我們將結束遊戲。 我們還將檢查和 看看有沒有打領帶。 這將是很容易，看看是否有一個平手。 這意味著，所有的位已滿， 但還沒有分出勝負呢。 我們可以聲明領帶和完成。 那麼真正的meat--如果 它是一台機器的球員， 我們將允許 機播放器搜索 通過使用這種極大極小算法， 找到最好的招之能。 然後我們會把這個拉升。 否則，如果它是一個人的球員， 我們將閱讀從人的一些輸入。 然後，無論是人 玩家或機器播放器， 我們很少做一對夫婦 錯誤檢查位， 以確保它保持的範圍內 董事會的實際尺寸 我們有，要確保 這空間是空的， 沒有人的放 片中出現了。 然後，我們就放 一塊電路板上， 改變播放器到下一個層，和 增加了多少動作發生。 這對於主循環 我們井字棋遊戲。 極小的話，是完全 該算法之前我們。 唯一的調整是 我們已經取得了讓我們 可以播放高 維板是我們 保持這種所謂的深度額外的參數。 和深度只是說，如果我 通過樹向下搜索 而我得到這麼遠了 超出一定水平的深度 我只是不希望 再往前走， 我會停下來，只是 評估委員會在這一點上。 我會檢查，看看是否有一個贏家。 如果有一個贏家，我回報他們。 否則，我將經歷一個循環。 我會說，所有的 可能位置 那我可能 拿我的舉動，我會 建立一個假想的板， 包括我的舉動上板， 然後遞歸調用極小。 如果這是我的舉動，我可以找到 一個有足夠快的最大比分。 如果是我的對手的舉動，我們發現 那一定的最低分數的人。 和其他一切是 只是記錄保存。 好吧，讓我們看看這個運行。 其實，也許我們可以 找幾個志願者 拿出玩井字棋。 [聽不清]之一，和一個 多，二，就在那裡。 上來吧。 因此，讓我們繼續前進， 完全重新啟動此。 所以，喜。 聽眾：你好。 演講嘉賓：你叫什麼名字？ 聽眾：Gorav。 演講嘉賓：Gorav。 聽眾：我是萊拉。 演講嘉賓：而且萊拉，和萊拉，對不起。 上來吧。 Gorav，我們將讓你先走。 而我要問你是不是 非常良好的井字棋的球員。 好了，所有的壓力是關閉你。 讓我們來看看，雖然，我們的機器 玩家其實可以做一些聰明。 因此，繼續前進。 你會在哪個坐標輸入 你想將你的X研究。 A0，OK，機器已經 馬上，把它的標記在A1中。 把O於董事會。 好了，現在繼續。 您要在何處去？ C2。 我們的機器播放器已 廣場中間，擋住你。 所以這是一個很好的， 聰明的為它做。 你阻止它。 這是非常好的。 它開出角球那裡。 而且它會迫使你 取最後一個空間，B0。 而本場比賽以平局結束。 但它起到了合理的 遊戲對你，對不對？ 好，非常感謝，Gorav。 [掌聲] 好吧，萊拉，我們要去 她對你的遊戲在這裡。 聽眾：哦，太棒了。 演講嘉賓：我們打算給 你四乘四井字棋。 現在，在四乘四，你必須要贏 四成一排，沒有三連勝。 而這一切都屬於你。 所以蕾拉了D1。 我們現在要遵循 我們在這裡的電腦玩家。 三三井字棋是那種 東西，很容易對我們所有人。 但它仍然很好看 電腦玩家作出明智的舉動。 四乘四到達 是有點棘手。 做得好。 好吧，讓蕾拉的結束了。 哦，我們應該已經結束了在那裡。 但是，讓我們做一起來這裡。 所以蕾拉，謝謝。 做得好。 [掌聲] 因此，我們井字棋玩家進入 通過和發現的地點， 解決了他們使用這種極小。 而且我有一個深度設置 上，以便它 不會跑的太快， 這可能是為什麼 蕾拉能夠很好地向前走 她做到了，做得很好。 但是，這些系統只 經過和蠻力 走得更深，更深，更深， 並不斷尋找解決方案 他們需要，那些類型的系統 在這些相當成功的，好了， 標準的棋盤遊戲。 而事實上，如果我們看一下 三乘三井字棋遊戲， 這基本上是一個解決的問題。 這是一個美妙的圖 從蘭德爾·門羅在XKCD， 顯示哪些打動你應該 走，給你的對手的動作。 這是我們可以 隨便指定時間提前。 但是，當我們得到更多的會發生什麼 複雜的遊戲，更複雜的遊戲， 那裡有更大的板，更 的可能性，更深層次的戰略是什麼？ 事實證明，這 強力搜索仍 確實相當不錯，除了 當你到了點 其中，該樹是如此之大 你不能代表一切。 當你無法計算整個樹， 當你無法前進，並推 你自己，你已經點 得到整個樹在內存中， 或者是否可以得到它 在內存中，它只是 帶你太長時間進行搜索 它，你必須做一些更聰明。 為了做到這一點，你 必須做兩件事情。 首先，你必須要找到一些 限制你的深度的方法。 嗯，這是確定。 我們可以找到一些不錯的，最低限度 並說，你只能走這麼深。 但是，當你這樣做，這意味著你 有這些部分不完整的板。 而你要選擇，我喜歡 這部分不完整的主板， 或者這部分不完整的主板？ 而在我們的四經 4井字棋遊戲， 我們的電腦玩家得到了下來 的底部，它說， 我有兩個不同的電路板。 沒有一個是一個雙贏。 沒有一個是虧損的。 沒有一個是一個平局。 如何選擇它們之間？ 和它沒有一個 這樣做的聰明的辦法。 我們看到這種 評估發生的事情 隨著我們進入更複雜的遊戲。 國際象棋是一個很好的例子。 在國際象棋中，我們有，第一 所有的人，一個較大的電路板。 我們有更多的作品。 與這些片的定位 和方式，這些棋子 是非常重要的。 所以，如果我想用極小， 我需要能夠指定 並說，此板，其中， 沒有人贏了還是輸呢， 在某種程度上這比其他更好的 板，在那裡沒有人贏了還是輸。 為了做到這一點，我可能會做 像我可能只是 算我多少塊確實有 多少個，你呢？ 或者，我可以給不同 件的不同點。 我的皇后是20分。 你的棋子是一分不值。 誰擁有更多的積分總？ 或者，我可能會考慮一些事情，如， 誰擁有更好的板位置？ 輪到誰下一個， 什麼我可以 做評估更準確地 其中這些可能性 是沒有好 詳盡考慮 一舉一動都可能到來之後。 現在，使這項工作， 的事情的One 將成為非常重要的 對我們來說不只是直線運動 下降到特定深度 限制，但不能說， 這些想法一說我 已經是如此糟糕，它的 不值得考慮 所有的可能的方法 事情可以去每況愈下。 為了做到這一點，我們將添加到極小 一個原則叫做ALPH-β。 而α-β表示， 如果你有一個糟糕的主意， 不要浪費你的時間嘗試 找出它究竟是如何糟糕。 因此，這裡就是我們要做的。 我們將採取同樣的 我們收到的原則， 同樣極小極大類型 搜索，只是我們 要跟踪，不僅是 我們有實際價值，但我們會 跟踪的最佳可能 值，我能得到， 和最壞的可能 結果，我可以有。 而任何時候，最壞的可能 事情正在尋找可能的是， 我會拋棄樹的一部分。 我不會甚至不屑 看它了。 好了，所以可想而知，我們開始 與此完全相同的博弈樹。 而現在我們將去 再次回落，一路下行 到左下角。 而在這左下角，我們 看看我們評估這款主板。 也許這是一個四乘四井字棋 板，或者這是一個國際象棋棋盤。 但是，大家看看吧，我們評估 它，我們得到八的價值。 在這一點上，我們知道 我們將得到至少 八點從這個底部決定。 不要緊什麼其他 兩個是，這七有兩個。 它們可以是任何的值 他們想要的。 我們要得到的 至少8分。 好吧，但是我們可以 繼續檢查。 也許其中之一是超過八個更好。 我們來看一下七個。 那是超過八個好？ 沒有，這並不改變 我們的意見都沒有。 我們看看兩個。 那是超過八個好？ 沒有，這並不改變 我們的意見都沒有。 所以，現在我們知道我們已經用盡 所有存在的可能性。 我們不會得到 任何超過八個好。 我們將得到完全八強。 因此，我們改變節點 說了，就是現在是必然的。 我們去了一個級別上面。 現在我們知道的東西 有關最小化水平。 我們知道，我們永遠不會得到 八個多百分點，如果我們再往 這個方向努力。 因為即使這些 其他兩個部門轉出 是夢幻般的，值得 成千上萬的每一個點， 我們的對手會給我們 最低限度，並給我們八。 好吧，好吧，讓我們來看看。 我們會繼續走下去的道路。 我們再往左邊的中間。 我們往下看，我們看到有一個九歲。 我們知道，我們將得到 至少有九個點按下去 這中間的道路。 而在這一點上，我們就可以暫停。 我們可以說，看，我 知道在水平以上， 我會得到不超過八個 通過走這方向點。 但是，如果我去攔腰 路徑，而不是離開路徑， 我會得到至少9分。 我的對手永遠不會 讓我走這中間道路。 他們開始選擇。 而且他們會選擇 路徑向左朝8， 而不是下來，對中間 什麼是至少9分。 所以在這一點上，我會停下來。 我會說，你知道嗎？ 我沒有看任何 比較下來這個方向努力。 因為我永遠不會去那裡。 我可以跳過那一個， 我可以跳過那六， 因為這是永遠也不會發生。 所以，我會去，我會 考慮下一可能性。 我去那裡，我說，我看到了兩種。 我知道，如果我到了這裡，我 將得到的至少兩個。 好。 我繼續下去。 我看到一個四。 我知道我會得到至少有四個。 仍然有很多的 四個和八個，雖然。 所以，我繼續下去。 我低下頭，我看到有一個。 好吧，我知道，如果 我走上這條道路， 我將能夠選擇的四個。 什麼是我的對手會怎麼做？ 東西之間給了我 八，東西給我四， 和東西 讓我至少九個， 好了，他要給我四。 我現在知道了 最頂端，我要去 要能得到至少 四點了這個遊戲。 α-β的整體思路 是切斷部分樹， 我不看他們了。 但它仍然看起來像我一直 看著很多樹。 讓我們繼續下去。 現在，我們將下井下一個。 唐氏在底部，我找一個。 我知道我會得到至少一個。 我繼續尋找。 我找了三人。 我知道我會得到至少有三個。 我繼續下去。 我找了五位。 我知道我要送五 如果我在這條道路下不來。 而且我也知道再 我的對手，如果我 選擇中間 三大選擇， 他要給我 東西是五個或更少。 好。 我可以繼續去那裡。 我往下看，我 可以說，我該怎麼 拿到如果我往下走中間路線？ 我要得到的，還有三個在那裡。 我要得到的東西 這是至少三個。 目前仍然之間的事情 三和五，所以我一直在尋找。 哦，九，我肯定會 採取了三個。 我要拿到至少有九個 如果我走這中間道路。 現在，我的對手將停止，並說， 你看，有沒有一點了。 我知道我的 最小的對手，他的 要給我的東西，是 小於或等於五， 而非件事是 大於或等於9。 我停下。 我不看任何更多的那個。 我繼續下去。 我小看這一個。 下到谷底，我發現一個六人。 我知道我會得到至少六個。 而我能做些什麼？ 我可以停止。 因為有之間的選擇 東西是至少六個 而東西是 不到五年，他的 要給我的事 這是不到五年。 現在我知道我要去 要得到完全的選擇。 我要拿到五次選擇。 我回去到頂部。 我要去哪家 東西之間進行選擇 這是大於或等於4， 或東西是等於五？ 我要帶的東西 這至少五個。 我往下走過去的路，所有的 下到谷底的方式。 有一個。 好吧，至少我要拿到一分。 我繼續下去。 二，哦，這是比一個好。 我要拿到至少兩個。 我找了三人。 我知道我會得到三個。 和上面的一點， 我的對手是怎麼回事 給我的東西的 小於或等於3。 現在我可以停止。 因為在我的選擇是 能夠得到一個五我的對手 給我的東西不到三年， 我總是會拿這五。 所以，我不評價說 樹的底部都沒有。 現在，這似乎很小。 但是，當算術一點位， 大於和小於 可以切掉整個地區 這種指數級增長的樹， 這導致了巨大的 儲蓄，儲蓄量 這是足夠大的，我 可以開始玩競爭力 在更複雜的遊戲。 好吧，如果我們看一下尺寸 和不同的遊戲的複雜性， 井字棋是我們簡單的例子。 我們三個了小板，三。 我們得到的，最多，平均為 四種不同的選擇 因為我們去通過遊戲。 我們有地方約10至 第五個可能的不同葉子。 而建設一個井字棋 播放器，好了，我們只是做了它。 小菜一碟。 如果我們去到更多的東西 複雜，如連四。 你還記得這個遊戲， 你把小的令牌？ 這是一個六七板， 不是更大，仍 有大約相同的分支 因素，因為井字棋。 我有四個選擇 在那裡我可以把事情研究。 但現在，我已經得到了很多 引出，10到21的功率。 在這個時候，很容易 以至於我們解決這個問題的時候了。 跳棋，更complex--您 八牌上看到一個八。 你只能在半 他們在任何時候，雖然。 你已經有了一個分支 因素是關於2.8。 好了，我們已經有一對夫婦 移動可以採取。 你得約10至31葉， 大，大，和更大的空間。 當我不得不通過搜索 那些越做越大的空間， 這時候，像α-β和 能夠切掉整個分支 就顯得至關重要。 現在，跳棋在1992年很容易。 一種稱為計算機程序 奇努克擊敗世界跳棋 冠軍馬里昂·汀斯利。 從那以後，沒有 人類高手玩家 之所以能夠擊敗最好的 計算系統。 如果我們考察一下國際象棋，現在 再次，我們八板有八個。 但我們有更複雜 件，更複雜的動作。 我們有大約一個分支因子 35，35，平均可能的行動 我可以和狀態 空間，若干葉 是的成長到10到123電源， 數量巨大的可能性。 即使如此，現代的處理器 能夠成功地做到這一點。 在1995年，然後在1997年，一台電腦 程序調用深藍由IBM建造 可以運行在一個巨大的超級計算機 擊敗目前的世界冠軍， 卡斯帕羅夫。 這是一個轉折點。 今天，雖然，相同的處理 電力坐在我的MacBook。 處理速度保持 越走越快。 我們可以評估越來越多 板越來越快。 但更重要的是，我們有更好的 評價功能，更好地修剪 的方法。 所以，我們可以搜索 空間更加複雜地。 該板的最大 遊戲，我們能想到的， 像圍棋這 有一個19 19板， 現在突然，我們過去點 其中，計算系統可以贏得。 有沒有計算 系統在那裡 可以擊敗一個專業棋手。 關於最好的系統今天排名 排序好的業餘水平。 所以還是有相當多的出 那裡，你不能去還。 好吧，這些 傳統的棋牌遊戲， 這些類型的系統，其中，我們 建立這個極小，不管它有 α-β與否，這些算法的工作 因為有一定的限制。 我們有完善的信息 關於世界。 我們知道，所有的作品都是。 世界是靜態的。 沒有人獲得移動 左右，而我是個 坐在那裡想，採取輪到我了。 有一個動作空間的離散。 我可以把我的棋子在這裡， 或者，我可以把我的棋子在這裡。 我不能把我的棋子上 該行兩個廣場之間。 最後，操作 是確定性的。 我知道，如果我說， 車騎士三， 我的車是要結束了在騎士 三，只要它是一個有效舉措。 有沒有這方面的不確定性。 現在，當我去更多 不同類型的遊戲， 我們必須打破這些假設。 如果我去的東西是什麼 喜歡經典視頻遊戲？ 這裡有一個選擇的視頻 遊戲從雅達利2600。 我有什麼了嗎？ 我有青蛙，空間 入侵者，陷阱和Pac-Man的。 什麼樣的環境 我必須在這裡嗎？ 其中這些假設 我必須打破？ 嗯，這取決於遊戲。 我會下棋的2600，和 它會成為像從前那樣。 對於大多數這些系統的，有 關於世界的完整的知識。 有完全 確定性的行為。 但通常情況下，世界 不再是靜態的。 也就是說，當我坐在那裡 在等待的東西在移動。 鬼都來接我。 蝎子是繼我的下方。 太空侵略者 越來越近。 我們如何能做到針對這些？ 幾年前，谷歌 曾要求項目 DeepMind，他們培養了計算機 節目玩雅達利2600遊戲。 如果你認為這是不嚴重 企業，他們的研究結果 發表在Nature，所以 只是好出版物 因為你所能得到的。 下面是他們如何執行。 他們有一個算法，坐 看著剛剛屏輸入。 它任何沒有得到指令 關於遊戲的規則。 它本來是要弄清楚， 根據其成績，以及它如何在做什麼。 這是用什麼系統 所謂強化學習。 也就是說，它看著它的得分。 如果它得到了一個不錯的成績，它說， 我應該記住這些事情。 我應該再做這些。 如果它有一個不好的分數，它說， 我不應該再這樣做這些事情。 這是性能 這些訓練有素的系統 允許一玩 幾個小時的每場比賽， 相比較專業的玩家。 因此，對於所有的遊戲的 這條線的左側， 這個自學成才的電腦程序 跑贏了職業玩家。 而對於一切的 正確的職業玩家 仍然是最好的。 對於一些知道 一無所知的規則， 一無所知的結構 遊戲，這是令人印象深刻的表現。 而這正是我們今天能夠做到。 OK，你說的，但如果我們 想想AI在遊戲中， 通常我們想到的 事情，我們實際上可以 坐下來對戰。 如果我坐下來和我玩 星際爭霸，還是我玩免費篩， 計算機對手是 人控制的虫族， 或控制其他文明。 如何做到這些的球員 很難找到他們的舉動？ 那麼，這些遊戲的結構 大致相同的方式作為我們的下棋， 這些遊戲，我們會 共同呼籲四個X遊戲， 探索，expand--忘記的。 他們是什麼？ 探索，擴張，並熄滅， 我認為這是最後一個。 但是，他們基本上 探索和征服的遊戲。 通常，計算機對手 有有有限的信息。 他們不知道到底是什麼 會在後面的戰爭的迷霧。 他們不明白，看看有什麼 你有你的庫存。 這裡有一個環境是動態的。 一切都在不斷地變化。 你不要坐下來， 迫不及待地把你的舉動。 但大多數事情還是離散的。 我已經把我的城市在這裡。 或者，我已經把我的城市在這裡。 一切是確定性的。 當我說，把我的單位在這裡，我單位 移動這裡，除非障礙物突然 進場。 現在，這還不是全部電腦 今天比賽是在那裡。 如果我去和我玩一款第一人稱類型 遊戲，像小偷或輻射 或者天際，或暈，現在 我的電腦對手 是在那裡有 一個非常不同的情況。 他們再次，有限的信息。 他們只能看到一個 某些字段的圖。 環境仍然是動態的。 事情正在發生變化所有的時間。 但現在我有一個更 連續動作的空間。 我可以只偷看一 點點出了門道。 而一些遊戲，我 行動是隨機的。 我去嘗試跳過那道牆， 但我有一個失敗的機會。 這些類型的遊戲越來越近 和接近類型的控制器 我們建立的機器人。 在機器人技術，我們必須假設 我們有限制的信息。 我們有傳感器 給我們介紹一下這個世界。 我們有一個不斷更新的， 動態環境。 我們有一個世界中，空間 連續的，而不是離散的。 而且我們的行動，當我們試圖 其中，有一個失敗的機會。 而事實上，現代的遊戲 控制器的最後一戰的對手， 或用於在天際那些的NPC，基本上 經營小機器人的架構。 他們感知世界。 他們建造了世界的模型。 它們計算基於一組的 目標，他們希望實現的目標。 他們計劃基礎的行動 在他們所知道的。 而這些都是完全一樣的種 對我們構建機器人系統。 因此，這些結構，以 把這個重新走到一起， 往往是相當一致的。 因此，讓我們看看我們是否能夠看到。 讓我們回到我們 井字棋的例子。 而我要問我的幾個 博士後上來幫我。 所以陳明，和Alessandro和 奧利維爾，如果你們會來。 而我會需要 一對夫婦的志願者 好吧，我看到了一個手右上 中間有。 讓我帶一個，有人 進一步在後面可能。 好了，在那邊。 上來吧。 好吧。 因此，讓我們說蓋了下來。 如果你們會來的權利 回來在這裡對我來說太棒了。 所以這是一個叫百特的機器人。 和Baxter是一個機器人，這是一個 商業平台，設計 由一家名為反思。 而這個機器人被設計 對於小規模生產。 但今天我們要 用它玩井字棋。 現在，這個機器人也未嘗 這是比較獨特的。 因為如果我站在任何地方 接近標準的工廠自動化 系統，我會非常嚴重 危險受傷。 巴克斯特，但是，被設計成 相對安全進行交互。 所以，我可以把這個機器人。 你可以看到這是一個有點 位靈活，因為它到處移動。 我可以重新定位 在這裡我想它去。 現在，在一個正常的機器人系統， 我們將有一組接頭在這裡 這將是直接 響應位置指令。 他們不一定會在意 如果他們通過戶外運動， 或者，如果他們被感動 通過我的胸腔。 好。 並且通常，如果你 這裡的工業體系， 你會去遠不及它。 會有黃色 安全膠帶周圍的一切。 這個系統有一個 稍有不同的設計 要友好，更容易 人們互動， 中，在每一個關節，有一個春天。 而非控制 一個準確的位置， 我們控制一定量的 扭矩，一定量的力， 我們希望成為的那個春天。 好了，所以讓我 在這裡把我們的志願者。 你好，你的名字是什麼？ 聽眾：路易斯。 演講嘉賓：路易斯。 很高興見到你。 和？ 聽眾：大衛。 演講嘉賓：大衛。 很高興見到你。 如果你們會等 這裡適合第二， 我想給你 有機會做到這一點。 所以這個機器人，如果你來了 如果你輕推就可以了， 你會看到， 它移動一點點。 如果你抓住它的權利 這裡在手腕上剛 其中，以上這些按鈕，它 看起來你應該抓住的按鈕， 但搶正上方相反，你會 能夠輕輕地操縱它 通過空間。 路易斯，你想給它一個嘗試？ 所以給它一點點 推下手。 然後，如果你把你的手指 在那裡，並抓住它， 因為它會動你呢。 好吧，你想給它一個嘗試？ 上來吧。 所以給它只是一個溫柔 推那裡開始。 你可以感受到是什麼感覺。 然後，如果你抓住它那裡， 你就可以操縱左右。 好。 因此通常，這種機器人的會 用於小規模製造。 而且我要正義之舉這個手臂 淘汰下來的方式一點點在這裡。 但是今天，我們將使用 同樣的井字棋播放系統 根據我們先前建立極小。 好不好？ 所以，你們是各 要玩遊戲。 路易斯，你會是第一個。 讓我抱起來這裡進行了第二次。 我要你站在正確的 在這裡，只是讓每個人都可以看到你。 你們是不是在這裡設置？ 機器人：歡迎。 讓我們玩井字棋。 之前，不要抓住你的令牌 我說，這是輪到你了。 我開始遊戲。 這是輪到我了。 演講嘉賓：現在，如果你可以採取的一個 你的作品，並繼續前進，並把它。 機器人：它是輪到你了。 [笑聲] 這是輪到我了。 [笑聲] [笑聲] 輪到你了。 演講嘉賓：人類是 你指望在這裡，路易斯。 機器人：它是輪到我了。 演講嘉賓：所以，巴克斯特 在這裡成功地阻止。 機器人：它是輪到你了。 這是輪到我了。 輪到你了。 這是輪到我了。 演講嘉賓：我們將讓巴克斯特 在這裡完成了它的最後一步。 [笑聲] 機器人：這是一個平局。 我會贏得下一次。 [笑聲] 演講嘉賓：好的， 非常感謝，路易。 謝謝。 你可以走這條路。 機器人：我開始遊戲。 演講嘉賓：所以讓我來解釋一下 給你多一個小 前位，我們在這裡得到了複賽。 究竟是怎麼回事？ 因此，機器人有一個攝像頭向上頂在這裡。 而且它低頭看著板。 而且它看到是否 它有一個紅色的O或藍色 白色X.由於這些獲得放置在 板，這是基本相同的輸入 我們將從讀取 從我們的屏幕我們的數據結構。 它的運行相同 極大極小算法是 能夠找到在哪裡 把一個很好的象徵。 然後我們給有關的命令 在這裡我們想令牌放置。 手臂動了。 它採用真空夾具適用 一些吸引到木件， 把它撿起來，將其移動到右邊 現貨方面，然後釋放抽吸 並把它。 好吧，我們要去 給它多一槍 一個稍微聰明的球員在這裡。 你準備好了嗎？ 好吧，如果你站在直到 這裡為A--出現這樣的局面 所以你可以看到大家。 然後[聽不清]。 機器人：它是輪到我了。 演講嘉賓：百特將啟動。 輪到你了。 這是輪到我了。 輪到你了。 這是輪到我了。 [笑聲] 演講嘉賓：[WHISPERING]剛 讓他繼續前進，取得勝利。 機器人：它是輪到你了。 演講嘉賓：這是確定的。 機器人：它是輪到我了。 [笑聲] 我贏了。 [笑聲] 我開始遊戲。 演講嘉賓：好的，非常感謝你。 好吧，我想我們還有時間 多了一個優秀的井字棋的球員， 誰可以把這個事情 匹配，誰知道他們在做什麼。 [笑聲] 誰是要在這裡是我們的冠軍嗎？ 好吧，你的朋友自告奮勇你。 這對我來說不夠好。 再告訴我你的名字。 聽眾：塔米爾。 演講嘉賓：塔米爾，很高興見到你。 好吧，再次，我們打算把你 直到這裡，所以每個人都可以看到你。 你是我們的代表 在這場比賽了。 巴克斯特是哦，呵呵。 還是遺憾，一個OH和一個。 而它給你在這裡。 百特將獲得先動，雖然。 所以。 機器人：它是輪到我了。 [笑聲] 輪到你了。 這是輪到我了。 輪到你了。 這是輪到我了。 輪到你了。 [笑聲] 機器人：它是輪到我了。 演講嘉賓：這是一個很大困難時， 你站在這兒，伙計。 [笑聲] 機器人：你們人類是那麼容易被擊敗。 [笑聲及掌聲] 演講嘉賓：非常感謝。 機器人：我贏了。 我開始遊戲。 演講嘉賓：好的，十分感謝非常 太多的奧利維爾，並亞歷山德羅， 和陳明。 [掌聲] 我想提出最後一點。 所以巴克斯特在非常 到此為止，被騙。 這是出乎意料的。 一個夢幻般的 有關AI的事情是，我們 做工作，AI，使我們能夠建立 真的很有趣，智能化 設備。 但是，我們也愛做的工作 因為它告訴我們什麼 有關如何人類是聰明的。 人們所喜愛的 從我的實驗室研究是 看會發生什麼時 機器意外作弊。 我們這樣做原本不 百特玩井字棋， 但有一個名為淖較小的機器人， 誰發揮剪刀，石頭，布。 有時後 打很多很多 無聊的剪刀，石頭，布的遊戲， 機器人將拋出一個手勢， 輸了，然後突然改變 它的姿態，說，我贏了。 [笑聲] 現在，有時我們也不得不機器人， 只是作為一個控制，拋出一個手勢， 贏了，並改變其姿態 輸了，丟了比賽， 作弊是為了減肥。 這是幾乎沒有引人注目。 該秘籍機器人 為了贏得人們 到，就好像它是響應 出去找他們，喜歡它 正在積極尋求他們的破壞。 [笑聲] 它成為一個代理。 這就像一個人。 它有信念和意圖。 而且這不是善意。 和機器人拋出 遊戲只是故障。 這只是一個損壞的設備。 讓我告訴你一些例子 的，從我們的一些參與者。 因此，這裡的作弊是為了減肥。 [視頻回放] - [聽不清]獲勝。 讓我們玩。 -Wait，是什麼？ - [聽不清]獲勝。 讓我們玩。 [聽不清]獲勝。 讓我們玩。 演講嘉賓：這裡的作弊取勝。 - 是的，我贏了。 讓我們玩。 - 你不能這樣做。 [笑聲] - 是的，我贏了。 -你作弊。 現在，您被騙。 - 是的，我贏了。 - 嘿，你騙子。 你欺騙，超級騙子。 [結束播放] 演講嘉賓：這些不同 反應迅速 改變我們的感知設備。 這是否意味著， 我們特意打造 該作弊，因為這是機器 我們能做的最好的工程？ 沒有，但它告訴我們什麼 真正有趣的人。 這件事欺騙了你和 偷了你的勝利，這是 東西是活的，這是 動畫，那是出去找你。 它具有的精神狀態。 它有信念。 它的意圖。 這件事，手中的 遊戲中你，那不是。 這只是發生故障。 這是在許多方面它為什麼 易投擲遊戲的孩子。 但是，如果你試圖欺騙他們 和排序的取得勝利 如果，你知道的，只是為了縮短 比賽中，他們會抓住你的時候了。 這些種的效果是 我們看到走出來的AI， 他們教給我們很多關於自己。 好吧，這就是它的今天。 非常感謝大衛， 哈佛製作團隊 對下來。 [掌聲] 我們會看到你的測驗之一， 然後一最後一次演講。 祝你有美好的一天。 [掌聲] [音樂播放] 大衛·馬蘭：好吧，我們可能需要 引入加密一些， 對？ 因為那麼頭 這些HTTP請求將 炒使任何人 試圖嗅出你的流量 實際上不會能夠看到它們。 那麼，有什麼辦法解決這個問題？ 好了，我們需要真正引入 加密入公式， 這樣，當該人是 從A發送數據給B， 我們可以安全地send-- [笑聲] 在一個方式中的信息，該 攻擊者無法，其實，看到它。