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.展开更多
As computers have become faster at performing computations over the decades, algorithms to play games have also become more efficient. This research paper seeks to see how the performance of the Minimax search evolves...As computers have become faster at performing computations over the decades, algorithms to play games have also become more efficient. This research paper seeks to see how the performance of the Minimax search evolves on increasing Connect-4 grid sizes. The objective of this study is to evaluate the effectiveness of the Minimax search algorithm in making optimal moves under different circumstances and to understand how well the algorithm scales. To answer this question we tested and analyzed the algorithm several times on different grid sizes with a time limit to see its performance as the complexity increases, we also looked for the average search depth for each grid size. The obtained results show that despite larger grid sizes, the Minimax search algorithm stays relatively consistent in terms of performance.展开更多
In this paper,a class of unconstrained discrete minimax problems is described,in which the objective functions are in C 1.The paper deals with this problem by means of taking the place of maximum entropy function...In this paper,a class of unconstrained discrete minimax problems is described,in which the objective functions are in C 1.The paper deals with this problem by means of taking the place of maximum entropy function with adjustable entropy function.By constructing an interval extension of adjustable entropy function an d some region deletion test rules,a new interval algorithm is presented.The rele vant properties are proven.The minimax value and the localization of the minimax points of the problem can be obtained by this method. This method can overcome the flow problem in the maximum entropy algorithm.Both theoretical and numerica l results show that the method is reliable and efficient.展开更多
An interval algorlthm for inequality coustrained discrete minimax problems is described, in which the constrained and objective functions are C1 functions. First, based on the penalty function methods, we trans form t...An interval algorlthm for inequality coustrained discrete minimax problems is described, in which the constrained and objective functions are C1 functions. First, based on the penalty function methods, we trans form this problem to unconstrained optimization. Second, the interval extensions of the penalty functions and the test rules of region deletion are discussed. At last, we design an interval algorithm with the bisection rule of Moore. The algorithm provides bounds on both the minimax value and the localization of the minimax points of the problem. Numerical results show that algorithm is reliable and efficiency.展开更多
In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting....In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching algorithms on unbounded intervals. Dynamic programming equations, combined with a series of liner programming problems, describe relations between results for every pair of successive evaluations of function f in parallel. Properties of optimal search strategies are derived from these equations. The worst-case complexity analysis shows that, if the maximizer is located on a priori unknown interval (n-1], then it can be detected after cp(n)=「2log「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.展开更多
This paper investigates the cost control problem of congestion management model in the real-time power systems. An improved optimal congestion cost model is built by introducing the congestion factor in dealing with t...This paper investigates the cost control problem of congestion management model in the real-time power systems. An improved optimal congestion cost model is built by introducing the congestion factor in dealing with the cases: opening the generator side and load side simultaneously. The problem of real-time congestion management is transformed to a nonlinear programming problem. While the transmission congestion is maximum, the adjustment cost is minimum based on the ant colony algorithm, and the global optimal solu-tion is obtained. Simulation results show that the improved optimal model can obviously reduce the adjust-ment cost and the designed algorithm is safe and easy to implement.展开更多
文摘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.
文摘As computers have become faster at performing computations over the decades, algorithms to play games have also become more efficient. This research paper seeks to see how the performance of the Minimax search evolves on increasing Connect-4 grid sizes. The objective of this study is to evaluate the effectiveness of the Minimax search algorithm in making optimal moves under different circumstances and to understand how well the algorithm scales. To answer this question we tested and analyzed the algorithm several times on different grid sizes with a time limit to see its performance as the complexity increases, we also looked for the average search depth for each grid size. The obtained results show that despite larger grid sizes, the Minimax search algorithm stays relatively consistent in terms of performance.
基金Supported by the National Natural Science Foundation of China(50 1 740 51 )
文摘In this paper,a class of unconstrained discrete minimax problems is described,in which the objective functions are in C 1.The paper deals with this problem by means of taking the place of maximum entropy function with adjustable entropy function.By constructing an interval extension of adjustable entropy function an d some region deletion test rules,a new interval algorithm is presented.The rele vant properties are proven.The minimax value and the localization of the minimax points of the problem can be obtained by this method. This method can overcome the flow problem in the maximum entropy algorithm.Both theoretical and numerica l results show that the method is reliable and efficient.
文摘An interval algorlthm for inequality coustrained discrete minimax problems is described, in which the constrained and objective functions are C1 functions. First, based on the penalty function methods, we trans form this problem to unconstrained optimization. Second, the interval extensions of the penalty functions and the test rules of region deletion are discussed. At last, we design an interval algorithm with the bisection rule of Moore. The algorithm provides bounds on both the minimax value and the localization of the minimax points of the problem. Numerical results show that algorithm is reliable and efficiency.
文摘In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching algorithms on unbounded intervals. Dynamic programming equations, combined with a series of liner programming problems, describe relations between results for every pair of successive evaluations of function f in parallel. Properties of optimal search strategies are derived from these equations. The worst-case complexity analysis shows that, if the maximizer is located on a priori unknown interval (n-1], then it can be detected after cp(n)=「2log「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.
文摘This paper investigates the cost control problem of congestion management model in the real-time power systems. An improved optimal congestion cost model is built by introducing the congestion factor in dealing with the cases: opening the generator side and load side simultaneously. The problem of real-time congestion management is transformed to a nonlinear programming problem. While the transmission congestion is maximum, the adjustment cost is minimum based on the ant colony algorithm, and the global optimal solu-tion is obtained. Simulation results show that the improved optimal model can obviously reduce the adjust-ment cost and the designed algorithm is safe and easy to implement.
