Improvement Of The Performance Of The Alpha-beta Pruning Algorithm

The alpha-beta pruning algorithm is the base of computer game algorithm,it is also an optimized game tree search algorithm, using the alpha-betapruning algorithm searches the game tree, you can cut some unnecessarybranches, thereby improving the search efficiency; while the alpha-betapruning algorithm pruning efficiency in turn depends on the game treebranching order; the ideal order game tree pruning efficiency is much betterthan the worst case. This paper presents the use of machine learningalgorithms to improve the order of the game tree branches, can greatlyimprove the efficiency of the pruning of the alpha-beta pruning algorithm.In the text, the author describes the pruning principle of the alpha-betapruning algorithm and various optimization algorithms that already exist,given the common methods and precautions of the build learning system forthe auxiliary alpha-beta pruning algorithm for pruning. In order to verify thatthe proposed improvement method, the author first designed and implementedtic-tac-toe chess game which based on the alpha-beta pruning algorithm, andthen by the man-machine game to get the training examples used to train thelearning system; Second, the author designed and implemented a BP neuralnetwork, the network consists of14hidden nodes,9output nodes, which cansort the game tree branches according to their best path probability, after atraining sample extracted earlier training, BP neural network can identify50%of the test samples, that is, trained neural network to the current chess gamestate as input to predict the next best move, the correct rate of50%; Finally,the author added the trained BP neural network to the game of tic-tac-toechess, the improved tic-tac-toe chess compared with the original tic-tac-toechess, to the case in the outcome of the game for a draw, the number of nodessearch can reduce about35%proven.After a series of trials and validation, the proposed method really can greatly improve the pruning efficiency of the alpha-beta pruning algorithm.