雙明手橋牌打牌輔助分析程序研究

張志剛

（遼寧科技大學(xué)網(wǎng)絡(luò)信息中心，鞍山　114051）

雙明手橋牌打牌輔助分析程序研究

張志剛

（遼寧科技大學(xué)網(wǎng)絡(luò)信息中心，鞍山114051）

0　引言

隨著人工智能技術(shù)的迅速發(fā)展，棋類游戲領(lǐng)域的計算機(jī)實現(xiàn)研究已經(jīng)日趨完善。尤其是中國象棋、國際象棋、圍棋的人工智能程序已經(jīng)發(fā)展到了能和人類的大師級棋手直接對弈，并能夠取得勝利?！吧钏{(lán)”就是一個最好的證明。但是，對于牌類游戲的研究，特別是橋牌的計算機(jī)程序的實現(xiàn)，卻沒有達(dá)到棋類的智能程度。其主要原因就是，棋類游戲的信息是清晰明了的，可以用一定的數(shù)據(jù)結(jié)構(gòu)直接提供給計算機(jī)進(jìn)行智能決策；但是牌類游戲，尤其是橋牌其信息具有不完整性，即除了目前已經(jīng)打出的牌和明手牌外，不知道其他牌友中有什么牌，因此，計算機(jī)程序必須通過部分牌局信息推斷可能的牌型，從而做出下一步打法的決策。信息的不完整性和不對稱性，使得牌類游戲的求解在搜索策略上不能完全等同于或直接利用棋類游戲的技術(shù)，同時，也增加了牌類游戲的求解運算開銷。這就是牌類游戲的研究沒有趕超棋類游戲的主要原因。

對于牌類游戲的研究，橋牌計算機(jī)程序最具典型性，橋牌的搜索空間［1］和求解難度都比較大，目前的搜索方法有好多種。本文描述的是采用基本的回溯剪枝策略設(shè)計的雙明手橋牌的自動打牌系統(tǒng)。在雙明手情況下，所有的信息不完整和不對稱的情況都不存在，所以可以使用基本的剪枝策略就可以找出自動打牌的步驟。

1　系統(tǒng)設(shè)計

雙明手橋牌打牌輔助分析程序主要是將用戶輸入的牌局信息，可以是全部，可以是部分牌以及定約情況輸入給系統(tǒng)，系統(tǒng)會自動進(jìn)行打牌，給出一種取勝的策略［2］。

定理1任意初始牌局要么為南北方取勝牌局，要么為東西方取勝牌局，并且存在判定給定初始牌局是否為南北方取勝還是東西方取勝。

引理1若存在算法判定任意k+1階牌局是否是南北方取勝牌局，則存在算法判斷任意k階牌局是否為南北方取勝牌局。

上述定理和引理描述了橋牌取勝的必然性，在文獻(xiàn)［1］中給出了定理的詳細(xì)證明過程。文獻(xiàn)中取勝策略算法的運算量是比較大的，本文沒有采用，而是使用帶有位運算的回溯剪枝策略來迅速獲得給定牌局的解，并輔以可視化實現(xiàn)，便于牌手進(jìn)行結(jié)果的分析。

程序工作流程如下：

首先，讀入牌局信息。牌局信息包括：將牌的花色、當(dāng)前哪家出牌、南北家要贏多少墩、目前還需要幾墩牌才能結(jié)束和四家手中的牌詳細(xì)信息。

然后，系統(tǒng)根據(jù)目前的牌局信息進(jìn)行自動打牌，代理機(jī)會盡力搜索利于南北方贏墩的策略打牌。根據(jù)定理1和引理1可以斷定，肯定存在一個取勝打牌序列，如果南北方不能獲勝，則系統(tǒng)會盡量減少宕墩數(shù)目。

最后，將計算出的打牌次序顯示出來。

2　打牌算法

該程序的采用的是深度優(yōu)先的alpha-beta搜索來實現(xiàn)。算法處理過程如下：

（1）讀入基礎(chǔ)數(shù)據(jù)：包括將牌花色，剩余圈數(shù)，南北因該完成的定約，本圈牌權(quán)者，及本輪其要出的牌，牌手手中剩余的牌。

（2）整理剩余牌的數(shù)據(jù)，對數(shù)據(jù)進(jìn)行排序與處理。

（3）如果本輪牌權(quán)所有者指定了要出的牌，檢查其合理性，如果有則作為第一張牌，如果沒有則退出過程，提示出錯。

（4）深度搜索打牌序列，打出第一張牌后，產(chǎn)生下家的出牌，產(chǎn)生的原則：

如果當(dāng)前出牌者不是莊家，并且他有本輪首發(fā)花色的牌，則選擇同花色的最小牌；否則選擇非將牌花色最大牌。相反，如果是莊家出牌，選擇出牌的原則與之相反。

（5）確定本輪打牌的贏家，繼續(xù)下一輪出牌，轉(zhuǎn)（4）。

（6）如果完成定約則輸出合理的打牌序列，否則輸出沒有可行解。

3　系統(tǒng)的實現(xiàn)

上述算法通過CB加以實現(xiàn)，程序界面形式如圖1所示。

圖1　分析程序界面

用戶可以手動輸入牌局信息或者通過文件讀入文件。文件的格式如下：

文件的第一行數(shù)字4表示將牌花色，0-S，1-H，2-D，3-C，4-NT；第二個數(shù)字6表示剩余圈數(shù)，即目前的牌局還需要多少輪打牌才能結(jié)束；第三個數(shù)字5表示南北方還需要贏多少墩牌才能完成定約，如果想知道東西方的情況，處理以下數(shù)據(jù)就可以了；第四個數(shù)字表示當(dāng)前的牌權(quán)在東西南北那家，0-北1-東2-南3-西；文件接下來的四行數(shù)據(jù)分別表示北東南西，四家手中目前剩余的牌，不用排列大小，系統(tǒng)會自動排序。最后一行數(shù)據(jù)表示目前牌權(quán)獲得者想出哪一張牌，如果不想出的話就輸入XX。

根據(jù)上面的數(shù)據(jù)說明，可以看出，此程序的功能可以實現(xiàn)中途打牌或全局打牌的情況，基本上比較靈活。用戶可以根據(jù)自己的需要來準(zhǔn)備響應(yīng)的數(shù)據(jù)就可以了。如果用戶不想通過文件讀入數(shù)據(jù)的話可以在界面上直接輸入數(shù)據(jù)。為了提高程序的友好度，程序提供了按要求隨機(jī)生成牌局?jǐn)?shù)據(jù)，但是叫牌和首攻信息最好用戶的輸入，因為隨機(jī)產(chǎn)生數(shù)據(jù)不一定符合叫牌的常規(guī)，也就是說可以是錯誤的叫牌結(jié)論。在此并沒有加入叫牌的判斷邏輯。數(shù)據(jù)準(zhǔn)備完畢就可以運行程序來求出合理的打牌序列，看是否能夠找到完成定約的打牌序列。此程序只要找到完成所需的墩數(shù)的打牌序列就會退出，不會計算超墩的情況。

4　實驗分析

為了測試本程序算法的能力，在網(wǎng)上找了一些具體的打牌實例，通過本程序進(jìn)行自動生成打牌序列。以下是在網(wǎng)上找到的一個比較困難牌局：

程序生成的打牌序列如下：

將牌是：Hearts；

West出第一張牌是QS；

南北家需得墩數(shù)：13；

定約是否能完成：Yes；

程序找到打牌序列如圖2所示。

圖2　程序生成的打牌序列

為了找到合理打牌序列，此程序運行了大約3分鐘，最終還是找到了一個合理打牌序列。雖然找到了合理的打牌序列，但是時間還是比較長。

為了測試算法的平均效率執(zhí)行情況，將網(wǎng)上的數(shù)據(jù)經(jīng)過整理都處理成完成定約，即將東西方完成定約的直接轉(zhuǎn)換成南北方完成定約的情況。所以測試數(shù)據(jù)在打牌的過程中都是成功完成定約情況。以下是數(shù)據(jù)實驗分析結(jié)果見表1。

表1　實驗數(shù)據(jù)分析表

數(shù)據(jù)表1中最短時間基本上不到1秒鐘，通過平均運算時間可以看出程序會在2秒鐘左右計算出打牌的序列。在隨機(jī)生成數(shù)據(jù)中，因為包括叫牌在內(nèi)的數(shù)據(jù)都是隨機(jī)生成的沒有考慮到叫牌的因素，所以運行的時間比真實的數(shù)據(jù)稍長，但基本上在3秒鐘左右也會得出結(jié)論。

該算法采用的是對雙明手橋牌的進(jìn)行深度搜索，從實驗數(shù)據(jù)中可以看出性能不是很好，但是為進(jìn)一步研究和實現(xiàn)自動化橋牌程序設(shè)計奠定了研究條件。

5　結(jié)語

給出了一個采用深度優(yōu)先的alpha-beta搜索技術(shù)實現(xiàn)的玩家打牌分析程序，該程序可以幫助玩家輔助決策打牌。本程序稍作修改就可以實現(xiàn)最基本的人機(jī)博弈，為將來非確定性的推理問題的研究工作奠定了基礎(chǔ)。

［1］王彩霞，戰(zhàn)學(xué)剛，遲呈英．橋牌游戲搜索空間的研究．微計算機(jī)信息［J］，2007（23），10-2：199-200．

［2］何大華，陳傳波．關(guān)于橋牌的取勝策略．華中科技大學(xué)學(xué)報［J］，2004，7．

Double Dummy Bridge Play；Depth-First；alpha-beta Search Method

Research on Double-Dummy Bridge Playing Cards-Assisted Analysis Program

ZHANG Zhi-gang

（The Network and Information Center，University of Science and Technology，Liaoning 114051）

1007-1423（2015）34-0047-04

10.3969/j.issn.1007-1423.2015.34.013

張志剛（1980-），男，內(nèi)蒙古赤峰人，碩士，工程師，研究方向為自然語言處理、算法設(shè)計與分析

2015-11-03

2015-11-17

橋牌計算機(jī)自動打牌程序的設(shè)計與實現(xiàn)關(guān)鍵在于問題空間的搜索，而橋牌的搜索空間非常大，而對于傳統(tǒng)的蠻力搜索則面臨較大困難，因此提出解決雙明手橋牌的深度優(yōu)先的alpha-beta搜索算法，并采用C++Builder程序設(shè)計語言加以實現(xiàn)。實驗證明，該算法具有深入研究的價值，同時為計算機(jī)橋牌游戲智能化研究打下理論基礎(chǔ)。

雙明手橋牌；深度優(yōu)先；alpha-beta搜索算法

The key problem of design and implementation of the computer automatically playing the Bridge Game lies in the search space，and bridge game's search space is very large，and the traditional brute-force search method cannot easily solve it，and therefore proposes to solve double dummy bridge the depth-first alpha-beta search algorithm，uses C++Builder programming language to implement the algorithm，the experiments show that the algorithm has in-depth study of value.It is a fundamental study for the intelligent computer bridge game.