斗地主基本算法思想

-.z.三人斗地主算法基本思想一、牌型

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或9。2和大小王不可以連。

9三順：二個或更多的連續(xù)三條組成的牌型，比如777888或7。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)過上述選取、擴展和合并，則將一手牌中的所有連牌提取出來了，舉例如下：假定一手牌是：2AKQJ43

第一步，選取出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é)的“再確定單牌”。

三、一手牌的手數(shù)分析

為了使斗地主機器人有一定的智能，必須對一手牌的手數(shù)進行分析。所謂一手牌的手數(shù)，指的是在沒有別人壓牌的情況下需要出幾把能將牌出完。這個數(shù)字在經(jīng)過上面的分類后是可以確定的。還以上面的一手牌22AAKQJ9987776654為例，這手牌按照前面的分析方法可以分析出以下的牌型：

22、AA、K、Q、J、987654、9、77、6的牌型通過對上面牌型的計算，可以容易得出這手牌需要9手才能出完，因此這手牌的手數(shù)就是9。

四、絕對手數(shù)和相對手數(shù)的概念

因為在斗地主游戲中存在火箭或炸彈的可能，所以理論上只有火箭才不可能被別人壓住，所以，可以不考慮相對手數(shù)的概念。以后都簡稱手數(shù)。

五、叫牌原則分析

因為在斗地主中，火箭、炸彈、王和2可以認為是大牌，所以叫牌需要按照這些牌的多少來判斷。下面是一個簡單的原則：

假定火箭為8分，炸彈為6分，大王4分，小王3分，一個2為2分，則當分數(shù)

大于等于7分時叫三倍；

大于等于5分時叫二倍；

大于等于3分時叫一倍；

小于三分不叫。

六、出牌的一般原則

1出牌的原則一般按照從小到大的原則，即首先出包含最小牌的組合（單牌、對子、雙順、連牌、三順、三條等，炸彈、火箭不包括在內(nèi)）。

2三條的出牌原則：因為三條出牌可以帶一*單牌或一個對子，所以在出三條時需要檢測是否有單牌，如果有，則帶一*最小的單牌，如果沒有，則再檢測是否存在對子，如果有，則跟一個最小的對子，如果單牌和對子都沒有，則出三條。

在帶牌時，除非是只剩兩手牌，否則不能帶王或2。

3三順的出牌原則：因為三順出牌可以帶兩*（或更多）單牌或兩個（或更多）對子，所以與出三條一樣，需要檢測是否有單牌或?qū)ψ印Ｈ绻凶銐蚨嗟膯闻苹驅(qū)ψ?，則將其帶出。如果有單牌，但沒有足夠多的單牌，則檢查是否有6連以上的連牌，如果有將連牌的最小*數(shù)當作單牌帶出。如果有對子，但沒有足夠多的對子，則檢查是否有4連以上的雙順，如果有將雙順的最小對子當作對子帶出。

在帶牌時，除非是只剩兩手牌，否則不能帶王或2。

4連牌的出牌原則：直接出。

5雙順的出牌原則：直接出。

6對子的出牌原則：因為對子可以用三條、三順等帶出，所以在出對子時，應(yīng)該先檢測一下三條＋三順（中三條）的數(shù)量，如果所有三條數(shù)量<=對子＋單牌數(shù)量總和－2時，出對子，否則出三帶2等等。

7單牌的出牌原則：因為單牌可以用三條、三順等帶出，所以在出單牌時，應(yīng)該先檢測一下三條＋三順（中三條）的數(shù)量，如果所有三條數(shù)量<=對子＋單牌數(shù)量總和－2時，出單牌，否則出三帶1等等。

七、跟牌的一般原則

1如果手中有獨立的，與所出的牌一樣牌型的牌時，先跟之。

22可以作為單牌、對子、三條等形式跟出。

3當手中沒有相應(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)當一個偏家打出的是單牌時，一般情況下能跟就跟。如果手中必須跟2或以上的牌時，選擇PASS。

d)當一個偏家打出的是對子時，一般情況下能跟就跟。如果手中必須跟AA或以上的牌時，選擇PASS。

e)如果一個偏家打出的牌是除了單牌及對子以外的牌型，則選擇PASS。

f)如果處在下家的偏家只剩一*牌時，在出牌時出手中最小的牌。跟牌還按照一般的原則。

五子棋算法探討(轉(zhuǎn)貼)近來隨著計算機的快速發(fā)展，各種棋類游戲被紛紛請進了電腦，使得那些喜愛下棋，又常?？嘤跊]有對手的棋迷們能隨時過足棋癮。而且這類軟件個個水平頗高，大有與人腦分庭抗禮之勢。其中戰(zhàn)勝過國際象棋世界冠軍-卡斯帕羅夫的“深藍”便是最具說服力的代表；其它像圍棋的“手淡”、象棋的“將族”等也以其優(yōu)秀的人工智能深受棋迷喜愛；而我們今天將向大家介紹的是五子棋的算法。當我們與電腦對戰(zhàn)時，您知道這些軟件是怎樣象人腦一樣進行思考的嗎？總的來說（我們假定您熟悉五子棋的基本規(guī)則），要讓電腦知道該在哪一點下子，就要根據(jù)盤面的形勢，為每一可能落子的點計算其重要程度，也就是當這子落下后會形成什么棋型（如：“沖四”、“活三”等），然后通覽全盤選出最重要的一點，這便是最基本的算法。當然，僅靠當前盤面進行判斷是遠遠不夠的，這樣下棋很容易掉進玩家設(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ǔ)。在此之后還要為電腦和玩家雙方各建立一*棋型表puter[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ù)，我們就可以深入到程序的流程中去了。二：程序流程我們主要討論五子棋的核心算法，即：人工智能部分，而其他像圖形顯示、鍵盤鼠標控制等，因較為簡單，所以就不作過多介紹了。首先，請仔細閱讀圖1：我們看到本程序由六個基本功能模塊構(gòu)成，各模塊的詳細分析如下：（1）初始化：首先，建立盤面數(shù)組Table[15][15]、對戰(zhàn)雙方的棋型表puter[15][15][4]和Player[15][15][4]并將它們清零以備使用；然后初始化顯示器、鍵盤、鼠等輸入輸出設(shè)備并在屏幕上畫出棋盤。（2）主循環(huán)控制模塊：控制下棋順序，當輪到*方下子時，負責(zé)將程序轉(zhuǎn)到相應(yīng)的模塊中去，主要擔當一個調(diào)度者的角色。（3）玩家下子：當輪到玩家下時，您通過鍵盤或鼠標在棋盤上落子，程序會根據(jù)該點的位置，在Table[15][15]數(shù)組的相應(yīng)地方記錄‘2’，以表明該子是玩家下的。（4）盤面分析填寫棋型表：本程序核心模塊之一，人工智能算法的根本依據(jù)！其具體實現(xiàn)方法如下：您在下五子棋時，一定會先根據(jù)棋盤上的情況，找出當前最重要的一些點位，如“活三”、“沖四”等；然后再在其中選擇落子點。但是，電腦不會像人一樣分析問題，要讓它知道哪是“活三”、哪是“沖四”，就得在棋盤上逐點計算，一步一步的教它。先來分析己方的棋型，我們從棋盤左上角出發(fā)，向右逐行搜索，當遇到一個空白點時，以它為中心向左挨個查找，如果遇到己方的子則記錄然后繼續(xù)，如果遇到對方的子、空白點或邊界就停止查找。左邊完成后再向右進行同樣的操作；最后把左右兩邊的記錄合并起來，得到的數(shù)據(jù)就是該點橫向上的棋型，然后把棋型的編號填入到puter[*][y][n]中就行了（*、y代表坐標，n=0、1、2、3分別代表橫、豎、左斜、右斜四個方向）。而其他三個方向的棋型也可用同樣的方法得到，當搜索完整*棋盤后，己方棋型表也就填寫完畢了。然后再用同樣的方法填寫對方棋型表。注意：所有棋型的編號都要事先定義好，越重要的號數(shù)越大！OK!怎么樣？有點累了吧？不過千萬別泄氣！