宅學習 - Social Learning Space 社交學習空間@FJU CSIE

"

前言..

大學二年級上學期修了許見章老師的AI課程，那時候程式功力不足的我沒能把程式寫出來，藉由這次演算法的課程，總算能夠完成我的第一個game程式了

[@more@]

這次所寫的五子棋是一種最基本版的五子棋，在台灣五子棋協會的網站上我才了解其實五子棋有許多種規則，並不像我平常休閒時所玩的那麼簡單，有些下子的位置有其特別的稱呼，針對黑子(先手)，也有更嚴格的限制例如不能形成長連、雙活三等，而我這次的程式將規則最簡化，只要能夠連五子就算勝利了，這次的程式能夠人與人、人與電腦、電腦與電腦對戰，其中使用的演算法為Greedy和MinMax這兩種演算法，兩種演算法計算weight的方法大致上相同，將棋盤上所能夠下的位置去計算，以自己和對手的棋子分開計算weight，大致如下

自己 :  針對該點，看看四周是否有自己的棋子，如果有則該位置的weight+1

        若棋子距離該位置2格，則weight+2^2，若3格則weight+3^3，這是

        以棋子相連的情況下，若不相連則否。

對手 :  基本算法與自己相同，增加了若相連情況，而且的尾端為可放置棋子的

        位置則有額外加權。

Sample..

實做..

採用兩個thread( player1 player2)去判斷目前能夠下棋的是誰，能夠下棋的做下棋的動作，不能夠下棋的則等待另一個thread下完棋子。

Greedy..

Greedy的部分，只要對Greedy夠了解，還蠻容易實做出來的，要注意的是去計算weight的function夠不夠完善，就不會有特別的問題出現，當自己在跟greedy玩時，能夠邊玩邊modify function，讓greedy看起來更聰明。

MinMax..

MinMax演算法，我是搭配使用Alpha-Beta Pruning的方式來減少所要計算的node，所要計算的深度為三層(level 1-4)，為了能夠大幅度的增加效率，只要該位置周圍沒有棋子，就不將它加入我的game tree中，透過這個方式才讓電腦的計算時間從1分鐘以上降為1~5sec

結論..

對於演算法的選用，除了針對這個問題能不能夠使用這個演算法，也還要考慮到適不適合用來解決這個問題，此次五子棋的程式讓我覺得，若能夠將weight function考慮周全，就算使用Greedy演算法，所得到的solution並不會比MinMax還來的差，反而透過function來找solution所花的cost還遠遠小於MinMax所花的cost。針對一個問題來選擇適合的演算法，我想是要雙方面都要有一定的了解程度才能夠做一個好的選擇的。

心得..

我覺得對於一個game來說，AI並不是越高越好，雖然我計算weight的function並不是最好的，但是在我跟電腦的對弈中反而能夠獲得更多的樂趣，也許如果遊戲的演算法使用能夠學習的演算法，透過玩家跟電腦的互相學習，能夠逐漸的進步，我想能夠從game所獲得的樂趣能夠更多。

程式  五子棋TeamProject.rar

參考資料..

Book            Foundations of Algorithms Using Java Psuedocode, by Neapolitan, and Naimipour, Jones & Bartlett Publishers, July 2002

台灣五子棋協會  http://rif.compute.com.tw/

Bruce Moreland  http://www.seanet.com/~brucemo/topics/minmax.htm

Wikipedia        http://en.wikipedia.org/wiki/Alpha-beta_pruning

del.icio.us        http://del.icio.us/FJU_Algorithm

"

常使用於minMax game tree中，來增加search的效率，在Max node中的value稱為
alpha，在min node中的value稱為beta，透過alpha以及beta來修剪tree以減少訪
問的node，因為game tree通常很大，因此能夠有效的增加效率。[@more@]參考資料 http://en.wikipedia.org/wiki/Alpha-beta_pruning

A*是一種類似best-first search的演算法，但是比best-first還要更複雜一些
使用的Function如下..
    F(node) = G(node)+H(node)
G(node) : cost of the path so far leading up to the node
H(node) : underestimate of the distance of the node from a goal state
F(node) : path-base evaluation function
greedy algorithm就是一種把G function = 0的演算法

[@more@]參考資料  http://www-cs-students.stanford.edu/~amitp/gameprog.html

minmax演算法是一種蠻常用於game上的演算法，它演算法的行為是一種使用
遞迴depth-first search的方式，若current node是max，那他的child node
就是min，此child node的child就是max以此類推，因此若current node 是
max，則會往他眾child中最高的value的為他的solution.
但是game tree往往會很大，所以經常搭配bounded lookahead(限制level)、
alpha-beta purning來增加效率[@more@]參考資料  http://www.seanet.com/~brucemo/topics/minmax.htm

Search的演算法學了蠻多的，但似乎沒有講到過Parallel Search的觀念
Parallel Search的觀念其實還蠻容易了解的，例如利用tree來search的
時候將部分node分配給其他Processor來處理，進而提升效率，常見用於
處理IDA* 、chess-playing ..
也有不太適合用Parallel Search的演算法，如Alpha-Beta purning

[@more@]參考資料 http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume9/cook98a-html/node2...

想要將演算法課程中所學到的演算法，寫一個五子棋的程式實際的應用上去，

首先要能夠瞭解所學的演算法是否能夠應用上去，

以及各種不同的演算法之間比較優缺點，除了能夠使用者對抗演算法之外，

演算法跟演算法之間的pk賽也是我想要實做的。

[@more@]