人 工 智 慧 報 告 五子棋AI設計 報告者 : 潘輝銘.

Presentation on theme: "人 工 智 慧 報 告 五子棋AI設計 報告者 : 潘輝銘."— Presentation transcript:

1 人 工 智 慧 報 告 五子棋AI設計 報告者 : 潘輝銘

2 Outline 五子棋介紹 遊戲規則 AI 演算法 Demo

3 五子棋介紹 由兩人組成的對奕遊戲 先下者執黑子 ，後下者執白子 優勝條件：不論直向、橫向、斜向，先將五顆棋子連成一線者獲勝
白子獲勝! 由兩人組成的對奕遊戲 先下者執黑子 ，後下者執白子 優勝條件：不論直向、橫向、斜向，先將五顆棋子連成一線者獲勝 當棋盤整個下滿還未分出勝負 ，即為《雙方和局》 雙方和局!

4 遊戲規則 (1/2) 基本型：分為『連』、『四』、『三』 連 → 五個或五個以上的同色棋子連成一線。
四 → 再下一子可形成連，包括『活四』和『衝四』。 三 → 再下一子可形成『四』的三子連線，分為『連三』和『跳三』。 四 三 為可下的點

5 遊戲規則 (2/2) 禁手規則：對局中禁止使用的步法 長連：六子以上連成一線。 四四：一子形成兩個『四』 ，也有可能都在同一條線上。
三三：或稱雙三，即下一子可連兩個『三』局面。 先下黑子必須遵守禁手規定，白子無禁手。 四四 三三

6 AI 演算法 (1/3) 建構五子棋的初始原件： private int[,] virtualGobangBoard=new int[15,15]; // 虛擬棋盤 PictureBox[15,15]; // 棋子 private Stack backStack = new Stack(); // 計算悔棋堆疊 private Stack backTrackStack = new Stack(); // 計算回溯堆疊 const int M = 1; // 預測步數

7 AI 演算法 (2/3) 先建構繪製整個14*14的虛擬棋盤並初始化。 棋盤上的每一點都有個值，起始值為零。
上所有點 [直向] [橫向] [左上&右下斜向] [ 左下&右上斜向] 四個方向構成的棋型， 是否為禁手點。

8 AI 演算法 (3/3) 將所有棋盤上的點對黑子&白子的權重算出來，給予不同值。 棋盤點的值越高代表該空位越重要。
 重複上述之步驟，直至分出勝負。

9 Demo (1/3) 玩家執黑子，AI 執白子 當玩家有兩連子 AI必會阻擋 經過權重計算下在有利於己方的點 AI會先下子 形成三連子的局面

10 Demo (2/3) 阻擋AI的連三 AI下子在衝四 搶先優勢條件 玩家只能下子阻擋 AI經計算下在有可能為雙三的局面

11 Demo (3/3) 持續進子 AI隨時尋找可能有雙四或雙三的點 圖為『四三』白子佔盡優勢 AI白子獲勝!