This paper presents a distributed game tree search algorithm called DDS. Based on communication overhead, st,orage requirement, speed up, and oiller factors, the performance of algorithm DDS* is analysed, and the numb...This paper presents a distributed game tree search algorithm called DDS. Based on communication overhead, st,orage requirement, speed up, and oiller factors, the performance of algorithm DDS* is analysed, and the number of nodes searched with SSS as well as a-b algorithm. The simulation test shows that. DDS* is an efficient and practical search algorithm.展开更多
We developed a new approach for the reconstruction of phylogeny trees based on the chaos game representation (CGR) of biological sequences. The chaos game representation (CGR) method generates a picture from a biologi...We developed a new approach for the reconstruction of phylogeny trees based on the chaos game representation (CGR) of biological sequences. The chaos game representation (CGR) method generates a picture from a biological sequence, which displays both local and global patterns. The quantitative index of the biological sequence is extracted from the picture. The Kullback-Leibler discrimination information is used as a diversity indicator to measure the dissimilarity of each pair of biological sequences. The new method is inspected by two data sets: the Eutherian orders using concatenated H-stranded amino acid sequences and the genome sequence of the SARS and coronavirus. The phylogeny trees constructed by the new method are consistent with the commonly accepted ones. These results are very promising and suggest more efforts for further developments.展开更多
Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art pr...Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art program, on two Intel Xeon shared-memory multiprocessor systems. Our analysis shows that Crafty is latency-sensitive and the hash-table and dynamic tree splitting used in Crafty cause large scalability penalties. They consume 35%-50% of the running time on the 4-way system. Furthermore, Crafty is not bandwidth-limited.展开更多
Device to device(D2 D) multi-hop communication in multicast networks solves the contradiction between high speed requirements and limited bandwidth in regional data sharing communication services. However, most networ...Device to device(D2 D) multi-hop communication in multicast networks solves the contradiction between high speed requirements and limited bandwidth in regional data sharing communication services. However, most networking models demand a large control overhead in eNodeB. Moreover, the topology should be calculated again due to the mobility of terminals, which causes the long delay. In this work, we model multicast network construction in D2 D communication through a fuzzy mathematics and game theory based algorithm. In resource allocation, we assume that user equipment(UE) can detect the available frequency and the fuzzy mathematics is introduced to describe an uncertain relationship between the resource and UE distributedly, which diminishes the time delay. For forming structure, a distributed myopic best response dynamics formation algorithm derived from a novel concept from the coalitional game theory is proposed, in which every UE can self-organize into stable structure without the control from eNodeB to improve its utilities in terms of rate and bit error rate(BER) while accounting for a link maintenance cost, and adapt this topology to environmental changes such as mobility while converging to a Nash equilibrium fast. Simulation results show that the proposed architecture converges to a tree network quickly and presents significant gains in terms of average rate utility reaching up to 50% compared to the star topology where all of the UE is directly connected to eNodeB.展开更多
股票市场是一个复杂非线性动态系统,具有高度不确定性和多变性,股市趋势预测是数据挖掘领域的一个研究热点。针对基于数据驱动方法所生成的模型鲁棒性差,训练良好的模型不适应实际需要的问题,提出了一种多Agent博弈动态影响图模型(Mulit...股票市场是一个复杂非线性动态系统,具有高度不确定性和多变性,股市趋势预测是数据挖掘领域的一个研究热点。针对基于数据驱动方法所生成的模型鲁棒性差,训练良好的模型不适应实际需要的问题,提出了一种多Agent博弈动态影响图模型(Mulit-Agent Game Dynamic Influence Diagrams,MAGDIDs)。首先,从博弈的角度引入多方和空方作为股市的行为主体(Agent),提取行为主体的相关特征;然后,利用能量表示博弈主体的力量大小,并对行为主体特征进行量化融合;进而引入博弈策略,构建多Agent博弈动态影响图模型,对于股市行为主体的博弈过程进行建模;最后,利用联合树的自动推理技术,预测股市趋势。在实际数据上进行实验,实验结果表明多空博弈趋势预测算法具有良好性能。展开更多
Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one...Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortion. Our simulation has confirmed the effectiveness of the proposed algorithm. We provide an estimate of the additional computational costs of this new algorithm to detect sudden death/win and discuss heuristic strategies to further reduce the search complexity.展开更多
文摘This paper presents a distributed game tree search algorithm called DDS. Based on communication overhead, st,orage requirement, speed up, and oiller factors, the performance of algorithm DDS* is analysed, and the number of nodes searched with SSS as well as a-b algorithm. The simulation test shows that. DDS* is an efficient and practical search algorithm.
文摘We developed a new approach for the reconstruction of phylogeny trees based on the chaos game representation (CGR) of biological sequences. The chaos game representation (CGR) method generates a picture from a biological sequence, which displays both local and global patterns. The quantitative index of the biological sequence is extracted from the picture. The Kullback-Leibler discrimination information is used as a diversity indicator to measure the dissimilarity of each pair of biological sequences. The new method is inspected by two data sets: the Eutherian orders using concatenated H-stranded amino acid sequences and the genome sequence of the SARS and coronavirus. The phylogeny trees constructed by the new method are consistent with the commonly accepted ones. These results are very promising and suggest more efforts for further developments.
文摘Game-tree search plays an important role in the field of Artificial Intelligence （AI）. In this paper, we characterize one parallel game-tree search workload in chess： the latest version of Crafty, a state of art program, on two Intel Xeon shared-memory multiprocessor systems. Our analysis shows that Crafty is latency-sensitive and the hash-table and dynamic tree splitting used in Crafty cause large scalability penalties. They consume 35%-50% of the running time on the 4-way system. Furthermore, Crafty is not bandwidth-limited.
基金supported by the National Science and Technology Major Project of China(2013ZX03005007-004)the National Natural Science Foundation of China(6120101361671179)
文摘Device to device(D2 D) multi-hop communication in multicast networks solves the contradiction between high speed requirements and limited bandwidth in regional data sharing communication services. However, most networking models demand a large control overhead in eNodeB. Moreover, the topology should be calculated again due to the mobility of terminals, which causes the long delay. In this work, we model multicast network construction in D2 D communication through a fuzzy mathematics and game theory based algorithm. In resource allocation, we assume that user equipment(UE) can detect the available frequency and the fuzzy mathematics is introduced to describe an uncertain relationship between the resource and UE distributedly, which diminishes the time delay. For forming structure, a distributed myopic best response dynamics formation algorithm derived from a novel concept from the coalitional game theory is proposed, in which every UE can self-organize into stable structure without the control from eNodeB to improve its utilities in terms of rate and bit error rate(BER) while accounting for a link maintenance cost, and adapt this topology to environmental changes such as mobility while converging to a Nash equilibrium fast. Simulation results show that the proposed architecture converges to a tree network quickly and presents significant gains in terms of average rate utility reaching up to 50% compared to the star topology where all of the UE is directly connected to eNodeB.
文摘股票市场是一个复杂非线性动态系统,具有高度不确定性和多变性,股市趋势预测是数据挖掘领域的一个研究热点。针对基于数据驱动方法所生成的模型鲁棒性差,训练良好的模型不适应实际需要的问题,提出了一种多Agent博弈动态影响图模型(Mulit-Agent Game Dynamic Influence Diagrams,MAGDIDs)。首先,从博弈的角度引入多方和空方作为股市的行为主体(Agent),提取行为主体的相关特征;然后,利用能量表示博弈主体的力量大小,并对行为主体特征进行量化融合;进而引入博弈策略,构建多Agent博弈动态影响图模型,对于股市行为主体的博弈过程进行建模;最后,利用联合树的自动推理技术,预测股市趋势。在实际数据上进行实验,实验结果表明多空博弈趋势预测算法具有良好性能。
文摘Teaching computer programs to play games through machine learning has been an important way to achieve better artificial intelligence (AI) in a variety of real-world applications. Monte Carlo Tree Search (MCTS) is one of the key AI techniques developed recently that enabled AlphaGo to defeat a legendary professional Go player. What makes MCTS particularly attractive is that it only understands the basic rules of the game and does not rely on expert-level knowledge. Researchers thus expect that MCTS can be applied to other complex AI problems where domain-specific expert-level knowledge is not yet available. So far there are very few analytic studies in the literature. In this paper, our goal is to develop analytic studies of MCTS to build a more fundamental understanding of the algorithms and their applicability in complex AI problems. We start with a simple version of MCTS, called random playout search (RPS), to play Tic-Tac-Toe, and find that RPS may fail to discover the correct moves even in a very simple game position of Tic-Tac-Toe. Both the probability analysis and simulation have confirmed our discovery. We continue our studies with the full version of MCTS to play Gomoku and find that while MCTS has shown great success in playing more sophisticated games like Go, it is not effective to address the problem of sudden death/win. The main reason that MCTS often fails to detect sudden death/win lies in the random playout search nature of MCTS, which leads to prediction distortion. Therefore, although MCTS in theory converges to the optimal minimax search, with real world computational resource constraints, MCTS has to rely on RPS as an important step in its search process, therefore suffering from the same fundamental prediction distortion problem as RPS does. By examining the detailed statistics of the scores in MCTS, we investigate a variety of scenarios where MCTS fails to detect sudden death/win. Finally, we propose an improved MCTS algorithm by incorporating minimax search to overcome prediction distortion. Our simulation has confirmed the effectiveness of the proposed algorithm. We provide an estimate of the additional computational costs of this new algorithm to detect sudden death/win and discuss heuristic strategies to further reduce the search complexity.
