※ 引述《Beethovenlu@kkcity.com.tw (...)》之銘言：
: 我才剛開始想學寫C++的程式
: 其實之前就有修過一些程式語言的課程了
: 但是資料結構和演算法之類的課卻都沒有研究過
: 最近突發奇想想要寫一個程式
: 是人和電腦對戰的遊戲：「畫圈圈」
: 應該很多人玩過
: 盤面如下：
: *
: * *
: * * *
: * * * *
: * * * * *
: 五層的三角形
: 玩家和對手輪流劃掉盤面上的圈圈
: 最多劃三個，最少劃一個
: 誰劃到最後一個就輸了
: 這個遊戲最多才十五步
: 比圈圈叉叉多一點點
: 而且也有對稱性的盤面
正好我有寫過這個遊戲，畫圈圈
當你要設計如何讓電腦畫掉盤面上的圈圈時，不妨參考參考我設計過的方法
實際跑過之後，確實是可以破解這個遊戲的 (15個圈圈)
假設盤面的圈圈個數: n
因為畫到剩最後一個圈圈時，下一個人必定畫到最後一個
所以當 n=1 時，都是必敗盤面
接下來從 n=2 開始搜尋每一種畫法
假設 n=2 的其中一種盤面是 S2
令 T 為 S2 之中畫掉一次盤面上的圈圈的所有方法的集合
若存在 e 屬於 T，使得 S2 - e 的圈圈個數為 1
=> e 為必勝著點，且 S2 為必勝盤面
接下來從 n=k 開始插尋每一種畫法
假設 n=k 的其中一種盤面是 Sk
令 T 為 Sk 之中畫掉一次盤面上的圈圈的所有方法的集合
若存在所有 e 屬於 T，使得 Sk - e 為必勝盤面
=> Sk 為必敗盤面
若 Sk 為非必敗盤面，且若存在 e 屬於 T，使得 Sk - e 為必敗盤面
=> e 為必勝著點，且 Sk 為必勝盤面
舉例：
假設搜尋到 n=4，且 S4 = ○ ， T = { ○, ○, , , , ... , }
○○ ○ ○ ○○ ○ ○
○ ○ ○ ○
∵ T 的所有元素 e 都使得 S4 - e 為必勝盤面
∴ S4 為必敗盤面
假設搜尋到 n=3，且 S3 = ○ ， T = { ○, ○, ○ , , ... , }
○○ ○ ○ ○○ ○
∵ 存在 e = ○○ 屬於 T，使得 S3 - e = ○ 為必敗盤面
∴ e 為必勝著點，且 S3 為必勝盤面
以上報告完畢。
: 但是因為才剛開始想要研究這類的程式
: (象棋、西洋棋、五子棋...之類的對弈遊戲)
: 所以不太知道該從哪裡入門
: 有上網找過一些資料
: 包括MIN-MAX法或ALPHA-BETA法、樹狀結構、遞迴、指標...等好像都是必備的知識
: 不過完整的程式碼範例很像很少...
: 我想請有經驗寫過類似程式的人能夠推薦一些書讓我參考
: 希望書的內容由簡入深，並且有詳細的範例和說明(希望是以C++為設計平台)
: (找過好多書和資料都只是提供寫遊戲的"觀念"，但範例和步驟解釋卻不甚詳細...)
: 感謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.85