程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> 五子棋算法探討

五子棋算法探討

編輯:C語言基礎知識

  近來隨著計算機的快速發展,各種棋類游戲被紛紛請進了電腦,使得那些喜愛下棋,又經常苦於沒有對手的棋迷
  們能隨時過足棋瘾。而且這類軟件個個水平頗高,大有與人腦分庭抗禮之勢。其中戰勝過國際象棋世界冠軍-卡斯
  帕羅夫的“深藍”便是最具說服力的代表;其它像圍棋的“手淡”、象棋的“將族”等也以其優秀的人工智能深
  受棋迷喜愛;而我們今天將向大家介紹的是五子棋的算法。
  當我們與電腦對戰時,您知道這些軟件是怎樣象人腦一樣進行思考的嗎?前不久我曾編寫過一個五子棋的游
  戲,在這裡就以此為例和大家一起探討探討。
  總的來說(我們假定您熟悉五子棋的基本規則),要讓電腦知道該在哪一點下子,就要根據盤面的形勢,為每
  一可能落子的點計算其重要程度,也就是當這子落下後會形成什麼棋型(如:“沖四”、“活三”等),然後通覽
  全盤選出最重要的一點,這便是最基本的算法。當然,僅靠當前盤面進行判定是遠遠不夠的,這樣下棋很輕易掉進
  玩家設下的陷阱,因為它沒有考慮以後的變化。所以在此基礎上我們加入遞歸調用,即:在電腦中猜測出今後幾步
  的各種走法,以便作出最佳選擇,這也是我們下棋時常說的“想了幾步”。如此一來您的程序便具有一定的水平了。
  什麼?不信!過來試試吧!
   總體思路弄清之後,下面進行具體討論:
  一:數據結構
  先來看看數據結構,我們需要哪些變量?
  首先得為整個棋盤建立一張表格用以記錄棋子信息,我們使用一個15*15的二維數組 Table[15][15] (15*15是
  五子棋棋盤的大小),數組的每一個元素對應棋盤上的一個交叉點,用‘0’表示空位、‘1’代表己方的子、‘2’
  代表對方的子;這張表也是今後分析的基礎。
  在此之後還要為電腦和玩家雙方各建立一張棋型表Computer[15][15][4]和Player[15][15][4],用來存放棋型
  數據,就是剛才所說的重要程度,比如用‘20’代表“沖四”的點,用‘15’代表“活三”的點,那麼在計算重要
  性時,就可以根據20>15得出前者比後者重要,下子時電腦便會自動選擇“沖四”的點。那為什麼棋型表要使用三
  維數組呢?因為棋盤上的每一個點都可以與橫、豎、左斜、右斜四個方向的棋子構成不同的棋型,所以一個點總共
  有4個記錄;這樣做的另一個好處是可以輕易判定出復合棋型,例如:假如同一點上有2個‘15’就是雙三、有一個‘15’和一個‘20’就是四三。
  怎麼樣!3個數組構成了程序的基本數據骨架,今後只要再加入一些輔助變量便可以應付自如了。應該不會太
  難吧?OK!有了這麼多有用的數據,我們就可以深入到程序的流程中去了。
  二:程序流程
  我們主要討論五子棋的核心算法,即:人工智能部分,而其他像圖形顯示、鍵盤鼠標控制等,因較為簡單,所
  以就不作過多介紹了。
  我們看到本程序由六個基本功能模塊構成,各模塊的具體分析如下:
  (1)初始化:首先,建立盤面數組Table[15][15]、對戰雙方的棋型表Computer[15][15][4]和Player[15]
  [15][4]並將它們清零以備使用;然後初始化顯示器、鍵盤、鼠等輸入輸出設備並在屏幕上畫出棋盤。
  (2)主循環控制模塊:控制下棋順序,當輪到某方下子時,負責將程序轉到相應的模塊中去,主要擔當一個
  調度者的角色。
  (3)玩家下子:當輪到玩家下時,您通過鍵盤或鼠標在棋盤上落子,程序會根據該點的位置,在Table[15]
  [15]數組的相應地方記錄‘2’,以表明該子是玩家下的。
  (4)盤面分析填寫棋型表:本程序核心模塊之一,人工智能算法的根本依據!其具體實現方法如下:您在下
  五子棋時,一定會先根據棋盤上的情況,找出當前最重要的一些點位,如“活三”、“沖四”等;然後再在其中
  選擇落子點。但是,電腦不會像人一樣分析問題,要讓它知道哪是“活三”、哪是“沖四”,就得在棋盤上逐點
  計算,一步一步的教它。
  先來分析己方的棋型,我們從棋盤左上角出發,向右逐行搜索,當碰到一個空白點時,以它為中心向左挨個
  查找,假如碰到己方的子則記錄然後繼續,假如碰到對方的子、空白點或邊界就停止查找。左邊完成後再向右進
  行同樣的操作;最後把左右兩邊的記錄合並起來,得到的數據就是該點橫向上的棋型,然後把棋型的編號填入到Computer[x][y][n]中就行了(x、y代表坐標,n=0、1、2、3分別代表橫、豎、左斜、右斜四個方向)。而其他三
  個方向的棋型也可用同樣的方法得到,當搜索完整張棋盤後,己方棋型表也就填寫完畢了。然後再用同樣的方法
  填寫對方棋型表。
  注重:所有棋型的編號都要事先定義好,越重要的號數越大!
  OK! 怎麼樣?有點累了吧?不過千萬別洩氣!因為好戲還在後頭。
  Let's go!
  (5)電腦下子:有了上面填寫的兩張棋型表,現在要作的就是讓電腦知道在哪一點下子了。其中最簡單的
  計算方法,就是遍歷棋型表Computer[15][15][4]和Player[15][15][4]找出其中數值最大的一點,在該點下子即
  可。但這種算法的弱點非常明顯,只顧眼前利益,不能顧全大局,這就和許多五子棋初學者一樣犯了“目光短淺”
  的毛病。
  要解決這個問題,我們引入‘今後幾步猜測法’,具體方法是這樣的: 首先, 讓電腦分析一個可能的點,
  假如在這兒下子將會形成對手不得不防守的棋型(例如:‘沖四’、‘活三’);那麼下一步對手就會照您的思
  路下子來防守您,如此一來便完成了第一步的猜測。這時再調用模塊4對猜測後的棋進行盤面分析,假如出現了
  ‘四三’、‘雙三’或‘雙四’等制勝點,那麼己方就可以獲勝了(當然對黑棋而言‘雙三’、‘雙四’是禁手
  ,另當別論);否則照同樣的方法向下分析,就可猜測出第二步、第三步……
  等一等,要是盤面上沒有對手必須防的棋型,哪該怎麼辦呢?進攻不成的話就得考慮防守了,將自己和對手
  調換一下位置,然後用上面的方法來猜測對手的棋,這樣既可以防住對手巧妙的攻擊,又能侍機發動反擊,何樂
  而不為呢!
  但是必須告訴大家的是:猜測法的運算量相當之大,據我的經驗,用Pentium-100猜測3步的走法平均需要15
  秒以上時間,所以建議猜測量在5步以內。可別小瞧了這5步,有時它甚至會走出讓您拍手叫絕的妙著呢!
  (6)勝敗判定:務須多言,某方形成五子連即獲勝;若黑棋走出‘雙三’、‘雙四’或長連即以禁手判負。
  到現在為止,整個五子棋軟件就基本完成了,其水平大約在中級上下。當然,這種算法並不是最好的,但我
  相信它的基本思路是正確的。
  
 
  1. 上一頁:
  2. No
Copyright © 程式師世界 All Rights Reserved