Repeated games describe situations where players interact with each other in a dynamic pattern and make decisions ac- cording to outcomes of previous stage games. Very recently, Press and Dyson have revealed a new cla...Repeated games describe situations where players interact with each other in a dynamic pattern and make decisions ac- cording to outcomes of previous stage games. Very recently, Press and Dyson have revealed a new class of zero-determinant （ZD） strategies for the repeated games, which can enforce a fixed linear relationship between expected payoffs of two play- ers, indicating that a smart player can control her unwitting co-player＇s payoff in a unilateral way [Proc. Acad. Natl. Sci. USA 109, 10409 （2012）]. The theory of ZD strategies provides a novel viewpoint to depict interactions among players, and fundamentally changes the research paradigm of game theory. In this brief survey, we first introduce the mathematical framework of ZD strategies, and review the properties and constrains of two specifications of ZD strategies, called pinning strategies and extortion strategies. Then we review some representative research progresses, including robustness analysis, cooperative ZD strategy analysis, and evolutionary stability analysis. Finally, we discuss some significant extensions to ZD strategies, including the multi-player ZD strategies, and ZD strategies under noise. Challenges in related research fields are also listed.展开更多
There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum ga...There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum game, and prove that it is theoretically a polynomial time algorithm. We implement the Karmarkar method, and a preliminary computational result shows that it performs well for zero-sum games. We also mention an affine scaling method that would help us compute Nash equilibria of general zero-sum games effectively.展开更多
In this paper, we consider multiobjective two-person zero-sum games with vector payoffs and vector fuzzy payoffs. We translate such games into the corresponding multiobjective programming problems and introduce the pe...In this paper, we consider multiobjective two-person zero-sum games with vector payoffs and vector fuzzy payoffs. We translate such games into the corresponding multiobjective programming problems and introduce the pessimistic Pareto optimal solution concept by assuming that a player supposes the opponent adopts the most disadvantage strategy for the self. It is shown that any pessimistic Pareto optimal solution can be obtained on the basis of linear programming techniques even if the membership functions for the objective functions are nonlinear. Moreover, we propose interactive algorithms based on the bisection method to obtain a pessimistic compromise solution from among the set of all pessimistic Pareto optimal solutions. In order to show the efficiency of the proposed method, we illustrate interactive processes of an application to a vegetable shipment problem.展开更多
A conflict of three players, including an attacker, a defender, and a target with bounded control is discussed based on the differential game theories in which the target and the defender use an optimal pursuit strate...A conflict of three players, including an attacker, a defender, and a target with bounded control is discussed based on the differential game theories in which the target and the defender use an optimal pursuit strategy. The current approach chooses the miss distance as the outcome of the conflict. Different optimal guidance laws are investigated, and feasible conditions are analyzed for the attacker to accomplish an attacking task. For some given conditions, the attacker cannot intercept the target by only using a one-to-one optimal pursuit guidance law; thus, a guidance law for the attacker to reach a critical safe value is investigated.Specifically, the guidance law is divided into two parts. Before the engagement time between the defender and the attacker, the attacker uses this derived guidance law to guarantee that the evasion distance from the defender is safe, and that the zero-effort-miss(ZEM) distance between the attacker and the target is the smallest.After that engagement time, the attacker uses the optimal one-toone guidance law to accomplish the pursuit task. The advantages and limited conditions of these derived guidance laws are also investigated by using nonlinear simulations.展开更多
Minimax algorithm and machine learning technologies have been studied for decades to reach an ideal optimization in game areas such as chess and backgammon. In these fields, several generations try to optimize the cod...Minimax algorithm and machine learning technologies have been studied for decades to reach an ideal optimization in game areas such as chess and backgammon. In these fields, several generations try to optimize the code for pruning and effectiveness of evaluation function. Thus, there are well-armed algorithms to deal with various sophisticated situations in gaming occasion. However, as a traditional zero-sum game, Connect-4 receives less attention compared with the other members of its zero-sum family using traditional minimax algorithm. In recent years, new generation of heuristics is created to address this problem based on research conclusions, expertise and gaming experiences. However, this paper mainly introduced a self-developed heuristics supported by well-demonstrated result from researches and our own experiences which fighting against the available version of Connect-4 system online. While most previous works focused on winning algorithms and knowledge based approaches, we complement these works with analysis of heuristics. We have conducted three experiments on the relationship among functionality, depth of searching and number of features and doing contrastive test with sample online. Different from the sample based on summarized experience and generalized features, our heuristics have a basic concentration on detailed connection between pieces on board. By analysing the winning percentages when our version fights against the online sample with different searching depths, we find that our heuristics with minimax algorithm is perfect on the early stages of the zero-sum game playing. Because some nodes in the game tree have no influence on the final decision of minimax algorithm, we use alpha-beta pruning to decrease the number of meaningless node which greatly increases the minimax efficiency. During the contrastive experiment with the online sample, this paper also verifies basic characters of the minimax algorithm including depths and quantity of features. According to the experiment, these two characters can both effect the decision for each step and none of them can be absolutely in charge. Besides, we also explore some potential future issues in Connect-4 game optimization such as precise adjustment on heuristic values and inefficiency pruning on the search tree.展开更多
基金Supported by National High Technology Research and Development Program of China （863 Program） （2006AA04Z183）, National Natural Science Foundation of China （60621001, 60534010, 60572070, 60774048, 60728307）, Program for Changjiang Scholars and Innovative Research Groups of China （60728307, 4031002）
基金supported by the National Natural Science Foundation of China(Grant Nos.61004098 and 11222543)the Program for New Century Excellent Talentsin Universities of China(Grant No.NCET-11-0070)+2 种基金the Special Project of Youth Science and Technology Innovation Research Team of Sichuan ProvinceChina(Grant No.2013TD0006)the Research Foundation of UESTC and Scholars Program of Hong Kong(Grant No.G-YZ4D)
文摘Repeated games describe situations where players interact with each other in a dynamic pattern and make decisions ac- cording to outcomes of previous stage games. Very recently, Press and Dyson have revealed a new class of zero-determinant （ZD） strategies for the repeated games, which can enforce a fixed linear relationship between expected payoffs of two play- ers, indicating that a smart player can control her unwitting co-player＇s payoff in a unilateral way [Proc. Acad. Natl. Sci. USA 109, 10409 （2012）]. The theory of ZD strategies provides a novel viewpoint to depict interactions among players, and fundamentally changes the research paradigm of game theory. In this brief survey, we first introduce the mathematical framework of ZD strategies, and review the properties and constrains of two specifications of ZD strategies, called pinning strategies and extortion strategies. Then we review some representative research progresses, including robustness analysis, cooperative ZD strategy analysis, and evolutionary stability analysis. Finally, we discuss some significant extensions to ZD strategies, including the multi-player ZD strategies, and ZD strategies under noise. Challenges in related research fields are also listed.
文摘There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum game, and prove that it is theoretically a polynomial time algorithm. We implement the Karmarkar method, and a preliminary computational result shows that it performs well for zero-sum games. We also mention an affine scaling method that would help us compute Nash equilibria of general zero-sum games effectively.
文摘In this paper, we consider multiobjective two-person zero-sum games with vector payoffs and vector fuzzy payoffs. We translate such games into the corresponding multiobjective programming problems and introduce the pessimistic Pareto optimal solution concept by assuming that a player supposes the opponent adopts the most disadvantage strategy for the self. It is shown that any pessimistic Pareto optimal solution can be obtained on the basis of linear programming techniques even if the membership functions for the objective functions are nonlinear. Moreover, we propose interactive algorithms based on the bisection method to obtain a pessimistic compromise solution from among the set of all pessimistic Pareto optimal solutions. In order to show the efficiency of the proposed method, we illustrate interactive processes of an application to a vegetable shipment problem.
基金supported by the National Natural Science Foundation of China(11672093)
文摘A conflict of three players, including an attacker, a defender, and a target with bounded control is discussed based on the differential game theories in which the target and the defender use an optimal pursuit strategy. The current approach chooses the miss distance as the outcome of the conflict. Different optimal guidance laws are investigated, and feasible conditions are analyzed for the attacker to accomplish an attacking task. For some given conditions, the attacker cannot intercept the target by only using a one-to-one optimal pursuit guidance law; thus, a guidance law for the attacker to reach a critical safe value is investigated.Specifically, the guidance law is divided into two parts. Before the engagement time between the defender and the attacker, the attacker uses this derived guidance law to guarantee that the evasion distance from the defender is safe, and that the zero-effort-miss(ZEM) distance between the attacker and the target is the smallest.After that engagement time, the attacker uses the optimal one-toone guidance law to accomplish the pursuit task. The advantages and limited conditions of these derived guidance laws are also investigated by using nonlinear simulations.
文摘Minimax algorithm and machine learning technologies have been studied for decades to reach an ideal optimization in game areas such as chess and backgammon. In these fields, several generations try to optimize the code for pruning and effectiveness of evaluation function. Thus, there are well-armed algorithms to deal with various sophisticated situations in gaming occasion. However, as a traditional zero-sum game, Connect-4 receives less attention compared with the other members of its zero-sum family using traditional minimax algorithm. In recent years, new generation of heuristics is created to address this problem based on research conclusions, expertise and gaming experiences. However, this paper mainly introduced a self-developed heuristics supported by well-demonstrated result from researches and our own experiences which fighting against the available version of Connect-4 system online. While most previous works focused on winning algorithms and knowledge based approaches, we complement these works with analysis of heuristics. We have conducted three experiments on the relationship among functionality, depth of searching and number of features and doing contrastive test with sample online. Different from the sample based on summarized experience and generalized features, our heuristics have a basic concentration on detailed connection between pieces on board. By analysing the winning percentages when our version fights against the online sample with different searching depths, we find that our heuristics with minimax algorithm is perfect on the early stages of the zero-sum game playing. Because some nodes in the game tree have no influence on the final decision of minimax algorithm, we use alpha-beta pruning to decrease the number of meaningless node which greatly increases the minimax efficiency. During the contrastive experiment with the online sample, this paper also verifies basic characters of the minimax algorithm including depths and quantity of features. According to the experiment, these two characters can both effect the decision for each step and none of them can be absolutely in charge. Besides, we also explore some potential future issues in Connect-4 game optimization such as precise adjustment on heuristic values and inefficiency pruning on the search tree.
