黑白旗運用的相關演算法

資料來源:http://cindy.cis.nctu.edu.tw/EC/main/main.htm 這個主要目的是建構一個具有學習能力的黑白棋程式。實驗的系統架構可略分為二個部分，學習模組與下棋模組。學習部分主要是運用遺傳演算法來得到最佳的下棋策略，藉由將可能的下棋策略編碼與染色體中，並運用事先選好具一定棋力的教練程式模擬演化環境，再經由與教練程式對奕而得到每個個體個是存程度值，由週而復始的演化而得出最佳下棋策略。 而下棋的模組則是利用人工智慧的基本技巧，如遊戲樹，Alpha-Beta Pruning ，深度優先搜尋....等理論，評估每一個可下位置的可能風險與可能利益，而找出合適的位置。這個部份有許多的參數需要調整，而參數的不同便代表了不同的下棋策略，這些參數將會被編碼於染色體中，再郊遊遺傳演算法做最佳化。。 黑白棋(othello)遊戲是由二個玩家下棋，一方各執特定顏色的棋子，而最終勝負的認定則是視何種顏色棋子較多，多的一方為勝者，而其簡要的規則如下： 1.棋局最初時，雙方各持兩子，至於棋盤中心的對角線上。 2.雙方輪流下，只有當無合法位置可下時，才可 pass，將下子權交給對方。 3.雙方皆無合法位址可下時，則結束比賽。 4.合法位置的定義為下子後能吃掉對方一子以上的所有空白位置。 5.吃子的規則為：所有被新下棋子與己方棋子在縱、橫、對角等方向所包圍的敵方棋子，皆會被我方吃掉。吃子後，對方的棋子變成已方之顏色，即變成已方所有。 典型的黑白棋採用 8x8 的棋盤，圖中所示的圍棋局的最初狀態，而綠色區域則表示紅色一方可下的位置。 遊戲樹演算法 搜尋遊戲樹（min-max search tree）的原理，取自於我們平常玩競爭性遊戲的想法，以下我們就舉大家熟悉的棋類為例子：當我們要下棋時，總會考慮到對手可能對已方的傷害，而我們也因此必須選擇對已方最有利的下一步，也就是對已方傷害最少的下一步，不知不覺得已經講出遊戲樹的基本精神，在最大層就好比是對手的選擇，他總是選擇對已方最不利的下一步，而在最小層就好比是已方的選擇，選擇對已方傷害最少的下一步。 如圖，藍色的節點，表示在其子節點中，取最小者，反之，綠色的節點則取最大者，末端節點 2、7 其父節點為最小層（min），因此此一父節點為 2。 如圖，黑色的節點為被刪除的節點，而流程則如圖由上而下。 Alpha-Beta Pruning 目的: 減少搜尋樹的所必須經過的節點數，即刪除部分分枝， 而被刪除的節點，代表此一節點對結果沒有影響。 特徵擷取 以下舉出黑白棋可能的特徵: a. 每一棋盤上位置的重要性質，如四個角落的重要性較高,左圖即為每個位置的參考權值。 b. 我方目前子數與對方子數的差。 c. 我方可下之子數。 d. 對方可下之子數。 e. 穩定度。 f. 移動性。 g. 對手的穩定度。 演化的運算子非常多，但是大部分都是取自於大自然的現像，以下只舉出二個常見的例子： 染色體運算 染色體交配 : 即兩個染色體之間的某些基因互換，讓染色體之間 有機會能學到別人的長處。 染色體突變 : 染色體中的某些基因值自主的改變，主要 用來產生異於一般情況的染色體，以免讓學習的結果落入區域最 小值中。 演化流程 此一演化環境，一開始隨機產生一些染色體， 以形成一群體，接著評估每一染色體的適存度， 適合生存的染色體，可複製本身，接下來就是 進行染色體之間的交配，及染色體本身的突變， 當此一動作完成之後，也就形成了新的子代。 依此原則，不斷的重複此一演化法則，而最終 就產生了最適合生存的世代。 -------------------------------------------------------------------------------- 其中演化環境是由五個教練程式所組成，負責 測試染色體的適存度。 演化曲線 圖上是與練習範例一學習的結果，大概在6代之後就穩定。 圖下是與練習範例一至五學習的結果。 效能分析

與 Microsft Windows 所附的黑白棋程式(最高級)對下結果 
====================================================
教練程式 1  32     演化結果 1  28 
教練程式 2  6      演化結果 2 -38 
教練程式 3  8      演化結果 3  6 
教練程式 4  10     演化結果 4 -12 
教練程式 5  20     演化結果 5  11 
=====================================================

演化結果 1 是由教練程式 1 訓練而來，依此類推。 而正號表示贏，負表示輸。 網路志工聯盟----Visita網站http://www.vista.org.tw ---[ 發問前請先找找舊文章 ]--- 發表人 - axsoft 於 2002/08/23 09:24:23