Simple Trick Taking Gaming Based On Alpha-Beta Pruning And Heuristic Calculus

The Trick-Taking Game is a kind of zero-sum dynamic game.It is represented by Contract Bridge and is a long-term intellectual activity of human beings.It not only improves the intelligence level of human beings,but also has a high guiding value for industrial production,economic behavior and the study of other science and technology.The solving of trick-taking games is an important task in the field of machine gaming.The main problems are:the rules of the game often include incomplete information,whereas the prediction of incomplete information depends on the efficient soving of complete information;the naive complexity of the game is usually O(P(n!~m))and even higher,and the computational complexity is a huge obstacle to game solving.In view of the above problems,this paper determines the research target as a simplified form of the Trick-Taking Game,and uses the form deduction and statistical analysis to study inner laws and solving methods of the game.Finally,the effectiveness of the rules and methods is verified by computer experiments.The main research work is:1.By analyzing the core characteristics of the game,we defined the Simple Trick-Taking Game(STTG)model and its Sequence Diagram Structure.The optimal solution and optimal strategy of STTG and their equivalence relationship are defined according to the Min-Max principle.2.Through form deductions,the properties such as uniformity and saturation of STTG adjacency structure are found and proved.Through statistical analysis,the properties of adjacent balance,offensive balance,defensive balance and symmetry balance of STTG optimal solution are found and verified.According to these properties,the Defensive Decision Tree and the Precise Pruning Algorithm(PP)are proposed,which reduces the computational complexity of the accurate solving from O(n!~2)to O(n!).3.A Mediation Evaluation(ME)model of approximate solving is proposed,including feature mediation model and random mediation model.The Adjacent Graph(AG)and the Optimal Solution Distribution(OSD)are statistically analyzed.In this paper,three sets of experiments were completed using the self-written STTG debugging framework,which were used to test PP and ME and statistical analysis of AG and OSD.The results show that the absolute accuracy of PP in the statistical range is 100%,the computational complexity is in line with expectations;the relative coincidence of ME reaches 92.56%;AG grows in a centrally symmetric pattern;OSD obeys a normal distribution similar with an offset central axis.Experiments have shown the effectiveness of PP and ME,laying the foundation for subsequent research on STTG.