The efficiency of the alpha-betaalgorithm is largely dependent on the order in which its branches are searched;a well-ordered search can give a considerable reduction in the number of nodes processed by pruning ineff...
详细信息
ISBN:
(纸本)9780769542539
The efficiency of the alpha-betaalgorithm is largely dependent on the order in which its branches are searched;a well-ordered search can give a considerable reduction in the number of nodes processed by pruning ineffectual paths. This paper describes 'CLAMP' (an acronym for Chunk Learning And Move Prompting) which uses 'chunk knowledge' to order the moves on a chessboard in their likelihood to be played. Test results show, despite CLAMP having no knowledge of the rules of chess, ordering moves by using chunk knowledge gives an approximate 50% decrease in the number of nodes searched when compared to a random ordering of the same moves. This paper focuses on the alpha-beta function within a chess-playing program but as CLAMP has no knowledge of the rules of the game the same method can be applied to optimise searching in other domains.
The satisfactory performance of the intelligent agents conceived to solve several real-life problems requires efficient decision-making algorithms. To address issues with high state-spaces within reasonable runtime li...
详细信息
The satisfactory performance of the intelligent agents conceived to solve several real-life problems requires efficient decision-making algorithms. To address issues with high state-spaces within reasonable runtime limits, these algorithms are distributed according to some approaches that can be either synchronous or asynchronous, where the former guarantee the same results as their corresponding serial versions through synchronization points, which causes the undesirable effects of communication overhead and idle processors. To mitigate this, the asynchronous approaches reduce the message exchanges in such a way as to accelerate the runtime without too much compromising the response accuracy. The challenge of enhancing the minimax technique through pruning makes alpha-beta a relevant case study in parallelism research. Young Brothers Wait Concept (YBWC) and Asynchronous Parallel Hierarchical Iterative Deepening (APHID) are highlighted among the existing alpha-beta distributions. Knowing that APHID proved to be more suitable than YBWC to operate in distributed memory and that shared memory architectures are scarcely available due to their high costs, the primary motivation here is to implement the Asynchronous Distributed alpha-betaalgorithm (ADABA), which increases the accuracy and performance of APHID through the enhancement of the slaves' task ordering policies, the communication process between the processors and the window's updating strategy. Experiments fulfilled through tournaments involving ADABA-based and APHID-based Checkers agents proved that the player based on the best ADABA version reached, approximately, a victory rate 95% superior and a runtime two times faster than the APHID-based player, keeping the same response accuracy level of its opponent.
In Chinese-chess computer game (CCCG), a computer player could find the best move for a given board position by using alpha-beta search algorithm. The technique of iterative deepening is an enhancement to alpha-beta s...
详细信息
ISBN:
(纸本)9781424447053
In Chinese-chess computer game (CCCG), a computer player could find the best move for a given board position by using alpha-beta search algorithm. The technique of iterative deepening is an enhancement to alpha-betasearch. It is helpful to reduce the size of game tree. In this paper, we improved the prototypical one-ply iterative deepening (OPID) and proposed two-ply iterative deepening (TPID). In game tree searching, we extend the search by two plies from the previous iteration. An iterated series of 2-ply, 4-ply, 6-ply, (...) searches is carried out. In the experiments, we validate that TPID is feasible and effective. Through applying TPID to minimax search and alpha-betasearch respectively, we found that the total number of nodes generated in TPID minimax search and TPID alpha-betasearch are all reduced compared with OPID.
Computer games have always been considered to be the most challenging task in the field of artificial intelligence specially the Chinese chess as an example. The core technology of the computer games is the search. Th...
详细信息
Computer games have always been considered to be the most challenging task in the field of artificial intelligence specially the Chinese chess as an example. The core technology of the computer games is the search. This work is studied to research an improved pruning strategy in order to achieve a deeper level search of the game tree in a limited time. On the basis of the traditional alpha-beta search algorithm, the worthless nodes are discarded to be never searched by introducing the deep iterative, history table and other auxiliary methods of pruning. The number of nodes searched is effectively reduced to make the pruning earlier to shorten the search time. At the same time, its search depth is higher than the original searchalgorithm. The advanced and modified algorithm is proved to be practical and applicative by experimentations and tests of computer games system provided in this study.
In Chinese-chess computer game (CCCG), a computer player could find the best move for a given board position by using alpha-beta search algorithm. The technique of iterative deepening is an enhancement to alpha-beta s...
详细信息
In Chinese-chess computer game (CCCG), a computer player could find the best move for a given board position by using alpha-beta search algorithm. The technique of iterative deepening is an enhancement to alpha-betasearch. It is helpful to reduce the size of game tree. In this paper, we improved the prototypical one-ply iterative deepening (OPID) and proposed two-ply iterative deepening (TPID). In game tree searching, we extend the search by two plies from the previous iteration. An iterated series of 2-ply, 4-ply, 6-ply,…searches is carried out. In the experiments, we validate that TPID is feasible and effective. Through applying TPID to minimax search and alpha-betasearch respectively, we found that the total number of nodes generated in TPID minimax search and TPID alpha-betasearch are all reduced compared with OPID.
暂无评论