An Introduction to Applied AI

Presentation on theme: "An Introduction to Applied AI"— Presentation transcript:

1 An Introduction to Applied AI
Focus On Computer Games ‧演算法的簡單介紹 ‧目前的發展與未來的展望 余承叡

2 什麼是 Computer Game？ Computer Game 包括：五子棋 Go-moku、
、黑白棋 Othello、西洋棋 Chess 、圍棋 Go 象棋 Chinese Chess 等棋類。當電腦能與人類對奕，就可稱為 Computer Game。

3 AI 的研究和 Game 有什麼關係？ AI 應用在 game 上的好處：勝負清楚， ，能與人腦比較，且需要有系統、有對策地解決對手。
但這個解決對手的方法並不是那麼容易.. 每個人都有自己喜歡的一套下法。 若 Computer Game 能好好發展，這樣的 AI 有朝一日能應用在 High-performance Computing 的基礎上。

4 CG 演算法的基礎 目標--盡量接近人腦的思考方式 Evaluation Function
對於棋盤上目前的形勢給予一個相對分數的 method. 以象棋為例： 紅方目前的 EF 為零分

5 CG 演算法介紹 Tree Searching. 完全解決了五子棋和黑白棋 展開全部的可能性..

6 但以目前的軟硬體能力.. 對於西洋棋，這樣的展開要花上好幾百年。
Method – minimaxing 首先先把 EF 值加進來.. 但這個 tree 會成對數成長，非常龐大，若在西洋棋中每手要算8步，有 2*1012 個 node。

7 如何不失真地把tree 減小？ Alpha-beta pruning. 除去不可能實行的 sub-trees.

8 如何得到 EF 的值？ 從許多比賽，或專家的意見統計得來。 但每個人有自己的棋風，不能確定哪一種下法比較好。
以現在的科技，能夠解決的問題大多是能找出解題的公式，向 CG 這樣的 problem 比較難設計。 如果真能找到必勝的公式… 如果找不到，但仍設計出不錯的 CG…

9 Complexity 的比較 E : 從第一手開始到結束時，能落子的點數。
A : 若要完全把 tree 展開，需要多少 tree node。 Game log10(E) log10(A) Computer-Human results Othello 30 58 Logistello > H Chess 50 123 Deep Blue >= H 15x15 Go-moku 100 80 The game is solved 19x19 Go 160 400 Strongest Go program << H

10 最難 design 的 CG 是.. 圍棋是變化最複雜，最難設計的。這是一盤剛結束的圍棋
暨西洋棋之後，圍 棋應是下一波被 AI 衝擊的對象。

11 結語 目前發展 AI 最困難的部分除了技術之外， 就是電腦需要我們給予很明確的步驟，才 能一步步地解決問題。Computer games 大
都是 P Problem，不能用傳統的方式解決， 而生活中的問題也大多都是 P Problem…