張志剛

（遼寧科技大學網絡信息中心，鞍山　114051）

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

張志剛

（遼寧科技大學網絡信息中心，鞍山114051）

0　引言

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

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

1　系統(tǒng)設計

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

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

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

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

程序工作流程如下：

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

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

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

2　打牌算法

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

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

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

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

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

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

（5）確定本輪打牌的贏家，繼續(xù)下一輪出牌，轉（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ù)，即目前的牌局還需要多少輪打牌才能結束；第三個數(shù)字5表示南北方還需要贏多少墩牌才能完成定約，如果想知道東西方的情況，處理以下數(shù)據(jù)就可以了；第四個數(shù)字表示當前的牌權在東西南北那家，0-北1-東2-南3-西；文件接下來的四行數(shù)據(jù)分別表示北東南西，四家手中目前剩余的牌，不用排列大小，系統(tǒng)會自動排序。最后一行數(shù)據(jù)表示目前牌權獲得者想出哪一張牌，如果不想出的話就輸入XX。

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

4　實驗分析

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

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

將牌是：Hearts；

West出第一張牌是QS；

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

定約是否能完成：Yes；

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

圖2　程序生成的打牌序列

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

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

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

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

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

5　結語

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

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

［2］何大華，陳傳波．關于橋牌的取勝策略．華中科技大學學報［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-），男，內蒙古赤峰人，碩士，工程師，研究方向為自然語言處理、算法設計與分析

2015-11-03

2015-11-17

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

雙明手橋牌；深度優(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.