Research And Application Of Bridge Game Algorithm With Incomplete Information

In recent years,artificial intelligence attracts more and more attention,and becomes the hot topic of NPC &CPPCC(National People's Congress and Chinese People's Political Consultative Conference)this year.The study of computer game provided a lot of methods and theories for artificial intelligence,such as game search.Computer game is divided into complete information game and incomplete information game.Due to the incomplete information game is more close to the real life,such as war,stock markets and shopping malls,it attracts more and more attention.On the basis of the existing research works,this thesis studied the bridge game algorithms with incomplete information.The main contents of this thesis were as follows:(1)A GHA-BP bidding strategy based on the sampling time distribution of sliding window was proposed.The ambiguity of the bidding methods used by human had always been one of the most important problem in computer bridge biddings.However,it was unreasonable in the allocation of sampling time,and the accuracy of bidding based on ID3 algorithm was not high,which leaded to the limited learning ability to bridge bidding.In order to solve these problems,an improved bidding strategy was proposed.Firstly,the sliding window was used to predict the distribution of sampling time.Then,the GHA-BP neural network was employed to handle the ambiguity in bridge-bidding.The experimental results showed that the strategy improve the efficiency and accuracy of bridge bidding strategies.Moreover,our method reduced the difference with the double dummy bridge bidding results.(2)A heuristic Monte Carlo card playing strategy was proposed.The incomplete information had always been one of the most important problem in computer bridge playing.A feasible way to solve the problem by the random sampling method was presented in the existing Monte Carlo card playing strategy.However,the blindness of the conventional sampling method leaded to the problem of low sampling efficiency.To handle the problem,an improved Monte Carlo card playing strategy was proposed.Heuristic idea was used to generate the samples of hand of cards.Experiments showed that this strategy could produce more samples satisfying the bid constraints with the same time,and simulate the current situation more accurately,in order to make a more reasonable playing decision.(3)Based on the presented bridge game algorithms,a computer bridge game system was designed and implemented.The system included the control system and the bridge AI programs.AIs could communicate with each other.This system validated the algorithms presented in the previous chapters.