麻將胡牌的演算法
一個人會不會打麻將有一項基本的判斷方法,「能夠判斷是否胡牌」。在實戰中,判斷的速度越快越好,如此才能在麻將桌上取捨牌的時候,很快的知道打哪張牌聽的牌比較好,也不會因為停下來比畫思考,被看穿手裡擁有的牌型。
要知道聽什麼牌,最快的方式是背起來。常打麻將的人,腦中自然背了不少牌型,常見牌型瞬間就能判斷,除非拿了許多同花色的牌才會造成困擾。
電腦程式如何判斷聽牌?
打麻將要判斷聽牌,得先知道胡牌的牌型,如同要準備晚餐的食材之前,得先知道晚餐想吃什麼。
一般都是刪除「一刻(3張相同牌)」或「一順(3張連續牌)」,也就是所謂的「搭子」,再利用「遞迴」程序處理。這樣做的效率並不太優,雖然判斷一副牌還是瞬間完成,但若要判斷十萬副牌局,效率好壞造成的影響非常之大。
麻將定理1
在麻將玩法中,一副牌P,若把一個對子(俗稱眼睛)拿掉後,假設此時數字最小的牌是x。
若x的張數是3張以上,則拿掉3張x(一刻)後,剩下牌為Q。
否則拿掉x, x+1, x+2(一順)之後,剩下的牌為Q。(若無法拿,則P沒胡)
則「P胡」若且唯若「Q胡」。
舉例說明:
例1:判斷P = 33345678是否胡牌?
P中唯一能當眼睛的地方,就是3,因此把33一對眼睛拿掉,變成Q=345678,Q是胡牌型,所以P也是。
例2:判斷P = 55666777889是否胡牌?
其中55、66、77、88都可以當眼睛,每種情況都試一次。
若55當眼,剩下666777889;最小的6有三張,直接拿掉666,剩777889,再拿777,得889,所以沒胡。
若66當眼,剩下556777889;最小的是兩張5,但沒有辦法拿掉兩個567了,所以沒胡。
若77當眼,剩下556667889;最小的是兩張5,但沒有辦法拿掉兩個567了,所以沒胡。
各種能拿掉眼睛的方式都試過,都無法胡,所以P不是胡牌型。
這樣做的好處,是只要拿掉一副牌的眼睛後,就可以一路由最小的牌取到最大的牌,依序檢驗,「線性時間」即可判斷是否胡牌,避免來來去去的反覆嘗試,省下非常多的計算時間。
已經學會胡牌型之後,判斷聽牌就簡單了。
只要試著加入任何一張牌,再嘗試拿掉各種可能的眼睛,利用定理1判斷是否可以胡牌,即可得知聽哪些牌,僅需要O(n3)的時間。
例3:判斷3456667888聽什麼牌?
加入1,剩13開頭,沒胡
加入2
拿掉66,剩234567888,胡!
拿掉88,剩234566678,沒胡
加入3
拿掉33,剩456667888,沒胡
拿掉66或88,剩334開頭,沒胡
加入4
拿掉44,剩35開頭,沒胡
拿掉66或88,剩3445開頭,沒胡
加入5,略,胡
加入6,略,胡
加入7,略,胡
加入8,略,胡
加入9,略,胡
上述方法雖然是電腦的麻將判斷方式,但其實人腦判斷,也是相同道理,先把可能的眼睛拿出來,然後最小牌能拿走一刻即拿走一刻,否則試著拿走一順,由於人腦很強大,會自動省略一些無關緊要的判斷步驟,因此執行速度並不會太慢。
奴役電腦幫你辦事
有了快速判斷聽牌、胡牌的方法後,就可以開開心心奴役電腦幫我們做一些血汗麻將技巧了。
李志希教授的電腦幫忙跑了所有的情況,發現十三張麻將除了「國士無雙」(俗稱十三么)可以聽十三張牌之外,聽九個洞的情況只有一種:1112345678999,俗稱「九連寶燈」。而聽八個洞的情況有16種;聽七個洞的情況有79種。
筆者自己也計算了台灣麻將十六張的情況:聽九個洞的情況有11種,有1122233345678999、1112345667788999、1112345666777888、1112345566778999、1112344556678999,或是上述平移、對稱的牌型。聽八洞的情況有94種;聽七個洞的則有532種。
眼睛的判斷
從麻將規則的方法告訴我們判斷胡牌與否,先找出眼睛會比較快。一旦眼睛的選擇多,事情就變得越複雜,電腦當然沒問題,但人腦判斷可能稍微慢了一點。此時,數學可以派上用場。
方法是這樣的,先只看同個花色,把所有的牌分成3堆:「一四七」堆,「二五八」堆,「三六九」堆,接著觀察每堆的張數。
例如上面的牌型,其中三六九牌共7張,二五八牌共6張,一四七牌共4張。
這樣一眼就知道沒有胡牌,完全不用去試。
什麼!?為什麼可以這麼快?因為我有獨門秘技。
獨門秘技
麻將若要胡牌的話,要抓成三個三個一組的搭子再搭配一對眼睛,搭子若是「順」,貢獻這三堆的個數必同時都加1;搭子若是「刻」,則某一堆會加3。
因此,若先不看眼睛,這三堆的牌數除以3的餘數應該要相等。再加上眼睛,就只會讓某一堆個數與其他兩堆不同。
以上例來說,三堆的張數分別為7、6、4張,除以3的餘數為1、0、1,於是,眼睛只有可能出現在第二堆,也就是二五八。若55拿掉,前半的33344無法湊成兩搭,因此沒胡;若88拿掉,依定理1,333也可以拿掉,剩下的局部44556也無法湊成兩搭,所以也無法胡牌。
我們再將這個結果寫成定理(沒辦法,數學家就是喜歡這樣XD)
麻將定理2
一副牌,依一四七、二五八、三六九分成三堆,每堆的張數除以三的餘數必有一個與另兩個不同,則眼睛就在不同的那堆裡。
回到古天樂手上拿的牌型來說:23333444455556666是否胡牌呢?
因為一四七有4張,二五八有5張,三六九有8張,除以3分別餘1、2、2,所以眼睛只可能是44,接著把44拿掉,剩下 233334455556666,然後利用定理1依序去拿,得到234、333、456、555、666,所以是胡牌型。
有了定理2,判斷胡牌時眼睛的可能性,可縮減到一堆,檢驗至多三次,大幅提升計算效率。
當整副牌同時有萬、筒、條、字的時候,因為眼睛只會在其中一種花色,因此其它花色一定都是3的倍數,利用張數就可以推判眼睛在哪個花色,所以只要能判斷其中一種花色即可。
假想一個更困難的例子,每張牌可以超過4張的話,請問:33333444555566777888899999有沒有胡牌?
三六九,共12張,除以3餘0
一四七,共6張,除以3餘0
二五八,共8張,除以3餘2
在娛樂城,所以若能胡牌的話,眼睛必是55或88:假設是55,利用定理1,由小到大拿成333、345、345後,剩466777888899999,而4的後面斷了,所以沒有胡。
假設是88,利用定理1,由小到大拿成333、345、345、456、567、789、789、999,胡牌。