六子棋(connect6)設計大綱v2.0 發展源由及歷史 規則、棋盤、複雜度 演算法基本架構 遭遇的問題 結論 報告者：梁秦宜.

Presentation on theme: "六子棋(connect6)設計大綱v2.0 發展源由及歷史 規則、棋盤、複雜度 演算法基本架構 遭遇的問題 結論 報告者：梁秦宜."— Presentation transcript:

1 六子棋(connect6)設計大綱v2.0 發展源由及歷史 規則、棋盤、複雜度 演算法基本架構 遭遇的問題 結論 報告者：梁秦宜

2 發展源由及歷史 2003年暑假，交大吳毅成教授和其女兒的一個想法
之後，其指導學生黃德彥開始六子棋的研發，並於2005年9月在第11屆國際計算機賽局發展(Advances in Computer Games)研討會上發表六子棋研究

3 規則、棋盤 、複雜度 由執黑者先下，第一回1手，且為棋盤中心，之後每一回下2手，黑白輪流，先連六子則勝出
一般玩家棋盤以19路大小為準；專家級的棋盤以59路大小為準 19路棋盤時，state-space為10172，與圍棋想當，而game-tree為(300*150)30~10140，複雜度遠大於五子棋

4 演算法基本架構 觀念： 需要圖形比對、建立table來存放連線資訊 1.形成連線、權重值、及評估的區塊 由於二點可以決定一直線，因此最小的連
線由2點開始，分別給予不同的權重；評 估區塊以7X7為主(可判斷特殊型)，3X3為輔(開 局用) 2.活型、死型、特殊型 需要畫圖來解釋

5 權重分數： 目前先給予的分數---活四給5分，死四給4分，活三給3分，死三給2分，活二給1分, 死二給0分。 1.有中空加一分，因為除了二端點外，多一 個斷點要讓對方考慮； 2.被封死(二端皆有對方的子)直接變為0分 特殊型： 特別指的是中空2格的型，通常只看四顆子的，因為直接造成勝或負

6 結構： 1.以59路(0~58)棋盤為準，中心點為 (29,29)，因此結構點可設計為(X座標, Y座標,狀態字元)。W,B,E表白子，黑子， 空點 2.建立索引記載著：二子連線、三子連線、 四子連線，甚至五子連線各有哪些，配合 給予的權重高低不同，便可快速決定在哪 些點附近落子---只需考慮連線的二端點。 在二端點處，用7X7區塊來判斷何者優 先。若在區塊內有同色的棋，就再進入table比 對。

7 策略的優先： (可以設計特別形式有加分) 防禦的棋： (一定是對方二手皆下完) 1.四子或五子連成線，包括有中空 2.雙活三，包括有中空 攻擊的棋： (有第一手及第二手的先後) 1.是否能連六 2.是否一手能形成2個活四 3.是否二手能形成1個活四+1個死四 4.是否二手能形成2個活三+1個死三 5.是否一手能形成1個活四+1個活三 6.是否一手能形成2個活三 7.是否一手能形成1個死四+1個活三 8.是否一手能形成1個死四 9.是否二手能形成2個死四 (花二手形成1個死四的狀況沒有特別加分，因為先手會換對方)

8 遭遇的問題 一開始第一版的概念是沒有加入權重，並且是以3X3為判斷依據，但是很快的放棄了，因為沒有勝過任何人(原因是3X3的區塊，只會考慮落子的周圍8格)。因此加入了權重，Table表的建立，和加大到7X7的區塊的觀念來進行。 第二版多了圖形的比對在活二，活三，活四，和策略中的特殊加分形式---一手形成雙活三，或活四活三，死四活三等，單單如此，可能的形式就非常的龐大多樣，也是一個問題。

9 結論 一開始本來打算是否可以用min-max tree加上α-β切捨，但是棋盤面太大，因而用老師在圍棋的圖形比對觀念來設計，目前的架構為概念，並未實際有進入實作，因此是接下來要考量的目的。