投稿類別 : 資訊類 篇名 : 五子棋 黑棋不敗棋步? 作者 : 王牧謙 臺北市立大同高中 高二 15 班 指導老師 : 吳淑萍老師 張繼元老師
壹 前言 五子棋 黑棋不敗棋步? 一 研究動機 國小時初次接觸五子棋, 是手機內建的單機版遊戲, 那時雖已了解下棋基本規則, 但無論如何就是贏不了, 於是我開始思考, 是否有一套棋步能使電腦必勝? 爾後上網查詢些相關資訊, 得知當沒有禁手限制時, 只要棋盤沒有太小, 先下的有必勝棋步, 加入禁手規則後, 也依然有, 但複雜許多, 遂產生了一些細微的規則調整, 本文將不細究 這回, 我的目標將會是找出一種下法, 使得黑棋在禁手限制下, 仍可擁有較高勝率, 因為無論規則怎麼改, 只要基本禁手限制下有一定勝率, 使用其他規則也能有穩定的表現, 每種規則都細究的話效果不至有多大差異, 卻費時許多 二 五子棋介紹 五子棋是一種純策略性的棋類遊戲, 每一場有兩人對弈, 一方持黑子, 另一方持白子, 雙方輪流下一子在棋盤橫直線交點上, 落子後不可拿回, 已有子的點不能下, 直到分出勝負 或和局, 由黑子先下, 一方有五子相連即判獲勝 因為早在 1899 年, 日本人黑岩淚香便已證明 : 沒其他限制時, 存在一套棋步, 使得先下 方必勝, 五子棋規則就進行了一連串修改, 最後產生了 禁手 規則 此後雖仍有修改, 但 都只是微調, 將來亦有可能再變 禁手限制先下的黑棋, 若黑棋下出 雙活三 雙四 則判敗, 這使得黑棋受限, 白棋則有一些利用禁手得利或取勝的方法, 但即便有此限制, 多數人經由下棋經驗和電腦協助證明, 認定黑棋較具優勢, 規則因而有多次的修改, 至今仍在改進, 以期能真正使黑白雙方公平 三 研究目的 研究黑棋的下棋策略, 使得電腦在網路上與隨機玩家對弈, 持黑子時能有 80% 以上勝率 四 研究方法 1
五 名詞說明 ( 一 ) 活四 ( 二 ) 死四 四個同色子於同一條直線上 ( 橫 直 斜 ), 四個同色子於同一條直線上 ( 橫 直 斜 ), 白子可防禦黑子取勝的四 ( 必須有可能五連且白子無法防禦黑子取勝的四 才算 ) ( 三 ) 活三 ( 四 ) 死三 三個同色子於同一條線上 ( 橫 直 斜 ), 且非活三的三個同色子於同一條線上 ( 橫 直 能藉由該方下一步使其成為活四者, 稱這三斜 ), 且能藉由該方下一步使其成為死四者, 顆為一活三 稱這三顆為一死三 ( 五 ) 雙活三 ( 六 ) 雙四 當下該點後, 因該子而產生兩個以上的活三 其三顆子包含所下者 當下該步, 因該子而產生兩個以上的四 ( 含 活四和死四 ) 其四顆子包含所下者 2
( 七 ) 禁手 : 黑棋下出雙活三或雙四 ( 不限活四死四 ) ( 八 ) 天元 : 棋盤正中心的那一點 座標為 H8 的點, 在大多情況下為黑棋第一步所下之處 ( 九 )26 開局 : 為一種開始棋局的方法, 黑先下天元, 白下天元外圍一圈中的點, 黑再下天元外圍第二圈上的其中一點 正式比賽多規定照此開局, 業餘者則多不要求 六 規則 ( 一 ) 雙方決定好誰執黑後, 由黑子先下 ( 二 ) 黑白雙方輪流下一子, 直至一方取勝或確定平局為止 ( 三 ) 黑子不可下出禁手棋, 部分規定判輸, 部分則規定該步無效, 黑子需重下, 但 下該步即可取勝時除外 ( 四 ) 已被任一方下子的點不可再下, 已被下的子不可因任何緣故被移除或被敵方子取代 七 參考他人方法 ( 一 )Alphago Alphago 是一個由 google 發明的圍棋程式, 其所使用的方法大致上分成三部分, 使其成為當今最強的圍棋程式, 它不僅可以學圍棋, 它還可以學更多, 只要答案是可確定的 故我原欲仿效之, 但礙於資料量不足, 以及 C++ 任兩次輸入 / 輸出間執行時間受電腦影響無法過長, 遂僅採用其方法 3 的一小部分, 以下是其三大方法 方法 1: 爬梳資料 -Alphago 搜集眾多圍棋高手面對不同盤面時的下法, 由於爬梳資料量約有 3000 萬步, 故具有取勝一段棋手的實力 方法 2: 自己和自己比 -Alphago 跟 Alphago 對弈, 輸了的 Alphago 所用方法的分數下降, 贏 了的 Alphago 所用方法的分數上升 方法 3: 計算勝率 - 假設對手所下的點都正確, 找出下了之後勝率會最高的棋步下 在此, 我只使用方法 3 中的假設 : 對手下的點都正確 至於黑棋下子方法的部分並非以 勝率計算, 而是憑下棋技巧分析, 選擇一個認為較佳的落子點, 沒有學 Alphago 將大量資料 做統整分析以求出最佳落點 ( 二 ) 業餘五子棋設計 (C++) 大多業餘的程式都有一個共通的特色, 那就是很愛用 random 函數 顧名思義,random 即隨機, 也就是說它面對沒納入考量的情形時, 會以隨機的方式選擇一點下, 遇到兩點以上權重分相同時亦隨便選一, 因為這樣便不需考慮很多狀況, 可以節省很多時間, 但我不喜歡這方法, 故不將它寫入我的程式裡 3
貳 正文 五子棋 黑棋不敗棋步? 一 常見開局下法 :26 開局 因黑下一子白也下一子後, 以對哪一方較具優勢的開局便由黑決定, 而本文僅討論黑子求勝, 故僅就黑白二子相對位置不同的兩種情形下, 對黑最有利的開局法進行討論 : 溪月和浦月, 至於對付不照 26 開局者, 雖然較難以預測對手下法, 但會如此多是因對五子棋的不了解所致, 故以基本下棋原則應對即可 ( 一 ) 溪月 ( 二 ) 浦月 黑子天元, 白子在其上 下 左 或右一格, 黑下在白左 / 右上 左 / 右下 左上 / 下 右上 / 下 黑子天元, 白子在其右上 右下 左上 左 下, 黑下在棋右下 / 左上 右上 / 左下 右上 / 左下 左上 / 右下 二 C++ 設計 ( 一 ) 基本運作模式 如 圖一 所示 4
圖一 C++ 基本運作模式 ( 二 ) 建議棋步 包含基本運作模式中的 各點權重值歸零 計算各點權重值 以及 輸出最佳落點座標, 為此程式的重點 原欲參考 Alphago 的方法, 令電腦與電腦多次對戰, 並將每一個盤面的結果紀錄, 讓電腦從每個盤面找出一個落點使其勝率最大, 但 Alphago 用此法乃因為圍棋複雜度極高, 如欲嚴格的設計出必勝程式, 以人的腦力應該不太可能 五子棋複雜度明顯低了許多, 盤面僅 15*15 且一旦落子變不可將之移除, 過去也有不少人試著做出五子棋的必勝程式, 況且 C++ 常會遇上輸入 / 輸出間執行時間過長而無法運作, 而 Alphago 的作法執行時間絕對會超過 C++ 上限, 故我將於黑子下前 3 步 ( 前 5 回合 ) 時進行嚴格判斷, 第 4 步 ( 第 8 回合 ) 5
後進行 活三 活二 等情況的權重計算 以下 圖二 表示以第 3 回合的設計為例 圖二 模擬第三回合 其中 a[1],a[2],a[3] 為第 5 回合判定時所需的參數, 好讓電腦能在最短時間內進行多次 篩選 ( 多次 2 分法 ) 類似上圖, 每次判斷都把問題拆成兩半, 並在最後一次做完參數設定以及 提出建議, 一來比較不會太亂讓人看不懂, 二來也使編輯程式碼時較不易出錯 ( 三 ) 程式碼 由於行數太多, 有 2000 多行, 故以下僅顯示一部分, 作為範例, 如有不足處還請見諒 本程式基本運作架構, 其中 a[ ][ ] 是落點,b c 的判斷式和 a[ ][ ]==0 是用以確定該點可以下 子, 沒有子之前已在該點上, 或坐標超出邊界, 如 圖三 6
圖三 程式主結構 選擇落點用之程式碼, 藉由多層的 if 判斷式, 以做為分類標準, 讓上次輸入到後續輸出 建議點的執行時間大幅減少 ( 即使用二分法 ), 這樣每一次最多只會判斷 14 個 if,16 個條件, 如 圖四 7
圖四 第三回判定 ( 部分 ) 第三回合選擇落點部分, 一樣是採用二分法, 並藉由 a[1][1] a[0][0] 等數做初步的分解, 最後輸出 (cout,printf) 時再設定參數 sc[ ][ ]( 自訂參數 ), 供第五回合時判斷用, 如 圖五 8
圖五 第三回判定 ( 部分 ) 輸出時棕色部分為棋盤, 實心黑圓為黑子, 空心圓為白子 suggest: 後所寫為建議點座 標 右方數字陣列為各點權重值 前 5 回合將作逐步分析, 故不計算權重 下方 0 0 兩數字是 黑子上一步下棋時在該點上有幾個活三 / 四, 左邊數字為活三, 右邊為活 / 死四, 如 圖六 圖六 實際執行視窗 9
參 結論 五子棋 黑棋不敗棋步? 我以此程式在手機應用程式 五子棋達人 SUD lnc. 中實戰, 記錄了持黑棋時的勝負場數, 得出在這 96 場中取得 62 勝 34 敗 ( 勝率約 65%), 遠比預設的目標 80% 低, 令我頗感失望 雖然嚴格設計能帶來較全面的判斷, 但編寫所需時間較長, 且僅能在黑下前 3 步時嚴格判定, 第 4 步開始便無力再寫下去, 因為太複雜了, 只好放棄 故從 4 步開始即用概括式的編寫方法, 好讓問題簡化, 但這帶來的便是 80% 不到的勝率 希望將來可找出一套下法使得黑棋必勝, 再依此法重新編寫 修正, 以期達到目標 80% 以上勝率 此外, 也希望之後可以嘗試設計白子的程式, 雖然已被證明, 此條件下黑子有必勝法, 故無法達成必勝, 但下五子棋總不能只持黑不持白, 對吧? 況且如果做的好, 對付人腦應該綽綽有餘了, 畢竟世上沒多少人會這麼做, 不需太擔心 再說, 黑棋程式轉白棋, 費不了太多時間 ( 跟我第一次寫黑棋的比 ), 時間成本低很多, 卻能使下棋時不論持黑持白皆可輕鬆以對, 這樣似乎比只設計黑子要來的更好, 到時僅需再把黑 白棋程式合併, 就能使每次下棋時都不必擔心持黑還是持白了! 肆 引註資料 1. 林守德 (2016) Alphago: 不懂圍棋的棋王 科學人,170,24 2. 葉平 (2016) 人工智慧下出罕見妙手 科學人,171,24-25 3. Louis Victor Allis.1992.Searching for Solutions in Games and Artificial Intelligence,5,121-153.Retrieved January 23,2017, 2016 年 10 月 19 日, 取自 https://www.zhihu.com/question/24053236 4. Ryan s Blog 2016 年 12 月 9 日, 取自 http://diiuuli520.blogspot.tw/2011/08/c-1p-vs-ai.html 10