這次我們的term project選擇的主題是X3D

 

顧名思義，X3D即是使用XML可使在web上呈現3D物件的技術

 

類似的東西在幾年前就有了，印象比較深刻的是shockwave，不過當時技術還不太純熟，硬體配備也比不上現今，以現在的觀點去看當時的web 3D實在是不值一哂

 

隨著科技的進步、硬體效能的提升，現在的PC要處理一些簡單的3D繪圖運算並不困難，OpenGL和Direct3D也早就是普遍的技術，故X3D的發展也比當時VRML(X3D的前身)等web 3D技術來得順利許多，X3D使用XML，即有了跨平台、結構化等特性，並且XML已是多數網頁工程師所熟悉的language，DTD、schema也都可在X3D裡使用，並且可使用Maya、3DSMAX、AutoCAD等常見的3D繪圖軟體來強化X3D。

 

這次我們的最終目標是打算將小民在Second Life裡做的3D物件利用LSL(SL的語言)輸出，再轉為XML格式弄成X3D在web上，不過小民說要轉成X3D在數據的處理上可能會遇到很大的問題(再說我們對X3D也並不熟)，總之先訂下一個目標，之後再去嚐試看看。

 

一開始沒注意到課本上有說要用xml validator

結果直接把.xml丟上IE 發現會顯示 <!DOCTYPE addressBook (View Source for full doctype...)>

 

 這邊提供一下微軟的xml validator

http://msdn.microsoft.com/archive/default.asp?url=/archive/en-us/samples/internet/xml/xml_validator/default.asp

1.點選Download sample

2.執行下載的xml_validator.exe(它是自我解壓縮檔)

3.用IE開啟validate_js.htm 或validate_vbs.htm (其實我不知道這兩個有什麼不一樣...|||)

4.貼上url或檔案位置(e.g. file:///C:/xxx )

5.click VALIDATE  就能知道你有沒有寫對了 

"

資工三甲  493511553  樓維恩

 

Chapter1 前言

 

每個人從小到大或多或少都玩過電動玩具，而最早的電玩遊戲都是單人遊戲為主，單人遊戲中，益智遊戲也佔了很大的一部分，棋弈類遊戲，包括象棋、圍棋、跳棋、五子棋、西洋棋等，都是相信經典的遊戲，也是打發時間的好玩具，可以挑戰人腦是否能贏過電腦，而電腦沒有大腦，只是一堆電子零件，它又是怎麼思考的呢？它怎麼知道下一步棋該怎麼下呢？在幾十年前，軟硬體設備遠不如現今的年代，就已經有了這類遊戲，這次的目的主要在探討這些遊戲中所使用的演算法。

 

[@more@]

Chapter2 背景

2-1  Search Tree的分類

對於一般的益智遊戲或問題探討，解題的方法就是使用「search」，尋找一個最佳的解，一般search都會搭配tree的資料結構來表示，而解決一個search tree的方式主要有兩種：

1.     Data-driven search，又稱Forward chaining，即指從起點出發，尋找終點。通常是我們知道每個node的狀態(條件、規則等)。

2.     Goal-driven search，又稱Backward chaining，和Forward chaining相反，是由終點出發，回頭找尋起點。某些情況下，我們不清楚「規則」，不了解問題發生的原因，但知道其結果，則使用Backward chaining。

在很多情況下，Backward chaining會比Forward chaining更好用更有效率，最明顯的例子就是每個人都有玩過的走迷宮，常常我們會發現要從起點走到終點很難，可能繞了一大圈結果發現是死路，但從終點往回走卻非常簡單。但是Backward chaining的方式限定於"已知終點"的情況，故Forward chaining還是比較泛用的方法。故此次決定著重於Forward chaining的部分。

專家系統(expert system)也是採用Forward chaining的方式，從已知的原因(條件)推導出未知的結果。

 

 

Forward chaining最常用的兩種演算法為：

1.     Depth-First Search

Depth-First Search是一種很常用的搜尋演算法，其名的由來在於它是往最深的那個點走，每一條路徑都走到底，若沒路了再回頭

 

其用了”Chronological backtracking”的方法，若走到死路則回頭。在電腦應用上，尋找資料在硬碟中的位置也是使用Depth-First Search。

但在某些情況下，若問題的複雜度很高，其tree的展開非常的大，甚至趨近無限大，使用Depth-First Search將會非常沒有效率甚至找不到解。

2.     Breadth-First Search

和Depth-First Search相對的另一個方法是Breadth-First Search

和Depth-First Search往最深的level走下去的方法不同，Breadth-First Search是先將最淺的level的每個node走過一次，再往下個level走。適合用在當tree的深度很淺的時候，效率非常的高。但若目標(終點)在最深層，Breadth-First Search的效率就遠不如Depth-First Search。

2-2  Search方法的特性

上面介紹了一些不同的search方法，不同的方法在不同的問題上會有優劣，適合解決的問題也不同。故有幾樣特性用來評估一個演算法是否適用在某個問題：

■ complexity

■ completeness

■ optimality

■ admissibility

1.     Complexity：分為time complexity和space complexity，time complexity最直觀的方式就是計算其總共花了多少時間，但一般使用Big-O描述time complexity而非一個時間值。space complexity則是記憶體(儲存空間)的使用量。complexity通常只用來衡量一個演算法的解是否合適，因為通常最快的方法找出的解都不會是最好的。

2.     Completeness：第二個評估的特性就是「是否解出答案」，很簡單的，若演算法無法解出答案，則對這個問題完全沒有幫助(有時候可能問題本身就是無解，但必須能發現”無解”這個解答)。

3.     Optimality：有時問題可能不只一種解答，若能找到最佳的答案則稱之”optimal”。optimal的演算法不一定有效率，它可能要花較多的時間去尋找答案，但找到的答案卻會是最佳的。

4.     Admissibility：有些時候optimal的定義會被當成是「最快的」，這時就使用admissibility來代替optimality，而optimal則用admissible來代替。

 

 

Chapter3  Game Tree和實際應用

3-1 Game Tree

Game Tree，簡單的說，就是用tree來表示目前棋局的情況，和之後可能的走法

Game Tree實際使用的演算法有很多種，在這裡只討論其中兩種：

1.     Minimax：

在Minimax的演算法中，將tree的每個level從root開始依序設為MAX、MIN、MAX、MIN…

使用Depth-First Search，在MAX的level時，從其child node中挑選最大的值放入；在MIN的level時則從其child node中挑選最小的值放入，最後回到root的值就是解。

2.     Alpha-Beta Pruning

Alpha-Beta Pruning演算法是在Minimax的演算法上加入α值和β值，分別表示MAX level node的下限和MIN level node的上限，目的在於將tree中不必要的分枝給修剪(cut)掉。

 

若假設tree的深度為d，每個node的child數都為b，總共的node數為n(n=b^d)

則Minimax的time complexity為O(b^d)，而Alpha-Beta Pruning的time complexity可減為O(b^d/2)，明顯的比Minimax的演算法好。

3-2 實際遊戲應用

找了一些比較簡單常見的遊戲，和解決這些遊戲的實作方法，但在此只簡單介紹一些所找到的一些文獻中的實作方法，並不詳細敘述其步驟。

■井字遊戲

3*3的井字遊戲所有可能的排列組合共有3⁹=19683種，比起西洋棋或其他遊戲擁有上兆種排列組合，井字遊戲算是非常簡單的。

在3*3的井字遊戲中可以直接使用Depth-First Search或Breadth-First Search，在對手下了一步棋之後，直接評估剩下的8種的可能走法，再進一步評估更深層的更多可能解，最後統計這8種走法哪一個能得到最多的勝局計分，找出最佳的走法。

但在5*5的井字遊戲中就沒辦法使用這種方法，因為總共的組合有3²⁵=847,288,609,443，8千多億種，勢必得犧牲演算法執行的深度去換取執行的效率。在5*5的情況下，有一種方法是使用判斷「可能連成直線」的方法，在對手下第一步和第二步之間尋找關聯性，只判斷是否有可能連成一直線，可減少search的深度。

 

■五子棋

五子棋的棋盤比起井字遊戲大上非常多，所以絕不可能考慮所有可能組合，故有人想出使用一些五子棋的規則來設計演算法：

首先在棋盤上的每個空位都設一個cost值，初始值為0。當對手或自己每下一步棋，則判斷此步棋的直、橫、斜列是否有可能達成活四/活三(死四/死三)等，給予不同的cost值，cost值愈高的則代表這步棋愈重要，愈需要優先下這步。

但是每下一步棋就要將cost值歸零重新計算，較浪費時間。

 

■象棋

在象棋中因為棋子有很多種類，不像五子棋只分為黑棋和白棋，象棋每種棋子都有其特定走法。做法是先建立一個「殘局知識庫」，藉由目前盤面上所剩棋子，去評估若某一子被吃掉後可能最造成勝局、負局或和局，判斷哪一步是最佳的。這個作法只需展開一層game tree就可找到解，不會因為殘局的困難度而影響執行的時間。

 

■圍棋

圍棋的規則又更複雜了，要設計一個強大的圍棋判斷演算法，設計者本身的棋力也要夠強，因為圍棋的規則雖然簡單但卻有非常多種變化，除了一般下棋的原則外，又有很多矛盾的例外。其中一種作法是判斷棋盤上的黑白子是否交纏在一起，將搜尋法裡分為攻和防兩種不同模組，這兩種模組互相呼叫，形成一個game tree，再以AND-OR方式進行搜尋，並且要加入非常多各種棋法的判斷條件，此必須要有相當程度的圍棋能力。

 

■走迷宮

又被稱作「老鼠走迷宮」，走法算是誤打誤撞，沒有計畫的走。

實作方法其實跟這次Lab中的Sudoku一樣，直接採用recursive(backtracking)的方式實作，先設定好要先往上、下、左、右哪一邊前進，設定好順序後就開始走，若走到死路就回頭，跟Sudoku「走到無解的狀態就回頭」是一樣的道理。

 

 

Chapter4 結論

解決一個問題的演算法可能有千百種，而是否恰當、實用、有效率、容易實作都還是得先經過一番評估。該如何從這麼多演算法中挑出適合的，除了要先了解一些演算法的基本概念外，還要多參考一些其他資料，參考他人對於類似的問題有哪些更好的解決方法。在我們看來一些遊戲雖然玩起來很簡單，但要如何讓電腦學會怎麼去判斷下一步該如何走又是另一回事，對於不同的遊戲，除了要挑選適當的方法，還要先了解遊戲的規則，才能加入適合的判斷條件，以提升程式執行效能，雖然電腦執行速度很快，但若方法使用不當，很可能會讓玩遊戲的使用者等待過久，甚至導致程式當掉。對於益智遊戲這種電腦會需要「思考」的程式，和人工智慧也有相當大的關係，而人工智慧的範疇也非常大，要寫出一個複雜的遊戲其實非常不容易，要對演算法和遊戲都有一定程度的了解才能完全實作出一個好的遊戲演算法。

 

 

參考資料：

[1]井字遊戲的設計與製作 DESIGN AND IMPLEMENTATION OF TIC-TAC –TOE，王仲民，台灣科技大學電子工程系

[2] http://www.cyut.edu.tw/~fmlee/course/ai/NilssonAI/ch12-2.htm

Adversarial Search，蕭明芳、楊景森、陳武成、蘇祐新

[3] http://www.jfvs.tpc.edu.tw/jfvs/教學組/專題報告/91資訊科/教師研究.doc

[4]智慧型程式設計上課講義，許見章教授，輔仁大學資訊工程學系

[5] http://bbs.wefong.com/archiver/?tid-1183090.html

微風論壇 » 程式設計討論區 » 請求老鼠走迷宮的演算法

[6]象棋殘局回溯分析演算法之實作與評估 Retrograde Analysis Algorithm for Chinese Chess Endgames: Implement and Evaluation，方浩任，Institute of Information Science，Academia Sinica, Nankang 11529 Taipei, Taiwan

[7]棋串攻防搜尋中不進子的辨識與處理方法 Identifying Squeeze-Forbidden Conditions and Processing Them in Block-Capturing Search，嚴礽麒、劉邦鋒、許舜欽

"

"

Pandora，其名來自於希臘神話中"潘朵拉的盒子"，代表著最後的「希望」。

它到底是啥東西呢？來我的blog看全文吧~ 

[@more@]"

"

醫療最重要的就是即時診斷和處理，eShepherd使用了RFID和WI-FI ID系統技術，讓醫師能即時知道病人的資訊、所在位置及病例等。

詳細的作法請至我的blog參觀。 

[@more@]"

醫療最重要的就是即時診斷和處理，eShepherd使用了RFID和WI-FI ID系統技術，讓醫師能即時知道病人的資訊、所在位置及病例等。

大致的做法是：

1.病人入院時即帶上一個RFID條碼手環， 透過發送RFID訊號，可即時掌握病人所在的位置，和其使用的醫療設備(病床、輪椅等設備上都內建了RFID TAG_)

2.護士做完基本的醫護工作後便利用內建有RFID TAG的手持行動裝置將病人狀況回傳給醫生(醫生也有具RFID TAG的手持行動裝置)

3.醫生診斷或手術完成後也利用RFID將診斷記錄及所需的藥物等透過行動裝置及時發送給各單位人員(例如配藥師、HIS資料庫等)

4.病人出院時只需卸下手環，病床、輪椅等也可及時置空，下一個病人可以即時使用空的病床或輪椅。

其也開發了許多相關設備，透過軟硬體的配合來發揮其作用，例如Vra Fi Router，可以：

1.自動與各無線設備溝通

2.辨識病人ID

3.辨認病人、醫生、護士的所在位置

4.即時資料傳輸

透過無線網路的技術，能讓醫院裡的醫療設備更有效的利用，病人的資訊也能更快的記錄和查閱，病人若有緊急狀況也能即時收到通報，若能早一分鐘治療，存活的機率可能就更高了一點。 

 

資料參考來源：Intelligent times 2006.12 

"RFID未來醫療國外案例    eSheperd "

作者 蕭淑玲(資策會創新應用服務研究所)

資策會發行的Intelligent times 06年12月號中也有提到"Web虛擬桌面 eyeOS"

簡單的說就是一個網站，而網站的內容就跟你的桌面一樣

而它並不只是單純的模仿桌面的介面，eyeOS也提供了它自有的軟體套件

eyeOS最大的好處就是一個方便團隊辦公的群組軟體，不像 以往的群組軟體，必須安裝專屬的client端軟體才能互相聯繫(MSN、skype再方便也都是要先安裝吧?)，而eyeOS只要用可支援的瀏覽器即可 登入，至於機器...並不限於PC，也可以是手機、PDA、甚至電視遊樂器(現在PS3、XBOX360等新世代主機都可上網了)，也就是說，不管你用的 硬體為何，你在eyeOS上做的複雜運算，對你手上的機器來說也不過只是"瀏覽網頁"罷了

不過這對於server端的負擔應該相當大，但未來很可能會朝這方面走，因為對於行動辦公方面是個相當方便的技術

"

今天老師上課有講到BBS上有些學生用的"密碼"，還以為老師是要講這個"火星文"，結果不是...

這個"火星文"可是正港的火星文，跟國中生那種沒水準的火星文可不同XD

欲知詳情請到我的BLOG來看

[@more@]"

"

今天老師上課有講到BBS上有些學生用的"密碼"，還以為老師是要講這個"火星文"，結果不是...

這個"火星文"可是正港的火星文，跟國中生那種沒水準的火星文可不同XD

 

範例：

●◢▅┼▏█┼▏▃○ⅩⅠ▄┼▏▅Ⅰ▆┼▏▄┼▏◤

解碼：

Algorithm

 

都是符號，這樣看起來比較像是外星語言吧？XD

不過推測它的原理只是把某些固定的字元轉換成固定的ASCII圖示，要破解應該不是太困難，不過這東西本來也只是純娛樂性，好玩就好。但沒翻譯器還真看不懂咧！

有興趣的話，我有上傳到我系上的空間

http://www.csie.fju.edu.tw/~ie935155/Encoder.exe

(檔案很小，68KB， 我有掃過病毒，應該是沒問題XD

上半部是Input欄，下面是Output，只要在Input打上地球語言或是火星語言

再按Encode或Decode就可以了)

so,try it!!

◆Ⅸ◣↓┴◥┬∵▏◥◣♂┴◤┬▏◇┼├┤＼Ⅷ●◢◥

"