|
去年有想寫個斗地主的小游戲，自己玩玩。找了很多資料，后來好不容易在網(wǎng)上找到了一個AI算法。轉(zhuǎn)過的的時候是貼在自己電腦的TXT文本上，再次感謝下原作者?，F(xiàn)在借花獻佛發(fā)給你參考下。 我以前寫過一個斗地主機器人。思路如下，希望對你有幫助。 斗地主AI設(shè)計 一、牌型 1 火箭：大小王在一起的牌型，即雙王牌，此牌型最大，什么牌型都可以打。 2 炸彈：相同點數(shù)的四張牌在一起的牌型，比如四條A。除火箭外，它可以打任何牌型，炸彈對炸彈時，要比大小。 3 單支（一手牌）：單張牌，如一支3。 4 對子（一手牌）：相同點數(shù)的兩張牌在一起的牌型，比如55。 5 三條：相同點數(shù)的三張牌在一起的牌型，比如三條4。 6 三帶一手：三條 ＋ 一手牌的牌型，比如AAA+9或AAA+77。 7 單順：五張或更多的連續(xù)單支牌組成的牌型，比如45678或345678910JQKA。2和大小王不可以連。 8 雙順：三對或更多的連續(xù)對子組成的牌型，比如334455或445566778899。2和大小王不可以連。 9 三順：二個或更多的連續(xù)三條組成的牌型，比如777888或444555666777。2和大小王不可以連。 10 飛機帶翅膀：三順 ＋ 同數(shù)量的一手牌，比如777888+3+6或444555666+33+77+88。 11 四帶二：四條+兩手牌。比如AAAA+7+9或9999+33+55。 二、牌型分析 1 單順的確定 a) 選取五連，先取出最小的一個五連，再在剩余的牌中取出最小的一個五連，依此類推，直到?jīng)]有五連為止。 b) 擴展五連，將剩余的牌與已經(jīng)取出的牌進行比對，如果某張剩余的牌與已知的連牌能組成更大的連牌，則將其合并。一直到無法合并為止。 c) 合并連牌，如果某兩組連牌能無縫連接成更大的連牌，則將其合并成一組。 經(jīng)過上述選取、擴展和合并，則將一手牌中的所有連牌提取出來了，舉例如下： 假定一手牌是：2AKQJ1099877766543 第一步，選取出34567，678910兩個連牌組。剩余的牌還有79JQKA2 第二步，剩余的JQKA能和678910組成新的連牌678910JQKA。 第三步，已知的兩個連牌組不能合并成新的、更大的連牌組，則這手牌就被分成了34567、678910JQKA兩個連牌組和7、9、2三張單牌。 2 雙順的確定 將一副牌中所有的對子檢測出來，然后將對子排序，按照檢測三連的方式可以將所有的雙順都提取出來。 3 三條的確定 一副牌中的所有三條都能比較方便地提取出來。 4 三順的確定 在三條的基礎(chǔ)上進行比較，如果有相連的三條，則將其合并成（盡可能大的）三順。 5 炸彈的確定 所有的四頭都能很方便地確定。 6 火箭的確定 只要牌張包含大小王，就將其組成火箭。 7 牌張的分類方法 a) 先確定火箭：判斷是否有大小王。 b) 再確定炸彈：判明是否有四頭。 c) 再確定三條：在除了炸彈以外的牌中判斷是否包含三條。 d) 再確定三順：在已經(jīng)確定的三條中判斷是否包含相鄰的三條，如果有，則將其組成三順。注意，應(yīng)該使三順的數(shù)量盡可能大。即如果有444555666，則將其合成一個三順，而不是分成444555一個三順和666一個三條。 e) 再確定單順：判斷單順時必須去除四個2以外的所有炸彈。首先判斷是否存在除了三條牌（這里的三條是指所有的三條）以外的連牌，如果有，則將其提取出來。其 次，將剩余的牌與每一個三條（不包含三順）進行試組合，如果能夠重新組成單順和對子，則將原有的三條取消，重新組合成連牌和單順（例子4566678重新 組成45678和66）。最后，將已知的連牌、三條（不包含三順）和剩下的牌張再試組合，將所有如45678（已知的連牌）999（三條）10J（單 牌），重新組合成45678910J和99。通過以上的方法，就能將連牌和三條很好地重新組合。 f) 再確定雙順：首先，如果兩單順牌完全重合，則將其重新組合成雙順。其次，在除炸彈、三順、三條、單順以外的牌中檢測是否包含雙順。如果有，將其提取出來。 g) 再確定對子：在炸彈、三順、三條、連牌、雙順以外的牌中檢測是否存在對子，如果存在將其提取出來。 h) 再確定單牌：除了炸彈、三順、三條、連牌、雙順、對子以外的所有牌張都是單牌。 8 對子的確定 參見上一節(jié)的“再確定對子”。 9 單牌的確定 參見上一節(jié)的“再確定單牌”。 三、一手牌的手?jǐn)?shù)分析 為 了使斗地主機器人有一定的智能，必須對一手牌的手?jǐn)?shù)進行分析。所謂一手牌的手?jǐn)?shù)，指的是在沒有別人壓牌的情況下需要出幾把能將牌出完。這個數(shù)字在經(jīng)過上面 的分類后是可以確定的。還以上面的一手牌22AAKQJ9987776654為例，這手牌按照前面的分析方法可以分析出以下的牌型： 22、AA、K、Q、J、987654、9、77、6的牌型 通過對上面牌型的計算，可以容易得出這手牌需要9手才能出完，因此這手牌的手?jǐn)?shù)就是9。 四、絕對手?jǐn)?shù)和相對手?jǐn)?shù)的概念 因為在斗地主游戲中存在火箭或炸彈的可能，所以理論上只有火箭才不可能被別人壓住，所以，可以不考慮相對手?jǐn)?shù)的概念。以后都簡稱手?jǐn)?shù)。 五、叫牌原則分析 因為在斗地主中，火箭、炸彈、王和2可以認(rèn)為是大牌，所以叫牌需要按照這些牌的多少來判斷。下面是一個簡單的原則： 假定火箭為8分，炸彈為6分，大王4分，小王3分，一個2為2分，則當(dāng)分?jǐn)?shù) 大于等于7分時叫三倍； 大于等于5分時叫二倍； 大于等于3分時叫一倍； 小于三分不叫。 六、出牌的一般原則 1 出牌的原則一般按照從小到大的原則，即首先出包含最小牌的組合（單牌、對子、雙順、連牌、三順、三條等，炸彈、火箭不包括在內(nèi)）。 2 三條的出牌原則：因為三條出牌可以帶一張單牌或一個對子，所以在出三條時需要檢測是否有單牌，如果有，則帶一張最小的單牌，如果沒有，則再檢測是否存在對子，如果有，則跟一個最小的對子，如果單牌和對子都沒有，則出三條。 在帶牌時，除非是只剩兩手牌，否則不能帶王或2。 3 三順的出牌原則：因為三順出牌可以帶兩張（或更多）單牌或兩個（或更多）對子，所以與出三條一樣，需要檢測是否有單牌或?qū)ψ?。如果有足夠多的單牌或?qū)ψ樱? 則將其帶出。如果有單牌，但沒有足夠多的單牌，則檢查是否有6連以上的連牌，如果有將連牌的最小張數(shù)當(dāng)作單牌帶出。如果有對子，但沒有足夠多的對子，則檢 查是否有4連以上的雙順，如果有將雙順的最小對子當(dāng)作對子帶出。 在帶牌時，除非是只剩兩手牌，否則不能帶王或2。 4 連牌的出牌原則：直接出。 5 雙順的出牌原則：直接出。 6 對子的出牌原則：因為對子可以用三條、三順等帶出，所以在出對子時，應(yīng)該先檢測一下三條＋三順（中三條）的數(shù)量，如果所有三條數(shù)量 <= 對子＋單牌數(shù)量總和－2時，出對子，否則出三帶2等等。 7 單牌的出牌原則：因為單牌可以用三條、三順等帶出，所以在出單牌時，應(yīng)該先檢測一下三條＋三順（中三條）的數(shù)量，如果所有三條數(shù)量 <= 對子＋單牌數(shù)量總和－2時，出單牌，否則出三帶1等等。 七、跟牌的一般原則 1 如果手中有獨立的，與所出的牌一樣牌型的牌時，先跟之。 2 2可以作為單牌、對子、三條等形式跟出。 3 當(dāng)手中沒有相應(yīng)牌跟時，如果是本方人員出的牌，可以不跟，如果是對方出的牌，則必須拆牌跟，如果再沒有，出炸彈或火箭，否則PASS。 4 如果手中的牌除了炸彈。火箭外還剩一手牌，則如果牌型相符，則先跟之，否則炸之。 5 單牌的跟牌原則：如果手中有單牌，則跟之，否則拆2跟之，否則拆對牌跟之，否則拆6連以上的單順頂張跟之，否則拆三條跟之，否則拆三順跟之，否則拆5連單順跟之，否則拆雙順跟之，否則炸之，否則PASS。 6 對牌的根牌原則：如果手中有對子，則跟之，否則拆4連以上的雙順頂張跟之，否則拆三條跟之，否則拆雙順跟之，否則拆三順跟之，否則炸之，否則PASS。 7 三條、三帶1、三帶2等牌的根牌原則：如果手中有相同牌型的牌則跟之，否則拆三順跟之，否則炸之，否則PASS。注意，只有在手中牌在出了以后還剩一手牌時，或直接出完的情況下，才允許帶王或2。 在沒有足夠牌帶的情況下，參照單牌。對子的拆牌原則進行拆牌處理。 8 三順及三順帶牌的根牌原則：如果有相應(yīng)的牌型，則跟之，否則可以將大的三順拆成小的三順跟之，否則炸之，否則PASS。注意，只有在手中牌在出了以后還剩一手牌時，或直接出完的情況下，才允許帶王或2。 在沒有足夠牌帶的情況下，參照單牌。對子的拆牌原則進行拆牌處理。 9 連牌的跟牌原則：如果有相應(yīng)的牌型，則跟之，否則拆相同張數(shù)的雙順，否則拆相同張數(shù)的三順，否則拆不同張數(shù)的連牌，否則拆不同張數(shù)的雙順，否則拆不同張數(shù)的三順，否則炸之，否則PASS。 10 雙順的跟牌原則：有相同牌型的牌，則跟之，否則拆不同張數(shù)的雙順，否則拆不同張數(shù)的三順，否則拆相同張數(shù)的三順，否則炸之，否則PASS。 11 炸彈的跟牌原則：有超過所出炸彈的炸彈，或有火箭，則炸之，否則PASS。 12 炸彈帶兩手牌的跟牌原則：如果有炸彈，則炸之，否則PASS。 八、打牌原則解析 1 坐莊打法：因為坐莊的只是自己一個人，不存在配合問題，所以一般按照前面的原則出牌即可。 a) 在出牌時，如果偏家有一個人只剩一張牌時，盡量不出單牌，否則單牌由大到小出。 b) 在跟牌時，如果偏家有一個人只剩一張牌時，跟手中最大的牌。 2 偏家打法：偏家因為牽涉到配合問題，所以打法有一些不同。 a) 在出牌時，如果是莊家的上家，且莊家只剩一張牌時，盡量不出單牌，否則單牌由大到小出。 b) 在跟牌時，如果是莊家的上家，且莊家只剩一張牌時，跟手中最大的牌。 c) 當(dāng)一個偏家打出的是單牌時，一般情況下能跟就跟。如果手中必須跟2或以上的牌時，選擇PASS。 d) 當(dāng)一個偏家打出的是對子時，一般情況下能跟就跟。如果手中必須跟AA或以上的牌時，選擇PASS。 e) 如果一個偏家打出的牌是除了單牌及對子以外的牌型，則選擇PASS。 f) 如果處在下家的偏家只剩一張牌時，在出牌時出手中最小的牌。跟牌還按照一般的原則。 五 子棋算法探討(轉(zhuǎn)貼) 近來隨著計算機的快速發(fā)展，各種棋類游戲被紛紛請進了電腦，使得那些喜愛下棋，又常常苦于沒有對手的棋迷們能隨時過足棋癮。而且這類軟件個個水平頗高，大 有與人腦分庭抗禮之勢。其中戰(zhàn)勝過國際象棋世界冠軍-卡斯帕羅夫的“深藍”便是最具說服力的代表；其它像圍棋的“手淡”、象棋的“將族”等也以其優(yōu)秀的人 工智能深受棋迷喜愛；而我們今天將向大家介紹的是五子棋的算法。 當(dāng)我們與電腦對戰(zhàn)時，您知道這些軟件是怎樣象人腦一樣進行思考的嗎？ 總的來說（我們假定您熟悉五子棋的基本規(guī)則），要讓電腦知道該在哪一點下子，就要根據(jù)盤面的形勢，為每一可能落子的點計算其重要程度，也就是當(dāng)這子落下后 會形成什么棋型（如：“沖四”、“活三”等），然后通覽全盤選出最重要的一點，這便是最基本的算法。當(dāng)然，僅靠當(dāng)前盤面進行判斷是遠遠不夠的，這樣下棋很 容易掉進玩家設(shè)下的陷阱，因為它沒有考慮以后的變化。所以在此基礎(chǔ)上我們加入遞歸調(diào)用，即：在電腦中預(yù)測出今后幾步的各種走法，以便作出最佳選擇，這也是 我們下棋時常說的“想了幾步”。如此一來您的程序便具有一定的水平了。什么？不信！過來試試吧！ 總體思路弄清之后，下面進行具體討論：一：數(shù)據(jù)結(jié)構(gòu)先來看看數(shù)據(jù)結(jié)構(gòu)，我們需要哪些變量？首先得為整個棋盤建立一張表格用以記錄棋子信息，我們使用一個 15*15的二維數(shù)組 Table[15][15] (15*15是五子棋棋盤的大小)，數(shù)組的每一個元素對應(yīng)棋盤上的一個交叉點，用‘0’表示空位、‘1’代表己方的子、‘2’代表對方的子；這張表也是今 后分析的基礎(chǔ)。在此之后還要為電腦和玩家雙方各建立一張棋型表Computer[15][15][4]和Player[15][15][4]，用來存放棋 型數(shù)據(jù)，就是剛才所說的重要程度，比如用‘20’代表“沖四”的點，用‘15’代表“活三”的點，那么在計算重要性時，就可以根據(jù)20>15得出前 者比后者重要，下子時電腦便會自動選擇“沖四”的點。那為什么棋型表要使用三維數(shù)組呢？因為棋盤上的每一個點都可以與橫、豎、左斜、右斜四個方向的棋子構(gòu) 成不同的棋型，所以一個點總共有4個記錄；這樣做的另一個好處是可以輕易判斷出復(fù)合棋型，例如：如果同一點上有2個‘15’就是雙三、有一個‘15’和一 個‘20’就是四三。怎么樣！3個數(shù)組構(gòu)成了程序的基本數(shù)據(jù)骨架，今后只要再加入一些輔助變量便可以應(yīng)付自如了。應(yīng)該不會太難吧？OK！有了這么多有用的 數(shù)據(jù)，我們就可以深入到程序的流程中去了。 二：程序流程 我們主要討論五子棋的核心算法，即：人工智能部分，而其他像圖形顯示、鍵盤鼠標(biāo)控制等，因較為簡單，所以就不作過多介紹了。 首先，請仔細(xì)閱讀圖1： 我們看到本程序由六個基本功能模塊構(gòu)成，各模塊的詳細(xì)分析如下：（1） 初始化：首先，建立盤面數(shù)組Table[15][15]、對戰(zhàn)雙方的棋型表Computer[15][15][4]和Player[15][15][4] 并將它們清零以備使用；然后初始化顯示器、鍵盤、鼠等輸入輸出設(shè)備并在屏幕上畫出棋盤。（2） 主循環(huán)控制模塊：控制下棋順序，當(dāng)輪到某方下子時，負(fù)責(zé)將程序轉(zhuǎn)到相應(yīng)的模塊中去，主要擔(dān)當(dāng)一個調(diào)度者的角色。（3） 玩家下子：當(dāng)輪到玩家下時，您通過鍵盤或鼠標(biāo)在棋盤上落子，程序會根據(jù)該點的位置，在Table[15][15]數(shù)組的相應(yīng)地方記錄‘2’，以表明該子是 玩家下的。（4） 盤面分析填寫棋型表：本程序核心模塊之一，人工智能算法的根本依據(jù)！其具體實現(xiàn)方法如下：您在下五子棋時，一定會先根據(jù)棋盤上的情況，找出當(dāng)前最重要的一 些點位，如“活三”、“沖四”等；然后再在其中選擇落子點。但是，電腦不會像人一樣分析問題，要讓它知道哪是“活三”、哪是“沖四”，就得在棋盤上逐點計 算，一步一步的教它。 先來分析己方的棋型，我們從棋盤左上角出發(fā)，向右逐行搜索，當(dāng)遇到一個空白點時，以它為中心向左挨個查找，如果遇到己方的子則記錄然后繼續(xù)，如果遇到對方 的子、空白點或邊界就停止查找。左邊完成后再向右進行同樣的操作；最后把左右兩邊的記錄合并起來，得到的數(shù)據(jù)就是該點橫向上的棋型，然后把棋型的編號填入 到Computer[x][y][n]中就行了（x、y代表坐標(biāo)，n=0、1、2、3分別代表橫、豎、左斜、右斜四個方向）。而其他三個方向的棋型也可用 同樣的方法得到，當(dāng)搜索完整張棋盤后，己方棋型表也就填寫完畢了。然后再用同樣的方法填寫對方棋型表。 注意：所有棋型的編號都要事先定義好，越重要的號數(shù)越大！ OK! 怎么樣？有點累了吧？不過千萬別泄氣！因為好戲還在后頭。 Let’s go?。?） 電腦下子：有了上面填寫的兩張棋型表，現(xiàn)在要作的就是讓電腦知道在哪一點下子了。其中最簡單的計算方法，就是遍歷棋型表Computer[15][15] [4]和Player[15][15][4]找出其中數(shù)值最大的一點，在該點下子即可。但這種算法的弱點非常明顯，只顧眼前利益，不能顧全大局，這就和許 多五子棋初學(xué)者一樣犯了“目光短淺”的毛病。 要解決這個問題，我們引入‘今后幾步預(yù)測法’，具體方法是這樣的： 首先， 讓電腦分析一個可能的點，如果在這兒下子將會形成對手不得不防守的棋型（例如：‘沖四’、‘活三’）；那么下一步對手就會照您的思路下子來防守您，如此一 來便完成了第一步的預(yù)測。這時再調(diào)用模塊4對預(yù)測后的棋進行盤面分析，如果出現(xiàn)了‘四三’、‘雙三’或‘雙四’等制勝點，那么己方就可以獲勝了（當(dāng)然對黑 棋而言‘雙三’、‘雙四’是禁手，另當(dāng)別論）；否則照同樣的方法向下分析，就可預(yù)測出第二步、第三步…… 等一等，要是盤面上沒有對手必須防的棋型，哪該怎么辦呢？進攻不成的話就得考慮防守了，將自己和對手調(diào)換一下位置，然后用上面的方法來預(yù)測對手的棋，這樣 既可以防住對手巧妙的攻擊，又能侍機發(fā)動反擊，何樂而不為呢！ 但是必須告訴大家的是：預(yù)測法的運算量相當(dāng)之大，據(jù)我的經(jīng)驗，用Pentium-100預(yù)測3步的走法平均需要15秒以上時間，所以建議預(yù)測量在5步以 內(nèi)?？蓜e小瞧了這5步，有時它甚至?xí)叱鲎屇氖纸薪^的妙著呢！（6） 勝負(fù)判斷：務(wù)須多言，某方形成五子連即獲勝；若黑棋走出‘雙三’、‘雙四’或長連即以禁手判負(fù)。 到現(xiàn)在為止，整個五子棋軟件就基本完成了，其水平大約在中級上下。當(dāng)然，這種算法并不是最好的，但我相信它的基本思路是正確的。 |
|
|
